[r6rs-discuss] [Formal] Equivalence predicate version of memp

From: William D Clinger <will>
Date: Tue Sep 26 21:06:44 2006

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.

Andre van Tonder wrote:
> Memp is unwieldy and potentially inefficient in the very common
> case where one tests for membership is based on an equivalence predicate....
>
> (member x l =) ==> (memp (lambda (y) (= x y)) l)
>
> This gets unwieldy to write, is hard to read, and is
> inefficient in the absence of smart optimizations.

With regard to difficulty of optimization:

With the R6RS library semantics, compilers will be
allowed to generate inline code for all procedures
that are defined within the standard libraries. It
is easy to inline things like memp, just as several
compilers have been inlining things like memq, map,
and for-each for a long time now, when permitted by
various implementation-specific declarations.

Once memp is inlined, the closure for the predicate
and the call to that closure are likely to be eliminated
by another bit of inlining.

I checked this by writing a little benchmark that
defined memp or a SRFI-1-style member locally, so
it could be inlined even under R5RS semantics, and
called the benchmark a million times on a list of
length 1, or 10000 times on a list of length 1000
that didn't contain the value being sought. These
numbers show the timings in seconds:

                   memp:1e6:1 member:1e6:1 memp:1e4:1000 member:1e4:1000
SunBlade 1500:
  Larceny 0.92b .18 .13 .55 .58
  Chez 6.1 .14 .13 .55 .61
  MzScheme 352 1.8 1.4 6.7 5.7

2.8 GHz Pentium:
  Larceny 0.92b .05 .09 .15 .53
  MIT Scheme 7.7.90.+ .07 .22 .10 1.25
  MzScheme 352 .25 .04 .37 .32

Judging by those numbers, I don't think efficiency
is a major issue here.

Will
Received on Tue Sep 26 2006 - 21:06:40 UTC