7 ms·

How newlines affect Linux kernel performance

287 points by tbodt 8y ago

jwilk 8y ago
Ugh, all external links in this article go through the Google click tracker. :-/ Here are ungoogled URLs: https://elixir.bootlin.com/linux/v4.17/source/include/linux/jhash.h#L70 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://elixir.bootlin.com/linux/v4.17/source/include/net/dst.h#L442 https://elixir.bootlin.com/linux/v4.17/source/include/net/ds... https://elixir.bootlin.com/linux/v4.17/source/include/linux/thread_info.h#L121 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://c9x.me/x86/html/file_module_x86_id_318.html https://c9x.me/x86/html/file_module_x86_id_318.html https://elixir.bootlin.com/linux/v4.17/source/arch/x86/include/asm/bug.h#L33 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/inclu... https://gcc.gnu.org/onlinedocs/gcc-4.0.1/gcc/Extended-Asm.html https://gcc.gnu.org/onlinedocs/gcc-4.0.1/gcc/Extended-Asm.ht... https://www.embecosm.com/appnotes/ean10/ean10-howto-llvmas-1.0.html#idp109760 https://www.embecosm.com/appnotes/ean10/ean10-howto-llvmas-1... https://patchwork.kernel.org/patch/10450037/ https://patchwork.kernel.org/patch/10450037/ https://lkml.org/lkml/2018/10/4/25 https://lkml.org/lkml/2018/10/4/25 https://elixir.bootlin.com/linux/v4.17/source/include/linux/slab.h#L699 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/vmx.c#L9669 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/v... https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/vmx.c#L706 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/v...
- gruez 8y ago
  I was wondering why that'd be the case (usually the only reason these urls even pop up was because someone was copying urls from a google results page), then I saw this at the bottom: >Made with the new Google Sites, an effortless way to create beautiful sites.
  - kbd 8y ago
    TIL about Google Sites. TBH I'd prefer Google link tracking everywhere over popups every time I visit a la Medium.
    - anadav 8y ago
      Sorry for that. It was the path of least resistance when I set a website.
  - jrockway 8y ago
    The idea is to prevent you from leaking the URL of your internal google sites page through the referer header. Maybe Google does some tracking, but the idea behind the redirect was for privacy, as I understand it. (Disclaimer: former Googler.)
    - jwilk 8y ago
      You can disable sending the Referer header with Referrer-Policy: https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Referrer-Policy https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Re... (Maybe R-P didn't exist when the current solution was concocted.)
      - wolfgang42 8y ago
        Per MDN, Referrer-Policy isn't supported in IE/Edge either, so you'd have to do browser sniffing. This seems like it has the potential for something to go wrong and cause a referer leak. On the other hand, if it's a public site then obviously there's no concern about the URL leaking, so I'd think this should only be turned on for sites that are set as private.
        jrockway 8y ago
        I'm guessing that the underlying problem here is that you can share things in Google Drive / Google Docs to "anyone with the link" and when that's enabled, you probably didn't actually intend to share it with the owners of the websites that you happened to link to. Safer to just never let the URL leak.
- jwilk 8y ago
  Alternatively, you can run this in the web console to fix the links: for (let a of document.querySelectorAll('a[href*="/url?"')) { a.href = decodeURIComponent(a.href.match(/[?]q=([^&]+)/)[1]); }
rurban 8y ago
I'd really like to see a comparison with clang's inliner. In my cases [1] gcc constexpr support was always horrible and clang decent. So I'm not sure if using the builtin assembler would fix the gcc situation. 1: https://github.com/rurban/safeclib/blob/master/tests/perf_memcpy_s.c https://github.com/rurban/safeclib/blob/master/tests/perf_me...
- ndesaulniers 8y ago
  So I think the inlining decisions in a compiler are some of the most heuristic-y parts of the compiler. There was a paper from Jeff Dean and some other Googlers recently that hinted that machine learned models might be the next leap forward in compiler technology, as a potential means of replacing these heuristics.
  - rurban 8y ago
    Machine learning? If some logic, than precise and reproducible please. Prolog would be nice, not some neural nets. gcc already has some nice lisp. Jeff Dean usually has good ideas, but not this one. ML would be more useful for a JIT, dynamic optimization problems at run-time. But the problem is only the botched architecture, with non-manageable interdependencies. Of course inlining is the mother of all optimizations, most other optimization should be applied after inlining. But for inlining to be effective it has to run after constant folding. And then after inlining you have to run most optimization passes again to get the real benefits. This problem is much simpler: Missing as-integration and a botched constexpr API. They should just take it from llvm.
zbjornson 8y ago
v8 (before v5.9) used to only inline functions that were under 600 characters (and 196 AST nodes). That was another fun way to add fuel to the tab vs. spaces fire: identical functions that used spaces instead of tabs could run significantly slower because they weren't inlined.
- umvi 8y ago
  > The kernel compiler, GCC, is unaware to the code size that will be generated by the inline assembly. It therefore tries to estimate its size based on newline characters and statement separators (';' on x86). Seems like a poor decision to use whitespace as a factor in estimating code size. Some people like to space out their code with lots of comments even if it is only a few lines long. This is my naive view, though - does anyone out there have any insight as to why semicolons alone aren't sufficient to estimate code size?
  - chrisseaton 8y ago
    > Seems like a poor decision to use whitespace as a factor in estimating code size. It's a heuristic. It's always going to be more poor in some respect that doing something precise. You could probably make it better in a million different ways, but it's suppose to be quick and simple.
    - trhway 8y ago
      to inline the parsing must be done. Once parsing is done there is no newlines and semicolons, only AST nodes. Counting AST nodes is very quick and simple and provides for much better heuristic.
      - chrisseaton 8y ago
        > to inline the parsing must be done Yes... that's the point. For your metric counting AST nodes you need to have parsed the method. The other heuristic works on unparsed source-code. So you don't waste time parsing a method that you won't inline. > Counting AST nodes is very quick and simple But parsing is neither. And you need to have done that first. I think (there's a paper I'm sure but can't find it) that parse time for JS applications is very substantial.
