On Thu, 19 Aug 2010 04:14:42 -0700 (PDT), spinoza
wrote:
>On Aug 18, 1:44=A0am, James Kanze wrote:
>> On Aug 17, 6:21 pm, Standish P wrote:
>>
>> > > Garbage collection doesn't use a stack. It uses a "heap",
>> > > which is in the abstract a collection of memory blocks of
>> > > different lengths, divided into two lists, generally
>> > > represented as linked lists:
>> > > 1. =A0A list of blocks that are free and may be used to store
>> > > new data
>> > > 2. =A0A list of blocks that are in use, or haven't been freed (yet)
>> > Is this all that a heap is or is there more to it ?
>>
>> There are many different ways to implement a heap. =A0The above is
>> not a good one, and I doubt that it's really used anywhere.
>
>Actually, that's the only way to implement a heap in the abstract.
>Forest and trees, mate. Mathematically a heap is a block of storage, a
>list of free blocks and a list of allocated blocks. All the rest is
>detail for the little techies to normally, get wrong. The confusion
>between scientific and technical progress is a mirror of the (far more
>serious) confusion between scientific progress and ethical advance.
>
>Sure, when you free a block it is a good idea to see if you can join
>it with its neighbors to get the biggest "bang for the buck".
[snip]
I appreciate your desire to provide a "mathematical" definition
but the one you gave won't quite do. Your definition does not
specify what is meant by a block. The notion of defining a heap
as a list of free list and a list of allocated blocks is
unfortunate. Neither a free list nor a list of allocated blocks
is of the essence.
It isn't easy to give a good definition of a heap (in the sense
of a storage heap) but here is a shot at it.
A heap is a data structure consisting of a pair (H,B) of
substructures, operations (split,join), and attribute A where:
H is a set of sequentially addressable elements. That is, the
elements form a sequence, each element has an integer associated
with it (its address) and the difference between the addresses of
successive elements is a constant, w. Let h_i be the address of
the initial element of H and h_f be the address of the final
element of H.
B is a set of integers such that (1) each element b of B is an
address of an element of H, and (2) h_i and h_f are elements of
B. From this definition we can define the successor succ(b) of
each element (h_f has no successor) and we can order B if we
wish.
Given the construction of succ on B we can define block(b) as the
set of elements in H such that their addresses a satisfy
b <= a < succ(a)
It is trivial to prove that the blocks of B divide H into
disjoint subsets that cover H.
The attribute A is defined for elements of B. A(b) may have
either of two values - free and inuse. A block b is said to be
free if A(b) = free and in use if A(b) = inuse.
An address, h, of H is said to be free if A(largest address b in
B that is <= h) = free and in use otherwise.
Now for the two operations:
The join operator operates on all free elements of b except h_f.
It removes the successor of an element of b. The effect is to
set succ(b) := succ(succ(b)).
The split operator operates on all free element addresses in H
that are not element addresses in B. Let s be the argument for
split. Split adds s to B. The effect of split is to find the
largest address b in B that is smaller than s, set succ(s) :=
succ(b) and succ(b) := s. Note that the successor changes
implicitly follow from the definitions of H, B, split, and join.
The above definition covers defining a storage heap. It
establishes what blocks are, what the sequence of blocks is, and
how to alter the sequence of blocks.
The important thing here is that free lists/allocated lists are
not basic abstractions; rather they are derived concepts based on
the primitive concept of a block and the operations performed on
a set of blocks.
--
http://mail.python.org/mailman/listinfo/python-list
