🚀 go-pugleaf

In article <H1_6+7A@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
>In article <5347@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
>> I know the IBM-PC is the cause of the ANSI restriction.
>
>And means that the ANSI restriction is pretty much irrelevent: if they'd
>left it out, then your PC compilers would have kept doing whatever it is
>they do, they would just be "sub ANSI". As it is you can assume that pointer
>comparison is safe without restrictions so long as you're not on an 80x86.

The 80x86 is not the only architecture with multi-level memory.  There have
been quite a few systems built with segmented or object-based memory
architectures.

I use a machine on which implementing pointer comparison between unrelated
arrays is even harder than on an 80x86.  On the 80x86 dealing with the
segment number is just a performance issue.  On my Lisp Machine, global and
malloc'ed objects are allocated as individual arrays in the Lisp heap
(pointers are a combination of an array and an index), and garbage
collection can change the relative order in memory of two heap objects, so
it wouldn't be correct to use the machine addresses when comparing
pointers.

There are ways consistent pointer comparison could be implemented in this
system, but they're as unattractive as the mechanism for the 80x86.  For
instance, the arrays could have an extra element at the beginning that
would contain its object number, a number that would be incremented for
each object allocated; pointer comparison would first compare the object
numbers, and only compare the offsets if the object numbers are equal
(unfortunately, this would mean that pointer comparison could cause page
faults).

Or the C runtime could allocate a big array at program startup time, and do
all its allocation out of that (growing it when necessary).  Symbolics
Fortran does this for all its static data.  Pointers would just be indices
into this one array, so comparison would just compare their values.
However, one of the prime benefits of allocating each object as a separate
array, though, is that the Lisp Machine's hardware array bounds checking
will catch invalid array accesses, and this would be lost if a single array
were used (actually, a variant using indirect arrays might work, but then
comparisons would cause indirection and possible page faults, as above).
And growing the C heap would be expensive, as it would have to be copied.

You keep on talking about implementing a portable memory allocator in C.  I
presume you're talking about a design where it allocates big chunks of
memory using the system's malloc(), and then doles out smaller pieces of
this; pointer comparison would be used by your free primitive to determine
which chunk the object came from.  This can be done portably by using back
pointers from the allocation points to the beginning of the chunk; this is
faster than the comparison method (the former is constant time, the latter
is O(Nchunks)), but it does require extra overhead for each allocated
object.  Other portable designs make similar tradeoffs.  This just goes to
show that memory management is best done using implementation-dependent
techniques, because efficient memory management requires consideration of
the memory architecture of the system.  Portable memory allocators are nice
toys, but don't expect them to be blazingly fast.
--
Barry Margolin, Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar