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

From: William D Clinger <will>
Date: Wed Oct 4 11:35:17 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.

Aubrey Jaffer wrote:
> length-circ accesses data from two locations simultaneously, while the
> length-regular accesses only one. If there is no difference in speed,
> then the whole list must be living in the L2 cache. Performance in
> uncontrived list-intensive programs will not be identical.
>
> Also, simply consing long lists sequentially will make their cache
> footprints smaller than would consing during execution of a nontrivial
> program.

Just in case no one has noticed: For the first-order
procedures such as length, the overheads that are
being discussed should be incurred only in programs
that actually use mutable pairs. Sensible implementors
will write list? and length something like this:

(define (length x)
  (if (pairs-are-mutable?)
      (length-circ x)
      (length-regular x)))

That trick is one of the reasons set-car! and set-cdr!
are not part of the (r6rs) library. Programs should
not have to pay for mutable pairs unless they use them.

The higher-order procedures can't use the above trick,
however, because the draft R6RS says they must raise
an exception for things like

    (for-each (lambda (x) (do () (#f)))
              '(1 2 . 3))

It should be clear that the cost of raising an exception
for situations such as the above has absolutely nothing
to do with mutable pairs or with circular lists.

Will
Received on Wed Oct 04 2006 - 11:35:09 UTC