Ok, I just changed Felix gc to replace a doubly linked list with a JudyLArray and an auxiliary Judy1 array. The GC now scans for garbage using JudyLFirst/Next functions instead of tracing the doubly linked list. Test program timings:
Without Judy: 1 minute 8 seconds With Judy: 1 minute 28 seconds The test program makes a list of 10000 random integers. Then it maps it to a list where 1 is added to each integer, then calls the collector, repeated 1000 times. The tests were done on an AMD64, so that the Judy trie has an 8 way fanout (i.e. depth 8 tree). The real collector will be slower again: this version only allows pointers to allocated objects, the real one will allow pointers *into* an allocated object (i.e. so called interior pointers). This cannot be done with the doubly linked list, without scanning the WHOLE list looking for candidates, so the check would be O(N) per pointer. Even if the doubly linked list were sorted in address order, on average half the list would need to be searched, so still O(N). The cool thing is .. it works. In fact it worked first time :) Felix program below.. should be 'semi-readable' by C programmers .. :) ///////////////////////////////////// #import <flx.flxh> open List; println "GC test"; var x = Empty[int]; var i:int; forall i in 1 upto 10000 do r := Cstdlib::rand()%10; x = Cons(r,x); done; print$ str x; endl; forall i in 1 upto 1000 do x = map (fun (x:int)=>x+1) x; println$ q"Done $(i)x"; collect; done; print$ str x; endl; println "GC test done"; -- John Skaller <skaller at users dot sf dot net> Felix, successor to C++: http://felix.sf.net ------------------------------------------------------------------------- This SF.net email is sponsored by DB2 Express Download DB2 Express C - the FREE version of DB2 express and take control of your XML. No limits. Just data. Click to get it now. http://sourceforge.net/powerbar/db2/ _______________________________________________ Judy-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/judy-devel
