Re: [Felix-impl] judy bug

[Doug B. <dou...@ya...>]

John:=0A=0A> Word_t *pshape=3D (Word_t*)JudyLGet(j_shape,(Word_t)memory,&je=
);=0A>   if(pshape=3D=3DNULL||pshape =3D=3D (Word_t*)(void*)PPJERR) abort()=
;=0A=0AI have been considering on getting rid of the PJError_t parameter in=
 the =0AJudy routines that do not malloc(2).  It seems that nobody uses it.=
=0AJudy returning a -1 in the "pointer to value" word do so because:=0A=0A1=
) There was a malloc(2) failure.=0A2) There was a Judy array corruption.=0A=
3) There was a programming mistake.=0A=0AThe NULL return simply means "not =
found".  In JudyLGet() this is=0Anot an error (unless the programmer does n=
ot expect it).=0A=0AFor example, in the above code, the "je" error structur=
e is never used.=0AIf you were lucky and looked at the error code number, i=
t may of said: =0A"not a Judy array" or some clue like that.=0A=0ASo, it mi=
ght as well of been written:=0A=0AWord_t *pshape=3D (Word_t*)JudyLGet(j_sha=
pe,(Word_t)memory,NULL);=0A=0AJudy was designed to have a zero (NULL) in th=
e error parameter place.=0A=0AIn Judy routines that do not call malloc(2), =
then the -1 return means a=0A(2 Judy array corruption or a (3) programming =
mistake -- both of which=0Ashould be gone with production code. (32 bit Jud=
y1Count() is an exception).=0A=0AIn using Judy for the last 6 years, I have=
 very seldom run into a Judy array=0Acorruption -- usually the result of a =
(random) RAM failure.=0A=0AOne of the original  (perhaps misguided) reasons=
 for the -1 return was=0Ato avoid the "core dumps" from within the Judy cod=
e.  I got tired of =0Aexplaining to programmers that it was their error in =
the calling parameters.=0A=0AAs for your mistake with JudyLGet(), we all ha=
ve done it and I have considered=0Achanging interface.  The design of JudyL=
Ins() requires the "&" so that the =0A"allocate the array with NULL pointer=
" property of Judy can be used.=0AThis is very important in "applications" =
such as JudySL().  However, it is=0Apossible (and perhaps desirable) to do =
that with an additional code outside=0Athe JudyLIns() code and code that ca=
lls malloc(2)/free(2).=0AAgain, this was not done originally because of the=
 additional overhead=0Aof a subroutine call -- no longer significant in a m=
odern processor.=0AThe Judy macros (JLG() etc.) were an attempt to avoid th=
at mistake, but=0Ait seems that programmers don't like using them for reaso=
ns I don't understand.=0A=0AOn another subject, you suggest the JudyLNext()=
 return some=0Astateful information -- for performance.  I studied that ver=
y=0Aextensively 6 years ago to improve the performance on Next/Prev.  =0AAg=
ain, on a modern processor, these routines almost always run when the=0Adat=
a is "in the cache" and they almost disappear from the profiles.=0A(Having =
stateful information does not help in avoiding cache misses).=0A=0AI am sti=
ll actively working on a new Judy.  Improved speed was the=0Ahighest object=
ive, but it looks like greatly improved memory efficiency=0Awill be the big=
gest improvement.=0A=0AI take your suggestions very seriously, so keep them=
 coming.=0ANobody likes the Judy semantics, but I have not found a better=
=0Asolution or even had suggestions -- with code examples.=0A=0AThe latest =
wrinkle with C++ not compatible with Judy is troublesome=0Afor me.=0A=0A=0A=
> The typing and docs on the interface are not so good.. ouch.=0A=0AI accep=
t suggestions with examples on that too.  I do not like a=0A"man" page long=
er than 1 screen full.=0A=0AThanks for your interest and inputs.=0A=0ADoug=
=0A =0ADoug Baskins <dou...@gm...>=0A=0A=0A=0A----- Original Messa=
ge ----=0AFrom: skaller <sk...@us...>=0ATo: aj...@fr...=
=0ACc: jud...@li...; fel...@li...=
=0ASent: Monday, September 17, 2007 6:53:26 AM=0ASubject: Re: [Felix-impl] =
judy bug=0A=0AOn Sun, 2007-09-16 at 22:08 -0600, Alan Silverstein wrote:=0A=
> > Ah, found bug in my code -- how I hate that moronically stupid C=0A> > =
language.  Was using &a instead of a for JudyLGet.=0A> =0A> All too easy.  =
I've made recent use of libJudy myself in my contract=0A> job, and even as =
one of the authors I find it surprisingly difficult to=0A> keep the pointer=
 expressions correct.  In particular when *Pvalue return=0A> by JudyL or Ju=
dySL, which it only knows as a word -- no forced=0A> interpretation of the =
contents -- is known to the caller to contain a=0A> pointer.  So you must f=
irst check for Pvalue being null, etc:=0A> =0A>     foo_t * Pfoo;=0A>     J=
LG(Pvalue, ...);=0A> =0A>     Pfoo =3D ((Pvalue =3D=3D NULL) ? NULL : (foo_=
t *) (*Pvalue));=0A> =0A> It can get confusing, especially when dealing wit=
h array-of-array, etc.=0A=0AI'm not using the macros .. so it is much worse=
: Ihave this, =0Afor example:=0A=0A  Word_t *pshape=3D (Word_t*)JudyLGet(j_=
shape,(Word_t)memory,&je);=0A  if(pshape=3D=3DNULL||pshape =3D=3D (Word_t*)=
(void*)PPJERR) abort();=0A=0A> But it sure has sped up some slow programs d=
ramatically.=0A=0AMy experience is slightly different. The Felix gc is actu=
ally slightly=0Aslower with Judy than the doubly linked list I used before.=
=0AMemory consumption is about the same I think .. not sure.=0A=0AFor me th=
e BIG difference was in another area: functionality.=0A=0APreviously, the F=
elix gc used memory blocks like:=0A=0A    [ shape pointer ]=0A    [ array c=
ount ]=0A    [ flags for gc ]=0A    [ previous block ]=0A    [ next block ]=
=0A    [ padding for alignement]=0A=3D=3D=3D=3D>    [ USER HEAP BLOCK ]=0A=
=0AWith a 'header' in front of every block on the heap to retain RTTI=0Afor=
 the garbage collector, array repeat count, and flags etc,=0Aas well as the=
 prev and next links, overhead 48 bytes on 64 bit box.=0AFor list nodes of =
two words (16 bytes) that's a lot of overhead.=0A=0AFurthermore pointers we=
re like:=0A=0A    struct { void * heap_block; offset_t offset; }=0A=0Abecau=
se the garbage collector could only work with pointers to the=0Ablock, not =
with pointers INTO the block.=0A=0AJudy changed all that. The gc now has ZE=
RO header, i.e. there is =0Ano header at all. Instead a JudyL array maps po=
inters to RTTI=0Ashape data. A separate map for array count is kept for ent=
ries=0Awith lengths NOT equal to 1 -- so non-arrays don't have an entry=0Ai=
n the JudyL array (that's 99% of most objects).=0A=0AAnd using JudyL I can =
find the key equal to or just before any=0Apointer .. so the gc now works w=
ith interior pointers.=0A=0AThe ability of the gc is further enhanced, sinc=
e it can now=0Adetect 'foreign pointers' in O(1) [pointers not being manage=
d=0Aby the gc] =0A=0AFurthermore the user could malloc() some data, play ab=
out,=0Aand then *register* the object for gc management .. impossible=0Aif =
there had to be a header block on managed memory.=0A=0AAnd Felix pointers a=
re now plain C pointers. This actually=0Asimplified the programming languag=
e and standard library=0Aquite significantly (forgetting about the performa=
nce=0Aimprovement and simplification of the run time library ..)=0A=0ASo th=
e result is: roughly the same amount of memory is wasted=0Aon meta-data. Ju=
dy saves here and there on the constant block=0Aoverhead, but using separat=
e arrays means the keys use up=0Aspace several times. Functionality/capabil=
ity is vastly =0Aimproved without sacrificing performance, which is critica=
l=0Afor a garbage collector.=0A=0AFurthermore, it is possible to scan the R=
TTI of all the=0Aobjects in memory without scanning the actual memory.=0AWh=
en following pointers, it is only necessary to examine=0Aobjects that actua=
lly contain them .. so the gc can =0Afind all the reachable objects WITHOUT=
 actually paging=0Ain every object (only ones with pointers in them need=0A=
to be paged in). This should improve cache/VM locality=0Aa bit, though I ha=
ve done no measurements.=0A=0AI read somewhere that a standard Hashtable is=
 as fast=0Aas Judy.. so why bother. Well, I have given one answer.=0AHashta=
ble can't give a sorted list of keys. Judy Can.=0A=0AHashtbl can't find 'ne=
xt after' or 'next after or equal to'=0Aor 'Next empty' and Judy can.=0A=0A=
The typing and docs on the interface are not so good.. ouch.=0ABut the actu=
al *design* of the interface is close to perfect.=0A=0A=0A-- =0AJohn Skalle=
r <skaller at users dot sf dot net>=0AFelix, successor to C++: http://felix=
.sf.net=0A=0A--------------------------------------------------------------=
-----------=0AThis SF.net email is sponsored by: Microsoft=0ADefy all chall=
enges. Microsoft(R) Visual Studio 2005.=0Ahttp://clk.atdmt.com/MRT/go/vse01=
20000070mrt/direct/01/=0A_______________________________________________=0A=
Judy-devel mailing list=0AJ...@li...=0Ahttps://lists.=
sourceforge.net/lists/listinfo/judy-devel=0A=0A=0A=0A=0A