14 ms·

Linux with “memory folios”: a 7% performance boost when compiling the kernel

238 points by marcodiego 5y ago

account42 5y ago
> There does not appear to be a way to tell gcc that it can cache the result of compound_head() Isn't this what __attribute__((pure)) [0] is for? [0] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-pure-function-attribute https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
- hyperman1 5y ago
  As I understood it, pure means a function's output is dependent only on its input: y=f(x);z=f(x) implies y=z What they want is something different: y= f(x) implies y=f(y) This means if you give something the head of a list of pages, it won't try to go to the head again and again, it knows its already there. The 'folio' idea as I understand it is roughly an alias for the existing 'page' structure, but code knows it is already at a head AND it should do the work on the whole list, not only on the head.
marcodiego 5y ago
Now, consider that there's work going on to enable Linux to be compiled with profile guided optimization with clang[0], the DAMON patchset that enables proactive reclamation with "32% memory saving with only 1.91% runtime overhead"[1] and performance improvements achievable with futex2 system call[2]. Linux future seems bright with regard to performance. [0] https://lkml.org/lkml/2021/1/11/98 https://lkml.org/lkml/2021/1/11/98 [1] https://lore.kernel.org/lkml/20210608115254.11930-1-sj38.park@gmail.com/ https://lore.kernel.org/lkml/20210608115254.11930-1-sj38.par... [2] https://lkml.org/lkml/2021/4/27/1208 https://lkml.org/lkml/2021/4/27/1208
- londons_explore 5y ago
  Linux needs a standard set of benchmarks that are vaguely representative of things users use Linux for. Phone, laptop and a few server use cases. It then needs someone to do a big parameter tuning to select optimal settings. Too many decent algorithms don't make it into the kernel because there are too many tunables, and the ones that do typically arent well tuned for anyone's use case. Even big projects like Ubuntu typically don't change many tunables in the kernel.
  - voldacar 5y ago
    I wonder if someday you could make a differentiable kernel and do gradient descent in kernel-parameter-space
    - Daishiman 5y ago
      I believe Google already does this for setting their server's tunables.
      - eru 5y ago
        At Google's scale, you don't even need it to be differentiable. You can just do simulated annealing or so.
  - astrange 5y ago
    Tuning is highly overrated in software performance, eg compiler optimizations don't help that much and searching their params helps even less. I think it comes from people wishing they could change their software without actually needing to learn how to change it.
    - jeffbee 5y ago
      That's quite a bad take. You can bank on PGO+LTO of a C++ server being good for 20% throughput easily, and not compiling for k8-generic when you have a modern machine also makes a big difference. I would agree that just flipping compiler flags might not get you very far, but there are key inputs that you shouldn't leave on the table.
      - astrange 5y ago
        By "not that much" I mean orders of magnitude. 20% is reasonable, especially for C++ that needs a lot of inlining. But a more modern language would benefit from defining some optimizations like inlining as mandatory, the same way tail calls are (and of course GCC has this.) Then there isn't a chance of deploying a build with extra-slow behavior.
- MaxBarraclough 5y ago
  As someone with a limited knowledge of kernel stuff, does this mean Linux is likely to significantly outperform other comparable kernels like FreeBSD and OpenSolaris? Or are those other kernels keeping pace?
  - marcodiego 5y ago
    Considering the absolute dominance on HPC for a few years now, I don't think there is competition against Linux at the moment in terms of performance. Last time a non Linux system appeared in the top500 list was in June 2017.
    - damagednoob 5y ago
      Isn't cost also a factor at play here?
    - hawk_ 5y ago
      I suspect that's more due to "popularity" or richness of the ecosystem than performance necessarily.
deleted 5y ago
[deleted]
fulafel 5y ago
It's surprising that we have stuck with 4 kB pages on x86 since the 386, even though computers have ~10 000x as much memory now (4 MB -> 32GB).
- b9a2cab5 5y ago
  Indeed, the M1/A14 on mobile has larger pages which lets them have more effective TLB coverage with a smaller cache. In some applications this can boost performance by double digit % (which you can simulate by enabling large pages on x86).
