News for hackers. Stuff that matters.
Re:B-Heap vs. Binary Heap (2010) by kilburn on Sunday March 18, 2018 @06:16AM (#16611224)
> I don't understand is why his data structure for finding the least-recently-used item wasn't just a linked list

Because he is not talking about expiring the Least Recently Used item, but to expire the items whose "cache time" has expired. That is, when you add a new item to the cache, you add it with some lifetime (e.g.: an integer). Then you have some clock (another integer) and what Varnish wants to do is expire all items whose lifetime is lower than the current clock.

With a (doubly-)linked list you would have to traverse the list on insertion to place the item in the correct spot...

Re:B-Heap vs. Binary Heap (2010) by abainbridge on Monday March 19, 2018 @04:41AM (#16616897)
That explains it. Thanks.