imported>Bender the Bot: HTTP to HTTPS for SourceForge

2025-08-09T21:11:36Z

HTTP to HTTPS for SourceForge

New page

{{Short description|Implementation of an associative array}}
{{notability|date=April 2022}}

In [[computer science]], a '''Judy array''' is an early-2000s [[Hewlett-Packard]] hand-optimized implementation of a 256-ary [[radix tree]] that uses many situational node types to reduce latency from CPU [[cache-line]] fills.<ref name="patent">[https://patents.google.com/patent/US6735595B2/en Robert Gobeille and Douglas Baskins' patent]</ref><ref name="shop">Alan Silverstein, "[https://judy.sourceforge.net/application/shop_interm.pdf Judy IV Shop Manual]", 2002</ref> As a compressed radix tree, a Judy array can store potentially sparse integer- or string-indexed data with comparatively low memory usage and low read latency, without relying on hashing or tree balancing, and without sacrificing in-order traversal.<ref name="ten">{{Cite web|url=http://judy.sourceforge.net/doc/10minutes.htm|title=A 10-Minute Description of How Judy Arrays Work and Why They Are So Fast}}</ref> Per-operation latency scales as <math>O(\log n)</math>—as expected of a tree—and the leading constant factor is small enough that Judy arrays are suitable even to the peta-element range.<ref>{{Cite web|url=http://packages.debian.org/buster/libjudy-dev|title=Debian -- Details of package libjudy-dev in buster}}</ref> When applicable, they can be faster than implementations of [[AVL tree]]s, [[B-tree]]s, [[hash table]]s, or [[skip list]]s from the same time period.<ref name="ten" />{{Update inline|date=June 2025}}

==History==
The Judy array was invented by Douglas Baskins over the years leading up to 2002 and named after his sister.<ref name="judy.sourceforge.net">{{cite web |url=https://judy.sourceforge.net/|title=Home|website=judy.sourceforge.net}}</ref>

==Node types==
Broadly, tree nodes in Judy arrays fall into one of three categories, though the implementation uses situational variations within each category:<ref name="shop" />
* A '''linear''' node is a short, fixed-capacity, array-based [[association list]] meant to fit in one cache line. That is, such a node has an array of key bytes and a parallel array of values or pointers. Lookup is by [[linear search]] over the key array and then random access to the corresponding index in the value/pointer array.
* A '''bitmap''' node is a size-256 [[bit array|bitvector]] tracking which values/children are present and then a sorted list of corresponding values or pointers. Lookup is by [[Hamming_weight#Processor_support|population count]] of the bits up to the target index and then random access to the corresponding entry in the value/pointer array. The bitmap fits within a typical CPU cache line, and random access only loads one cache line from the sorted list, so for reading these nodes require at most two cache-line fills.
* An '''uncompressed''' node is a conventional [[trie]] node as an array of values/pointers. Lookup is by random access using the key byte as an index, which at the CPU level requires visiting one cache line.

Linear nodes are used for low branching, bitmap nodes for intermediate branching, and uncompressed nodes for high branching.<ref name="shop" />

==Advantages and disadvantages==
Due to [[CPU cache|cache]] optimizations, Judy arrays are fast, especially for very large datasets. On certain tasks involving data that are sequential or nearly sequential, Judy arrays can even outperform hash tables, since, unlike hash tables, the internal tree structure of Judy arrays maintains the ordering of the keys.<ref name="nothings">{{Cite web|url=http://www.nothings.org/computer/judy/|title=A performance comparison of Judy to hash tables}}</ref>

On the other hand, Judy arrays are not suitable for all key types, rely heavily on compile-time case-splitting (which increases both the compiled code size and the work involved in retuning for a new architecture<ref name="nothings"/>), make some concessions to older architectures that may not be relevant to modern machines, and do not exploit [[SIMD]].<ref name="shop" /> They are optimized for read performance over write performance.<ref name="shop" />

==See also==
* [[Radix tree]]
* [[Bitwise trie with bitmap]]
* [[Hash array mapped trie]]

==References==
{{reflist}}

==External links==
*[https://judy.sourceforge.net/ Main Judy arrays site]
*[https://judy.sourceforge.net/downloads/10minutes.htm How Judy arrays work and why they are so fast]
*[https://judy.sourceforge.net/application/shop_interm.pdf A complete technical description of Judy arrays]
*[http://www.nothings.org/computer/judy/ An independent performance comparison of Judy to Hash Tables]
*[https://github.com/JerrySievert/judyarray A compact implementation of Judy arrays in 1250 lines of C code]

[[Category:Associative arrays]]

Judy array - Revision history

imported>Bender the Bot: HTTP to HTTPS for SourceForge