- TD-Linux 5y ago
  Linux still has a lot of assumptions baked into the page size. Power9 and some aarch64 systems have 16kB pages, but occasionally you run into some corner cases - for example, you can't mount a btrfs partition created on a x86 machine on a power9 one because the btrfs page size must be >= the mmu page size.
  - classichasclass 5y ago
    64K pages, actually. Also, POWER9 and aarch64 are perfectly capable of running with 4K pages, but not everything does. My desktop POWER9 with Fedora is a 64K page system, but Void PPC runs the same hardware with a 4K page.
  - diegocg 5y ago
    That's the fault of btrfs (ext4 or xfs handle these cases just fine), and even btrfs is getting support for it in the latest releases
    - josteink 5y ago
      While you may be technically correct, I guess from a practical point of view, OP is correct in that page-size still matters if you trying to run Linux on "unconventional" platforms.
- delsarto 5y ago
mhh__ 5y ago
One thing I've been mulling over recently is that many containers like vector in C++ for example, have almost no state. That is to say, we at most might have a bit of logic to tune whether we do *1.5 or *2 on realloc, but why not more? There must be patterns we can exploit in common use cases to be sneaky and do less malloc-ing. Profile guided? Runtime? I might have some results by Christmas, I have some ideas. Food for thought: Your container has a few bytes of state to make decisions with, your branch predictor has a few megabytes these days.
- viraptor 5y ago
  While some heuristics would be nice if they improve the situation, a lot of apps still leave performance on the table by not estimating the capacity well. You don't have to be very clever about growth if you know that this vector will always have 3 elements and that one will have N that you can estimate from data size.
- gary_0 5y ago
  Please don't give the C++ people any more ideas, my compile times are already bad enough!
  - mhh__ 5y ago
    This could actually make your compiler a lot faster, compilers are really hard to maintain an efficient memory strategy in due to all the moving parts
- jabl 5y ago
  The size increase factor for vector is a compromise between performance and wasting memory. It's also a fairly hot code path, so you don't want to run some complicated code there to estimate the 'optimal' factor. About the best you can do is if you know beforehand roughly how big it will be, is to reserve that capacity with std::vector::reserve().
  - mhh__ 5y ago
    Malloc is at best a few hundred cycles, that's quite a lot of work if you can keep your data in L1. If you do a bit of work now you can save reallocs later. Think bigger than changing the coefficient, there probably is no optimal factor.
atoav 5y ago
A while ago I switched my main rendeeing machine to linux because blender rendered roughly 10% faster on it back then. This is equivalent to saving ~16 hours when you have a week of rendertime.
- jabl 5y ago
  This was a 7% perf boost compiling the kernel, which does a lot of small file IO and memory allocations and thus stresses the MM code in the kernel. Rendering is much more 'pure cpu' work, so you most likely won't see much difference there due to this work.
  - Ar-Curunir 5y ago
    I think the 16hr thing is 10% of 168 = 1wk of computation, not the 7% referred to in the title.
  - suyjuris 5y ago
    I believe GP is referring to the 10% boost they observed, not a hypothetical 7% boost as in the article. (7×24×0.1 = 16.8, while a 7% speedup would result in ~12 hours.)
    - jabl 5y ago
      Ah, right, I thougt GP assumed they would see another 7% on top of the previous 10%.
  - Tuna-Fish 5y ago
    You'd think so, but it's just not true. Linux has a substantial performance advantage over Windows for rendering, which is (partly) why all the large render farms use Linux instead of Windows. The most sensible hypothesis I've heard about it is that THP really helps with large rendering loads, and Windows doesn't do that yet.
    - mnw21cam 5y ago
      For reference - THP -> Transparent Huge Pages.
mappu 5y ago
There is some more in-depth discussion about the core folio idea on LWN at https://lwn.net/Articles/849538/ https://lwn.net/Articles/849538/ from a previous iteration of the patch set,
- WhyNotHugo 5y ago
  Pretty good explanation. I don't quite follow why it's all being done as one huge set of patches -- rather than first merge the groundwork and then all the conversions.
  - Denvercoder9 5y ago
    > I don't quite follow why it's all being done as one huge set of patches -- rather than first merge the groundwork and then all the conversions. It is. The patchset submitted contains only 33 patches, while the full patchset contans about 200 patches.
