Programming with Judy

About Judy
Chapter 1 9
1About Judy
The Judy technology brings the benefits of exceptionally efficient,
dynamic arrays to the C programmer.
• Judy is designed to work well over a wide, dynamic range of values
and maintains excellent performance across all array populations.
Data-intensive applications using Judy can scale up without tuning
as program requirements grow.
• Code creation and maintenance is much easier. Program data
structures do not need to be periodically reworked for increased
data-handling capability. Judy is a design-once solution proven over
time.
• Judy provides an internal count that is exceptionally fast between
any two array elements. In addition, data elements are stored in
numerically sorted order.
• Productivity increases. Judy is a plug-in solution with an API that
can be accessed through simple calls.
What is Judy? The Judy technology is a C language library that provides an unbounded
array capability. For example, suppose you could declare most arrays as:
array[max];
(Where max is 2
32
on a 32-bit machine or 2
64
on a 64-bit machine.)
Now imagine that the machine uses only RAM when data is stored into
an array. Before you continue you need more information. How much
RAM is required and how fast is storage and retrieval accomplished?
Normally you would expect a ratio of at least three words per element
stored: one word for the index (key), one word for the value, and one or
more words for the overhead to manage the structure. A linked list takes
three words. A well written binary tree or skip list requires more
memory.
By contrast, the Judy technology uses much less memory per element
than traditional data structures (depending on the density and
population of the indexes). It is remarkable that Judy often uses less
than two words per element with very high populations. This is possible