C doesn't have a flat memory model, other than within objects. ISO C doesn't even define the behavior of comparing two pointers to distinct objects for inequality, as in p0 < p1. Only exact equality: p0 == p1.
This illustrates perfectly the premature optimization paradox, unless having huge datasets and the need to scale towards huge numbers it won't be much worth and still hashing maps are going to outperform Judy in certain use cases. Having clarity of code and being able to patch a critical bug is also a priceless competitive advantage, and to be honest, diving into a 20k line codebase related to algorithmic intensive code just is nothing to be underestimated... I wonder if someone uses Judy in production and if they made also some measurements.
I used Judy for spkg (spkg.megous.com), to efficiently store refcounted list of all files on the system in ram. It performed excellently even on 486DX2 CPU with 16MB of RAM for this purpose. Any space saving is great in that situation.
I also use it as part of a custom indexing/inverted index search engine daemon for PostgreSQL, in one of the bookstore e-shops I made more than a decade ago.
Glad to read a real world experience from someone. Memory saving is a great point. Did you have the chance to compare it against other structures before you settled with Judy?
I compared it with plain newline separated list of absolute paths, and savings were such that I could not imagine beating it with anything else I knew at the time, which would have similar characteristics.
The dataset has a lot of shared prefixes, and Judy excels at storing such data.
There is no point to compare it with something from 15 years ago, but in that case, the natural competing data structure would have been a Trie, which would have made searches at logarithmic speed (based on path) and saved as much memory as it is possible.
> If your data is strictly sequential; you should use a regular array. If your data is often sequential, or approximately sequential (e.g. an arithmetic sequence stepping by 64), Judy might be the best data structure to use. If you need to keep space to a minimum--you have a huge number of associative arrays, or you're only storing very small values, Judy is probably a good idea. If you need an sorted iterator, go with Judy. Otherwise, a hash table may be just as effective, possibly faster, and much simpler.
14 comments
[ 3.5 ms ] story [ 43.3 ms ] threadI also use it as part of a custom indexing/inverted index search engine daemon for PostgreSQL, in one of the bookstore e-shops I made more than a decade ago.
The dataset has a lot of shared prefixes, and Judy excels at storing such data.
It was 15 years ago so don't ask me for details.
> If your data is strictly sequential; you should use a regular array. If your data is often sequential, or approximately sequential (e.g. an arithmetic sequence stepping by 64), Judy might be the best data structure to use. If you need to keep space to a minimum--you have a huge number of associative arrays, or you're only storing very small values, Judy is probably a good idea. If you need an sorted iterator, go with Judy. Otherwise, a hash table may be just as effective, possibly faster, and much simpler.
2013 https://news.ycombinator.com/item?id=5639013
2013 https://news.ycombinator.com/item?id=5043667
2012 https://news.ycombinator.com/item?id=3675759
2010 https://news.ycombinator.com/item?id=1419526
2009 https://news.ycombinator.com/item?id=859336
But are the assumptions made still applicable to newer hardware?