BIBOP page size?

[Paul Rubin]

Anyone know how big the pages were in historical BIBOP
implementatations? Are there non-obvious trade-offs? Is it a viable
technique in small memory systems? This question is inspired somewhat
by Picobit: https://github.com/stamourv/picobit

Picobit uses 16-bit cells with type tags and GC bits, allowing only 13
address bits. The idea is getting rid of those bits and using BIBOP,
allowing 16 bits of addresses, and by aligning all objects on 4-byte
boundaries (i.e. conses are two 16-bit cells) the addresses can be
shifted two bits, giving 256KB of address space, corresponding to the
larger ARM MCU's these days. Once above 256KB it becomes affordable to
use 32-bit cells.

[George Neuner]

On Sun, 22 Mar 2015 01:08:59 -0700, Paul Rubin
<no.e...@nospam.invalid> wrote:

>Anyone know how big the pages were in historical BIBOP
>implementatations?

Historically, BiBOP was implemented on top of the system's VMM page
size. Now there are systems that support multiple page sizes, but I
have no knowledge any BiBOP system that works with large(r) pages.

>Are there non-obvious trade-offs? Is it a viable technique in
>small memory systems?

The original notion of BiBOP was to identify the type of an object by
its address and to physically segregate objects into separate heaps
which sparsely populate the address space. This really is not viable
in a small system. [It is problematic even on a 32-bit system.]

The more modern idea is based on 2-level allocation and constructs
logical heaps from arbitrary pages. Objects still are segregated by
type, but the separate type heaps are interleaved through the address
space. The problem with it - relative to the original idea - is that
an object's address no longer intrinsically identifies the object's
type - so you need additional space to encode that. Most systems use
some form of separate address=>page=>type map.

>This question is inspired somewhat by Picobit:
> https://github.com/stamourv/picobit
>
>Picobit uses 16-bit cells with type tags and GC bits, allowing only 13
>address bits. The idea is getting rid of those bits and using BIBOP,
>allowing 16 bits of addresses, and by aligning all objects on 4-byte
>boundaries (i.e. conses are two 16-bit cells) the addresses can be
>shifted two bits, giving 256KB of address space, corresponding to the
>larger ARM MCU's these days. Once above 256KB it becomes affordable to
>use 32-bit cells.

You still have only 64K cells - that's awfully tight to be subdivided
by page (even if the "pages" are small). And you will need additional
space to track which pages are allocated to which types.

Your best bet might be to forget about type segregation, but to
replace the per cell tags with an address=>type map maintained
separately from the cell space.

George

[Alan Bawden]

George Neuner <gneu...@comcast.net> writes:

> On Sun, 22 Mar 2015 01:08:59 -0700, Paul Rubin
> <no.e...@nospam.invalid> wrote:
>
>>Anyone know how big the pages were in historical BIBOP
>>implementatations?
>
> Historically, BiBOP was implemented on top of the system's VMM page
> size. Now there are systems that support multiple page sizes, but I
> have no knowledge any BiBOP system that works with large(r) pages.

In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
used as an index into a "segment table" that described the type of
objects in that 512-word "segment". (Recall that a PDP-10 word was
36-bits wide, so every cons occupied exactly one word.)

On the ITS operating system, where MacLisp was developed, a page
contained 1024 words. So although we said MacLisp used BIBOP, it was
actually a big bag of _half_ pages.

MacLisp also ran under TOPS-20, where the pages really did contain 512
words. I believe it also ran under TOPS-10 on unmodified KA10s that had
no paging hardware at all -- since the idea really has nothing to do
with your virtual memory system's pages.

I don't know when BIBOP was invented. It was so perfectly suited for
the PDP-10 (and PDP-6) that I would expect it was invented by the
implementors of either MacLisp or InterLisp, but I don't know its
backstory.

--
Alan Bawden

[Jeff Barnett]

I implemented a Lisp system on on a Raytheon 704 mini-computer in the
early 1970's. It was a 32K 16 bit/word machine. Pointers where packed
into 15 bits of the 16 bit words. Types were determined by the area the
objected occupied. Full range arithmetic wasn't especially important so
small integers were mapped onto the addresses occupied by the operating
system. Since the OS took up approximately 2K, integers were restricted
to +/-1,000. This was, of course, an interpretive system and less than a
1,000 16-bit words sufficed to hold the interpreter, GC, and basic
primitives. (An ability to read and write disk files and save images was
added by Rick Bobrow when he was in high school!)

