HP has developed some thing called a Judy array, which is "A state-of-the art core technology that replaces many traditional data structures and algorithms, such as arrays, sparse arrays, hash tables, B-trees, binary trees, linear lists, skip lists, sort and search algorithms, and counting functions".

Right now it's only available in library form (no source) for HP-UX and x86-based Linux. However, if it becomes more widespread (or better yet open source), and works like it's advertised, would this be of interest to the Perl community? Either as a module, or perhaps as part of core Perl itself?

Replies are listed 'Best First'.
Re: Judy arrays and Perl
by demerphq (Chancellor) on Jun 20, 2002 at 15:44 UTC
    Well, this is interesting and exciting, but until it is released in source code and undergoes some rigorous academic peer review I cant help but feel suspicious about HP's rather grandiose claims regarding the algorithm.

    But if it is indeed what it claims to be then I for one would be very interested in playing around with it.

    Thanks for the link.

    Yves / DeMerphq
    ---
    Writing a good benchmark isnt as easy as it might look.

[reply]
Re: Judy arrays and Perl
by gumby (Scribe) on Jun 20, 2002 at 14:59 UTC
    Of course. Anything that manages to eliminate several tertiary structures, as you've indicated, and does not bring performance penalties, would be welcomed by me.

    Update: I forgot to mention saving me valuable time and effort... any Perl implementation would be welcomed, but since i am already a data structures/algorithms obsessive I will probably end up implementing it anyway (to add to my existing pile of bizarre heap's and sorting methods)...

    Update(2): Ok, 'Judy' is basically a trie, since this has been dealt with wonderfully by demerphq, i won't go into details... also try 10 minute description

[reply]
      i am already a data structures/algorithms obsessive

      You too eh? My next target (ive got Trie's, Efficient Huffman Encoding, 2-3 trees, Pagoda Heaps under my belt so far) is a Treap. Any idea of a good place to look for documentation? Knuth only provided the most fleeting mention in AoP, and apparently they outperform splay trees and normal heap implementations (while being fully ordered) so I really want to release a CPAN implementation (especially as IMO the Heap:: heirarchy chews)

      BTW thanks for the nod. :-)

      Yves / DeMerphq
      ---
      Writing a good benchmark isnt as easy as it might look.

[reply]
        My own reference for implementing a Treap was section 2 of this paper.

        A google search for Randomized Search Trees provided only a handful of relevant links. The entry in NIST DADS was pathetic, but provided a link to an implementation in Scheme.

[reply]
Re: Judy arrays and Perl
by Anonymous Monk on Aug 09, 2002 at 17:23 UTC
    Judy Arrays were opened sourced with a LGPL license in June 2002. It is hosted on http://sourceforge.net/. There is a web page www.sourcejudy.com for info. Read the updated 10 minute doc on www.sourcejudy.com. Much of the information from HP is out of date. I will be happy to answer all reasonable questions. Doug <doug@sourcejudy.com>
[reply]
      Is there a perl implementation. Preferably both pure-perl and XS Perl?

      If there isnt then with a bit of elbow grease there soon will be...

      (Er, that is if someone else wants to do the XS version... ;-)

      UpdateWell apon the reading the documents I see that Judy isn't really a single algorithm, nor has it been explained as one. Its more an advanced data storage system, and that there isnt really any point of trying to implement it in perl as the whole idea of it is to micromanage memory in such a way to stay in the CPU cache as much as possible. Id bet that an SV struct doesnt even fully fit into a cache line at once....

      But it would be really exciting to see what potential it has as either a DB_FILE type module, or perhaps built into core perl for lower level stuff.

      Yves / DeMerphq
      ---
      Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)

[reply]

Back to Meditations