A Faster whatIs
Mon, 2 Dec 2002 11:36:17 -0000
> > Hello everyone: I made some changes to the Hugs sources which give
> > small runtime speed gains.
> I think you're the first person to look at optimizing Hugs in quite a
> while. Great stuff!
> I toyed with changing whatIs a few years ago. Instead of your
> table-based approach, I was thinking of using a bitwise encoding. My
> idea was to use one bit to select int/not int and that everything else
> would be interpreted as a triple of the form:
> Where, for example, the WhatisTag is 5 bits, the ModuleId is 10 bits
> and the Index is 16 bits (the numbers will probably need tweaked
> somewhat). So, each module would have its own set of tables for
> storing names, types, etc.
In the Hugs-alike compiler I was working on a few years ago (never got
around to finishing it) I used the following representation: a 'cell' is
either boxed or unboxed, according to bit zero (0 =3D=3D a heap =
and an unboxed word consists of 7 bits of "tag" (bits 1-8), and 24 bits
of data. Applications and list cells are just pairs (like Hugs), but
everything else has a "box" tag in the first word. The heap stored
variable-width objects unlike Hugs which only has pairs, but I don't
think that's relevant.
I think this is pretty similar to what you suggested above, Alastair.
The appropriate macros are:
#define IsRef(c) (((c) & 1) =3D=3D 0)
#define IsBox(c) (((c) & 1) && TagOf(c) >=3D BoxedThings)
#define IsApp(c) (IsRef(c) && !IsBox(Fst(c)))=20
#define MkValue(c) ((uint)(c) << 8)
#define ValueOf(c) ((uint)(c) >> 8)
#define TagOf(c) ((c) & 0xff)
#define whatIs(c) (IsRef(c) ? (IsBox(Fst(c)) ? Fst(c) : Ap) :
I remember testing various representations at the time, and this one
turned out to be pretty good.