search

rafaelkallis / adaptive-radix-tree

An adaptive radix tree for efficient indexing in main memory.
GNU General Public License v3.0
146 stars 30 forks source link

benchmark missing space / mem used #16

Open hiqsociety opened 3 years ago

hiqsociety commented 3 years ago

possible to include the benchmark of space / mem used?

rafaelkallis commented 3 years ago

hi @hiqsociety, would a make benchmark-mem command solve your needs? The command would run a file using valgrind massif. For the benchmark itself I would test two scenarios of interest: 1) uniformly distributed keys and 2) zipfian keys. I would fill the tree with nullptr values to only measure data structure overhead.

Would that solve your use case? Do you have any other parameter (dependent variable) wishes for the benchmark?

superdolt commented 3 years ago

yes, that'll be great.

by the way, is adaptive radix tree better than patricia trie? (compressed radix)

rafaelkallis commented 3 years ago

by the way, is adaptive radix tree better than patricia trie? (compressed radix)

I can't give you a clear answer, it depends, define your use-case/workload and run a benchmark.

You can think of ART as patricia + node compression. If you want to read I would suggest you go over the original paper https://db.in.tum.de/~leis/papers/ART.pdf

It also strongly depends on the implementation. Not every ART implementation will have the same performance.

Also "better" might not always mean "more performance". My implementation also tries to be developer friendly and sometimes this comes at a performance cost.