Topic: Alignment requirements of allocation functions
Author: AlbertoBarbati@libero.it (Alberto Ganesh Barbati)
Date: Fri, 20 Jan 2006 04:31:45 GMT Raw View
wade@stoner.com wrote:
> struct xy
> {
> xy():x(0),y(0){}
> char x;
> char y;
> static void* operator new(size_t);
> };
>
> If xy has alignment 1, size 2, and int has alignment 2, size 2 the
> current standard allows the implementation to translate
>
> return new xy;
>
> into
>
> void* ptr = xy::operator new(2);
> *(int*) ptr = 0; // Fast constructor replacement. Fails if
> ptr is not suitably aligned.
> return (xy*) ptr;
What makes you think that the standard allows this? Please state the
exact statement in the standard, because I couldn't find it.
Ganesh
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: "Gerald Thaler" <gerald.thaler@gmx.de>
Date: Fri, 20 Jan 2006 09:52:09 CST Raw View
> Assuming your interpretation is correct, think about what an
> dynamic allocator that violated it would look like. Seems like
> it would have to have a bit map of each allocated byte (or
> byte pair), with the bits corresponding to the start and end
> of an allocated block being set. This sort of allocator would
> only make sense for applications that allocated very small
> blocks almost exclusively, Or, another posibility would
> be an allocator for an application that never really needed
> to free memory, that is to say, 'delete' would simply call
> the destructor. Maybe the Committee thought these cases
> were so odd they wern't worth taking into consideration.
>
> I think ANSI-C's 'malloc()' alignment requirements are
> independent of the size of the allocation. So maybe this is
> just baggage from C.
There are very clever allocator implementations, that don't need
"bitmaps". These allocators are fast and have almost zero space
overhead for small objects (like char, int). For example the
Loki-Library by Andrei Alexandrescu contains such an allocator. It is
described in detail in the book "Modern C++ Design".
I think these allocators are widely used, but i wonder if they are
allowed by the standard.
Gerald
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: wade@stoner.com
Date: Fri, 20 Jan 2006 09:54:57 CST Raw View
Alberto Ganesh Barbati wrote:
> wade@stoner.com wrote:
> > struct xy
> > {
> > xy():x(0),y(0){}
> > char x;
> > char y;
> > static void* operator new(size_t);
> > };
> >
> > If xy has alignment 1, size 2, and int has alignment 2, size 2 the
> > current standard allows the implementation to translate
> >
> > return new xy;
> >
> > into
> >
> > void* ptr = xy::operator new(2);
> > *(int*) ptr = 0; // Fast constructor replacement. Fails if
> > ptr is not suitably aligned.
> > return (xy*) ptr;
>
> What makes you think that the standard allows this? Please state the
> exact statement in the standard, because I couldn't find it.
Mostly the as-if rule (1.9):
1) If the results look right, you can't complain about how the
implementation got them (1.9/1).
2) If your program has undefined behavior (UB) the results don't even
need to be right. (1.9/5).
The observable behavior for
return new xy;
is
1) If xy::op new throws an exception, pass it along.
2) If xy::xy() throws an exception (ignore this case, can't happen
here) ...
3) Return the pointer (converted to xy*) returned from xy::op new.
4) The object on the heap must have ptr->x == 0 && ptr->y == 0.
My "translated" code will do this on any implementation where int(0)
and char(0) are all bits zero, and my other assumptions about size also
hold, unless the "Fast constructor" assignment fails. The "Fast
constructor" assignment should only fail if we hit some implementation
limit (like out of stack space), op new returned a "bogus" pointer (for
instance NULL) or an unaligned pointer.
3.7.3.1/2 says that result of op new shall be suitably aligned for any
complete object (including int).
If the user-defined op new does not satisfy 3.7.3.1/2 then the program
has UB, and the implementation can do whatever it wants.
Note that user code cannot use my "trick" because it violates aliasing
rules. However implementations are allowed to violate aliasing rules
(and most other program restrictions) as long as the observable
behavior is correct.
So if I missed something, what makes you think the standard does not
allow this?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: Alberto Ganesh Barbati <AlbertoBarbati@libero.it>
Date: Sat, 21 Jan 2006 01:38:47 CST Raw View
wade@stoner.com wrote:
> So if I missed something, what makes you think the standard does not
> allow this?
I didn't say that. In fact you conviced me that the standard allows this
in the sense that it has the same observable behaviour as the
"non-optimized" version. However, the key point is that the
implementation can perform such optimization only because of the
statement in 3.7.3.1/2 that de facto disallows space-efficient
allocators. The question is: is the cost worth the benefit? Given that
I'm not sure that such an optimization 1) provides a serious benefit and
2) has a wide opportunity of being applicable, my opinion is that the
sentence in 3.7.3.1/2 "shall be suitably aligned for any complete
object" could be relaxed for allocation functions which are members of a
class T to "shall be suitably aligned to any complete object of type T
or derived from T" without a great loss.
Just my opinion.
Ganesh
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: "Gerald Thaler" <gerald.thaler@gmx.de>
Date: Sun, 15 Jan 2006 18:02:38 CST Raw View
Hi, the C++ Standard requires for all user defined operator new
functions that:
"The pointer returned shall be suitably aligned so that it can be
converted to a
pointer of any complete object type and then used to access the object
or array in the storage allocated..." [basic.stc.dynamic.allocation]
This statement is somewhat unclear. Does it really mean, that the
returned pointer must be always suitably aligned for _any_ complete
object type (independent of the size of the actual allocation, even if
only one byte of storage is requested)? If so, that would not allow the
use of space efficient small object allocators.
Thanks,
Gerald
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: wkaras@yahoo.com
Date: Wed, 18 Jan 2006 15:41:44 CST Raw View
Gerald Thaler wrote:
> Hi, the C++ Standard requires for all user defined operator new
> functions that:
>
> "The pointer returned shall be suitably aligned so that it can be
> converted to a
> pointer of any complete object type and then used to access the object
> or array in the storage allocated..." [basic.stc.dynamic.allocation]
>
> This statement is somewhat unclear. Does it really mean, that the
> returned pointer must be always suitably aligned for _any_ complete
> object type (independent of the size of the actual allocation, even if
> only one byte of storage is requested)? If so, that would not allow the
> use of space efficient small object allocators.
I think this is meant to be equivalent to saying "the expresion
static_cast<T *>(operator new (N)), where N is of type size_t,
must result in a valid instance of T * for any (compeletely
defined) type T where sizeof(T) <= N ". (Hopefully, the
Standard has a blanket statement somewhere that would
cover the case where 'new' throws an exception.)
I don't see what how using the terms "suitably aligned", "converted"
and "complete object type" add any clarity, especially if the Standard
doesn't contain identifiable definitions of them. A standard is a
layer of knowledge. Its "top" interface is the thing it's defining.
Its "bottom" interface is the standards it references, plus the
set of terms that the standard uses but does not
itself define. The bottom interface, as much as the top one
(or any other good interface), has to be clearly defined and as
small as possible.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: AlbertoBarbati@libero.it (Alberto Ganesh Barbati)
Date: Thu, 19 Jan 2006 05:51:00 GMT Raw View
wkaras@yahoo.com wrote:
> Gerald Thaler wrote:
>>
>>"The pointer returned shall be suitably aligned so that it can be
>>converted to a
>>pointer of any complete object type and then used to access the object
>>or array in the storage allocated..." [basic.stc.dynamic.allocation]
>>
>>This statement is somewhat unclear. Does it really mean, that the
>>returned pointer must be always suitably aligned for _any_ complete
>>object type (independent of the size of the actual allocation, even if
>>only one byte of storage is requested)? If so, that would not allow the
>>use of space efficient small object allocators.
>
> I think this is meant to be equivalent to saying "the expresion
> static_cast<T *>(operator new (N)), where N is of type size_t,
> must result in a valid instance of T * for any (compeletely
> defined) type T where sizeof(T) <= N ". (Hopefully, the
> Standard has a blanket statement somewhere that would
> cover the case where 'new' throws an exception.)
operator new(N) returns a pointer to uninitialized data, so
static_cast<T *>(operator new (N)) is a pointer to rubbish, certainly
not pointing to a valid instance of type T.
I believe the OP raised an interesting point. Whatever the intent of the
standard is, what it says is that an allocation function CANNOT be used
for space efficient small object allocators. That is a defect in my
opinion. The current wording is certainly correct for an allocation
function that is provided as a global function, because it could be
called for any type. But if an allocation function is provided as a
member of class T, then it will be called only to allocate objects of
complete type T or derived from T. IMHO it's too strict to require that
it should return a pointer "suitably aligned so that it can be converted
to a pointer of ANY complete object type", in this case. I think the
wording could be relaxed in some way. Any comment?
> I don't see what how using the terms "suitably aligned", "converted"
> and "complete object type" add any clarity, especially if the Standard
> doesn't contain identifiable definitions of them.
"Alignment" is defined in 3.9/5. "Conversion" is the subject of the
whole clause 4. "Complete object" is defined in 1.8/2. Please read more
carefully next time.
Ganesh
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: wkaras@yahoo.com
Date: Thu, 19 Jan 2006 12:16:39 CST Raw View
Alberto Ganesh Barbati wrote:
> wkaras@yahoo.com wrote:
> > Gerald Thaler wrote:
> >>
> >>"The pointer returned shall be suitably aligned so that it can be
> >>converted to a
> >>pointer of any complete object type and then used to access the object
> >>or array in the storage allocated..." [basic.stc.dynamic.allocation]
> >>
> >>This statement is somewhat unclear. Does it really mean, that the
> >>returned pointer must be always suitably aligned for _any_ complete
> >>object type (independent of the size of the actual allocation, even if
> >>only one byte of storage is requested)? If so, that would not allow the
> >>use of space efficient small object allocators.
> >
> > I think this is meant to be equivalent to saying "the expresion
> > static_cast<T *>(operator new (N)), where N is of type size_t,
> > must result in a valid instance of T * for any (compeletely
> > defined) type T where sizeof(T) <= N ". (Hopefully, the
> > Standard has a blanket statement somewhere that would
> > cover the case where 'new' throws an exception.)
>
> operator new(N) returns a pointer to uninitialized data, so
> static_cast<T *>(operator new (N)) is a pointer to rubbish, certainly
> not pointing to a valid instance of type T.
It's a valid instance of T * in the sense that a constructor of T can
use it to run the "rubbish" into a valid instance of T. This
illustrates
my point, I needed to define what I meant by "valid instance" of
a pointer.
> I believe the OP raised an interesting point. Whatever the intent of the
> standard is, what it says is that an allocation function CANNOT be used
> for space efficient small object allocators. That is a defect in my
> opinion. The current wording is certainly correct for an allocation
> function that is provided as a global function, because it could be
> called for any type. But if an allocation function is provided as a
> member of class T, then it will be called only to allocate objects of
> complete type T or derived from T. IMHO it's too strict to require that
> it should return a pointer "suitably aligned so that it can be converted
> to a pointer of ANY complete object type", in this case. I think the
> wording could be relaxed in some way. Any comment?
Assuming your interpretation is correct, think about what an
dynamic allocator that violated it would look like. Seems like
it would have to have a bit map of each allocated byte (or
byte pair), with the bits corresponding to the start and end
of an allocated block being set. This sort of allocator would
only make sense for applications that allocated very small
blocks almost exclusively, Or, another posibility would
be an allocator for an application that never really needed
to free memory, that is to say, 'delete' would simply call
the destructor. Maybe the Committee thought these cases
were so odd they wern't worth taking into consideration.
I think ANSI-C's 'malloc()' alignment requirements are
independent of the size of the allocation. So maybe this is
just baggage from C.
>
> > I don't see what how using the terms "suitably aligned", "converted"
> > and "complete object type" add any clarity, especially if the Standard
> > doesn't contain identifiable definitions of them.
>
> "Alignment" is defined in 3.9/5. "Conversion" is the subject of the
> whole clause 4. "Complete object" is defined in 1.8/2. Please read more
> carefully next time.
You are correct that the Standard has a good definition of
"complete object". I don't see anything in clause 4 that's
relevant to the explicit conversion of a void pointer to
a type-specific pointer. I have read that the only
Standard-required valid values of T * are &t where t
is an instance of T, a + i where a is an array of T and
i is a non-negative integral value less than or equal
to the dimension of a (with *(a + dimension) only being
valid for comparison or pointer arithmetic), or
static_cast<T *>(operator new (N)), where
(it may or may not be required that) N >= sizeof(T).
But I don't see how you'd get that from 3.9/5.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: wade@stoner.com
Date: Thu, 19 Jan 2006 12:37:57 CST Raw View
Alberto Ganesh Barbati wrote:
> I believe the OP raised an interesting point. Whatever the intent of the
> standard is, what it says is that an allocation function CANNOT be used
> for space efficient small object allocators. That is a defect in my
> opinion. The current wording is certainly correct for an allocation
> function that is provided as a global function, because it could be
> called for any type. But if an allocation function is provided as a
> member of class T, then it will be called only to allocate objects of
> complete type T or derived from T. IMHO it's too strict to require that
> it should return a pointer "suitably aligned so that it can be converted
> to a pointer of ANY complete object type", in this case. I think the
> wording could be relaxed in some way. Any comment?
The current standard allows the implementation to initialize the
allocated object using word-aligned copies.
struct xy
{
xy():x(0),y(0){}
char x;
char y;
static void* operator new(size_t);
};
If xy has alignment 1, size 2, and int has alignment 2, size 2 the
current standard allows the implementation to translate
return new xy;
into
void* ptr = xy::operator new(2);
*(int*) ptr = 0; // Fast constructor replacement. Fails if
ptr is not suitably aligned.
return (xy*) ptr;
I'm not sure how much this is worth.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: AlbertoBarbati@libero.it (Alberto Ganesh Barbati)
Date: Fri, 20 Jan 2006 00:08:40 GMT Raw View
wkaras@yahoo.com wrote:
>>"Alignment" is defined in 3.9/5. "Conversion" is the subject of the
>>whole clause 4. "Complete object" is defined in 1.8/2. Please read more
>>carefully next time.
>
> You are correct that the Standard has a good definition of
> "complete object". I don't see anything in clause 4 that's
> relevant to the explicit conversion of a void pointer to
> a type-specific pointer. I have read that the only
> Standard-required valid values of T * are &t where t
> is an instance of T, a + i where a is an array of T and
> i is a non-negative integral value less than or equal
> to the dimension of a (with *(a + dimension) only being
> valid for comparison or pointer arithmetic), or
> static_cast<T *>(operator new (N)), where
> (it may or may not be required that) N >= sizeof(T).
> But I don't see how you'd get that from 3.9/5.
Of course you don't see how you get that from 3.9/5 because, as I said,
it only contains the definition of "alignment". It was not expected to
contain anything about conversions.
I agree that the reference to clause 4 was not resolutive as it contains
the definition of only the conversion from T* to void* (4.10/2), but in
this case we are converting in the opposite direction. The conversion
from void* to T* is described in 5.2.9/10 about static_cast. However,
you might find more interesting subclause 3.8 about object lifetime,
which covers pointers to uninitialized memory.
Ganesh
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Author: cbarron413@adelphia.net (Carl Barron)
Date: Fri, 20 Jan 2006 00:08:43 GMT Raw View
In article <1137683497.446014.27060@o13g2000cwo.googlegroups.com>,
<wade@stoner.com> wrote:
>
> The current standard allows the implementation to initialize the
> allocated object using word-aligned copies.
>
> struct xy
> {
> xy():x(0),y(0){}
> char x;
> char y;
> static void* operator new(size_t);
> };
>
> If xy has alignment 1, size 2, and int has alignment 2, size 2 the
> current standard allows the implementation to translate
>
> return new xy;
>
> into
>
> void* ptr = xy::operator new(2);
> *(int*) ptr = 0; // Fast constructor replacement. Fails if
> ptr is not suitably aligned.
> return (xy*) ptr;
it also allows the layout of xy to be as if
char x
char fill_1[sizeof(int)-1]
char y
char fill_2[sizeof(int)-1]
were started where a double could be started. the result of your 'fast'
construction is no longer even going to store data in is proper place.
How the interior padding is assigned if any is an implementation detail
and not written in the language. There is no guarantee that
sizeof(struct xy) == 2 either.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]