On 01/04/2012, at 1:39 PM, Doug Baskins wrote:
[]
FYI: Judy is used in the Felix Garbage collector
to keep track of every allocated object, its length,
and also a run time description .. all non-invasively.
It's also used to implement sparse arrays.
Coming soon .. a string -> T associative array .. aka "dictionary"
or "hash". Only hassle with that is the null terminator.
It may be interesting to consider the "cursor" used in the modified
implementation. If you consider a typical sequential scan you have
key = next_key(key) ...
which implies looking up the whole array to find the old key, before
finding the next one.
In a 64 bit implementation that can imply 8 lookups .. even when the
next key is in the same cache line as the previous one.
The other implementation achieved better performance than Judy
by retaining the last position, making a sequential scan much faster.
However that's wrong IMHO, a single inbuilt cursor in the public
interface is a bad design. However there are two alternatives:
just using it as a cache (hiding the details) is one, the other is to
provide a way to save the current position in a separate object.
Either way, sequential scans are common enough to think about it.
For example when Felix uses Judy as an application data structure
the garbage collector has to do a sequential scan of the values
as part of the usual "mark-sweep" processing (which itself also uses
Judy for temporary storage!!)
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
This SF email is sponsosred by:
Try Windows Azure free for 90 days Click Here
http://p.sf.net/sfu/sfd2d-msazure
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