kzrdude 5y ago
It sounds like the quoted benchmark is for XFS, so other filesystems may be different?
dncornholio 5y ago
The other day I was wondering what would happen if all operating systems would stop developing and only optimise for a week or 2. How much time and electricity could have been saved? If you add up an optimisation of just a nanosecond in like openSSH, how much would that do globally?
- nikhizzle 5y ago
  I used to be a kernel developer at Apple starting in 2006. Internally, every alternate major release was exactly this. All common paths were identified, and most of the dev time on the release was spent on optimizing those features to hit a goal for the path. Eg. moving 100 files in finder should not take more than x ms
  - w-m 5y ago
    The upgrade from Leopard to Snow Leopard on a plastic MacBook just made everything better. Things were faster, smoother, and you could run more things at the same time without killing the machine. It was the perfect OS. Then when Lion came around, it was the exact opposite, it felt terribly buggy, and made everything clunky and worse. At least that's my memory of these OS updates. Makes me wonder whether this alternate major release cycle was a good idea. If you delay all feature development for a year, you'll get a barrage of features once the performance-only OS version is out the door, and there's not enough time to do all of them properly, so you get buggy and slow versions. Maybe doing performance improvements and feature development at the same time would have been the better choice? How is it being done at Apple nowadays?
    - nikhizzle 5y ago
      I do not know, Apple is a place where most practices are need to know only.
- georgyo 5y ago
  > If you add up an optimization of just a nanosecond in like openSSH, how much would that do globally? I believed optimizations like that at a global scale will not have any impact. Lets say that this nanosecond will be saved trillions of time a day. Resulting in minutes to an hour a day saved globally. * Not a single user will notice. * In 99.99% of cases the CPU will not be fully pegged and thus that one nanosecond of compute will not be used to do something else at all. * CPU throttling isn't that fast so, you won't even save that much power. If we bump it up by 6 orders of magnitude to a millisecond that all remains true. Even though you are potentially saving 100s of years of computing time a day. Extremely small gains distributed across very large number of machines don't tend to be as impactful as you would hope on a global scale. This is not to say that small gains are worthless. Many small gains added together can be substantial.

238 points by marcodiego 5y ago

> There does not appear to be a way to tell gcc that it can cache the result of compound_head() Isn't this what __attribute__((pure)) [0] is for? [0] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-pure-function-attribute https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...

hyperman1 5y ago
As I understood it, pure means a function's output is dependent only on its input: y=f(x);z=f(x) implies y=z What they want is something different: y= f(x) implies y=f(y) This means if you give something the head of a list of pages, it won't try to go to the head again and again, it knows its already there. The 'folio' idea as I understand it is roughly an alias for the existing 'page' structure, but code knows it is already at a head AND it should do the work on the whole list, not only on the head.

marcodiego 5y ago

Now, consider that there's work going on to enable Linux to be compiled with profile guided optimization with clang[0], the DAMON patchset that enables proactive reclamation with "32% memory saving with only 1.91% runtime overhead"[1] and performance improvements achievable with futex2 system call[2]. Linux future seems bright with regard to performance. [0] https://lkml.org/lkml/2021/1/11/98 https://lkml.org/lkml/2021/1/11/98 [1] https://lore.kernel.org/lkml/20210608115254.11930-1-sj38.park@gmail.com/ https://lore.kernel.org/lkml/20210608115254.11930-1-sj38.par... [2] https://lkml.org/lkml/2021/4/27/1208 https://lkml.org/lkml/2021/4/27/1208

londons_explore 5y ago
Linux needs a standard set of benchmarks that are vaguely representative of things users use Linux for. Phone, laptop and a few server use cases. It then needs someone to do a big parameter tuning to select optimal settings. Too many decent algorithms don't make it into the kernel because there are too many tunables, and the ones that do typically arent well tuned for anyone's use case. Even big projects like Ubuntu typically don't change many tunables in the kernel.
- voldacar 5y ago
  I wonder if someday you could make a differentiable kernel and do gradient descent in kernel-parameter-space
  - Daishiman 5y ago
    I believe Google already does this for setting their server's tunables.
    - eru 5y ago
      At Google's scale, you don't even need it to be differentiable. You can just do simulated annealing or so.
