General purpose dynamic array - Judy

I like it, although I didn't take the time to read it all.  At first
based on the URL I thought maybe Google Itself had taken notice and
written this webpage, but then I realized not, it's a subdomain under
google.com.  It's a smaller reimplementation of the library?  With some
creative variations in the API.  Does it work as well?  That's the key
criterium to me.

The introduction could but does not say why libJudy is special.  In my
mind it has to do with the iron-clad by-expanse (radix) approach to
decoding keys (indexes), which is infinitely extensible, coupled with
all the pragmatic tricks employed in the original code to as portably as
possible make the radix method practical, in fact extremely efficient,
in time and space.  Digital trees (tries) were always dissed in the past
as inherently inefficient, and we proved that's not true, undermining
decades of complicated work on optimizing the performance of non-radix
(by-population) trees of many kinds.  Unfortunately being R&D engineers
rather than academicians, we never "published our work" other than the
source code, which relegated libJudy to the dusty corners of computer
history when HP canceled the project.

In your reimplementation, did you study the existing code (difficult I
know), or just recreate the interface but probably not as efficiently?

Cheers,
Alan Silverstein

Hi Alan,

I'm not the author. The author of this re-implementation is a very well known/respected engineer/coder in USA.
Karl Malbrain:
http://sites.google.com/site/karlmalbrain/

regards
Y.

Le 9 janv. 2011 à 23:20, Alan Silverstein a écrit :

> I like it, although I didn't take the time to read it all.  At first
> based on the URL I thought maybe Google Itself had taken notice and
> written this webpage, but then I realized not, it's a subdomain under
> google.com.  It's a smaller reimplementation of the library?  With some
> creative variations in the API.  Does it work as well?  That's the key
> criterium to me.
> 
> The introduction could but does not say why libJudy is special.  In my
> mind it has to do with the iron-clad by-expanse (radix) approach to
> decoding keys (indexes), which is infinitely extensible, coupled with
> all the pragmatic tricks employed in the original code to as portably as
> possible make the radix method practical, in fact extremely efficient,
> in time and space.  Digital trees (tries) were always dissed in the past
> as inherently inefficient, and we proved that's not true, undermining
> decades of complicated work on optimizing the performance of non-radix
> (by-population) trees of many kinds.  Unfortunately being R&D engineers
> rather than academicians, we never "published our work" other than the
> source code, which relegated libJudy to the dusty corners of computer
> history when HP canceled the project.
> 
> In your reimplementation, did you study the existing code (difficult I
> know), or just recreate the interface but probably not as efficiently?
> 
> Cheers,
> Alan Silverstein

On 10/01/2011, at 8:30 AM, judy wrote:

> What do you think guys:
> http://code.google.com/p/judyarray/
> 

I will have a deeper look, but some comment from a quick scan:

"uint" NO NO NO. You must not do it !

On 64 bit windows, unsigned int is still 32 bit. Judy requires a full
size machine word.

You must not usurp a name as common as "uint".

The correct name to use "would be" 

uintptr_t

if only the dang C99 Standard actually mandated it, but it doesn't.

So you can either 

(a) give up and tell people they have to run C99 or ISO C++ with C99 extensions
or arrange to fix their broken systems themselves 

(b) use a name like "Judy_word_t"

which not one else is likely to use.

Unfortunately, I have to recommend (b). It's unfortunate our standards bodies
have let us down a bit here, but people like to preserve old code.




--
john skaller
skaller@...

On 10/01/2011, at 9:20 AM, Alan Silverstein wrote:

>   With some
> creative variations in the API.  Does it work as well?  That's the key
> criterium to me.

More important to most people is not even performance: this is a very
hard library to work on so most  users including me could never actually
fix a bug if one were found.

So .. the question is, does it work. Full Stop. Forget "as well".
Yeah, I'd like it to be as fast as Judy or even faster, but if there's
a single bug my whole product is completely screwed because it
relies utterly on Judy.


> The introduction could but does not say why libJudy is special.  In my
> mind it has to do with the iron-clad by-expanse (radix) approach to
> decoding keys (indexes), which is infinitely extensible,

FYI: this is not quite true. Technically yes. But in practice no,
because of the old "memory management problem".

It's fine to glue arrays together, but it's very hard to ensure correct
memory management in the presence of variants other than NULL.

For example suppose you use Judies of Judies to represent strings.
After 64 bytes, if the string hasn't run out, you just point at a new Judy
array. But now to delete the top level array in C, without C++ destructors
to automate it, or a garbage collector, is a nightmare because you have
to scan the whole arrays recursively, deleting objects bottom up.

Of course if there is any sharing at all, then it is almost unmanageable.



--
john skaller
skaller@...

On 10/01/2011, at 8:30 AM, judy wrote:

> What do you think guys:
> http://code.google.com/p/judyarray/

BTW also: internal stack confuses me. I haven't looked at the source
but if the internal stack is a static variable I can't use it.

