On Mon, Dec 20, 2010 at 6:28 PM, john skaller
<[email protected]> wrote:
>> Ah, I was curious if anyone else was using Judy this way. I have been
>> using Judy arrays to store all the GC meta info for my jhc compiler
>> and it works really well. Although I no longer depend on it in the
>> default case,
>
> Oh? So how do you access the information?
>
> I suppose Haskell has different requirements. In Felix I have to cope with
> C pointers as well and also pointers INTO objects, and want to mix them all up
> as best as possible.
>
> Judy is just great since I can search for a pointer less than or equal to p,
> then use the result q to get a length n, and ask if q <= p < q+n and if
> so I have a pointer to q I allocated, otherwise it's a pointer I didn't
> allocate,
> or, maybe even an integer or something else from some C library.
I was basically using it to implement a standard tri-color GC except
instead of attaching the bits to the heap objects, I used Judy sets to
represent the color sets. It had a numer of advantages, the sweep
phase was as simple as discarding the array and the cache benefits of
not having to bounce all over the heap were substantial. I could add
something to the grey set and pre-fetch it then go on and by the time
I went to follow its pointers it would be prefetched in, having to go
to the heap location to set the grey bit would introduce a cache line
stall. Judy helped me quickly experiment with different
traversal/pre-fetching strategies. For the common case of allocations
that have no internal pointers (known statically due to typing) I need
never follow the pointer at all, just mark it black in my judy set and
skip the grey list.
Using judy to add debugging information was straightforward too, just
have a judy map of memory location to whatever debugging info I wanted
to collect at the allocation point (line number of code for instance,
or the last lazy evaluation update to said location).
I didn't want to make programs compiled with jhc depend on the judy
library and could actually implement something better than straight
judy due to having type information to take advantage of, but I was
able to implement a fully formed and tested GC system due to my
experimentation with judy which was quite useful.
John
------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