This Lisp was originally used to host a version of Eliza. In short
order, we implemented some fairly strange software: the top-end of a
phoneme string to audio speech - rule based transformations; the entire
non-acoustic top-end of a speech understanding system- syntax, semantic,
and pragmatic knowledge; a number of game like programs in addition to
Eliza; a voice interactive repair facility to fix a piece of electronic
equipment - simple walk-a-tree from question answers to next question
and/or diagnoses (speech output pre-generated); data management software
for a data base (coped from Jean's) of the floating fleets of the USA,
USSR, and the UK - Questions such as "Who is the skipper of the flagship
Seawolf" with answer "Jimmy Carter".

The system spent a lot of its time in the GC but was surprisingly fast.
Some more details are available at
http://www.softwarepreservation.org/projects/LISP/
--
Jeff Barnett

[George Neuner]

On Sun, 22 Mar 2015 15:13:30 -0400, Alan Bawden
<al...@scooby-doo.csail.mit.edu> wrote:

>George Neuner <gneu...@comcast.net> writes:
>
>> On Sun, 22 Mar 2015 01:08:59 -0700, Paul Rubin
>> <no.e...@nospam.invalid> wrote:
>>
>>>Anyone know how big the pages were in historical BIBOP
>>>implementatations?
>>
>> Historically, BiBOP was implemented on top of the system's VMM page
>> size. Now there are systems that support multiple page sizes, but I
>> have no knowledge any BiBOP system that works with large(r) pages.
>
>In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
>used as an index into a "segment table" that described the type of
>objects in that 512-word "segment". (Recall that a PDP-10 word was
>36-bits wide, so every cons occupied exactly one word.)
>
>On the ITS operating system, where MacLisp was developed, a page
>contained 1024 words. So although we said MacLisp used BIBOP, it was
>actually a big bag of _half_ pages.

Were those really BiBOP, or were they "card" allocators.

My understanding was that "BiBOP" referred to VMM hardware based
systems. The (older) pure software implementation is known as "card"
allocation in the literature.

>I don't know when BIBOP was invented. It was so perfectly suited for
>the PDP-10 (and PDP-6) that I would expect it was invented by the
>implementors of either MacLisp or InterLisp, but I don't know its
>backstory.

AFAIK, the basic idea originated with Guy Steele on the PDP-10 and was
documented in a MACLISP technical note in 1977. But Steele's paper
called allocation blocks "hunks" and gave only a vague description of
a pure software implementation that later came to be called card
allocation. The term "BiBOP" was introduced later: I don't know for
certain, but I *believe* it was coined by Andrew Appel and first
appeared in print in 1989.


But I could be completely mistaken. The nice thing about c.l.l is
that somebody here will know for sure. 8-)

George

[Alan Bawden]

George Neuner <gneu...@comcast.net> writes:

> On Sun, 22 Mar 2015 15:13:30 -0400, Alan Bawden
> <al...@scooby-doo.csail.mit.edu> wrote:
>
>>George Neuner <gneu...@comcast.net> writes:
>>
>>> On Sun, 22 Mar 2015 01:08:59 -0700, Paul Rubin
>>> <no.e...@nospam.invalid> wrote:
>>>
>>>>Anyone know how big the pages were in historical BIBOP
>>>>implementatations?
>>>
>>> Historically, BiBOP was implemented on top of the system's VMM page
>>> size. Now there are systems that support multiple page sizes, but I
>>> have no knowledge any BiBOP system that works with large(r) pages.
>>
>>In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
>>used as an index into a "segment table" that described the type of
>>objects in that 512-word "segment". (Recall that a PDP-10 word was
>>36-bits wide, so every cons occupied exactly one word.)
>>
>>On the ITS operating system, where MacLisp was developed, a page
>>contained 1024 words. So although we said MacLisp used BIBOP, it was
>>actually a big bag of _half_ pages.
>
> Were those really BiBOP, or were they "card" allocators.

Perhaps the terminology has changed over the years, but we definitely
called what MacLisp had "BIBOP" in the 1970s. Proof below.