ndesaulniers 8y ago
__builtin_constant_p is a rats nest of edge cases. We're looking into differences between implementation from gcc and clang now for the kernel.
- ndesaulniers 8y ago
  Also, we're working on getting Clang's integrated assembler to assemble the Linux kernel, but there's a long tail of syntactic sugar and simpler basic things Clang has to implement as GAS from binutils is a defacto standard for assembler.
amelius 8y ago
Seems like those competitions where people write one-liners have their merits.
- faitswulff 8y ago
  Code golf! https://codegolf.stackexchange.com/ https://codegolf.stackexchange.com/
- est 8y ago
  https://github.com/torvalds/linux/pull/437 https://github.com/torvalds/linux/pull/437
deleted 8y ago
[deleted]

287 points by tbodt 8y ago

Ugh, all external links in this article go through the Google click tracker. :-/ Here are ungoogled URLs: https://elixir.bootlin.com/linux/v4.17/source/include/linux/jhash.h#L70 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://elixir.bootlin.com/linux/v4.17/source/include/net/dst.h#L442 https://elixir.bootlin.com/linux/v4.17/source/include/net/ds... https://elixir.bootlin.com/linux/v4.17/source/include/linux/thread_info.h#L121 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://c9x.me/x86/html/file_module_x86_id_318.html https://c9x.me/x86/html/file_module_x86_id_318.html https://elixir.bootlin.com/linux/v4.17/source/arch/x86/include/asm/bug.h#L33 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/inclu... https://gcc.gnu.org/onlinedocs/gcc-4.0.1/gcc/Extended-Asm.html https://gcc.gnu.org/onlinedocs/gcc-4.0.1/gcc/Extended-Asm.ht... https://www.embecosm.com/appnotes/ean10/ean10-howto-llvmas-1.0.html#idp109760 https://www.embecosm.com/appnotes/ean10/ean10-howto-llvmas-1... https://patchwork.kernel.org/patch/10450037/ https://patchwork.kernel.org/patch/10450037/ https://lkml.org/lkml/2018/10/4/25 https://lkml.org/lkml/2018/10/4/25 https://elixir.bootlin.com/linux/v4.17/source/include/linux/slab.h#L699 https://elixir.bootlin.com/linux/v4.17/source/include/linux/... https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/vmx.c#L9669 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/v... https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/vmx.c#L706 https://elixir.bootlin.com/linux/v4.17/source/arch/x86/kvm/v...

gruez 8y ago
I was wondering why that'd be the case (usually the only reason these urls even pop up was because someone was copying urls from a google results page), then I saw this at the bottom: >Made with the new Google Sites, an effortless way to create beautiful sites.
- kbd 8y ago
  TIL about Google Sites. TBH I'd prefer Google link tracking everywhere over popups every time I visit a la Medium.
  - anadav 8y ago
    Sorry for that. It was the path of least resistance when I set a website.
