From: Aaron Sloman
Subject: Re: GC and time critical code? (use of numbers)
Date:
Message-ID: <452@cvaxa.sussex.ac.uk>
In response to article <·····@bbn.COM> ······@bbn.com
Jeff Dalton (····@aiva.ed.ac.uk) writes:
>From: ····@aiva.ed.ac.uk (Jeff Dalton)
>Message-ID: <···@aiva.ed.ac.uk>
>Organization: Dept. of AI, Univ. of Edinburgh, UK
>Unfortunately, your program will be using numbers to represent
>reaction times, and creating a number tends to allocate storage in
>most Lisps even though you haven't done an explicit MAKE-NUMBER.
-----------------
Just for the record. In POPLOG Common Lisp (and also in the other Poplog
languages, namely POP-11, Prolog and ML) storage is NOT allocated for
integers or single-precision floating point numbers that can fit into 30
bits of store.
POPLOG divides data objects into two types: simple and compound.
Compound items are represented by pointers to structures in the heap,
whereas simple items (integers and single-precision decimals) are
represented by themselves.
Unlike some Lisp systems Poplog uses only two bits of a 32 bit
machine word to indicate what sort of object it is, i.e. pointer,
integer, or decimal. Hence 30 bits are available for integers
and decimals and arithmetic operations using them generate no
garbage collections. If very large integers (bignums), high
precision floating point numbers, ratios, or complex numbers
are used, then store is allocated, and some time will normally
have to be spent on garbage collection.
To be fair, Jeff did write
>Some types/sizes of numbers may be represented directly (as part of a
>pointer) rather than by an allocated object. If these are suitable
>for reaction times, you win.
but he made it sound as if most Lisp systems would not be able to cope.
I presume that if Poplog can cope with quite a wide range of integers
and floats, other lisp systems on 32 bit machines can too? After all
reaction times are not going to be measured to a very high precision.
Aaron Sloman,
School of Cognitive Sciences, Univ of Sussex, Brighton, BN1 9QN, England
ARPANET : ·························@nss.cs.ucl.ac.uk
JANET ······@cvaxa.sussex.ac.uk
BITNET: ·························@uk.ac
As a last resort (it costs us more...)
UUCP: ...mcvax!ukc!cvaxa!aarons
or ······@cvaxa.uucp
From: Richard Tobin
Subject: Re: GC and time critical code? (use of numbers)
Date:
Message-ID: <354@aiva.ed.ac.uk>
In article <···@cvaxa.sussex.ac.uk>
······@cvaxa.sussex.ac.uk (Aaron Sloman) writes:
>Jeff Dalton (····@aiva.ed.ac.uk) writes:
>>Unfortunately, your program will be using numbers to represent
>>reaction times, and creating a number tends to allocate storage in
>>most Lisps even though you haven't done an explicit MAKE-NUMBER.
>
>Just for the record. In POPLOG Common Lisp (and also in the other Poplog
>languages, namely POP-11, Prolog and ML) storage is NOT allocated for
>integers or single-precision floating point numbers that can fit into 30
>bits of store.
It is recommended (CLtL page 19) that the type short-float provide
such non-heap floats, so programs concerned to avoid garbage collection
should use this type for floats where possible.
POPLOG appears to provide two floating point formats: single (which
also serves as short) and double (which also serves as long). Since
the precision of singles is only 22 bits, which is less than that
recommended (24 bits - see page 17), perhaps it would be more
appropriate to adopt the alternative divison, and have the types short
and single, with single serving as double and long.
On the other hand, "more appropriate" (the term used in CLtL) isn't
very precise, so I don't think one could say POPLOG is wrong here.
-- Richard
--
Richard Tobin, JANET: ·······@uk.ac.ed
AI Applications Institute, ARPA: ················@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin
From: Darrel VanBuer
Subject: Re: GC and time critical code? (use of numbers)
Date:
Message-ID: <5243@sdcrdcf.UUCP>
The range of numbers varies quite widely between different Lisp
implementations. There are three catagories in many Lisps:
SMALLP -- stored in a reserved range of (fake) pointers, these only cost a
few cycles to add/subtract/shift to/from naked number
FIXP -- a full machine word with a pointer to it. 32 to 36 bits on most.
BIGNUM -- usually open ended, often implemented with arrays or lists
Implementation SMALLP FIXP BIGNUM
============== ====== ==== ======
Interlisp 10 -1536..1535 36 bits no
Interlisp VAX -2^30..2^30-1 no no
Interlisp D -65535..65535 32 bits yes
Interlisp 360 24 bits 32 bits no
CWIC 360 -4096..12287 32 bits no
I have also seen a few implementations with NO smallp.
Commonlisp only talks of FIXNUM and BIGNUM, but discourages knowing the
dividing line since it is unportable (though it suggests that fixnums should
provide at least 16 bits), and is even vague about how much of an efficiency
difference there is (or how you would split up the three catagories into the
two Commonlisp sets).
--
Darrel J. Van Buer, PhD; unisys; 2400 Colorado Ave; Santa Monica, CA 90406
(213)829-7511 x5449 KI6VY ······@CAM.UNISYS.COM or
...{allegra,burdvax,cbosgd,hplabs,ihnp4}!sdcrdcf!darrelj
From: Barry Margolin
Subject: Re: GC and time critical code? (use of numbers)
Date:
Message-ID: <20045@think.UUCP>
In article <····@sdcrdcf.UUCP> ·······@sdcrdcf.UUCP (Darrel VanBuer) writes:
>Implementation SMALLP FIXP BIGNUM
>============== ====== ==== ======
Symbolics 3600 32 bits no yes
>I have also seen a few implementations with NO smallp.
It probably simplifies the implementation if you don't have to decide
at runtime whether to dereference a pointer or not.
>Commonlisp only talks of FIXNUM and BIGNUM, but discourages knowing the
>dividing line since it is unportable (though it suggests that fixnums should
>provide at least 16 bits), and is even vague about how much of an efficiency
>difference there is (or how you would split up the three catagories into the
>two Commonlisp sets).
Common Lisp seems to consider that the important difference between
FIXNUM and BIGNUM is the speed of the arithmetic. In this case, the
difference between SMALLP and FIXP is not great, because both can
generally use hardware arithmetic instructions; FIXP just requires an
extra indirection first. BIGNUM arithmetic is generally implemented
using subroutines (or, in the case of some Lisp Machines, microcode).
If speed is what you care about, FIXNUM = SMALLP U FIXP.
The other distinction, storage efficiency, can also be important;
that's what this whole discussion started with. Unfortunately, the
Lisp implementations that most CL designers came from didn't have
FIXPs, so they didn't include this distinction in the language. They
were used to implementations of SMALLP that were close enough to the
word size that it didn't pay to have another one-word integer type. A
common way of implementing SMALLP in a typed-pointer Lisp is to
include some of the bits that would ordinarily be type bits in the
integer, by specifying that if the first N bits (where N is often 2)
of the type code are all 0 or all 1 the object is a SMALLP and the
rest of the bits of the type code are actually the high-order bits of
the number. This allows SMALLP's to get very large without forcing
type codes to be too small.
Barry Margolin
Thinking Machines Corp.
······@think.com
uunet!think!barmar
From: Tim Brengle
Subject: Re: Re: GC and time critical code? (use of numbers)
Date:
Message-ID: <640003@hpcltjb.HP.COM>
Lucid Common LISP uses 30 bit "immediate" integers in a 32 bit word.
PSL 3.4 uses 28 bit immediate integers.
Both do a lot of work to make arithmetic FAST. I know; I was part of the team
that worked on porting both of these to HP's Precision Architecture.
Tim Brengle
Hewlett-Packard Company
·······@hplabs.hp.com