John:
Glad to hear of your successes with Judy.
I have often thought of how to do a faster Judy[1L]Next(). It has
always fallen below my priorities list -- partly because I believed
that modern processor caches would lessen the overhead of a
complete re-walking of the tree to almost the same place (thus same
cache-lines). However, I have recently discovered another problem with
modern processors that may be a mitigating factor. That is
"branch prediction" miss-match of the compiler with the processor.
So here is my best shot on how I would approach the problem:
Note: Key & Index words are used interchangeably and mean the same thing.
A walk of the Judy tree often terminates with an object called a Leaf.
ALeaf has 1..256 Key/Value items in sorted order for an average
length of around 20+ elements. If Judy[1L]NextX() returned the
whole Leaf (or partial if required), then that array of 20+ Keys/Values
could be scanned very quickly. It would be up to the caller to
determine how long this data would be valid (I.E. no Inserts or Deletes.)
The caller would have to supply the memory for storing the Keys/Values
along with how many were returned and the current Key. The caller would
also haveto remember what was the last Key accessed (cursor) out of the
memory todetermine the next Key. The distance from Key (Leaf population)
to the Value would also be required. There a few other minor details
I haven't mentioned.
Actually, it would be fairly easy to implement, but the API wouldbe ugly.
Let me know if this seems worthwhile. It seems it has the potential of being
much faster.
About the Null terminator problem with JudySL. I think a student in perhaps
Brazil has written a *Next() to JudyHS(). If I remember correctly, a simple
#define will change JudyHS() into a sorted (numeric?) order store of the tree
of trees.
If your interested, I can research it further.
Thanks for your interest,
doug
Doug Baskins <[email protected]>
>________________________________
> From: john skaller <[email protected]>
>To: Doug Baskins <[email protected]>
>Cc: "[email protected]" <[email protected]>; judy <[email protected]>;
>Phil Stanhope <[email protected]>
>Sent: Sunday, April 1, 2012 8:20 PM
>Subject: Re: I'd like to congratulate you and the team that worked on Judy
>Arrays
>
>
>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
>
>
>
------------------------------------------------------------------------------
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