- astrange 5y ago
  Tuning is highly overrated in software performance, eg compiler optimizations don't help that much and searching their params helps even less. I think it comes from people wishing they could change their software without actually needing to learn how to change it.
  - jeffbee 5y ago
    That's quite a bad take. You can bank on PGO+LTO of a C++ server being good for 20% throughput easily, and not compiling for k8-generic when you have a modern machine also makes a big difference. I would agree that just flipping compiler flags might not get you very far, but there are key inputs that you shouldn't leave on the table.
    - astrange 5y ago
      By "not that much" I mean orders of magnitude. 20% is reasonable, especially for C++ that needs a lot of inlining. But a more modern language would benefit from defining some optimizations like inlining as mandatory, the same way tail calls are (and of course GCC has this.) Then there isn't a chance of deploying a build with extra-slow behavior.
MaxBarraclough 5y ago
As someone with a limited knowledge of kernel stuff, does this mean Linux is likely to significantly outperform other comparable kernels like FreeBSD and OpenSolaris? Or are those other kernels keeping pace?
- marcodiego 5y ago
  Considering the absolute dominance on HPC for a few years now, I don't think there is competition against Linux at the moment in terms of performance. Last time a non Linux system appeared in the top500 list was in June 2017.
  - damagednoob 5y ago
    Isn't cost also a factor at play here?
  - hawk_ 5y ago
    I suspect that's more due to "popularity" or richness of the ecosystem than performance necessarily.

deleted 5y ago

[deleted]

fulafel 5y ago

It's surprising that we have stuck with 4 kB pages on x86 since the 386, even though computers have ~10 000x as much memory now (4 MB -> 32GB).

b9a2cab5 5y ago
Indeed, the M1/A14 on mobile has larger pages which lets them have more effective TLB coverage with a smaller cache. In some applications this can boost performance by double digit % (which you can simulate by enabling large pages on x86).
TD-Linux 5y ago
Linux still has a lot of assumptions baked into the page size. Power9 and some aarch64 systems have 16kB pages, but occasionally you run into some corner cases - for example, you can't mount a btrfs partition created on a x86 machine on a power9 one because the btrfs page size must be >= the mmu page size.
- classichasclass 5y ago
  64K pages, actually. Also, POWER9 and aarch64 are perfectly capable of running with 4K pages, but not everything does. My desktop POWER9 with Fedora is a 64K page system, but Void PPC runs the same hardware with a 4K page.
- diegocg 5y ago
  That's the fault of btrfs (ext4 or xfs handle these cases just fine), and even btrfs is getting support for it in the latest releases
  - josteink 5y ago
    While you may be technically correct, I guess from a practical point of view, OP is correct in that page-size still matters if you trying to run Linux on "unconventional" platforms.
delsarto 5y ago

mhh__ 5y ago

One thing I've been mulling over recently is that many containers like vector in C++ for example, have almost no state. That is to say, we at most might have a bit of logic to tune whether we do *1.5 or *2 on realloc, but why not more? There must be patterns we can exploit in common use cases to be sneaky and do less malloc-ing. Profile guided? Runtime? I might have some results by Christmas, I have some ideas. Food for thought: Your container has a few bytes of state to make decisions with, your branch predictor has a few megabytes these days.

viraptor 5y ago
While some heuristics would be nice if they improve the situation, a lot of apps still leave performance on the table by not estimating the capacity well. You don't have to be very clever about growth if you know that this vector will always have 3 elements and that one will have N that you can estimate from data size.
gary_0 5y ago
Please don't give the C++ people any more ideas, my compile times are already bad enough!
- mhh__ 5y ago
  This could actually make your compiler a lot faster, compilers are really hard to maintain an efficient memory strategy in due to all the moving parts
jabl 5y ago
The size increase factor for vector is a compromise between performance and wasting memory. It's also a fairly hot code path, so you don't want to run some complicated code there to estimate the 'optimal' factor. About the best you can do is if you know beforehand roughly how big it will be, is to reserve that capacity with std::vector::reserve().
- mhh__ 5y ago
  Malloc is at best a few hundred cycles, that's quite a lot of work if you can keep your data in L1. If you do a bit of work now you can save reallocs later. Think bigger than changing the coefficient, there probably is no optimal factor.

