[R6RS] Enumerations proposal pre-draft
William D Clinger
will at ccs.neu.edu
Sun Apr 23 13:55:49 EDT 2006
> > I don't see how the speed of run-time type checking would be
> > faster with specialized enumeration values than with symbols.
>
> Presumably, you have to go through the list of valid symbols to check
> that a given symbol is a member. With a separate type, you just have
> to check the tag.
It depends on what you mean by "run-time type checking".
Here are the four things I think you could mean:
enumeration type: run-time type checking is just as
fast with either proposal
enumeration set type: run-time type checking is just
as fast with either proposal
enumeration value: checking whether something is a
symbol will probably be a little faster than
checking whether something is a specialized
enumeration value, because the latter is likely
to involve two checks: (1) Is it a record?
(2) Is it the right kind of record?
checking whether some enumeration value belongs
to some enumeration type: this is essentially
the same as computing the index of an enumeration
type, which is discussed below; the short answer
is no, you do not have to go through the list of
valid symbols to check that a given symbol is a
member; you would use exactly the same machinery
compilers already use for case dispatch on symbols
(with specialized enumeration types, that machinery
would have to be duplicated in the implementation
of your proposed <name-constructor>, and would
probably not be duplicated as well)
> >> - The mapping to integers is much faster than with symbols. This
> >> could also be exploited to produce very fast code for a case
> >> distinction, via tables or binary search. (This may also be
> >> possible for symbols, but I don't see how.)
> >
> > Faster, yes, but not much faster.
>
> That depends on the size of the universe, no?
Not very much. With both proposals, the construction of an
enumeration set by enumerating its values takes time proportional
to the number of elements in the set. It is also influenced
by the size of the universe, but not by very much because
hash tables usually have O(1) amortized cost and binary
search is O(lg n), where n is the size of the universe.
I will measure this cost for universes of various sizes, and
will report the results in a future message.
> > The speed of set operations is the same with symbols as with
> > specialized enumeration values.
>
> Don't you lose a bit at least at construction time, through the
> overhead in converting to an integer?
The only place where there is any difference at all is in
the construction of an enumeration set by enumerating its
values, which we were talking about above. This usually
gets done only once, when the set computation is set up
(no pun intended) and usually accounts for an insignificant
fraction of the set computation.
Will
More information about the R6RS
mailing list