From: "Mauricio Fernández" Date: 2002-09-01T08:35:27+09:00 Subject: Re: ANN: RJudy-0.1 - Judy Arrays for Ruby On Sun, Sep 01, 2002 at 01:17:14AM +0900, Doug Baskins wrote: > Mauricio Fern�ndez wrote in message news:<20020828023514.GB19917@kodos>... > > diff -rwdu ruby/configure.in ruby-judy/configure.in > > --- ruby/configure.in Sun Aug 11 23:43:24 2002 > > +++ ruby-judy/configure.in Tue Aug 27 17:46:42 2002 > > @@ -281,6 +281,7 @@ > > AC_CHECK_LIB(crypt, crypt) > > AC_CHECK_LIB(dl, dlopen) # Dynamic linking for SunOS/Solaris and SYSV > > AC_CHECK_LIB(dld, shl_load) # Dynamic linking for HP-UX > > +AC_CHECK_LIB(Judy, JudyLIns) # Judy > > ....deleted > > Mauricio: > > I am the author of Judy. I just had a chance to look over this file. > Overall I am impressed. Actually this patch is derived from Lyle Johnson's original work on RJudy; you should direct your kudos to him :) I hacked it quite fast (around 6 hours from my downloading RJudy 0.1 to the first release of my patch), and at the beginning I was just trying to get Judy to work inside the internal hash of Ruby. > I just heard of Ruby for the first time a week or two ago. It also > looks like there has been discussion of how this performs VS. the > normal hashing routines in Ruby. This is good, I want know how the > performance compares. I am commited to making Judy the fastest and > most memory efficient method on the Planet. Cool! We're still pretty much amazed at Judy being faster than regular hashes :) > The first thing I noticed that could affect the performance of the > Judy version is the lack of use of the Judy Macros --JLG() JLN(), > JLI() etc. It is obvious you read the JudyHashing application > note, but missed one of the very important parts. The use of > JLG() and JLN()are very important for the best performance at > low populations of the Judy Array. [deleted] As I said before, the first version of the patch (the one I posted to this list) was a mere copy of RJudy's, modified to work as Ruby's internal hash. I inherited his lack of use of the Judy macros, for I knew I could change them later and I was mostly doing cut & paste anyway... However, once I caught some bugs which would make Ruby segfault from time to time, I started more serious modifications, which made it faster than RJudy. I also used macros in selected places (the main lookup function and a couple more). I experienced little change in the overall speed of Ruby and specifically of the operations on hashes, but it was slightly better. After reading your post, I replaced all the function calls by macros and... it's slower now :-( Must be some code cache issue... I do lack a serious benchmarking procedure, and I'm mostly running Lyle's example with minor corrections on different data sets, and Christoph's Ackerman and Fibonacci functions. I try to compare fairly the execution time, and consider the page faults involved too, as I suspect they are important :) > The use of JLG and JLN should improve the performance of the retrieve > to be very competitive with the hash method used here. Please let me > know how it goes. At the moment, with my not-so-reliable benchmarks, I've observed the following: * standard hash is faster at low populations; this is extremely important since that will affect method and attribute lookups * as size grows, insertion in the Judy-based hash is a little faster, but lookup remains slightly slower * everything's faster w/ HASHSIZE=1 than with HASHSIZE=256. Plus st_foreach is a serious speed hit when HASHSIZE grows, as it must iterate over all the Judy arrays... > I also have some other concerns, but I will talk > about that later. And while your at it, change all the JudyL* routines > to their macro counterparts. I have designed the macros to give all > the flexibility in handling errors I think you need. I don't care much about error handling (as long as I can benchmark it, it's fine by me for the moment). I do more about macros being slower than function calls, for all my code is useless if it can't run faster than the hashing currently used... > I am new to the open source community. I am about to change the phrase > "faster than the speed of light" to "faster than the speed of the internet". We're a massively parallel system now, a CPU with an enormous pipeline, each part working on its own timezone :-) It takes some time for the first result to come, but thereafter... -- _ _ | |__ __ _| |_ ___ _ __ ___ __ _ _ __ | '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ | |_) | (_| | |_\__ \ | | | | | (_| | | | | |_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_| Running Debian GNU/Linux Sid (unstable) batsman dot geo at yahoo dot com We come to bury DOS, not to praise it. -- Paul Vojta, vojta@math.berkeley.edu