atoav 5y ago

A while ago I switched my main rendeeing machine to linux because blender rendered roughly 10% faster on it back then. This is equivalent to saving ~16 hours when you have a week of rendertime.

jabl 5y ago
This was a 7% perf boost compiling the kernel, which does a lot of small file IO and memory allocations and thus stresses the MM code in the kernel. Rendering is much more 'pure cpu' work, so you most likely won't see much difference there due to this work.
- Ar-Curunir 5y ago
  I think the 16hr thing is 10% of 168 = 1wk of computation, not the 7% referred to in the title.
- suyjuris 5y ago
  I believe GP is referring to the 10% boost they observed, not a hypothetical 7% boost as in the article. (7×24×0.1 = 16.8, while a 7% speedup would result in ~12 hours.)
  - jabl 5y ago
    Ah, right, I thougt GP assumed they would see another 7% on top of the previous 10%.
- Tuna-Fish 5y ago
  You'd think so, but it's just not true. Linux has a substantial performance advantage over Windows for rendering, which is (partly) why all the large render farms use Linux instead of Windows. The most sensible hypothesis I've heard about it is that THP really helps with large rendering loads, and Windows doesn't do that yet.
  - mnw21cam 5y ago
    For reference - THP -> Transparent Huge Pages.

mappu 5y ago

There is some more in-depth discussion about the core folio idea on LWN at https://lwn.net/Articles/849538/ https://lwn.net/Articles/849538/ from a previous iteration of the patch set,

WhyNotHugo 5y ago
Pretty good explanation. I don't quite follow why it's all being done as one huge set of patches -- rather than first merge the groundwork and then all the conversions.
- Denvercoder9 5y ago
  > I don't quite follow why it's all being done as one huge set of patches -- rather than first merge the groundwork and then all the conversions. It is. The patchset submitted contains only 33 patches, while the full patchset contans about 200 patches.

kzrdude 5y ago

It sounds like the quoted benchmark is for XFS, so other filesystems may be different?

dncornholio 5y ago

The other day I was wondering what would happen if all operating systems would stop developing and only optimise for a week or 2. How much time and electricity could have been saved? If you add up an optimisation of just a nanosecond in like openSSH, how much would that do globally?

nikhizzle 5y ago
I used to be a kernel developer at Apple starting in 2006. Internally, every alternate major release was exactly this. All common paths were identified, and most of the dev time on the release was spent on optimizing those features to hit a goal for the path. Eg. moving 100 files in finder should not take more than x ms
- w-m 5y ago
  The upgrade from Leopard to Snow Leopard on a plastic MacBook just made everything better. Things were faster, smoother, and you could run more things at the same time without killing the machine. It was the perfect OS. Then when Lion came around, it was the exact opposite, it felt terribly buggy, and made everything clunky and worse. At least that's my memory of these OS updates. Makes me wonder whether this alternate major release cycle was a good idea. If you delay all feature development for a year, you'll get a barrage of features once the performance-only OS version is out the door, and there's not enough time to do all of them properly, so you get buggy and slow versions. Maybe doing performance improvements and feature development at the same time would have been the better choice? How is it being done at Apple nowadays?
  - nikhizzle 5y ago
    I do not know, Apple is a place where most practices are need to know only.
georgyo 5y ago
> If you add up an optimization of just a nanosecond in like openSSH, how much would that do globally? I believed optimizations like that at a global scale will not have any impact. Lets say that this nanosecond will be saved trillions of time a day. Resulting in minutes to an hour a day saved globally. * Not a single user will notice. * In 99.99% of cases the CPU will not be fully pegged and thus that one nanosecond of compute will not be used to do something else at all. * CPU throttling isn't that fast so, you won't even save that much power. If we bump it up by 6 orders of magnitude to a millisecond that all remains true. Even though you are potentially saving 100s of years of computing time a day. Extremely small gains distributed across very large number of machines don't tend to be as impactful as you would hope on a global scale. This is not to say that small gains are worthless. Many small gains added together can be substantial.