5 ms·

A "50/50" rule such as the one described is a clear signal that the memory manager's cache eviction policy is an ad-hoc hack. This sort of problem would benefit

A "50/50" rule such as the one described is a clear signal that the memory manager's cache eviction policy is an ad-hoc hack. This sort of problem would benefit from some old-fashioned operations research-style statistical and mathematical modeling. What's the probability that a page will be needed? What's the cost of keeping it around? A proper model would be able to answer these questions. A "recency cache" and "frequency cache" is missing the bigger picture.

joe_the_user 13y ago
Well, Keep in mind that never, ever having really bad things happen is first priority for an algorithm of that sort and only then can it think about being efficient in a really clever way. I'd imagine that from the statistical analysis perspective, all memory managers seem like "ad-hoc hacks" but I believe what happens is they are really smart hacks tested with multiple use cases. Creating a statistical analysis/machine-learning/etc program that can deal quickly with heterogeneous data robustly in real-time would be an incredible achievement. If anyone knows of a situation where serious machine learning has been applied at such a low level, I would love to hear about it (the only thing vaguely similar I recall is that use of neural networks for branch prediction, something that's been studied but not implemented).
phaemon 13y ago
Well don't just post this here. Post on the Linux Kernel Mailing List. If you can explain to them how to improve their ad-hoc hack, I'm sure they'd love to hear from you. It would almost certainly be hugely valuable to companies like IBM or Google to have better memory management on their servers. In fact, it could probably boost Linux performance on the Supercomputer list!
- dllthomas 13y ago
  And they'll be super friendly about it.
  - phaemon 13y ago
    I would pay money to watch it.
ori_b 13y ago
> What's the probability that a page will be needed? What's the cost of keeping it around? The answer is pretty simple: It depends. What's your workload? There's no general answer. So, Linux picked a heuristic. They could probably have picked a better one, but short of some sort all knowing of machine learning algorithm which can predict future workloads, the heuristic they pick will be suboptimal in some regard.
- jacques_chester 13y ago
  > The answer is pretty simple: It depends. What's your workload? There's no general answer. Which is, ironically, an argument for microkernels. In some microkernel designs you could, in principle, allow for applications to provide their own disk and memory managers.
  - ori_b 13y ago
    To a degree. Both memory and disk bandwidth are shared resources. It's hard to prevent one algorithm from stomping on another without giving it exclusive control. So while you may be able to swap in a memory manager that doesn't have this pathological case, it might negatively affect other applications. To give an extreme example, imagine that an application sets up a custom memory manager that takes all available RAM, and makes it exclusive to that application. In reality, it would probably be less insane, but you would still get regressions with multiple memory managers. And if you decide you have to have one true memory manager... you're back to the situation that exists today, only potentially slightly easier to configure away from bad behavior.
    - jacques_chester 13y ago
      Definitely, but my argument is that OSes must account for the shared-server case, but in practice many servers are dedicated to a single service. Supposing you built a memory manager exclusively tuned for PostgreSQL, with the assumption that it has the machine to itself. That memory manager would have a different performance profile from the kind of "veil of ignorance" that a general-purpose memory manager has to cope with.
deleted 13y ago
[deleted]
blt 13y ago
I was under the impression that this code has to be really fast. I wonder how much computation they can get away with.
zidar 13y ago
You should look up some links in the article (proposed solution https://lkml.org/lkml/2013/11/24/133 https://lkml.org/lkml/2013/11/24/133) "Currently, the VM aims for a 1:1 ratio between the lists, which is the "perfect" trade-off between the ability to protect frequently used pages and the ability to detect frequently used pages. This means that working set changes bigger than half of cache memory go undetected and thrash indefinitely, whereas working sets bigger than half of cache memory are unprotected against used-once streams that don't even need caching."

joe_the_user 13y ago

Well, Keep in mind that never, ever having really bad things happen is first priority for an algorithm of that sort and only then can it think about being efficient in a really clever way. I'd imagine that from the statistical analysis perspective, all memory managers seem like "ad-hoc hacks" but I believe what happens is they are really smart hacks tested with multiple use cases. Creating a statistical analysis/machine-learning/etc program that can deal quickly with heterogeneous data robustly in real-time would be an incredible achievement. If anyone knows of a situation where serious machine learning has been applied at such a low level, I would love to hear about it (the only thing vaguely similar I recall is that use of neural networks for branch prediction, something that's been studied but not implemented).

phaemon 13y ago

Well don't just post this here. Post on the Linux Kernel Mailing List. If you can explain to them how to improve their ad-hoc hack, I'm sure they'd love to hear from you. It would almost certainly be hugely valuable to companies like IBM or Google to have better memory management on their servers. In fact, it could probably boost Linux performance on the Supercomputer list!

dllthomas 13y ago
And they'll be super friendly about it.
- phaemon 13y ago
  I would pay money to watch it.

ori_b 13y ago

> What's the probability that a page will be needed? What's the cost of keeping it around? The answer is pretty simple: It depends. What's your workload? There's no general answer. So, Linux picked a heuristic. They could probably have picked a better one, but short of some sort all knowing of machine learning algorithm which can predict future workloads, the heuristic they pick will be suboptimal in some regard.

jacques_chester 13y ago
> The answer is pretty simple: It depends. What's your workload? There's no general answer. Which is, ironically, an argument for microkernels. In some microkernel designs you could, in principle, allow for applications to provide their own disk and memory managers.
- ori_b 13y ago
  To a degree. Both memory and disk bandwidth are shared resources. It's hard to prevent one algorithm from stomping on another without giving it exclusive control. So while you may be able to swap in a memory manager that doesn't have this pathological case, it might negatively affect other applications. To give an extreme example, imagine that an application sets up a custom memory manager that takes all available RAM, and makes it exclusive to that application. In reality, it would probably be less insane, but you would still get regressions with multiple memory managers. And if you decide you have to have one true memory manager... you're back to the situation that exists today, only potentially slightly easier to configure away from bad behavior.
  - jacques_chester 13y ago
    Definitely, but my argument is that OSes must account for the shared-server case, but in practice many servers are dedicated to a single service. Supposing you built a memory manager exclusively tuned for PostgreSQL, with the assumption that it has the machine to itself. That memory manager would have a different performance profile from the kind of "veil of ignorance" that a general-purpose memory manager has to cope with.

deleted 13y ago

[deleted]

blt 13y ago

I was under the impression that this code has to be really fast. I wonder how much computation they can get away with.

zidar 13y ago

You should look up some links in the article (proposed solution https://lkml.org/lkml/2013/11/24/133 https://lkml.org/lkml/2013/11/24/133) "Currently, the VM aims for a 1:1 ratio between the lists, which is the "perfect" trade-off between the ability to protect frequently used pages and the ability to detect frequently used pages. This means that working set changes bigger than half of cache memory go undetected and thrash indefinitely, whereas working sets bigger than half of cache memory are unprotected against used-once streams that don't even need caching."