3 ms·
> I mean, he's basically arguing that CS hasn't revisited heaps since 1961...But that's of course not the case. Then kindly link me to the paper which describe
by jemfinch 16y ago
> I mean, he's basically arguing that CS hasn't revisited heaps since 1961...But that's of course not the case.
Then kindly link me to the paper which describes his B-heaps; I'd love to read it.
- _delirium 16y agoHis specific B-heaps might indeed be novel; I'm not claiming he makes no contribution. I'm just objecting to the portion of his paper that claims that nobody in CS has ever thought of the idea of optimizing heaps for the properties of a modern computer's memory hierarchy. He seems to really believe Knuth's 1961 paper is the last word on the subject, or at least says so. Fwiw, here's a widely cited 1996 paper that describes a different variety of block-aggregated heaps, "d-heaps", aimed mainly at cache-aware performance: http://lamarca.org/anthony/pubs/heaps.pdf http://lamarca.org/anthony/pubs/heaps.pdf It's quite possible that no existing heap layouts solve his specific problem, but he could've at least acknowledged that there exist heaps newer than Knuth's, and that many of them specifically look at the influence of the memory hierarchy on performance.
- jemfinch 16y agoThat's a great paper, thanks for the reference.