How Judy arrays work and why they are so fast (2002)

Re:How Judy arrays work and why they are so fast (2002) by megous on Thursday August 29, 2019 @07:53AM (#20828643)

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.

[ Parent | on HN ]

Re:How Judy arrays work and why they are so fast (2002) by nudpiedo on Thursday August 29, 2019 @12:05PM (#20830711)

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?

[ Parent | on HN ]

Re:How Judy arrays work and why they are so fast (2002) by megous on Thursday August 29, 2019 @03:12PM (#20832625)

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.

It was 15 years ago so don't ask me for details.

[ Parent | on HN ]

Re:How Judy arrays work and why they are so fast (2002) by nudpiedo on Friday August 30, 2019 @02:48AM (#20836422)

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.

[ Parent | on HN ]