Ruby and Judy

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I was also thinking… what if ruby internal hash and array used Judy?
I wonder how much faster it would be? I’ve CC:d the author of Judy on
this note, he may have some insight.

thanks,
-joe

Quoting from the site:

···

On Sat, Aug 24, 2002 at 07:50:22AM +0900, Joseph McDonald wrote:

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

			******

Judy arrays are both speed- and memory-efficient, with no tuning or
configuration required, across a wide range of index set types
(sequential, periodic, clustered, random). Judy’s speed and memory usage
are typically better than other data storage models such as skiplists,
binary trees, b-trees, or even hashing, and improves with very large
data sets.
******

It looks impressive. Faster than hashing (wow)!
However it seems Judy only maps indexes or strings to 32 or 64-bit wide
words. Thus we’d have to add another layer to handle arbitrarily sized
structs via pointers. I hope this wouldn’t kill Judy’s speed.

If Judy were faster than most hashes as it claims (which I’m rather
inclined to believe after taking a look at its site), it might be faster
than the st_* hashing in Ruby! Now changing st.* would bring Judy’s
speed to method and value lookup, hashes, etc.

Why make a SWIG interface? If we change the st_* functions the
modification is transparent to the rest of the code…

Is something bound to happen between Judy and Ruby? }:->


_ _

