··········@apollo.hp.com (Bill Sommerfeld) writes:
>With respect to using a subfield of the address as a type tag: given a
>sufficiently large sparse address space, you can "just do it" by
>allocating different primitive types in different parts of the address
>space.
This has been done for quite a long time, even on machines with fairly
small address spaces. The allocation technique is known as BIBOP, for
``Big Bag O' Pages'', and seems to have mostly died out (due in part to
the historical lack of support in Unix for attaching memory to random
chunks of address space).
In general, it seems that systems which use BIBOP like to have a `real'
type tag associated with heap objects as well as a high-bit type. This
is because 32-bit address spaces don't give you enough high address
bits to play freely with, so you reserve smallish sets of pages for
allocating objects of each type. Using a pure BIBOP system, you then
have to do a little bit of table lookup before you can determine what
type an object is from its high address bits.
The only current Lispy implementation I know of that uses BIBOP typing
is Chez Scheme from Indiana University (see IU TR 400), which uses it
solely for the storage manager to play with; run-time type
identification for other purposes is done using normal tag bits, being
faster as outlined above. The claimed win is that BIBOP frobbery makes
it easier for Chez' allocator and collector to accommodate other
languages' run time systems -- the GC can sweep through memory in the
normal fashion, but when it reaches a group of pages marked as
`externally allocated', it just skips past them. There's also some
cleverness in their BIBOP system that allows their generational GC to
avoid copying large objects, though I can't remember the exact details
of this.
I don't know what the Chez folks make of the possibilities of thrashing
the TLB or cacking on access locality as mentioned by Rob MacLachlan.
<b
--
Bryan O'Sullivan u nas est tolko odyeen yagnyonok seychas.
Inadequate Pay Department email: ···@cyclic.com, ···@dcs.gla.ac.uk
University of Glasgow web.gunge: http://www.scrg.cs.tcd.ie/~bos
From: Jeff Dalton
Subject: Re: Validating/using all 2^lgn address bits
Date:
Message-ID: <Cvo20o.I01@cogsci.ed.ac.uk>
In article <··········@dcs.gla.ac.uk> ···@dcs.gla.ac.uk (Bryan O'Sullivan) writes:
>··········@apollo.hp.com (Bill Sommerfeld) writes:
>
>>With respect to using a subfield of the address as a type tag: given a
>>sufficiently large sparse address space, you can "just do it" by
>>allocating different primitive types in different parts of the address
>>space.
>
>This has been done for quite a long time, even on machines with fairly
>small address spaces. The allocation technique is known as BIBOP, for
>``Big Bag O' Pages'', and seems to have mostly died out (due in part to
>the historical lack of support in Unix for attaching memory to random
>chunks of address space).
Franz Lisp, the BSD Lisp, uses BIBOP. Some objects also have a header
that includes a type. (E.g. struct instances.)
>The only current Lispy implementation I know of that uses BIBOP typing
>is Chez Scheme from Indiana University [...]
Franz Lisp still exists and is usable with FreeBSD and NetBSD
and (presumably) other 4.3 (soon to be 4.4) -based systems.
It is not strongly restricted as to hardware since I have a
compiler for it that compiles to C. However, there's still a
small amount of assembly code in the 386 port and some work
would be needed to get it working on incompatible hardware.
(If you want a copy of Franz for 386 BSD systems, I think it's
mentioned in the FAQ these days so I won't repeat the information
here. Should add it to my WWW page at some point...)
-- jeff
[Followups restricted.]
····@aiai.ed.ac.uk (Jeff Dalton) writes:
>Franz Lisp still exists and is usable with FreeBSD and NetBSD
>and (presumably) other 4.3 (soon to be 4.4) -based systems.
Did it use BIBOP under versions of BSD prior to those that had NFS (and
hence mmap) folded in, do you know?
<b
--
Bryan O'Sullivan
From: Richard Tobin
Subject: Re: Validating/using all 2^lgn address bits
Date:
Message-ID: <CvpKrJ.90E@cogsci.ed.ac.uk>
In article <··········@cogsci.ed.ac.uk> I wrote:
>You can just allocate a page [...] and record
>it in a table mapping high-order bits to types.
I've just looked back through the thread and I see that Bryan O'Sullivan
already mentioned this. Anyway, it's what Franz does.
-- Richard
--
Richard Tobin, HCRC, Edinburgh University ·······@ed.ac.uk
Ooooh! I didn't know we had a king. I thought we were an
autonomous collective.
From: Jeff Dalton
Subject: Re: Validating/using all 2^lgn address bits
Date:
Message-ID: <CvqDJ9.1I6@cogsci.ed.ac.uk>
In article <··········@dcs.gla.ac.uk> ···@dcs.gla.ac.uk (Bryan O'Sullivan) writes:
>[Followups restricted.]
>
>····@aiai.ed.ac.uk (Jeff Dalton) writes:
>
>>Franz Lisp still exists and is usable with FreeBSD and NetBSD
>>and (presumably) other 4.3 (soon to be 4.4) -based systems.
>
>Did it use BIBOP under versions of BSD prior to those that had NFS (and
>hence mmap) folded in, do you know?
Franz was in 4.1 BSD, which I'm pretty sure didn't have mmap.
Also, Franz doesn't _use_ mmap even in FreeBSD and NetBSD
(which do have it).
-- jeff
In article <··········@dcs.gla.ac.uk> ···@dcs.gla.ac.uk (Bryan O'Sullivan) writes:
>With respect to using a subfield of the address as a type tag: given a
>sufficiently large sparse address space, you can "just do it" by
>allocating different primitive types in different parts of the address
>space.
This has been done for quite a long time, even on machines with fairly
small address spaces. The allocation technique is known as BIBOP, for
``Big Bag O' Pages'', and seems to have mostly died out (due in part to
the historical lack of support in Unix for attaching memory to random
chunks of address space).
I think you're confused. I believe that the term BIBOP has generally
been applied to allocation schemes that pack objects of a particular
type on a "page" of storage (not necessarily the same size as the
operating system's virtual memory pages). When the current page of,
say, list space or double-float space is used up, you go allocate a
new one, but this allocation may be done adjacent to the existing
heap memory. The high-order bits of a pointer tell you what page
you're on, but they don't directly encode the type of object on that
page -- you need a table-lookup to do that.
I first saw this technique used in a version of Maclisp developed by
Jonl White back in the 1970's, but I don't know if he coined the term
"BIBOP". I think that Franz used BIBOP in this sense.
The scheme of using some of the high-order address bits to directly
encode the type is a different idea (and doesn't have a snappy names
as far as I know). In this scheme, each type is kept in a contiguous
chunk of the address space, and these chunks are separated by many
megabytes of unused space. This provides lots of room for each space
to grow, if there aren't too many of them, but it has the problems
that others have pointed out, especially in some older versions of
Unix which insist on allocating memory in one or two contiguous
chunks.
-- Scott
===========================================================================
Scott E. Fahlman Internet: ····@cs.cmu.edu
Principal Research Scientist Phone: 412 268-2575
School of Computer Science Fax: 412 268-5576 (new!)
Carnegie Mellon University Latitude: 40:26:46 N
5000 Forbes Avenue Longitude: 79:56:55 W
Pittsburgh, PA 15213 Mood: :-)
===========================================================================