What Are Judy Arrays?

While building a key-value store for a university project, I came across a data structure called Judy Arrays. It was developed by Douglas Baskins while he was working at HP. Because there's so little academic research on it, Judy Arrays aren't nearly as well known as other data structures. This is my attempt to explain what's actually happening under the hood.

A simple Wikipedia lift will tell you that

Judy array is a data structure implementing a type of associative array with
high performance and low memory usage.

If it's just an associative array, why do we need another data structure doing the same job as AVL trees, B-trees, or skip lists? Let's find out.

Any living being who's written a few lines of code is familiar with traditional arrays, available in most programming languages. A traditional array works exceptionally well due to its

1. fast lookup
2. fast insertion, and
3. fast deletion

All we need is the array's base address and an offset to access an element, since all the values are stored contiguously.

But what if the data you need to index is sparse? The size of a traditional array is fixed and can't adapt to how sparse the data is. That's grossly memory inefficient. To better understand this, consider that your range of keys, or expanse, is 1…100. So we create a traditional array of size = 100 to cover the entire expanse. Now, if we only fill 10 locations in the array, that's a loss of 90 memory locations. Memory inefficient, isn't it? A densely populated array would be the exception.

Enter Judy Arrays. In a nutshell, a Judy Array is a trie. I suggest reading up about tries if you're not familiar with them. It's a fundamental and useful data structure, also called a digital tree or a radix tree.

Each node in a Judy Array has 256 branches. For a 32-bit expanse, that translates to at most 4 lookups. Also, if the number of keys to be stored, or population, is small, Judy stores everything in the root. A well-implemented Judy Array also uses highly efficient node-compaction schemes that further reduce the size of each node.

Judy Array does not use any hashing function and stores the keys in sorted
order just like other tree implementations.

What makes it fast?

1. Avoids cache-line fills: A cache-line fill is the additional time required to do a read reference from RAM when a word is not found in cache. On today's computers, the time for a cache-line fill is in the range of 50..2000 machine instructions. A cache-line fill should be avoided when fewer than 50 instructions can do the same job. Judy is designed to avoid cache-line fills wherever possible.

2. Memory efficient: Its node-compaction and branch-compression schemes make it well suited for semi-sequential sparse data. Some of the branch compression schemes are linear and bitmap, but they're beyond the scope of this article. Judy Arrays are also left uncompressed when the population is dense.

3. No tree balancing, and grows dynamically: A Judy Array can grow or shrink as elements are added to, or removed from, the array. The memory used by a Judy Array is nearly proportional to the number of elements in it.

When to use it?

Judy Arrays are suitable to use under the following conditions.

1. Large and sparse data sets.
2. Semi-sequential data sets.
3. General low-latency requirements.

Benchmarks

Source: https://rusty.ozlabs.org/?p=153

In a series of benchmarks conducted by Rusty Russell (linked above) between Judy Arrays, Google's SparseHash and DenseHash, and DumbHash, the following results were obtained.

Task 1

Initial insertion of keys 0 to 49,999,999 in order, looking them up in order, looking up keys 50,000,000 to 99,999,999 in order.

Task 2

Delete everything and reinsert them all (in order).

Task 3

Lookup random elements and access the elements.

You can read further about these benchmarks at https://rusty.ozlabs.org/?p=153.

Current implementations

The original implementation of Judy Array was written by Douglas Baskins and his team at HP. It's probably the fastest, but sprawls across 20,000 lines of code, making it difficult to comprehend. It's available as an API library, though.

Link: https://sourceforge.net/projects/judy

Below is an example of the API this implementation provides.

Judy1  - maps an Index (word) to a bit
JudyL  - maps an Index (word) to a Value (word/pointer)
JudySL - maps an Index (null terminated string) to a Value
JudyHS - maps an Index (array-of-bytes) of Length to a Value

Years later, Karl Malbrain rewrote Douglas's Judy Arrays in 1,250 lines of code, with help from Jan Weiss. His implementation is quite popular within the FOSS community, with multiple language-specific wrappers written around it.

Link: https://code.google.com/archive/p/judyarray/