__ __ | | ___ _ __ ___ __ _ _ __
’_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |
__ \ | | | | | (| | | | |
.__/ _,
|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Actually, typing random strings in the Finder does the equivalent of
filename completion.
– Discussion on file completion vs. the Mac Finder

In article 40331876042.20020823155011@vpop.net,

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

Does look pretty cool…

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I believe it’s been Swig’ed for Python, so it shouldn’t be too hard to
swig it for Ruby.

Phil

···

Joseph McDonald joe@vpop.net wrote:

Joseph McDonald wrote:

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I’ve actually been working on this already and should be able to post
something Sunday or Monday (just working through the test cases). “Watch
this space for further news ;”

Joseph McDonald wrote:

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I’ve actually been working on this already and should be able to post
something Sunday or Monday (just working through the test cases). “Watch
this space for further news ;”

Joseph McDonald wrote:

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html

I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I’ve actually been working on this already and should be able to post
something Sunday or Monday (just working through the test cases). “Watch
this space for further news ;”

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/

Group: I should of called JudySL something else.

Judy1 and JudyL is ONE technology (word [32/64 bits] keys) and JudySL
(null terminated string keys - NTSK) is ANOTHER. I get confused about
which people are talking about in these discussions.

Lately, JudySL seems to be the popular one people are interested in.
Perhaps, I should spend some time tuning it. I admit that its
performance could be improved for short strings (an ascii word v.s a
sentence).

About 99% of my design effort was spent on Judy1/L. Hashing was about
the only known technology that performed well in this problem space.
However, hashing has scalability problems, is machine dependent (hash
algorithms), does not sort, and has numerous pitfalls that everybody
seems to fall into sooner or later (when the data changes). I designed
Judy1/L to be as near a complete solution as I could think of.

JudySL is an APPLICATION that uses JudyL. It demonstrates how
scalability can be used to "think outside the box" -- to overuse an old
cliche. At least that's how the experiment started. When we tested the
performance of JudySL, it measured very memory efficient and only
hashing was able to beat its speed -- sometimes. JudySL does not have
scalability problems and seems to sort at a remarkable speeds (USA
telephone book in a minute or two).

Actually, I considered the state of the art for storing and retrieving
NTSK fairly mature and it should be, considering how easy it is to do.
JudySL was just an accident -- nobody would begin a design with that
approach. <See www.sourcejudy.com/application/judysl.pdf>

I wrote a program (actually borrowed) to compare JudySL with its
competition, called SLcompare.c. See <www.sourcejudy.com/benchmarks/>.

Please welcome/challenge/invite anybody to to add a faster/cheaper
method than the 4 included in this program. (Also I will be updating
it to output more detailed data soon -- to begin investigating JudySL
with short strings and/or at small populations).

Doug Baskins <doug@sourcejudy.com>

It looks impressive. Faster than hashing (wow)!
However it seems Judy only maps indexes or strings to 32 or 64-bit wide
words. Thus we'd have to add another layer to handle arbitrarily sized
structs via pointers. I hope this wouldn't kill Judy's speed.

Right, the keys map to pointers, I think this is an intended use.

thanks,
-joe

Why make a SWIG interface? If we change the st_* functions the
modification is transparent to the rest of the code...

Let's see what Matz says. But at first glance, it looks like it's
worth a try (the person that doesn't have to do the trying says...)
:slight_smile:

thanks,
-joe

Seems very interesting.

I’d think it almost as sensible to consider throwing it in at a
"lower" level than SWIG.

The thing that concerns me is that there are some sections of the
document where the authors document the design where they leave out
some bits that seem to refer to possible patenting of pieces of the
techniques.

It would be fairly distressing to (for instance) make Ruby associative
arrays into Judy arrays, only to discover that this makes any
resultant code dependent on the good graces of HP’s lawyers…

···

The world rejoiced as Lyle Johnson lyle@users.sourceforge.net wrote:

Joseph McDonald wrote:

Judy looks cool: http://www.sourcejudy.com/ docs at:
http://www.sourcejudy.com/application/
I think it would be great to have a ruby interface to Judy. Someone
has done a SWIG interface to Judy, pointer here:
http://www.nclug.org/pipermail/nclug/2002-August/004079.html
I’ve never used SWIG before, Lyle could probably whip it into shape
faster than I could read the SWIG docs :slight_smile:

I’ve actually been working on this already and should be able to post
something Sunday or Monday (just working through the test
cases). “Watch this space for further news ;”


(reverse (concatenate 'string “gro.gultn@” “enworbbc”))
http://cbbrowne.com/info/
“Of course 5 years from now that will be different, but 5 years from
now everyone will be running free GNU on their 200 MIPS, 64M
SPARCstation-5.” – Andrew Tanenbaum, 1992.

Today I presented a talk called “An Invitation to Ruby” at a local
computer fest show. If anyone is interested, the notes are online at

http://w3.one.net/~jweirich/development/talks/invitationtoruby/cover.html

If anyone is in the Dayton Ohio region tommorrow (Sunday, Aug25), I do
a repeat performance at 1:00 pm.

The talk was lightly attended, but the most interesting part of the
afternoon was that I met a fellow named Bob Ruby and spent an hour
with him getting him started doing web stuff with Ruby. He thought it
was pretty cool to use a programming language with his name on it.

···


– Jim Weirich jweirich@one.net http://w3.one.net/~jweirich

“Beware of bugs in the above code; I have only proved it correct,
not tried it.” – Donald Knuth (in a memo to Peter van Emde Boas)

“Douglas Baskins” wrote in

Please welcome/challenge/invite anybody to to add a faster/cheaper
method than the 4 included in this program. (Also I will be updating
it to output more detailed data soon – to begin investigating JudySL
with short strings and/or at small populations).

Hi,

I was trying to compile judy with vc7 - so far no luck;-( yet)
… so what is the official status of a port to mswin32, mingw32
and the many non-linux'',non-hp’’ unixes?

/Christoph

Here are some off-topic thougths about the missing byteswap assembly
macro for the mswin32 platform - either wrap the assembly bswap
instruction in a function

unsigned __int32 bswap32(unsigned __int32 word)
{
__asm
{
mov eax, word
bswap eax
}
}

or use a straight assembly macro

#define SET_BSWAP32(x,y)
__asm
{
__asm mov eax, ((y))
__asm bswap eax
__asm mov ((x)) , eax
}

and use the SET_BSWAP32 instead of judy’s __BSWAP32 macro
(essentielly there are only two places).

Today I presented a talk called “An Invitation to Ruby” at a local
computer fest show. If anyone is interested, the notes are online at

http://w3.one.net/~jweirich/development/talks/invitationtoruby/cover.html

That’s great, Jim. I’m intrigued by some of your examples.
I’ll bet that (for us) you could do a whole talk on the
uses of blocks and closures…

The talk was lightly attended, but the most interesting part of the
afternoon was that I met a fellow named Bob Ruby and spent an hour
with him getting him started doing web stuff with Ruby. He thought it
was pretty cool to use a programming language with his name on it.

There’s a programming language called Bob?? :slight_smile:

Cheers,
Hal

···

----- Original Message -----
From: “Jim Weirich” jweirich@one.net
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: Saturday, August 24, 2002 11:32 PM
Subject: Yet another Ruby Talk

Christopher Browne wrote:

I’d think it almost as sensible to consider throwing it in at a
"lower" level than SWIG.

Yes, this was brought up on another branch of this thread :wink:

To be clear, the extent of what I’m currently working on will just
expose three new classes (Judy1, JudyL and JudySL) to Ruby; it’s not an
attempt to replace Ruby’s current hashing code with Judy arrays. But I
agree that it would be interesting to see if this offers any benefits.

The thing that concerns me is that there are some sections of the
document where the authors document the design where they leave out
some bits that seem to refer to possible patenting of pieces of the
techniques.

It would be fairly distressing to (for instance) make Ruby associative
arrays into Judy arrays, only to discover that this makes any
resultant code dependent on the good graces of HP’s lawyers…

Since the code is now released under the LGPL this shouldn’t be a
problem (assuming that it’s compatible with Ruby’s license).

Very, very, enjoyable reading ! Excellent examples …
Keep it up Jim.

– Shanko

“Jim Weirich” jweirich@one.net wrote in message
news:87elcnmubg.fsf_-_@traken.access.one.net

Today I presented a talk called “An Invitation to Ruby” at a local
computer fest show. If anyone is interested, the notes are online at

http://w3.one.net/~jweirich/development/talks/invitationtoruby/cover.html

···

If anyone is in the Dayton Ohio region tommorrow (Sunday, Aug25), I do
a repeat performance at 1:00 pm.

The talk was lightly attended, but the most interesting part of the
afternoon was that I met a fellow named Bob Ruby and spent an hour
with him getting him started doing web stuff with Ruby. He thought it
was pretty cool to use a programming language with his name on it.


– Jim Weirich jweirich@one.net http://w3.one.net/~jweirich

“Beware of bugs in the above code; I have only proved it correct,
not tried it.” – Donald Knuth (in a memo to Peter van Emde Boas)

I liked the talk.

I recommend that you add a link in the RAA.

It is exactly that kind of jewel that gets people
to look in more depth at Ruby.

Thx,
Armin

···

Armin Roehrl, http://www.approximity.com
Training, Development and Mentoring
OOP, XP, Java, Ruby, Smalltalk, Datamining, Parallel computing, Webservices

Rubybuch: http://approximity.com/rubybuch/

Agile Entwicklerkonferenz: 22. und 23.10 in Nürnberg.
http://www.approximity.com/public/conferences/AgileConf.html

Today I presented a talk called “An Invitation to Ruby” at a
local computer fest show. If anyone is interested, the notes
are online at

> http://w3.one.net/~jweirich/development/talks/invitationtoruby/cover.html

Several people have asked for a downloadable copy of the presentation.
You can find it wrapped up as a giant tar/gzip ball from:

ftp://ftp.one.net/pub/users/jweirich/talks/invitationtoruby.tgz

Let me know if you have problems with the download version.

···


– Jim Weirich jweirich@one.net http://w3.one.net/~jweirich

“Beware of bugs in the above code; I have only proved it correct,
not tried it.” – Donald Knuth (in a memo to Peter van Emde Boas)

Christopher Browne wrote:

I’d think it almost as sensible to consider throwing it in at a
"lower" level than SWIG.

Yes, this was brought up on another branch of this thread :wink:

To be clear, the extent of what I’m currently working on will just
expose three new classes (Judy1, JudyL and JudySL) to Ruby; it’s not an
attempt to replace Ruby’s current hashing code with Judy arrays. But I
agree that it would be interesting to see if this offers any benefits.

This (Judy in general) is a very interesting concept to
me, partly because I find it hard to imagine this kind
of thing coded with the kind of efficiency we seem to
talking about, and yet presumably in a platform-independent
manner.

I’m not knocking it, I’m just surprised that Judy exists.

Does anyone else think this is unintuitive?

Hal

···

----- Original Message -----
From: “Lyle Johnson” lyle@users.sourceforge.net
Newsgroups: comp.lang.ruby
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: Sunday, August 25, 2002 12:21 AM
Subject: Re: Ruby and Judy

Hal E. Fulton wrote:

From: “Jim Weirich” jweirich@one.net

The talk was lightly attended, but the most interesting part of the
afternoon was that I met a fellow named Bob Ruby and spent an hour
with him getting him started doing web stuff with Ruby. He thought it
was pretty cool to use a programming language with his name on it.

There’s a programming language called Bob?? :slight_smile:

Yep.

http://macinsearch.com/infomac/dev/bob-15.html

···

----- Original Message -----

I agree. But I would make this, or something very like it, the home page of
ruby-lang.org, with links to everything else.

···

On Sunday 25 August 2002 04:52 am, Armin Roehrl wrote:

I liked the talk.

I recommend that you add a link in the RAA.

It is exactly that kind of jewel that gets people
to look in more depth at Ruby.

Jim Weirich wrote:

Several people have asked for a downloadable copy of the presentation.
You can find it wrapped up as a giant tar/gzip ball from:

ftp://ftp.one.net/pub/users/jweirich/talks/invitationtoruby.tgz

Let me know if you have problems with the download version.

Thanks for providing this. As a pay-per-minute-internet-user I really
appreciate it.

Stephan