It's imperative NO global variables are used for anything,
and there is no hidden state between function calls. 

I use Judy in a multi-threaded environment, re-entrancy
is mandatory.



--
john skaller
skaller@...

On 10/01/2011, at 8:30 AM, judy wrote:

> What do you think guys:
> http://code.google.com/p/judyarray/

Ok, had a quick look at source:

typedef struct {
	judyslot root[1];	// root of judy array
	void **reuse[8];	// reuse judy blocks
	JudySeg *seg;		// current judy allocator
	uint level;			// current height of stack
	uint max;			// max height of stack
	JudyStack stack[1];	// current cursor
} Judy;

basically, this data structure holds state information between
calls, and so the system isn't re-entrant. However it's a per-Judy
array structure, so provided distinct threads access distinct arrays
it should be ok.

However, distinct threads SHOULD be able to read a single Judy array
without interference.

This is an age old problem, first becoming critical in the mis-design of SQL
and repeated again and again and again by people that learnt C as a first
programming language and never graduated to learning how to program
properly. (SQL "cursor" concept is screwed).

Generally, if you need any state  to do read access to a data
structure, it has to go on the stack, or, be created dynamically and
held by the client, never the data structure. Clearly if you're
modifying a data structure the situation is different, asynchronous
modifications are unprincipled (which means NO you should NOT
lock anything, it's up to the client to do the synchronisation).

Again, I'm not sure from a brief look at the code. Re-entrant code
can sometimes be slower.

Another stupid example of this problem is OpenGL. Another mis-design
which in this case is inexcusable (since it's relative modern).

Microsoft, generally, got this stuff right. Most Unix stuff does not.


--
john skaller
skaller@...

> More important to most people is not even performance:  this is a very
> hard library to work on so most users including me could never
> actually fix a bug if one were found.

Agreed.

> So ..  the question is, does it work.  Full Stop.  Forget "as well".
> Yeah, I'd like it to be as fast as Judy or even faster, but if there's
> a single bug my whole product is completely screwed because it relies
> utterly on Judy.

But it's never had a bug after being released.  Period.

We tested the crap out of it.  I've used it heavily myself, and was
never disappointed.

Yeah, there are usability disconnects that can make it hard to write
code to the API, and masquerade as bugs, but the library itself, as
released to SourceForge many years ago, has been flawless, as far as I
know and have experienced.

Given something with simpler source, great, but what's the point of
using it if performance is no better than you can get with hash-this and
that-tree already out there in the public domain?  libJudy lets you
build array-of-array, millions/billions, with small memberships,
something that no other API lets you do easily.

> For example suppose you use Judies of Judies to represent strings.
> After 64 bytes, if the string hasn't run out, you just point at a new
> Judy array.  But now to delete the top level array in C, without C++
> destructors to automate it, or a garbage collector, is a nightmare
> because you have to scan the whole arrays recursively, deleting
> objects bottom up.

Not if use let the JudyS*() wrappers take care of that for you?

OH well, it's been years since I worked on it, and a couple of years
since I used it as a developer (of higher-level code), so what do I
know?  You are probably right.

Cheers,
Alan Silverstein

On 10/01/2011, at 1:18 PM, Alan Silverstein wrote:

>> More important to most people is not even performance:  this is a very
>> hard library to work on so most users including me could never
>> actually fix a bug if one were found.
> 
> Agreed.
> 
>> So ..  the question is, does it work.  Full Stop.  Forget "as well".
>> Yeah, I'd like it to be as fast as Judy or even faster, but if there's
>> a single bug my whole product is completely screwed because it relies
>> utterly on Judy.
> 
> But it's never had a bug after being released.  Period.
> 
> We tested the crap out of it.  I've used it heavily myself, and was
> never disappointed.


But that's the point: the "old Judy" is heavily tested and in use
in a several applications. The "new code" is untested, so there's
a big issue trusting it.

However the new code is more readable, more modern, less
macro heavy, and easier to build.

> 
>> For example suppose you use Judies of Judies to represent strings.
>> After 64 bytes, if the string hasn't run out, you just point at a new
>> Judy array.  But now to delete the top level array in C, without C++
>> destructors to automate it, or a garbage collector, is a nightmare
>> because you have to scan the whole arrays recursively, deleting
>> objects bottom up.
> 
> Not if use let the JudyS*() wrappers take care of that for you?

That was just a trivial example. And Judy's string stuff only works
on NTBS, not strings with counted length. You can get counted
lengths by roll your own Judy arrays of arrays: just round the string
up to multiple of 8 bytes, use J1 to store the length and J2 for the
first 8 bytes. If length > 8 then store a second array in the first.
[I'm thing of a set of strings here].

Ok, so all this is easy, but how do yo remove a string from the set?
You can't just remove the key, because that would leave the value
(another Judy array) dangling. You have to make sure that second
Judy array is empty first.

Yeah, it's just a bottom up recursive descent, but then this is a trivial
example. If you have a harder example where you're mapping
stuff, you have to be careful the target is deleted. For example
consider mapping to a C++ shared pointer, you have to invoke
the destructor. Will it fit in 64 bits? If not you need to malloc
a object for it and store that pointer instead.

Easy to mess all those indirections up .. :)

--
john skaller
skaller@...

> But that's the point:  the "old Judy" is heavily tested and in use in
> a several applications.  The "new code" is untested, so there's a big
> issue trusting it.
>
> However the new code is more readable, more modern, less macro heavy,
> and easier to build.

Right, in which case there's less reason to worry about using it.

> And Judy's string stuff only works on NTBS, not strings with counted
> length.

Sure, a long-known, discussed, and documented shortcoming.

> You can get counted lengths by roll your own Judy arrays of arrays:
> just round the string up to multiple of 8 bytes, use J1 to store the
> length and J2 for the first 8 bytes.  If length > 8 then store a
> second array in the first.  [I'm thing of a set of strings here].

Yes, the only catch is that the strings are sorted by length, which is
fine if you don't care.

> Ok, so all this is easy, but how do yo remove a string from the set?
> You can't just remove the key, because that would leave the value
> (another Judy array) dangling.  You have to make sure that second Judy
> array is empty first.

Yes, you must traverse cleanly any array-of-array to do proper removals,
nothing special about length-associated (rather than JudySL*()
length-terminated) string arrays.

> Yeah, it's just a bottom up recursive descent, but then this is a
> trivial example.  If you have a harder example where you're mapping
> stuff, you have to be careful the target is deleted.  For example
> consider mapping to a C++ shared pointer, you have to invoke the
> destructor.

Absolutely.  In fact I wrote a lot of code just like that in the last
few years.  Care is required, but then it works well.  TANSTAAFL, if you
don't mind possibly serious performance losses, you can always use
languages or tools that manage the memory for you.

> Easy to mess all those indirections up ..  :)

Agreed.

Alan

On Sun, Jan 9, 2011 at 5:37 PM, john skaller
<skaller@...> wrote:
> On 64 bit windows, unsigned int is still 32 bit. Judy requires a full
> size machine word.

Linux too, it's mandated by the SYSV ABI. Oddly enough, this mixed mode works
quite well on x86 due to its CISC nature and historical accident, it's
arithmetic operations default to 32 bit so you get more compact code when
using a 32 bit int, however x86 still has all these wacky indexing modes for
pointers, meaning you rarely actually have to directly manipulate pointers as
if they are numbers. So you can have 32 bit ints and 64 bit pointers while
still having compact code.

> You must not usurp a name as common as "uint".
>
> The correct name to use "would be"
>
> uintptr_t
>
> if only the dang C99 Standard actually mandated it, but it doesn't.

I think it is okay to consider it standard de facto. It was made optional to
allow C compilers on machines that can't manipulate pointers as if they are
numbers, odd tagged memory machines or whatnot. In any case, I have not lost
any sleep over assuming it is available and having autoconf create a conforming
stdint.h if it isn't there.

> Unfortunately, I have to recommend (b). It's unfortunate our standards bodies
> have let us down a bit here, but people like to preserve old code.

I don't think this was about old code, it is about machines that actually don't
have any representation of pointers that can be fit in a word. Using uintptr_t
is fully portable in practice and I encourage its use. (it is a pet peeve of
mine when people don't use it.)

     John

On 11/01/2011, at 8:22 AM, John Meacham wrote:

>> 
>> The correct name to use "would be"
>> 
>> uintptr_t
>> 
>> if only the dang C99 Standard actually mandated it, but it doesn't.
> 
> I think it is okay to consider it standard de facto.

>  Using uintptr_t
> is fully portable in practice and I encourage its use. (it is a pet peeve of
> mine when people don't use it.)


Even in C++? I mean, there's no C++ library containing it (soon to be
fixed in C++11?)

In Felix, we use an alias of uintptr_t if it exists, otherwise config script
aliases something else big enough.

--
john skaller
skaller@...

On 11/01/2011, at 5:12 AM, Alan Silverstein wrote:

> 
> Absolutely.  In fact I wrote a lot of code just like that in the last
> few years.  Care is required, but then it works well.  TANSTAAFL, if you
> don't mind possibly serious performance losses, you can always use
> languages or tools that manage the memory for you.


It isn't clear there are performance losses :)

Felix uses a gc, which itself uses .. Judy Arrays:)

Modern GC is not slow, in fact it's believed to be faster than manual memory management.
If you have a complex structure you MUST use a GC. For less complex structures,
ref counting is required but GC is faster .. its a LOT faster if the data structure is
multi-threaded and uses locks on the ref counts.

[The Felix GC is naive so it isn't a "modern" GC, because it has to
cope with C code]

--
john skaller
skaller@...