> My understanding was that "BiBOP" referred to VMM hardware based
> systems. The (older) pure software implementation is known as "card"
> allocation in the literature.
>
>
>>I don't know when BIBOP was invented. It was so perfectly suited for
>>the PDP-10 (and PDP-6) that I would expect it was invented by the
>>implementors of either MacLisp or InterLisp, but I don't know its
>>backstory.
>
> AFAIK, the basic idea originated with Guy Steele on the PDP-10 and was
> documented in a MACLISP technical note in 1977.

That would be AI Memo 420 "Data Representations in PDP-10 MacLisp".
Which in fact I looked at just before I replied to your previous
message! (I also pulled out the technical note that describes the ITS
paging hardware, just to be sure I had that right.) It is true that in
that Memo, Steele doesn't use the term "BIBOP", but see below.

> But Steele's paper called allocation blocks "hunks" and gave only a
> vague description of a pure software implementation that later came to
> be called card allocation.

No, the word "hunk" referred to a generalization of a cons cell. It was
really just a kind of vector. (In fact, defstruct usually implemented
structures by using hunks.)

> The term "BiBOP" was introduced later: I don't know for
> certain, but I *believe* it was coined by Andrew Appel and first
> appeared in print in 1989.

In the release notes for MacLisp version 767, dated 1 March 1974
(which is the oldest entry in the "LISP NEWS" file), the very first
entry reads:

[1] IT HAS BEEN OBSERVED THAT OCCASIONALLY RUNTIMES WILL BE
MEASURED AS BEING NEGATIVE. THIS IS APPARENTLY AN ITS BUG
HAVING SOMETHING TO DO WITH REQUESTING CORE MANAGEMENT,
SO IT HAPPENS MORE IN BIBOP LISP THAN IN NON-BIBOP. I'VE
TAKEN SOME COMPENSATIVE ACTIONS, BUT BE FOREWARNED AND BEWARE.

And there you have evidence that the word BIBOP was being used for what
MacLisp did in 1974. And we also learn that BIBOP had only been
introduced recently, and so MacLisp existed in both BIBOP and non-BIBOP
versions.

By the time I started using MacLisp in 1976, the non-BIBOP MacLisp was gone.

> But I could be completely mistaken. The nice thing about c.l.l is
> that somebody here will know for sure. 8-)

That we called it BIBOP in the 1970s I know for sure.

Of who invented it, I am less sure.

--
Alan Bawden

[Rob Warnock]

George Neuner <gneu...@comcast.net> wrote:
+---------------

| Alan Bawden <al...@scooby-doo.csail.mit.edu> wrote:
| >In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
| >used as an index into a "segment table" that described the type of
| >objects in that 512-word "segment". (Recall that a PDP-10 word was
| >36-bits wide, so every cons occupied exactly one word.)
| >
| >On the ITS operating system, where MacLisp was developed, a page
| >contained 1024 words. So although we said MacLisp used BIBOP, it was
| >actually a big bag of _half_ pages.
|
| Were those really BiBOP, or were they "card" allocators.
|
| My understanding was that "BiBOP" referred to VMM hardware based
| systems. The (older) pure software implementation is known as "card"
| allocation in the literature.

+---------------

You might be confusing two things. BiBOP has mainly to do with
object type tagging, and thus the "pages" used for BiBOP have
no real correlation with whatever hardware paging is available.

On the other hand, VM (paging) hardware and software card marking
are different ways of providing a write barrier for generational
garbage collection. They have nothing to do with type tagging.

[Note: It is possible to use *both* BiBOP and software card marking
in the same system. In that case, the BiBOP "page" size and the card
marking "card" size might be the same *or* might be different.]


-Rob

-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403

[Pascal J. Bourguignon]

Alan Bawden <al...@scooby-doo.csail.mit.edu> writes:

> In the release notes for MacLisp version 767, dated 1 March 1974
> (which is the oldest entry in the "LISP NEWS" file), the very first
> entry reads:
>
> [1] IT HAS BEEN OBSERVED THAT OCCASIONALLY RUNTIMES WILL BE
> MEASURED AS BEING NEGATIVE. THIS IS APPARENTLY AN ITS BUG
> HAVING SOMETHING TO DO WITH REQUESTING CORE MANAGEMENT,
> SO IT HAPPENS MORE IN BIBOP LISP THAN IN NON-BIBOP. I'VE
> TAKEN SOME COMPENSATIVE ACTIONS, BUT BE FOREWARNED AND BEWARE.

