Alien-Judy
view release on metacpan or search on metacpan
src/judy-1.0.5/doc/int/10minutes.htm view on Meta::CPAN
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML EXPERIMENTAL 970324//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="Adobe FrameMaker 5.5/HTML Export Filter">
<LINK REL="STYLESHEET" HREF="10minutes.css">
<TITLE> A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST</TITLE></HEAD>
<BODY BGCOLOR="#ffffff">
<DIV>
<H1 CLASS="Title">
<A NAME="pgfId=997347">
</A>
A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST</H1>
<P CLASS="Body">
<A NAME="pgfId=997353">
</A>
By Doug Baskins, doug@sourcejudy.com</P>
<P CLASS="Body">
<A NAME="pgfId=997395">
</A>
October 16, 2001, Revised July 2002</P>
<P CLASS="Body">
<A NAME="pgfId=997492">
</A>
As the inventor of the Judy algorithm I've been asked repeatedly, "What makes Judy so fast?" The answer is not simple, but finally I can share all of the details. (In June 2002, Judy was opened sourced with a LGPL license and hosted at
<A HREF="http://sourceforge.net/projects/judy">http://sourceforge.net/projects/judy</A>
Let's see if I can give you a good understanding in 10 minutes. (The Judy data structures are very well described in another paper, the
<A HREF="http://www.sourcejudy.com/application/shop_interm.pdf">Judy Shop Manual</A>
, but it took me about three hours to read!)</P>
<P CLASS="Body">
<A NAME="pgfId=997354">
</A>
A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing...
<A HREF="http://www.sourcejudy.com/application/">http://www.sourcejudy.com/application/</A>
Judy_hashing.</P>
<P CLASS="Body">
<A NAME="pgfId=997488">
</A>
<EM CLASS="bold">
Expanse</EM>
, <EM CLASS="bold">
population</EM>
, and <EM CLASS="bold">
density</EM>
are not commonly used terms in tree search literature, so let's define them here:</P>
<UL>
<LI CLASS="Bulleted">
<A NAME="pgfId=997357">
</A>
<EM CLASS="bold">
Expanse</EM>
is a range of possible keys, such as: 256..511</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997358">
</A>
<EM CLASS="bold">
Population</EM>
is the count of keys contained in an expanse, such as, 260, 300, 499, 500 = 4.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997359">
</A>
<EM CLASS="bold">
Density</EM>
is used to describe the sparseness of an expanse of keys; density = population / expanse. A density of 1.0 means that all possible keys are set or valid in that expanse.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=997360">
</A>
<EM CLASS="bold">
Node</EM>
and <EM CLASS="bold">
branch</EM>
are used interchangeably in this document.</P>
<P CLASS="Body">
<A NAME="pgfId=997361">
</A>
<EM CLASS="bold">
Key</EM>
and <EM CLASS="bold">
index</EM>
are used interchangeably. A Judy tree is thought of as an unbounded Judy array at the API level. The expanse of JudyL or Judy1 arrays are bounded by the expanse of the word (32[64]-bits) used for the index/key. A JudySL array is only bounded by the ...
<P CLASS="Body">
<A NAME="pgfId=997362">
</A>
A (CPU) <EM CLASS="bold">
cache-line fill</EM>
is additional time required to do a read reference from RAM when a word is not found in cache. In today's computers the time for a cache-line fill is in the range of 50..2000 machine instructions. Therefore a cache-line fill should be avoided when f...
<P CLASS="Body">
<A NAME="pgfId=997363">
</A>
Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:</P>
<UL>
<LI CLASS="Bulleted">
<A NAME="pgfId=997364">
</A>
Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API).</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997365">
</A>
Judy is designed to avoid cache-line fills wherever possible. (This is the main design criteria for Judy.)</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997366">
</A>
A b-tree requires a search of each node (branch), resulting in more cache-line fills.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997367">
</A>
A binary-tree has many more levels (about 8X), resulting in more cache-line fills.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997544">
</A>
A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997545">
</A>
An "expanse"-based digital tree (of which Judy is a variation) never needs balancing as it grows.</LI>
<LI CLASS="Bulleted">
<A NAME="pgfId=997370">
</A>
A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression.</LI>
</UL>
<P CLASS="Body">
<A NAME="pgfId=997371">
</A>
The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-effici...
<P CLASS="Body">
<A NAME="pgfId=997372">
</A>
From a speed point of view Judy is chiefly a 256-ary digital tree or trie (per D. Knuth Volume 3 definitions). A degree of 256-ary is a somewhat "magic" N-ary for a variety of reasons -- mostly because a byte (the least addressable memory u...
<P CLASS="Body">
<A NAME="pgfId=997373">
</A>
It is interesting to note that an early version of Judy used branch widening (sometimes called a level-compressed trie). Branch widening opportunities occur primarily in the upper level(s) of the tree. Since a tree is a hierarchy, the upper branches ...
<P CLASS="Body">
<A NAME="pgfId=997374">
</A>
The presence of a CPU cache in modern machines has changed many of the ways to write a performance algorithm. To take advantage of a cache, it is important to leverage as much as possible. In a Judy tree, the presence of a cache results in 1..3 (or m...
<P CLASS="Body">
<A NAME="pgfId=997375">
</A>
As a digression, note that a hash method loses the advantages of a cache as the size of the hash table approaches or exceeds the size of the cache. With very large hash tables, the cache is no help at all. Also, hash methods often use a linked list ...
<A HREF="http://www.sourcejudy.com/application/">http://www.sourcejudy.com/application/</A>
Judy_hashing.</P>
<P CLASS="Body">
<A NAME="pgfId=997376">
( run in 0.576 second using v1.01-cache-2.11-cpan-cdf2f3d4e48 )