[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: pass at srfi-89 implementation

From: Julian Graham
Subject: Re: pass at srfi-89 implementation
Date: Sat, 16 Aug 2008 17:19:56 -0400

(Sorry for the late reply -- I was out of the country last week...)

>> Okay, I've tried -- at length.  And so far I haven't been able to top
>> the performance of the reference implementation.  In fact, it actually
>> seems to be fairly efficient
> Did you run some sort of "benchmark"?

Yes.  Nothing formal, though -- I pretty much just defined a number of
different SRFI-89-style functions with different signatures (optional
arguments, keyword arguments, optional and keyword arguments) and used
`(gettimeofday)' to see how long it took to run them in a loop a few
hundred thousand times.  On average, my implementation still takes
about 70% longer than Marc's, which is pretty embarrassing, but I'm
still attempting to profile and optimize it (at the moment it looks
like most of the time is spent in an initial sorting pass).

(Has anyone else noticed that statprof hasn't been working for a while
now?  I get a "Numerical overflow" from `statprof-display' no matter
what arguments I pass to `statprof-reset'.)

> The reference implementation strives to create a perfect hash table,
> while Guile's built-in hash tables may not be perfect all the time
> (there can be collisions, although tables are automatically resized once
> in a while).  So, theoretically, the reference implementation's solution
> is more efficient.
> OTOH, as is often the case with Guile, it may turn out to be faster to
> use Guile's built-in hash tables, especially since they may end up being
> "perfect" (i.e., collision-free) in most cases here; in addition,
> running one `make-perfect-hash-table' for each `lambda*' at
> initialization time may turn out to be more costly than just
> `make-hash-table'.  Could you try that out?

Yeah, I'm already using Guile's hash tables and creating the table
with a big enough initial size to store all of the keywords specified
in the argument list -- and since Guile's hash tables are native, my
(naive) assumption is that they're probably as fast or faster than a
pure-Scheme perfect hashing system.  But I could try perfect hashing.

>> * Symbol generation for naming run-time helper functions (the
>> reference implementation explicitly exports bindings for helper
>> functions)
> Hmm, what are you referring to precisely?

Well, like Marc's version, my code requires a few named procedures at
runtime to handle things like argument processing (see `$process-args'
in the reference implementation) buts needs to avoid collisions
between these bindings and bindings in user code.  I'm assuming this
was Marc's intent in naming his helper procedures with $-signs and
binding them in the top-level environment -- i.e. that he made it
obvious which names users need to avoid.  But Guile's `gensym' allows
for the creation of local (to the lambda* expression) bindings that
are guaranteed not to shadow anything in the user's environment.

> Overall, it may indeed be wise to use the reference implementation.
> However, we'd need a copyright assignment from Marc and/or licensing
> under LGPLv2+.

Yeah.  My approach thus far has been to do this as a "clean room"
implementation based only on the SRFI-89 spec, and it goes without
saying that Marc understands this SRFI more intimately than I do.
Maybe let me hack on it a bit longer and report back, though?


reply via email to

[Prev in Thread] Current Thread [Next in Thread]