[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: compare function return values

This page is part of the web mail archives of SRFI 67 from before July 7th, 2015. The new archives for SRFI 67 contain all messages, not just those from before July 7th, 2015.



On Sat, Jun 04, 2005 at 11:07:15AM -0700, bear wrote:
> >> The "numbers can be used in index computations" also refer to the fact
> >> that one at the assembly level can dispatch to the proper branch by
> >> doing a simple table lookup based upon the return value of a compare
> >> function.
> >This can't possibly lead to any performance gain, because in the general
> >case, the compiler will have to bound-check the integer returned by the
> >compare function, which leads to two checks - the same number of
> >comparisons as caused by checking which symbol it is.
> This isn't true, I don't think.  Depending on the level at
> which this function is integrated into the scheme system,
> the compiler can *know* that it will return one of the
> three values - and know that therefore it doesn't need to
> range check the table lookup.

True, but this is also _exactly_ the case where the compiler can skip
using actual symbols.

> >(1) there are no good reasons for using integers as the return values.
> >(2) bad code should be discouraged. (eg. using compare values for
> >indexing, addition etc.)
> >(3) using symbols would lead to more descriptive user experience.
> >-> ergo, the return values of compare functions should be symbols.
> 
> Hmmm.  I see your point and it is a valid point, but I have a
> few nits to pick:
> 
> First, symbols, from an implementation POV, are a *lot* heavier
> than small integer numbers.  There are table lookups to do, and
> guarantees to make about symbols being eq? and hash functions to
> call and store the result of, etc.  Depending on the implementation,

I'm surprised to see so much misunderstanding about symbols in the
Scheme community... since symbols are _atomic_, their comparison by eq?
is a pointer comparison in all implementations I know of.  The only time
one needs to find a symbol by its string representation is when it is
being (read).  For builtin functions, all symbols are already in their
"pointer" form, that is, they're already references to the Unique Symbol
With That Name.

Symbols that are used by builtins are statically allocated.  In an
average implementation, this means an overhead of something like 8 bytes
in addition to the storage usage of the string representation of the
symbol.

The great thing about symbols is exactly that they show that symbolic
(descriptive) expressions _are_ as efficient to process as their
non-expressive counterparts (like numeric tags).

Now, I understand if people think that the long matured custom of
mathematics to use (-1, 0, 1) is better.  But I think the original
motivation for this codomain of signum was more likely the reluctance of
adding new data types to mathematics than any real benefit these numbers
convey.

> Second, small integers are useful in indexing arrays, and indexing
> arrays is a natural use of comparison results.  Indexing arrays with

(Just to make sure: did you understand that preventing explicit indexing
of arrays with comparison results was one of my original intentions in
the proposal of using symbols?)

> table suggested by comparison results.  It would almost certainly
> be a better implementation strategy to do three comparisons.

As is the case with numbers, too.

> Third, the limitation of array indexes to exact nonnegative integers
> only, and the requirement of starting at zero, is a problem that ought
> to be addressed first.  If arrays could be indexed by an arbitrary

Aiee!  Maybe.  But I never found Scheme the language to do "nifty
tricks" in, like indexing arrays with comparison results.  I think
Scheme should remain simple, clean, powerful (in terms of tools it
provides, not weird expressions it enables the programmer to use), and
elegant.

Panu

-- 
personal contact: atehwa@xxxxxx, +35841 5323835, +3589 85619369
work contact: pkalliok@xxxxxxxxxxxxxxxx, +35850 3678003
kotisivu (henkkoht):	http://www.iki.fi/atehwa/
homepage (technical):	http://sange.fi/~atehwa/