3 ms·
That's good to know! I assumed from the comments -- most of which were from 2010 and admonished him for not being familiar with the data structure already -- t
by jfarmer 14y ago
That's good to know! I assumed from the comments -- most of which were from 2010 and admonished him for not being familiar with the data structure already -- that he was describing something which already existed at the time.
Anyhow, man, comments on HN are tedious sometimes. Everyone's glomming onto citation issues. Bo-ring.
I loved, loved, loved the visual representation of the two different data structures. It makes it really clear what's going on and why you'd want one structure vs. the other depending on memory access patterns. It makes it much easier to put frequently co-accessed and co-manipulated data in the same page of memory.
I'm a shitty systems programmer, but my understanding is that having to hop around among many different pages will cause the OS to barf out page faults. What you wind up saving in user time by optimizing for rebalancing operations you pay for 10-fold in system time.
Is that a correct understanding?
- cperciva 14y agoThe B-heap was, as far as I'm aware, a new data structure. There were other more sophisticated data structures for the same problem, and most of the criticism surrounded phk inventing his own rather than reading the literature and using one of the existing data structures. Yes, you want to minimize the number of pages you touch; this is true both in the presence of VM pressure (to avoid page faults) and to a lesser degree even without it (because you want to avoid the cost of TLB misses).
- jfarmer 14y agoThat makes the comments on the original all the more inane, then.