Hogwash. The negative runtimes were due to the lisp system using
imaginary squared time to run, thus transforming O(in²) algorithms into
-O(n) time.


--
__Pascal Bourguignon__ http://www.informatimago.com/
“The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.” -- Carl Bass CEO Autodesk

[George Neuner]

On 23 Mar 2015 07:45:38 GMT, rp...@rpw3.org (Rob Warnock) wrote:

>George Neuner <gneu...@comcast.net> wrote:
>+---------------
>| Alan Bawden <al...@scooby-doo.csail.mit.edu> wrote:
>| >In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
>| >used as an index into a "segment table" that described the type of
>| >objects in that 512-word "segment". (Recall that a PDP-10 word was
>| >36-bits wide, so every cons occupied exactly one word.)
>| >
>| >On the ITS operating system, where MacLisp was developed, a page
>| >contained 1024 words. So although we said MacLisp used BIBOP, it was
>| >actually a big bag of _half_ pages.
>|
>| Were those really BiBOP, or were they "card" allocators.
>|
>| My understanding was that "BiBOP" referred to VMM hardware based
>| systems. The (older) pure software implementation is known as "card"
>| allocation in the literature.
>+---------------
>
>You might be confusing two things. BiBOP has mainly to do with
>object type tagging, and thus the "pages" used for BiBOP have
>no real correlation with whatever hardware paging is available.
>
>On the other hand, VM (paging) hardware and software card marking
>are different ways of providing a write barrier for generational
>garbage collection. They have nothing to do with type tagging.

Yes. However, there is also "card allocation" which also is about
type tagging. As described in the literature it is virtually the same
as BiBOP, but using any suitably sized block - i.e. it is not tied to
VMM page size, disk block size or any other system level parameter.

IME, BiBOP always has been described in conjunction with VMM assisted
GC and always used the VMM page as its allocation unit. Although GC
technically is orthogonal to allocation, in real systems they are
tightly bound and I have seen no examples using the term "BiBOP" that
did not use VMM. I may have incorrectly associated them due to that.

>[Note: It is possible to use *both* BiBOP and software card marking
>in the same system. In that case, the BiBOP "page" size and the card
>marking "card" size might be the same *or* might be different.]

Yes. Card marking puts mark flags in an array separate from the cells.
It has nothing per se to do with how things are allocated.

But card _marking_ is not what I was referring to.


>-Rob
George

[Rob Warnock]

George Neuner <gneu...@comcast.net> wrote:
+---------------
| rp...@rpw3.org (Rob Warnock) wrote:
| >George Neuner <gneu...@comcast.net> wrote:
| >+---------------

| >| Were those really BiBOP, or were they "card" allocators.
| >|
| >| My understanding was that "BiBOP" referred to VMM hardware based
| >| systems. The (older) pure software implementation is known as "card"
| >| allocation in the literature.
| >+---------------
| >
| >You might be confusing two things. BiBOP has mainly to do with
| >object type tagging, and thus the "pages" used for BiBOP have
| >no real correlation with whatever hardware paging is available.
| >
| >On the other hand, VM (paging) hardware and software card marking
| >are different ways of providing a write barrier for generational
| >garbage collection. They have nothing to do with type tagging.
|
| Yes. However, there is also "card allocation" which also is about
| type tagging. As described in the literature it is virtually the same
| as BiBOP, but using any suitably sized block - i.e. it is not tied to
| VMM page size, disk block size or any other system level parameter.

+---------------

As Alan Bawden previously noted in this thread, BiBOP was not always
tied to the hardware VM page size, so "card allocation" is just BiBOP
with smaller "pages".

[Paul Rubin]

Alan Bawden <al...@scooby-doo.csail.mit.edu> writes:
> In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
> used as an index into a "segment table" that described the type of
> objects in that 512-word "segment".

Thanks, Alan. That is the info I was looking for but couldn't find in
the Maclisp manual. A few followup questions if it's ok:

1) Where were the GC mark bits kept, e.g. for conses?

2) Did the GC compact stuff in memory? Did it need much extra memory
for bookkeeping to do that? I'm presuming it was a mark-sweep collector
since I think I heard that somewhere.

