[boost] Re: Challenge: pool allocator

From: Stephen Cleary (scleary_at_[hidden])
Date: 2000-03-02 12:55:55

john maddock wrote: 
> I've only looked *quickly* at your alignment code, however I don't
think
> that it quite guarentees correct alignment - as I understand it your
code
> only guarantees alignment on a sizeof(char*) boundary, but there may
be
> types which require alignment on a larger boundary than that, I
figured
> that the logic goes like this:

My code required alignment on a multiple of sizeof(char *); however, it
would still break if other alignments are not multiples of sizeof(char
*).  This is because the chunk partition size was min(sizeof(T),
sizeof(char *)), rounded up to the nearest multiple of sizeof(char *). 
However, I've fixed it now -- the chunk partition size is now
lcm(sizeof(T), sizeof(void *)).

The update is in the vault.  While I was there, I also changed some of
the code to be more readable :).  Also, I ran testing on every
alignment BCB supports, but odd alignments like the one below are not
supported.

First, just one comment on the portability of your code:

> 
> ...
> 
> template <typename T>
> struct alignment_of
> {
>    static const unsigned value =
> (char*)&(static_cast<align_size<T>*>(0)->t) - static_cast<char*>(0);
> };
>
> ...
>

This method of getting around offsetof() is questionable at best. 
Since p->m is defined to be (*p).m [5.2.5/3], the result may well be
the dereferencing of a null pointer (implementation-defined).  C:ARM
[11.1] suggests using a predefined, non-null pointer to get around
this.  Even with that, though, this form of expression cannot be used
in an integral constant expression [5.19/1, last sentence], or even in
an address constant expression [5.19/4, 2nd-to-last sentence].

There are ways to guarantee alignment without needing something like
this.

> As an after thought, I haven't been able to figure out a specific
example
> where your code would fail (so you may be correct) - unless a
platform did
> something really strange and had say 6-byte alignment rules for some
types
> and 4-byte alignment rules for others.

This is the only type of situation where my scheme would break down.  I
have now fixed it.  It does, however, waste memory if this is the case
(say, 6-byte alignment on "T" and 4-byte alignment on "void *" results
in 12-byte chunks).

-------------------------------------------------
Why I think my alignment works (after I fixed it)
-------------------------------------------------

My reasoning goes like this:
  1) We allocate an array "A1" of "A1Bound" characters.  This memory
"ptr" is guaranteed to be properly aligned for all objects of size
A1Bound or smaller [3.7.3.1/2] [5.3.4/10].
  2) We will now look at "ptr" in another way.  Create a pretend type
"Element", where sizeof(Element) = lcm(sizeof(T), sizeof(void *)).  Now
look at "ptr" as pointing to an array of "Element"; name this array
"A2".  Assume A1Bound >= sizeof(Element).
  3) The upper bound of "A2" is "A2Bound" = A1Bound/sizeof(Element).
  4) Note that sizeof(A2) = A2Bound * sizeof(Element).  [5.3.3/2]
  5) Note that an array type is an object type.  [3.9/9]
  6) Note that sizeof(A2) <= A1Bound, because (A1Bound/sizeof(Element))
*sizeof(Element) <= A1Bound.
  7) From (4-6) and (1), we know that "ptr" is properly aligned for
"A2".
  8) From (1) and the fact that sizeof(Element) <= A1Bound, we know
that "ptr" is also properly aligned for "Element".
  9) From (7) and (8), we claim that the first element of "A2" is
properly aligned, on the strength of "&(a[0]) == a" [5.2.1/1] [5.7/8]
and the fact that arrays cannot have any padding [5.3.3/2].
  10) Since, for any i, (0 <= i < A2Bound), &(a[i]) = a + i, and from
(9), we claim that *every* element of "A2" is properly aligned.
  11) Using this same scheme, look at "ptr" as an array "A3" of "T";
the bound "A3Bound" is A1Bound/sizeof(T).  "ptr" is properly aligned
for "A3", "T", the first element of "A3", and every element of "A3".
  12) Since sizeof(Element) is a multiple of sizeof(T) and from (11),
every element of "A2" is properly aligned for "T".
  13) Now we use the array "A2" to return pointers to "T" that we know
are properly aligned.

(Steps 11-12 need to be repeated for an array of "void *", so that we
can portably thread our free-list through the same array).

Note that step 10 makes an assumption that if "p" is properly aligned
for "T", then, for any integer i, "p + i" (when well-defined) is
properly aligned for "T".  I believe that this assumption would be
backed up by the definition of "alignment requirements". 
Unfortunately, no such definition exists in the Standard!

---------------------
Why it is inefficient
---------------------
(meaning "What I wish I could change but can't figure out how to")

pool, as it stands right now, has a list of storage units:
  pool  ->  storage0
            storage1
            storage2

The problem is that each of these storage units is just two pointers
(the "first" pointer for the free list and a pointer to reference the
allocated memory block):
  pool  ->  storage0 -> block
            storage1 -> block
            storage2 -> block

However, each time another storage unit is needed, the allocator must
be called *twice*, once for the small storage unit and once for the
block.  Since each storage unit can only have one block, it seems
wasteful, in both run-time and memory terms.

Basically, it comes down to: non-POD types (even types without virtual
functions or base classes) don't have a guarantee that their first
member is at the beginning of the object.  If we had this guarantee, we
could place the 'block' at the beginning of the storage unit, and know
our alignment would be correct because storage units are allocated. 
Any ideas on how to get around this?

        -Steve