[r6rs-discuss] [Formal] Requirement to detect circular lists - benchmarks

From: William D Clinger <will>
Date: Mon Oct 2 17:51:02 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.

Kent Dybvig wrote:
> In Chez Scheme, with full optimization enabled (as one would do for
> built-in primitives), the difference is totally in the noise, with the
> circ version beating the regular version as often as not.

Furthermore, an implementor could use the trick of
using tortoise-and-hare only for lists whose length
exceeds some large threshold, e.g. the fixnum range.

In the interest of adding more noise, here are timings
in seconds, for the fastest of two runs that correspond
to Chez Scheme's (optimize-level 2), which is one less
than the "full optimization" Kent mentioned. The "R5RS"
column is for Andre van Tonder's length-regular, and
the "R6RS" column is for his length-circ.

                    10000 iterations 10 iterations
                    on 1000-element on 1000000-element
                    list list

                    R5RS R6RS R5RS R6RS

SunBlade 1500:
  Larceny v0.92b 0.095 0.212 0.258 0.449
  Chez v6.1 0.160 0.230 0.330 0.460
  MzScheme v352 4.683 6.773 5.160 7.369

2.8 GHz Linux:
  Larceny v0.92b 0.048 0.064 0.059 0.077
  MzScheme v352 0.066 0.079 0.100 0.124
  MIT Scheme 0.110 0.110 0.120 0.120
  Petite Chez 7.0a 0.916 2.746 0.863 2.883

It should be clear that the difference between the R5RS
and R6RS semantics is less than the differences between
popular implementations.

Will
Received on Mon Oct 02 2006 - 17:50:57 UTC