[r6rs-discuss] an essay on language design

From: William D Clinger <will>
Date: Wed, 11 Jul 2007 21:10:59 -0400

Kent Dybvig wrote:
> > If you don't like the restriction, then remove it.
>
> By piling yet another feature on?

If I were designing this thing, and were not constrained
to remain compatible with the features that have already
been piled on, I would remove the restriction by
eliminating the preferred constructor descriptors.

> > The procedural layer already provides accessors and mutators
> > that are analogous in complexity and efficiency to vector-ref
> > and vector-set! with offsets determined at closure creation
> > time. As Mike and I were discussing, the difference between
> > an offset determined at closure creation time and a constant
> > offset is at most one load instruction. There will seldom be
> > any difference at all, since implementations can special-case
> > small offsets.
>
> You ignore the additional cost involved in calling the record predicate to
> enforce safety, which is again at least one additional memory reference
> (and possibly more, depending on the representation of the hierarchy).
> This reference can't be special cased.

Not so. That check was included within the operations
I enumerated in my original essay. Its cost is about
the same as the range check required by vector-ref, so
it turns out that an unoptimized record access, as
implemented by the procedural layer, costs almost
exactly the same as an unoptimized vector reference.

This is not obvious. I wouldn't have understood it had
I not implemented a prototype of the procedural layer
in Larceny and then put some thought into improving the
representation of records. See <magic> below.

> You also ignore additional costs
> in complexity and/or efficiency in the allocation of records via the
> record constructor.

There you may have a point. A complicated constructor
descriptor, with multiple levels of inheritance and a
weird protocol at each level, might well be slow. The
syntactic layer may have some advantage here, but that
has not been demonstrated.

For simple record constructors, however, the code that
will be generated at compile time will be almost exactly
the same as for a call to vector:

    (let* ((x1 <value-for-field-x1>)
           (x2 <value-for-field-x2>)
           (x3 <value-for-field-x3>)
           (v (make-vector:trusted 4)))
      (vector-set!:trusted v 0 <magic>)
      (vector-set!:trusted v 1 x1)
      (vector-set!:trusted v 2 x2)
      (vector-set!:trusted v 3 x3)
      (vector-subtag-set!:trusted v <record-subtag>)
      v)

where <magic> is a data structure computed at
constructor-definition time.

(If you choose a poor representation for <magic>,
as you have been assuming, then safety checking will
be slow. With the representation we will be using
in Larceny, however, the safety check will be quite
fast, as claimed in my original essay: an indirect
load followed by an eq? check. That representation
is a minor tweak of the representation that Larceny
has been using for records since 1998.)

> Simple inlining can eliminate the closure creation and procedure calling
> costs you say overwhelm these indirects. Even some interpreters already
> perform such inlining and will not have to be extended to handle the
> syntactic layer well, when the parent-rtd clause isn't used.

Hey, I'm all for inlining.

As I have pointed out several times now, inlining is
just as easy with the procedural layer as with the
syntactic. You yourself raised the issue of
assignments to the variable whose value you wish to
inline, as though you hadn't realized that such
assignments are just as possible and pose just as
much a problem with the syntactic layer as with the
procedural.

That means assignment analysis is required regardless
of whether the parent-rtd clause is used.

> > True statements about the efficiency of the procedural layer
> > would have a reassuring effect.
>
> Agreed. The statements in R5.97RS do go overboard, but not as far as you
> would have us believe.

I have investigated this matter pretty thoroughly,
and your claim above concerning the cost of safety
checking shows that you do not yet understand just
how fast the procedural layer can and should be.

Will
Received on Wed Jul 11 2007 - 21:10:59 UTC