0
$\begingroup$

This question has been asked in the theoretical community, but deemed as too practical. I am moving it here, I hope it is on-topic.


I'd like to know more about real performances of data structures, in particular two families attract my interests:

  • hash tables
  • cache oblivious

My researches didn't find any "comprehensive" (let me use this adjective) book or article that describes the advantages and disadvantages of these two families. I have found the Intel's paper from this question, but it doesn't compare the two.

When is a hash table more performant than a cache oblivious data structure? What are the real use cases for a hash table, when is a cache oblivious B-tree (or simply binary) preferable?

The questions I'm asking are related not only on theoretical results, but also on real results on real computers.

I've read the book "Handbook of Data Structures and Applications", but it contains only theoretical limits, and it is not sufficient to me: I need to evaluate which data structures to implement on a real system.

Thanks for any pointers!

$\endgroup$
5
  • 3
    $\begingroup$ "When is a hash table more performant than a cache oblivious data structure?" that's like asking something like "who are better people, Christians or vegetarians?". It does not make sense to compare these things. Plus, there may be entities in the intersection. "What are the real use cases for a hash table, when is a cache oblivious B-tree (or simply binary) preferable? " -- what about cache-oblivious hashtable and regular B-trees? "real results on real computers." -- that's easy -- just run benchmarks! $\endgroup$ – Raphael Mar 31 '16 at 15:27
  • $\begingroup$ 1. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration. Please pick one of your two copies to delete; only one copy should be open at a time. Thank you! $\endgroup$ – D.W. Mar 31 '16 at 22:41
  • $\begingroup$ 2. In fact, CSTheory.SE did not deem your post to be too theoretical for them -- if they had, they would have closed your question, but your question remains open. Two people commented that they felt it was too theoretical, but that view did not prevail. $\endgroup$ – D.W. Mar 31 '16 at 22:41
  • $\begingroup$ @D.W. I said that they deemed it too practical and more appropriate to CS: " I am not arguing that your value system is wrong, I am arguing that your question may be better suited for a different stackexchange site, like maybe cs.stackexchange.com. – jbapple Mar 6 at 8:25". How can I proceed, should I close there with a redirect? Thanks! $\endgroup$ – senseiwa Apr 1 '16 at 9:27
  • $\begingroup$ @senseiwa, no further action is needed from you at this point. Thanks for checking! (And sorry, I meant to write "too practical" instead of "too theoretical" -- but my main point stands; that was two individuals, not the consensus opinion that ultimately prevailed.) $\endgroup$ – D.W. Apr 1 '16 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.