Re: truth of %nil

[Mark H Weaver]

Below is a proposal for how to make boolean tests and end-of-list
tests faster and more compact, by renumbering the representations for
SCM_ELISP_NIL, SCM_EOL, SCM_UNDEFINED, and SCM_EOF_VAL.

But first, I decided to quantify the increase in code size testing
against two constants instead of one, by compiling the following short
test program with gcc -Os on three architectures: x86-32, arm, and
sparc:

(specifically, I did "gcc -Os -S foo.c" and then "as -a foo.s")

        loop1(int *p)
        {
          while (*p != 0x004)
            p++;
        }
        
        loop2(int *p)
        {
          while ((*p & ~0x200) != 0x004)
            p++;
        }

The size of the resulting loop bodies, in bytes, are as follows:

        arch   loop1   loop2
        --------------------
        x86-32   8      13
        arm     12      16
        sparc   16      20
        --------------------

I guess this is not too bad.

The constants chosen above are based on the following proposal on how
best to make SCM_BOOL_F and SCM_ELISP_NIL differ by only one bit, and
the same for SCM_EOL and SCM_ELISP_NIL.

This can be accomplished by making:

SCM_ELISP_NIL equal to SCM_MAKIFLAG (2) i.e. 0x204, and
SCM_EOL       equal to SCM_MAKIFLAG (3) i.e. 0x304.

These values are currently used by SCM_UNDEFINED and SCM_EOF_VAL, but
I'm hoping it won't be too disruptive to renumber those, especially if
it's done before the release of 2.0.

Then, testing for boolean truth becomes:

        if ((x & ~0x200) != 0x004)

and testing for end-of-list becomes:

        if ((x & ~0x100) == 0x204)

These should of course be written differently, perhaps as follows:

        if ((x & ~(SCM_ELISP_NIL ^ SCM_BOOL_F)) != (SCM_ELISP_NIL & SCM_BOOL_F))

and for end-of-list:

        if ((x & ~(SCM_ELISP_NIL ^ SCM_EOL)) == (SCM_ELISP_NIL & SCM_EOL))

along with a regression test somewhere to complain unless both of the
XOR subexpressions above are powers of two:

        #define IS_POWER_OF_TWO(x)             ((x) & ((x)-1) == 0)
        #define DIFFER_BY_ONLY_ONE_BIT(x, y)   IS_POWER_OF_TWO((x)^(y))
        
        if ( ! DIFFER_BY_ONLY_ONE_BIT(SCM_ELISP_NIL, SCM_BOOL_F) )
          complain();
        if ( ! DIFFER_BY_ONLY_ONE_BIT(SCM_ELISP_NIL, SCM_EOL) )
          complain();

What do you think?

    Mark