3) How much memory did it take to run a reasonable Maclisp program
(i.e. in the 1 KLOC range with a kword or two of live user data, not
something like Macsyma)? If you were on a small PDP-10 and wanted to
whip out a utility to (say) reformat a text file, would you have used
Maclisp the way people use scripting languages now? Did programs of
that era tend to use data mutation (setq, rplaca/rplacd) a lot to avoid
consing, as opposed to later styles that relied on GC more? (Hmm, now
that I think of it, SNOBOL existed back then, but I don't know how many
people used it).

Thanks again.

Paul

[Alan Bawden]

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

> Alan Bawden <al...@scooby-doo.csail.mit.edu> writes:
>> In PDP-10 MacLisp, where addresses are 18-bits wide, the top 9 bits were
>> used as an index into a "segment table" that described the type of
>> objects in that 512-word "segment".
>
> Thanks, Alan. That is the info I was looking for but couldn't find in
> the Maclisp manual. A few followup questions if it's ok:
>
> 1) Where were the GC mark bits kept, e.g. for conses?

For conses (and some other types) the garbage collector allocated blocks
of GC bits for every segment of conses. Some other types of objects had
room to spare where a GC bit could be stashed.

>
> 2) Did the GC compact stuff in memory? Did it need much extra memory
> for bookkeeping to do that? I'm presuming it was a mark-sweep collector
> since I think I heard that somewhere.

No compaction was done.

You can read all about this yourself by reading Steele's memo directly:

ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-420.pdf

(And anyone interested in the history of MacLisp should also read:

ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-421.pdf

Which is about arithmetic in MacLisp.)

> 3) How much memory did it take to run a reasonable Maclisp program
> (i.e. in the 1 KLOC range with a kword or two of live user data, not
> something like Macsyma)?

This kind of question is very hard to answer 39 years later. At the
time we would write pretty much anything sufficiently complicated in
MacLisp. It was the high level language of choice. And it's hard to
believe, but we really didn't worry too much about running out of
address space. At the time, 262144 36-bit words seemed huge. Half a
MILLION cons cells! Sure, we knew that really serious programs like
Macsyma were running out of memory all the time (read Steele's memo!),
but for writing most ordinary programs it wasn't much of a concern.

You have to realize that these machines were also amazingly slow by
todays's standards, so it actually took a lot of time to fill up that
amount of memory. And also these machines didn't have that much physical
memory, so if you had a process using an entire address space, and there
were other people trying to do other things on the machine at the same
time (this was timesharing after all), you were probably making the
machine thrash. (And soon an angry professor would appear in your door
wondering what the *BLEEP* you were doing!)

So other things discouraged you from using that much memory before you
actually ran out of address space.

> If you were on a small PDP-10 and wanted to whip out a utility to
> (say) reformat a text file, would you have used Maclisp the way people
> use scripting languages now?

Definitely. (Of course on the PDP-10 we also wrote a lot of stuff in
assembler -- not always for efficiency's sake, but just because PDP-10
assembler was such fun to program in!)

> Did programs of that era tend to use data mutation (setq,
> rplaca/rplacd) a lot to avoid consing, as opposed to later styles that
> relied on GC more?

Yes, we did some really really ugly things with RPLACA and RPLACD.
Whole data structures that were implemented out of nothing but cons
cells linked together in insane ways. The Lisp world is a better place
now that those days are behind us.

> (Hmm, now that I think of it, SNOBOL existed back then, but I don't
> know how many people used it).

I'm not sure I understand how SNOBOL got in here...

--
Alan Bawden

[Richard Fateman]

The BIBOP allocation idea was used in Franz Lisp
http://en.wikipedia.org/wiki/Franz_Lisp

circa 1978,

in recognition of its success in Maclisp
on the PDP-6/10, and somewhat easing the transition to
the VAX 11/780. There were vastly more installations of
Franz Lisp (on BSD VAX UNIX) than there ever were on PDP-10s.
The address space was huge compared to PDP-10, and I think that
in retrospect the page size on the VAX has been viewed as
rather small. (resulting in the need to page the page-tables).

I do not know the page size used by Franz Lisp for BIBOP, but
probably there are people in the Franz INc company
who could respond to this question if asked.

Another trick that might be appropriate for small memory systems
is allocating small fixed numbers in fixed locations. "Most" numbers
are like oh, -255 to 255. Or pick some other bounds.
If you haven't thought about the consequences, have fun.