[racket-dev] Optional equality predicate for assoc and member

10 hours ago, Matthew Flatt wrote:
> I've pushed the change that makes `assoc', `assv', and `assq'
> implemented in Racket, including the new optional argument for
> `assoc'.

Thanks!  That, and the other improvement, sounds really good.  (I'm
excited enough about this that I'm running the third master build
today -- very unusual during a release...)

Also, what about `member'?


> > > The cost for a non-JIT platform is why I hadn't changed `assq',
> > > `assv', and `assoc' before. But a plain-Racket implementation is
> > > surely better in the long run, and we can keep the C code and
> > > bind functions conditionally when the JIT is disabled. Maybe we
> > > can eventually close the gap between the JIT-generated code and
> > > C. Also, I think the JIT could be smarter about `equal?', which
> > > could tilt the balance in favor of the JIT for `assoc'.
> > 
> > (Maybe it'll be feasible to dump jit-generated machine code at
> > some point...?)
> 
> Just so you can see the generated code? I think Sam's tool is on the
> right track. Otherwise, I'm not sure what you're suggesting.

(No -- this was a very bogus, sleep-deprived-induced, suggestion.  I
was talking about the non-JIT hit, and thinking that maybe it's easy
to dump the jitted code to a file which can then be used by the
non-jitted version, but that's obviously helping only platforms on
which non-jit is a user choice rather than a limitation...)


> > > I'm happy that the compiler is doing its job, but inlining
> > > optimizations are fragile, so I'm a little reluctant to rely on
> > > them.  Sad but true: the macro approach feels more comfortable
> > > for now.
> > 
> > If by "macro approach" you refer to what I was talking about, then
> > isn't that needed to have versions with inlined comparators?
> 
> Every time I look into changing `map' or other functions into
> macros, I conclude that it would be better to implement cross-module
> inlining.

Oh -- there were two "macro things" that I was talking about: one was
the dispatch on the equality type, and the other was having multiple
implementations with inlined comparators via a (local) template macro.
The first is obviously better done via inlining, and I see that you
did the second, as expected.  (That second use is what I referred to
as RTCG-like.)


> Currently, the Racket implementation of `assq', etc., is used
> always.  I've thought about ways to fall back to the C
> implementation when the JIT is unavailable, but I haven't settled on
> anything yet.

Here's another idea: in a world of immutable lists there are *much*
less circular lists.  (Even more: the fact that they're generated via
a temporary structure that is then copied means that they're usually
very short too.)  Maybe it's fine to take it to the next level and
just have all the standard functions ignore cycles?  Possibly with
alternative names (or a new module) for versions that do account for
cycles -- therefore putting the burden on the rare uses of circular
lists?

Alternatively, maybe do that as "unsafe" variants?  (But that seems
less useful since it won't be used as much.)

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!