- jrockway 8y ago
  The idea is to prevent you from leaking the URL of your internal google sites page through the referer header. Maybe Google does some tracking, but the idea behind the redirect was for privacy, as I understand it. (Disclaimer: former Googler.)
  - jwilk 8y ago
    You can disable sending the Referer header with Referrer-Policy: https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Referrer-Policy https://developer.mozilla.org/en-US/docs/Web/HTTP/Headers/Re... (Maybe R-P didn't exist when the current solution was concocted.)
    - wolfgang42 8y ago
      Per MDN, Referrer-Policy isn't supported in IE/Edge either, so you'd have to do browser sniffing. This seems like it has the potential for something to go wrong and cause a referer leak. On the other hand, if it's a public site then obviously there's no concern about the URL leaking, so I'd think this should only be turned on for sites that are set as private.
      - jrockway 8y ago
        I'm guessing that the underlying problem here is that you can share things in Google Drive / Google Docs to "anyone with the link" and when that's enabled, you probably didn't actually intend to share it with the owners of the websites that you happened to link to. Safer to just never let the URL leak.
jwilk 8y ago
Alternatively, you can run this in the web console to fix the links: for (let a of document.querySelectorAll('a[href*="/url?"')) { a.href = decodeURIComponent(a.href.match(/[?]q=([^&]+)/)[1]); }

rurban 8y ago

I'd really like to see a comparison with clang's inliner. In my cases [1] gcc constexpr support was always horrible and clang decent. So I'm not sure if using the builtin assembler would fix the gcc situation. 1: https://github.com/rurban/safeclib/blob/master/tests/perf_memcpy_s.c https://github.com/rurban/safeclib/blob/master/tests/perf_me...

ndesaulniers 8y ago
So I think the inlining decisions in a compiler are some of the most heuristic-y parts of the compiler. There was a paper from Jeff Dean and some other Googlers recently that hinted that machine learned models might be the next leap forward in compiler technology, as a potential means of replacing these heuristics.
- rurban 8y ago
  Machine learning? If some logic, than precise and reproducible please. Prolog would be nice, not some neural nets. gcc already has some nice lisp. Jeff Dean usually has good ideas, but not this one. ML would be more useful for a JIT, dynamic optimization problems at run-time. But the problem is only the botched architecture, with non-manageable interdependencies. Of course inlining is the mother of all optimizations, most other optimization should be applied after inlining. But for inlining to be effective it has to run after constant folding. And then after inlining you have to run most optimization passes again to get the real benefits. This problem is much simpler: Missing as-integration and a botched constexpr API. They should just take it from llvm.

zbjornson 8y ago

v8 (before v5.9) used to only inline functions that were under 600 characters (and 196 AST nodes). That was another fun way to add fuel to the tab vs. spaces fire: identical functions that used spaces instead of tabs could run significantly slower because they weren't inlined.

umvi 8y ago
> The kernel compiler, GCC, is unaware to the code size that will be generated by the inline assembly. It therefore tries to estimate its size based on newline characters and statement separators (';' on x86). Seems like a poor decision to use whitespace as a factor in estimating code size. Some people like to space out their code with lots of comments even if it is only a few lines long. This is my naive view, though - does anyone out there have any insight as to why semicolons alone aren't sufficient to estimate code size?
- chrisseaton 8y ago
  > Seems like a poor decision to use whitespace as a factor in estimating code size. It's a heuristic. It's always going to be more poor in some respect that doing something precise. You could probably make it better in a million different ways, but it's suppose to be quick and simple.
  - trhway 8y ago
    to inline the parsing must be done. Once parsing is done there is no newlines and semicolons, only AST nodes. Counting AST nodes is very quick and simple and provides for much better heuristic.
    - chrisseaton 8y ago
      > to inline the parsing must be done Yes... that's the point. For your metric counting AST nodes you need to have parsed the method. The other heuristic works on unparsed source-code. So you don't waste time parsing a method that you won't inline. > Counting AST nodes is very quick and simple But parsing is neither. And you need to have done that first. I think (there's a paper I'm sure but can't find it) that parse time for JS applications is very substantial.

ndesaulniers 8y ago

__builtin_constant_p is a rats nest of edge cases. We're looking into differences between implementation from gcc and clang now for the kernel.

ndesaulniers 8y ago
Also, we're working on getting Clang's integrated assembler to assemble the Linux kernel, but there's a long tail of syntactic sugar and simpler basic things Clang has to implement as GAS from binutils is a defacto standard for assembler.

amelius 8y ago

Seems like those competitions where people write one-liners have their merits.

faitswulff 8y ago
Code golf! https://codegolf.stackexchange.com/ https://codegolf.stackexchange.com/
est 8y ago
https://github.com/torvalds/linux/pull/437 https://github.com/torvalds/linux/pull/437

deleted 8y ago

[deleted]