mesard@bbn.com (Wayne Mesard) (03/24/88)
I'm working on a spec for a program that needs to take collect reaction
time data (from humans). The program really wants to be written in Lisp
(as any well conceived program would :-), but I'm not clear about how
garbage collection will interfere with taking time data. That is, what
if the system is doing GC when the subject "presses the stop button"?
I imagine this problem has been dealt with before. Is there a way to
prevent this? (Forcing a GC right before the critical code isn't a
guarantee, but I'm willing to entertain arguments that that's good
enough.)
Any comments would be appreciated. Please mail to me. I'll summarize
to the net unless it turns out that this is a naive question.
Thanks.
--
unsigned *Wayne_Mesard(); MESARD@BBN.COM
BBN Labs, Cambridge, MA
Are you absolutely sure that you want to do this? [ny] ummm_jeff@aiva.ed.ac.uk (Jeff Dalton) (03/29/88)
In article <22550@bbn.COM> mesard@bbn.com writes: >I'm working on a spec for a program that needs to take collect reaction >time data (from humans). The program really wants to be written in Lisp >(as any well conceived program would :-), but I'm not clear about how >garbage collection will interfere with taking time data. That is, what >if the system is doing GC when the subject "presses the stop button"? This is a good question, which is probably why it keeps turning up. There are, basically, three answers: 1. Use a Lisp that has a "nondisruptive" garbage collection strategy. Some Lisps have garbaage collectors that do a little bit or work fairly frequently, so that it's like having a slightly slower CONS rather than long pauses for GC. Incremental GC, "ephemeral" GC, and perhaps some other strategies are largely nondisruptive, but at present tend not to be used in implementations for general- purpose machines. It's possible that such techniques are fast enough to be unnoticable even for your application. The delays shouldn't be worse than the paging and scheduling delays one accepts when running multiple processes. 2. Preallocate enough storage so there is no need to GC. 3. Don't generate any (or very much) garbage. The latter two techniques can be combined if you use explicit storage management, with a pool of resources that you allocate and free. Most Lisp systems give you a fair amount of control over when storage is allocated. That is, they try not to allocate storage on their own but only when you call something like CONS. But &REST parameters tend to cause a list allocation, and some interpreters construct environments when functions are called. So you get rules like don't use &REST, compile your code, etc. 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. 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. Otherwise, you may have to preallocate to make sure there is enough space for the numbers. Jeff Dalton, JANET: J.Dalton@uk.ac.ed AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
aarons@cvaxa.sussex.ac.uk (Aaron Sloman) (04/16/88)
In response to article <22550@bbn.COM> mesard@bbn.com Jeff Dalton (jeff@aiva.ed.ac.uk) writes: >From: jeff@aiva.ed.ac.uk (Jeff Dalton) >Message-ID: <305@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 : aarons%uk.ac.sussex.cvaxa@nss.cs.ucl.ac.uk JANET aarons@cvaxa.sussex.ac.uk BITNET: aarons%uk.ac.sussex.cvaxa@uk.ac As a last resort (it costs us more...) UUCP: ...mcvax!ukc!cvaxa!aarons or aarons@cvaxa.uucp
richard@aiva.ed.ac.uk (Richard Tobin) (04/19/88)
In article <452@cvaxa.sussex.ac.uk> aarons@cvaxa.sussex.ac.uk (Aaron Sloman) writes: >Jeff Dalton (jeff@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: R.Tobin@uk.ac.ed AI Applications Institute, ARPA: R.Tobin%uk.ac.ed@nss.cs.ucl.ac.uk Edinburgh University. UUCP: ...!ukc!ed.ac.uk!R.Tobin
darrelj@sdcrdcf.UUCP (Darrel VanBuer) (04/19/88)
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 darrel@CAM.UNISYS.COM or
...{allegra,burdvax,cbosgd,hplabs,ihnp4}!sdcrdcf!darreljbrengle@hpcltjb.HP.COM (Tim Brengle) (04/20/88)
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 brengle@hplabs.hp.com
barmar@think.COM (Barry Margolin) (04/20/88)
In article <5243@sdcrdcf.UUCP> darrelj@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. barmar@think.com uunet!think!barmar