5 ms·
Again, the kernel will use a simple LRU algorithm, where the granularity is the page. I don't think it's accurate to describe any performance critical part of
by scott_s 16y ago
Again, the kernel will use a simple LRU algorithm, where the granularity is the page.
I don't think it's accurate to describe any performance critical part of the Linux kernel as "simple." For an overview of the page replacement policy, see http://kerneltrap.org/node/7608 http://kerneltrap.org/node/7608. I wondered if CLOCK-Pro [1, 2] had made it into the kernel yet, but it looks like it has not.
This author makes compelling arguments for implementing application level paging. But the nice thing about doing systems work is we never have to rely on arguments alone to evaluate something - show me numbers.
[1] http://linux-mm.org/ClockProApproximation http://linux-mm.org/ClockProApproximation
[2] http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.pdf http://www.cse.ohio-state.edu/~fchen/paper/papers/usenix05.p...
- bch 16y agoThere was no mention of Linux in the article. This system also runs on the various *BSDs, Solaris, MacOS...
- scott_s 16y agoThen it's worth noting that CLOCK-Pro is used in NetBSD. My point here is that a lot of people have spent a lot of time working on the page replacement problem. I am very open to the idea that an application can beat the page replacement policy in the underlying kernel, for a variety of reasons. But: numbers. Always evaluate. The implementation of these algorithms in practice is always more subtle than our high level understanding, so we need to do real performance comparisons to know if we actually improved anything. (I'm getting my information from the algorithm's author's page: http://www.ece.eng.wayne.edu/~sjiang/ http://www.ece.eng.wayne.edu/~sjiang/ Jiang graduated from William and Mary while I was a young grad student there.)
- bch 16y agoAgreed. "Problems" without measurements aren't worth much. My initial reaction was to your assumption about Linux, but we agree that assumptions in general aren't worth much.
- dasil003 16y agoI'm a bit torn on this. I realize that you need to benchmark to really prove anything, and that optimization intuitions are often wrong, but on the other hand, you really need a wide variety of world benchmarks to approach any form of real world "proof". In the early implementation stages, I think clear thinking such as provided in this article is probably more important than spending 50 times as long setting up an array of benchmarks. Hopefully Salvatore has done some micro-benchmarks during development to guide his thinking, but even if not, it's hard to refute the thinking in this article. If you think about the problem space of Redis vs Varnish, it's intuitively obvious that Varnish deals with a wide variety of general data without many opportunities to optimize beyond general purpose algorithms such as an OS provides. Whereas Redis has specific data types often with small footprints, and very careful attention paid to the details of optimization for memory and disk usage.
- scott_s 16y agoI think you're overstating the time it takes to come up with benchmarks to evaluate performance optimizations. Even micro-benchmarks tailored to showcase your performance under ideal circumstances are a start. The longer you go without doing any performance comparisons, the longer you go without knowing if your work was worth it. I'm not trying to deride his work - it's a neat project, and I will probably read through his earlier entries more. I'm down with all of the reasons provided, but I recognize that as humans, we tend to believe in things we understand. Hence, we need to evaluate.
- dasil003 16y agoPerhaps I am, but why are we assuming he hasn't done any benchmarks? It seems quite likely that his opinion is informed by actual results. Does he need to draw up graphs and spend more time on a blog post to be taken seriously?
- scott_s 16y agoWell, yes. I take him "seriously," but I'm not yet convinced his techniques outperform the kernel. That's how systems work is done. If you want to convince people that your way is better, then you need data to back it up.
- nwmcsween 16y agoHow is LRU not simple? The page replacement policy in Linux is simple it's just makes use of available information - The algorithm does not make the system. Clock-pro is not in Linux and I doubt it ever will be. The goal in creating manageable code is passing the information that you know to the next person that doesn't by using comments and even Linux doesn't do this at all so hack-ability of any non trivial parts is near impossible without a few months of poking.