Re: optimizations Stalin does

[hjstein@bfr.co.il (Harvey J. Stein)]

Just ran across this on comp.lang.scheme:

------- Start of forwarded message -------
From: Jeffrey Mark Siskind <qobi@research.nj.nec.com>
Newsgroups: comp.lang.scheme
Subject: Re: 32-bit crunching in Scheme?
Date: 10 Dec 1998 00:50:17 -0500
Organization: NEC Research Institute, Princeton, NJ 08824
Message-ID: <yq790ggpmue.fsf@qobi.nj.nec.com>
References: <366CBEE5.552A755F@mail.webspan.net>
Reply-To: Qobi@research.nj.nec.com
To: Andy Gaynor <silver@mail.webspan.net>

> What implementation would be most suitable for doing
> a lot of bitwise crunching of 32-bit (or N-bit) integers?

When Stalin determines that an abstract location (i.e. a variable, a slot of an
abstract pair or structure, or an element of a abstract vector) or the value
of an expression can only be an exact integer, it uses the underlying C type
signed int to represent that abstract location. On most machines this will be
a 32 bit fixnum representation. In the development version of Stalin, one can
easily change the representation for an exact integer to be any C signed
integral type, i.e. signed char, short signed int, signed int, long signed
int, and even long long signed int on platforms that support long long signed
int.

Actually, Stalin will use the selected underlying C signed integral type to
represent exact integers in many cases even where an abstract location or
expression can take on both exact integer and other values. The only case
where the full range of the selected underlying C signed integral type will
not be available is when Stalin chooses a `squished' representation where one
or more lower order bits are used as type bits. Squished representations are
only used when the type set of the abstract location or expression contains
zero or more abstract values of unit cardinality (like #T, #F, (), the
EOF-OBJECT, and symbols that appear in the source program), a collection of k
abstract values that are represented as pointers, so long as all of the
pointers must be aligned to 2^ceiling(lg(k+1)) boundaries or better, along
with the abstract exact integer value. (This is only part of the story. Each
abstract degenerate vector, i.e. an abstract vector whose abstract element
location is fictitious, counts as a distinct abstract exact integer value so
the above number is really 2^ceiling(lg(k+n)) when there are n distinct
abstract exact integer values in a type set. The definition of when a location
is fictitious is too long to put in this email message.)

In any case, Stalin gives you an option of disabling squishing so that you can
be guaranteed of the full range of the selected underlying C signed integral
type.

I have done serious bitwise crunching in Stalin. I have implemented graphs
using bit matrices represented as vectors of vectors of exact integers. And I
have written bit matrix multiplication and transitive closure both in C and
Scheme. And the Scheme code for such bit crunching, with the development
version of Stalin, runs as fast or faster than the C code.

    Jeff (http://www.neci.nj.nec.com/homepages/qobi)
------- End of forwarded message -------


-- 
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il