On 19/02/2014, at 5:11 PM, john skaller wrote:
>
> As for killer apps .. that's the wrong idea. There are numerous
> places in most code where Judy is the ONLY data structure
> that can be used:
>
> A) Where the key is an integer or pointer
> B) Where you need O(1) fast random AND sequential access
Here's my use of it. In my Garbage Collector, I keep this map:
pointer -> RTTI (includes size of one object)
pointer -> count (if count != 1)
So given ANY pointer I want to know: is it a Felix pointer (managed
by the GC) or a C pointer Felix doesn't know about?
So here's what I do. First try to find a pointer less than or equal
to the given pointer. If there isn't one its a foreign pointer.
if the pointer is equal to the candidate, its a native pointer
and points to the object base.
Otherwise get the element size from the RTTI. Then get the count
of elements from the second Judy Array. Multiple and add to
the base pointer returned from the first array.
Now check if our candidate pointer is less than the result.
If it is, its a pointer INTO the object, otherwise it's a foreign pointer.
[Felix doesn't allow pointers "one past the end", otherwise you could
use less then or equal instead of just less than]
The most vital pointer here is that Felix uses malloc() for allocation.
The only way to do the above operation without Judy with similar
performance requires implementing your own suballocator.
The collector itself clearly scans all the pointers from the root,
using the RTTI to tell it where pointers are. It does the above
test on every pointer so it can trace a pointed at object.
Then all the unreachable objects destroyed and put into a temporary Judy Array.
Then the storage is reaped. This has to be done separately because unreachable
objects can reach each other in their destructors. Note destructors can also
allocate new objects! (Just because an object is unreachable doesn't
mean it cant itself reach reachable objects ..:)
This is a fairly naive algorithm but the key thing is it is totally un-invasive.
The RTTI pointer is not stored in the object. The algorithm is not fast.
It wouldn't be tenable at all without Judy.
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
Managing the Performance of Cloud-Based Applications
Take advantage of what the Cloud has to offer - Avoid Common Pitfalls.
Read the Whitepaper.
http://pubads.g.doubleclick.net/gampad/clk?id=121054471&iu=/4140/ostg.clktrk
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
