Alan Bawden <alan@csail.mit.edu> writes:

Paul Rubin <no.email@nospam.invalid> writes:

All CPython integers are boxed, but small ones (-5 through +250 or
something like that) are pre-allocated. Sounds awful but I think some
Lisps also have done that.

For example, PDP-10 MacLisp. The PDP-10 is a word addressed machine,
where addresses are 18 bits, and words are 36 bits. PDP-10 integers are
36 bits long, so pretty much your only choice for representing fixnums
is as an 18-bit pointer to a 36-bit signed integer, i.e. "boxed".

I had no idea! Never having used it, I had always assumed that MACLISP
shared the behavior of things like SBCL, Smalltalk, and recent versions
of Python???transparently overflowing from fixnums to bignums.

One advantage of the transparent-overflow approach is that most of the
time users don?t care what the actual fixnum limit is???it?s ?just? a performance optimization, in that your arithmetic starts consing when
you exceed the limit.

This does mean, however, that by default, for example on SBCL, all of
your arithmetic is stuffed full of overflow checks, which has
performance costs of its own.

? If an intermediate fixnum needs to be allocated, say to pass as an
argument to another function, it can be allocated in a special area
of memory that has fixnum type, but that is managed as a stack -- the
GC doesn't touch it. That temporary number is then popped out of
existence after the function call returns. This does mean that the
compiler has to constantly worry that an object that it is about to
store someplace permanent might be a stack allocated "PDL number".
The utility that replaces a potential PDL number with a permanent
number is named "PDLNMK", and every serious MacLisp programmer knows
exactly what it does because it frequently appears in our compiled
code.

This is an interesting idea; I imagine it?s a pretty big performance
win, particularly since MACLISP predates generational garbage collection
(and, I imagine, never had it bolted on). Consing *per se* is pretty
fast in a pointer-bumping allocator; what used to kill you was the GC,
and generational GC largely solved that problem. Still, I'm pretty sure
that Java, LuaJIT, Chez Scheme, V8, and SpiderMonkey don?t box their
fixnums.

There's a paper by Guy Steele titled "Fast Arithmetic in MacLisp" that describes all these techniques in detail: <hdl.handle.net/1721.1/6279>.

Thank you very much! I?d never read it. For the peanut gallery, that?s AIM-421.pdf, MD5 158106732f63bf268ffe4c1728950710.

Kragen

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Kragen Javier Sitaker <kragen@canonical.org> writes:

Alan Bawden <alan@csail.mit.edu> writes:

For example, PDP-10 MacLisp. The PDP-10 is a word addressed machine,
where addresses are 18 bits, and words are 36 bits. PDP-10 integers are
36 bits long, so pretty much your only choice for representing fixnums
is as an 18-bit pointer to a 36-bit signed integer, i.e. "boxed".

I had no idea! Never having used it, I had always assumed that MACLISP shared the behavior of things like SBCL, Smalltalk, and recent versions
of Python???transparently overflowing from fixnums to bignums.

One advantage of the transparent-overflow approach is that most of the
time users don?t care what the actual fixnum limit is???it?s ?just? a performance optimization, in that your arithmetic starts consing when
you exceed the limit.

Note that MacLisp _does_ have "transparent-overflow" arithmetic, you
just have to use `PLUS`, `TIMES` and `DIFFERENCE` instead of `+`, `*`
and `-`. The `+` family is fixnum-only, but the `PLUS` family handles
all types of numbers.

There is also a flonum-only family: `+$`, `*$`, `-$`, etc.

The names `PLUS`, `TIMES`, `DIFFERENCE`, etc. are taken from LISP 1.5,
so you can think of them as the "true" Lisp arithmetic functions. `+`,
`+$` and friends are just MacLisp extensions for efficient machine
arithmetic.

--
Alan Bawden

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)

Alan Bawden <alan@csail.mit.edu> writes:

Kragen Javier Sitaker <kragen@canonical.org> writes:

I had no idea! Never having used it, I had always assumed that MACLISP
shared the behavior of things like SBCL, Smalltalk, and recent versions
of Python???transparently overflowing from fixnums to bignums.

Note that MacLisp _does_ have "transparent-overflow" arithmetic, you
just have to use `PLUS`, `TIMES` and `DIFFERENCE` instead of `+`, `*`
and `-`. The `+` family is fixnum-only, but the `PLUS` family handles
all types of numbers.

I see! Thank you for explaining.

Kragen

--- PyGate Linux v1.5.19
* Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)