4 ms·

Hm... this is interesting, but I’m wondering whether it makes more sense to compare b-heap to other block-oriented data structures? I’m thinking of b-tree and i

by jmull 7y ago

Hm... this is interesting, but I’m wondering whether it makes more sense to compare b-heap to other block-oriented data structures? I’m thinking of b-tree and it’s variants.

perennate 7y ago
I think binary heap -> B-heap is analogous to balanced binary tree -> B-tree. It applies a similar idea, but provides O(1) lookup for the minimum element, O(1) average insert, and O(n) search [1], instead of O(log n) min-lookup, O(log n) insert, and O(log n search) [2]. So a B-tree would not perform well in applications where a heap is desirable. [1] https://en.wikipedia.org/wiki/Binary_heap https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree
- jmull 7y ago
  I mean in the context of block-oriented access, like VM as discussed in the article. That a block-aware data structure performs much better than a block-unaware one isn’t that surprising or interesting, at least to me. The question is: In the context of a block-oriented store, like a VM system, when is b-heap better or worse than b-tree and variants? Note, I said “and variants” deliberately because of course plain b-tree is pretty simple. Just comparing O between b-heap and b-tree isn’t enough because B-tree variants can have the same O characteristics, I think.
proverbialbunny 7y ago
Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations. Modern languages like Scala's Vector type is an rrb-tree under the hood: https://docs.scala-lang.org/overviews/collections/performance-characteristics.html https://docs.scala-lang.org/overviews/collections/performanc... For more fun: https://youtu.be/sPhpelUfu8Q https://youtu.be/sPhpelUfu8Q
- mruts 7y ago
  Unfortunately, Scala’s vector type actually sucks big time in regards to performance: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html http://www.lihaoyi.com/post/BenchmarkingScalaCollections.htm... Moreover if you want random access just use Arrays (especially now that 2.13 has immutable ones). The only use case for Vector is when you don’t know the collection size up front and need random access. Though even then it honestly might just be a better idea to build up a list and then convert it to an array.

by jmull 7y ago

Hm... this is interesting, but I’m wondering whether it makes more sense to compare b-heap to other block-oriented data structures? I’m thinking of b-tree and it’s variants.

perennate 7y ago

I think binary heap -> B-heap is analogous to balanced binary tree -> B-tree. It applies a similar idea, but provides O(1) lookup for the minimum element, O(1) average insert, and O(n) search [1], instead of O(log n) min-lookup, O(log n) insert, and O(log n search) [2]. So a B-tree would not perform well in applications where a heap is desirable. [1] https://en.wikipedia.org/wiki/Binary_heap https://en.wikipedia.org/wiki/Binary_heap [2] https://en.wikipedia.org/wiki/B-tree https://en.wikipedia.org/wiki/B-tree

jmull 7y ago
I mean in the context of block-oriented access, like VM as discussed in the article. That a block-aware data structure performs much better than a block-unaware one isn’t that surprising or interesting, at least to me. The question is: In the context of a block-oriented store, like a VM system, when is b-heap better or worse than b-tree and variants? Note, I said “and variants” deliberately because of course plain b-tree is pretty simple. Just comparing O between b-heap and b-tree isn’t enough because B-tree variants can have the same O characteristics, I think.

proverbialbunny 7y ago

Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations. Modern languages like Scala's Vector type is an rrb-tree under the hood: https://docs.scala-lang.org/overviews/collections/performance-characteristics.html https://docs.scala-lang.org/overviews/collections/performanc... For more fun: https://youtu.be/sPhpelUfu8Q https://youtu.be/sPhpelUfu8Q

mruts 7y ago
Unfortunately, Scala’s vector type actually sucks big time in regards to performance: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html http://www.lihaoyi.com/post/BenchmarkingScalaCollections.htm... Moreover if you want random access just use Arrays (especially now that 2.13 has immutable ones). The only use case for Vector is when you don’t know the collection size up front and need random access. Though even then it honestly might just be a better idea to build up a list and then convert it to an array.