Subject: bug#41354: equal? has no sensible code path for symbols

From: David Kastrup <[email-masked]>
Date: Thu, 28 May 2020 18:50:20 +0200

Ludovic Courtès <[email-masked]> writes:

> David Kastrup <[email-masked]> skribis:
>
>> Ludovic Courtès <[email-masked]> writes:
>>
>>> Hi David,
>>>
>>> David Kastrup <[email-masked]> skribis:
>>
>> Symbols comparing as _unequal_ have no special path in equal?.
>
> I was going to say that this is necessary for uninterned symbols, but it
> turns out that uninterned symbols that look the same are not ‘equal?’:
>
> scheme@(guile-user)> (define a (make-symbol "x"))
> scheme@(guile-user)> (define b (make-symbol "x"))
> scheme@(guile-user)> (eq? a b)
> $10 = #f
> scheme@(guile-user)> (equal? a b)
> $11 = #f

And it would be pretty horrible if they were, in my book.

> Thus we could go with the patch below, though I doubt it would make a
> measurable difference (and it actually adds tests for other cases).

It made a considerable measurable difference in LilyPond where it slowed
down the operation of assoc when used for symbol lookup (while assoc has
a short-circuit path to assq for SCM_IMP (key) that happens to have the
same problem of not being effective for symbols).  It took some
debugging to figure out why so much time was spent in equal? .

> Thoughts?
>
> Besides, in the common case where one is comparing against a symbol
> literal, the question is moot:
>
> scheme@(guile-user)> ,optimize (equal? 'x s)
> $14 = (eq? 'x s)

That is really quite irrelevant since the problem becomes visible when a
large number of comparisons in a row is done and if you were only
looking for a single constant key among a large set, you'd hardly have a
single constant key your code path would be looking for among that large
set.

> Ludo’.
>
> diff --git a/libguile/eq.c b/libguile/eq.c
> index 627d6f09b..16c5bfb3f 100644
> --- a/libguile/eq.c
> +++ b/libguile/eq.c
> @@ -303,6 +303,8 @@ scm_equal_p (SCM x, SCM y)
>      return SCM_BOOL_F;
>    if (SCM_IMP (y))
>      return SCM_BOOL_F;
> +  if (scm_is_symbol (x) || scm_is_symbol (y))
> +    return SCM_BOOL_F;
>    if (scm_is_pair (x) && scm_is_pair (y))
>      {
>        if (scm_is_false (scm_equal_p (SCM_CAR (x), SCM_CAR (y))))
>

Yes, that looks reasonable.  scm_is_symbol checks some tag subset that
the code for equal_p later looks at closer as well: if you worry about
the extra cost of the scm_is_symbol check, one could try folding the
symbol check into that later code passage, which would slow down the
symbol check and effect the more costly fallbacks less.  But since those
fallbacks _are_ more costly, I doubt it would be worth the trouble.

-- 
David Kastrup