10 ms·
Multigenerational LRU: more performant, versatile, straightforward than Linux's
- CyberRabbi 6y agoI know it’s slightly imprudent but I initially discount the opinion of anyone who uses the word “performant.” I know many others do as well. Language matters. Use precise language that has a specific meaning. Anyone can make a vague claim that something is “performant”
- gfody 6y ago"performs better" the dictionary will catch up edit - apparently oxford dictionary has it already as "performs well"
- CyberRabbi 6y ago“Performs better” is just as vague. What does it mean to perform? What does it mean to do it better? Most of the time people actually mean “more efficient CPU usage”
- gfody 6y agofor this case where the thing is a cache and the description a headline, "more performant" seems perfectly cromulent. it says here's a cache that does all the stuff a cache is expected to do well but better
- CyberRabbi 6y agoSeems like a very proactive development
- mlyle 6y agoPerformant is problematic because it's tech jargon that is only now gaining grudging acceptance as a word in the overall population. It's not wrong, but it's best avoided if you want to avoid pedants waving their King's English stick at you.
- CyberRabbi 6y agoFYI “problematic” is also a vague and essentially meaningless term that is no more specific than “bad.”
- johncolanduoni 6y agoEnglish has lots of words that mean mostly the same thing. Do you seethe at every entry in a thesaurus? How does one determine which word is blessed by the higher minded beings you choose to exclusively associate with?
- CyberRabbi 6y agoI don’t usually seethe, it’s more like remote embarrassment. I think there is a German word for that. I often recommend a “non-hire” as well. Edit: I changed “non hire” to “non-hire” because I have no personal issue with acknowledging my usage of improper punctuation. Why should it be controversial to point out usage of improper vocabulary in others?
- mlyle 6y agoFYI, non-hire is the type of phrase that should be hyphenated.
- mlyle 6y agoProblematic is just fine, brah-- with usage dating to the late 17th century and with a pretty clear connotation of "presenting numerous problems" instead of just being undesirable/bad.
- yesenadam 6y agoI suggest "performy" and "problemy" as shorter. (Although many people seem to think length a virtue in words) And instead of "more performant" – "performore"?!
- bboreham 6y agoSo, we need words that say on what dimension it is performing better. I hereby coin “latencyant” and “throughputant”.
- MaxBarraclough 6y agoIf a system is highly latencyant, does that mean it performs well in terms of latency, or does it mean it exhibits high latency?
- bboreham 6y agoI was thinking “lower latency”. Is there a suffix that means “less of”? “Timeless” is already taken...
- wongarsu 6y agolatencyless and throughputful? latencyette and throughputous? latencycule and throughputty?
- gfody 6y agowhat about hit rate and time and space efficiency? i think "cachy" says it all - the cachiest cache
- yesenadam 6y agoWell, there are hypo- and hyper-.
- bboreham 6y agoNow I like hypolatent and throughputful.
- ghshephard 6y agoPerformant is a pretty common word in technology, and has been since at least 2003 when I first heard it. It's used in the same vein as "scaleable" - in both cases, suggests the positive nature of the performance and scaling.
- CyberRabbi 6y agoYes and I’ve been judging people negatively who have used it since then
- mlyle 6y agoYah, screw anyone who's on the leading edge of linguistic drift! After all, if someone doesn't properly use the second-person singular pronoun of yore, they're an illiterate scoundrel! Language shouldn't change. I think your argument has been decimated (which means reduced by a literal 10%; metaphorical and drifting meanings of words are bad!)
- CyberRabbi 6y agoI sincerely wish I understood what motivates so many people to defend poor language. Celebration for those who race to the bottom and condemnation of those who race to the top.
- MaxBarraclough 6y agoWhat's wrong with this particular drift though? Presumably you don't hold that all linguistic drift is regrettable?
- CyberRabbi 6y agoI’ve made no claim about “linguistic drift,” and I’ve explained many times in this thread why “performant” is in poor taste.
- orf 6y ago
- throwingawaymat 6y agoA more engaging summary of the article: Google engineer proposes changes in caching algorithm based on observations from "millions of servers and clients", arguing for improved performance both on low-end (phone) and high-end (hundreds of gigabytes of ram) devices.
- CyberRabbi 6y agoProbably would have made a good top-level comment. My comment is about the poor taste of the word “performant”
- dang 6y ago"Eschew flamebait. Avoid unrelated controversies and generic tangents." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- CyberRabbi 6y agoI genuinely didn’t think a negative opinion about a marketing word would be this controversial but point well taken. Last time I criticize presentation.
- NovaX 6y agoWhat is the relationship of this change with mm/workingset.c? [1] That implements a custom algorithm, Double Clock, which is inspired by LIRS. This patch touches related code, but not that file where the core algorithm is described. I tried to reimplement it in a simulator for analysis and found its hit rate varied significantly on workloads due to the percent given to LRU/LFU regions being based on machine's total memory capacity [2]. That caused it to do better in MRU/LFU workloads on high memory systems and better at LRU workloads on low-memory systems [3]. Talking to the author and there were other details not documented that might make those regions adaptive. In the end, I gave up trying to understand the page cache and if there was a benefit of switching to an alternative eviction policy. It is well written but very confusing code that seems scattered if not a kernel developer. [1] https://github.com/torvalds/linux/blob/master/mm/workingset.c https://github.com/torvalds/linux/blob/master/mm/workingset.... [2] https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42c992cabfd380e0338f2/mm/vmscan.c#L2176-L2204 https://github.com/torvalds/linux/blob/1590a2e1c681b0991bd42... [3] https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZeFn9i_iV0TPE8je4ADwlMNM8/edit#gid=1826249098 https://docs.google.com/spreadsheets/d/16wEq5QBzqOtownEtZvZe...
- uyt 6y agoThis sounds similar to https://en.wikipedia.org/wiki/Adaptive_replacement_cache https://en.wikipedia.org/wiki/Adaptive_replacement_cache which has patent issues?
- NovaX 6y agoARC shares the concept of non-resident (ghost) entries with LIRS, but uses that to dynamically adjust the SLRU partition (an LRU where probation entries are promoted to a protected region on a second hit). LIRS has fixed partitions and uses a larger history (~3x) to track the "inter-reference recency". This is a much more complex algorithm, but offers a higher hit rate and is more scan resistant. Linux's DClock calculates the "refault distance" which is their similar concept. You can compare the code of ARC [1], LIRS [2], and DClock [3] to see how similar they are. ARC obtained a lot of awareness but the hit rate is not that great. It is modestly better than LRU, but very wasteful in metadata overhead. LIRS is much better, except it is complex and the paper is confusing so almost all implementations are broken. DClock seems okayish by borrowing LIRS' ideas, but I think it performs worse in most comparisons. [1] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/adaptive/ArcPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [2] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/LirsPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/... [3] https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/policy/irr/DClockPolicy.java https://github.com/ben-manes/caffeine/blob/master/simulator/...
- Ericson2314 6y agoThe cynic in me summarizes "Google engineer says page cache is shrinking as Google has all your data instead".
- jeffbee 6y agoI have to say how much I love the Chrome OS profiling ecosystem. Google engineers bring these changes to lkml with the data in hand. Reduces tab kills by a factor of 20x, in the field? Very nice.
- yuzhao 6y agoIt's not just Chrome OS, it covers data centers too. We call it Google-wide profiling. Check these papers out: Profiling a warehouse-scale computer https://research.google/pubs/pub44271/ https://research.google/pubs/pub44271/ Google-Wide Profiling: A Continuous Profiling Infrastructure for Data Centers https://research.google/pubs/pub36575/ https://research.google/pubs/pub36575/ AutoFDO: Automatic Feedback-Directed Optimization for Warehouse-Scale Applications https://research.google/pubs/pub45290/ https://research.google/pubs/pub45290/
- goodSyntax 6y agoI don't see how this would be useful for people other than Google/Amazon/Microsoft because, to my uneducated self, it seems like their problem is driven by this: > Over the past decade of research and experimentation in memory overcommit, we observed a distinct trend across millions of servers and clients: the size of page cache has been decreasing because of the growing popularity of cloud storage. Nowadays anon pages account for more than 90% of our memory consumption and page cache contains mostly executable pages.
- jhalstead 6y agoFWIW, the Use Cases section presents data about the impact in mobile and laptop environments: On Android, our most advanced simulation that generates memory pressure from realistic user behavior shows 18% fewer low-memory kills, which in turn reduces cold starts by 16%. ... On Chrome OS, our field telemetry reports 96% fewer low-memory tab discards and 59% fewer OOM kills from fully-utilized devices and no UX regressions from underutilized devices.
- vinay_ys 6y agoThe implication of `growing popularity of cloud storage` is that today the user's data files are sitting in a remote cloud storage and not on local file system. This means a typical most-used application on user's Android/ChromeOS device (say a web browser, or a streaming app) has very little local file storage usage and hence very little page cache usage. Bulk of the memory is used by non-page-cache memory – that's anon memory. Based on this mix shift in memory use, this patchset is enhancing the swap system to evict anon pages better. It is useful for end-user linux devices like phones and laptops.
- ldng 6y agoWell, you are just confirming parent's affirmation. Not everybody uses the cloud. A database like PostgreSQL very much has local file storage usage and hence very high page cache usage. Or am I missing something ?
- refulgentis 6y ago
- throwaway29303 6y agoAwesome work! But I don't understand why they haven't implemented a neural network to take care of this. Jeff Dean even mentioned something about it[0]. [0] - https://learningsys.org/nips17/assets/slides/dean-nips17.pdf https://learningsys.org/nips17/assets/slides/dean-nips17.pdf (pp 29, 50 etc)
- magicalhippo 6y agoI guess your comment has been downvoted since it comes off a bit like "neural network all the things". But it did make me wonder, so I went searching and found this paper: "Applying Deep Learning to the Cache Replacement Problem"[1], which sounded quite interesting. In the paper they train a LSTM network to predict if an item should be cached or not, but then analyze the resulting model and identify key features of its performance. From the paper: We use these insights to design a new hand-crafted feature that represents a program’s control-flow history compactly and that can be used with a much simpler linear learning model known as a support vector machine (SVM). Our SVM is trained online in hardware, and it matches the LSTM’s offline accuracy with significantly less overhead; in fact, we show that with our hand-crafted feature, an online SVM is equivalent to a perceptron, which has been used in commercial branch predictors. We use these insights to produce the Glider4 cache replacement policy, which uses an SVM-based predictor to outperform the best cache replacement policies from the 2nd Cache Replacement Championship. Glider significantly improves upon Hawkeye, the previous state-of-the-art and winner of the 2nd Cache Replacement Championship. Training a neural network and then using it to restate the problem in more optimal way is an approach I haven't seen before (though I'm just a casual observer of the field), and which sounds very interesting. [1]: https://www.cs.utexas.edu/~lin/papers/micro19c.pdf https://www.cs.utexas.edu/~lin/papers/micro19c.pdf
- throwaway29303 6y agoI don't think I've read that before, thanks! Yeah, I believe there's also a very primitive NN on AMD's latest chips as well. I believe they used it on their branch predictors. I can't find the URL at such a short notice, though.
- 6y ago
- dshpala 6y agoI wonder how Linux with that compares to XNU (iOS)? For some reason (maybe because I work with Android) I always thought that XNU is better at memory management (fewer low memory kills, better paging, etc.).
- m463 6y ago> This causes "janks" (slow UI rendering) and negatively impacts user experience. If this makes phones faster, I am all for it. Apple is pretty good at this with ios.
- PaulHoule 6y agoThe cost of memory seems like a problem because end users experience P95+ but the people who set the spec sheet set P50. Memory that looks expensive because it has little effect on P50 (expensive to the device maker) is cheap to the end user who experiences a big change.
- peter_d_sherman 6y ago>"On Android and Chrome OS, executable pages are frequently evicted despite the fact that there are many less recently used anon pages. This causes "janks" (slow UI rendering) and negatively impacts user experience."