malloc() and alignment

[Francine.Neary]

I've been trying to understand the design decision to have one (well,
three of course, but essentially one) allocation function that returns
a pointer guaranteed to be aligned for any type.

It seems to me that there's a tradeoff here between flexibility and
efficiency. It's easy to imagine on a 64-bit machine that, say, a long
or a pointer would need to be aligned at an 8-byte boundary. Then if
you have a program with a large number of strings, for example, then
you'd potentially be losing 7 bytes of memory for each one! (I guess
chars can always take any alignment)

I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

[Ian Collins]

Fr************@googlemail.com wrote:

I've been trying to understand the design decision to have one (well,
three of course, but essentially one) allocation function that returns
a pointer guaranteed to be aligned for any type.

It seems to me that there's a tradeoff here between flexibility and
efficiency. It's easy to imagine on a 64-bit machine that, say, a long
or a pointer would need to be aligned at an 8-byte boundary. Then if
you have a program with a large number of strings, for example, then
you'd potentially be losing 7 bytes of memory for each one! (I guess
chars can always take any alignment)

Potentialy more, it all depends how the system breaks down available memory.

On every project I've worked on over the past couple of decades, I've
added profiling allocator as a testing tool. In every case the
allocation sizes where predominantly multiples of the machine word size.
Most allocations were for structures.

I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

No one wants it?

--
Ian Collins.

[Eric Sosman]

Fr************@googlemail.com wrote:

I've been trying to understand the design decision to have one (well,
three of course, but essentially one) allocation function that returns
a pointer guaranteed to be aligned for any type.

It seems to me that there's a tradeoff here between flexibility and
efficiency. It's easy to imagine on a 64-bit machine that, say, a long
or a pointer would need to be aligned at an 8-byte boundary. Then if
you have a program with a large number of strings, for example, then
you'd potentially be losing 7 bytes of memory for each one! (I guess
chars can always take any alignment)

I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

It might be instructive to implement your own malloc()
et al. to gain familiarity with some of the issues. There's
a fairly simple version in K&R (the original; I imagine it's
also in K&R II but I don't know for sure) that you could use
as a starting point.

One thing you'll probably discover is that malloc() often
reserves a little more space than is requested, space in which
it can park some housekeeping data. That data typically takes
at least as much space as a size_t, perhaps more. It's surely
most convenient if the housekeeping data itself is properly
aligned, which in turn influences the alignment of the entire
inflated chunk. And if you already need alignment sufficient
for a size_t, it's usually no hardship to provide "strictest"
alignment.

Of course, not all allocators follow the straightforward
K&R style. Some, for example, avoid storing housekeeping data
along with every allocation by allowing the address itself to
imply the housekeeping: If the address is in THIS region of
memory, it refers to an object of THAT size and we need not
store the size explicitly. (This is one reason why realloc()
might fail when shrinking an area.) Such an allocator might
be able to dish out single-byte allocations without undue
penalties, but those I've actually seen in practice have used
a larger "minimum allocation" size.

Long ago, c.l.c. debated whether malloc(1) needed to provide
memory that was properly aligned for double, say, in the common
situation where sizeof(double)>1. One side stuck to the letter
of the Standard: the returned value had to be properly aligned
for any type, and that was that. The other side pointed out that
any attempt to store a double in the 1-byte region would invoke
undefined behavior anyhow, hence no strictly conforming program
could run afoul of looser alignment for small allocations; the
difference made no difference. If I recall correctly, the strict
Standard constructionists carried the day, but it was more due
to volume than to virtue.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Keith Thompson]

Eric Sosman <es*****@acm-dot-org.invalidwrites:

Fr************@googlemail.com wrote:

[...]

>I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.
Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

[...]

>
One thing you'll probably discover is that malloc() often
reserves a little more space than is requested, space in which
it can park some housekeeping data. That data typically takes
at least as much space as a size_t, perhaps more. It's surely
most convenient if the housekeeping data itself is properly
aligned, which in turn influences the alignment of the entire
inflated chunk. And if you already need alignment sufficient
for a size_t, it's usually no hardship to provide "strictest"
alignment.

Also, back when malloc() was first designed, it's likely that the
strictest alignment requirement possible was just 2 bytes, or maybe 4
(think PDP-11 and friends), so malloc()'s alignment requirement
wouldn't have wasted much space.

[...]

Long ago, c.l.c. debated whether malloc(1) needed to provide
memory that was properly aligned for double, say, in the common
situation where sizeof(double)>1. One side stuck to the letter
of the Standard: the returned value had to be properly aligned
for any type, and that was that. The other side pointed out that
any attempt to store a double in the 1-byte region would invoke
undefined behavior anyhow, hence no strictly conforming program
could run afoul of looser alignment for small allocations; the
difference made no difference. If I recall correctly, the strict
Standard constructionists carried the day, but it was more due
to volume than to virtue.

Another argument in that debate is that just assigning a misaligned
pointer value invokes undefined behavior. For example, this:

void *ptr = malloc(1);
assert(ptr != NULL);
double *dptr = ptr;

must work properly; dptr's value must be distinct from the address of
any double object, and you must be able to detect this using "==" or
"!=". If assigning a misaligned pointer value to a double* causes a
trap, this implies that the result of malloc(1) must be properly
aligned.

If, on the other hand, assigning a misaligned pointer value to a
double* doesn't cause a trap (until you try to dereference it), then
an implementation could get away with having malloc(1) return a
misaligned pointer; it arguably would violate the standard, but the
violation would be difficult to detect.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Francine.Neary]

On Apr 2, 12:25 am, Ian Collins <[e-mail]:

I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

I don't think that's a valid argument - you still can't make those
casts now. For example, if you try
char c=42;
long l=*((long *) &c);
Then whether l contains 42 or not depends (as I understand it) on the
endienness of your machine, so already you can't do this sort of cast
portably.

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

No one wants it?

--
Ian Collins.

[Francine.Neary]

On Apr 2, 8:51 am, [e-mail] wrote:

On Apr 2, 12:25 am, Ian Collins <[e-mail]:

I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

I don't think that's a valid argument - you still can't make those
casts now. For example, if you try
char c=42;
long l=*((long *) &c);
Then whether l contains 42 or not depends (as I understand it) on the
endienness of your machine, so already you can't do this sort of cast
portably.

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

No one wants it?

Oops, sorry, meant to reply to this bit too...

....and ask: why not? If someone's using a language where they have to
manage memory themselves, it seems quite possible to me that they'd be
generally concerned about resource usage. And in that situation,
surely they'd want something to avoid a 7x wastage of memory?

[Ian Collins]

Fr************@googlemail.com wrote:

On Apr 2, 12:25 am, Ian Collins <[e-mail]:

>>>I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

I don't think that's a valid argument - you still can't make those
casts now. For example, if you try
char c=42;
long l=*((long *) &c);
Then whether l contains 42 or not depends (as I understand it) on the
endienness of your machine, so already you can't do this sort of cast
portably.

You know and more importantly, the compiler knows c is a char. If we
have void* pointers that can't be cast to anything other than (unsigned)
char*, we have a new class of void*.

--
Ian Collins.

[Ian Collins]

Fr************@googlemail.com wrote:

On Apr 2, 8:51 am, [e-mail] wrote:

>>

>>>>Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

>>>No one wants it?

Oops, sorry, meant to reply to this bit too...

....and ask: why not? If someone's using a language where they have to
manage memory themselves, it seems quite possible to me that they'd be
generally concerned about resource usage. And in that situation,
surely they'd want something to avoid a 7x wastage of memory?

Then you manage your own memory, or as is often the case on small
systems, don't use dynamic memory allocation. As I said earlier, in
systems I have worked on, the vast majority of allocations were
multiples of the machine word size.

--
Ian Collins.

[Keith Thompson]

Fr************@googlemail.com writes:

On Apr 2, 8:51 am, [e-mail] wrote:

>On Apr 2, 12:25 am, Ian Collins <[e-mail]:

[...]

Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

No one wants it?

Oops, sorry, meant to reply to this bit too...

...and ask: why not? If someone's using a language where they have to
manage memory themselves, it seems quite possible to me that they'd be
generally concerned about resource usage. And in that situation,
surely they'd want something to avoid a 7x wastage of memory?

The waste isn't nearly that bad. The overhead imposed by alignment
requirements is likely to be less than that imposed by the need for
bookkeeping information. And in real code, it's rare to allocate a
single byte at a time. Most allocations are either for a buffer of
some significant size, or of a structure.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Francine.Neary]

On Apr 2, 9:43 am, Ian Collins <[e-mail]:

[e-mail] wrote:

On Apr 2, 12:25 am, Ian Collins <[e-mail]:

>>I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

>Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

I don't think that's a valid argument - you still can't make those
casts now. For example, if you try
char c=42;
long l=*((long *) &c);
Then whether l contains 42 or not depends (as I understand it) on the
endienness of your machine, so already you can't do this sort of cast
portably.

You know and more importantly, the compiler knows c is a char. If we
have void* pointers that can't be cast to anything other than (unsigned)
char*, we have a new class of void*.

I think you have misinterpreted what I said. I intended to propose
that there should be the following functions:
void *malloc(size_t size);
char *malloc_char(size_t size);
int *malloc_int(size_t size);

[Eric Sosman]

Fr************@googlemail.com wrote On 04/02/07 03:53,:

On Apr 2, 8:51 am, [e-mail] wrote:

>>On Apr 2, 12:25 am, Ian Collins <[e-mail]:

>>>>I'd say the situation would be greatly improved by having eg three
types of allocation function:
1) malloc, generic allocator, same as current malloc
2) malloc_char, returns a pointer only guaranteed to be aligned for
char
3) malloc_int, same but for int.

>>>Imagine the pain involved in keeping track of what type a pointer is and
what it can and can not be cast to.

I don't think that's a valid argument - you still can't make those
casts now. For example, if you try
char c=42;
long l=*((long *) &c);
Then whether l contains 42 or not depends (as I understand it) on the
endienness of your machine, so already you can't do this sort of cast
portably.

>>>>Is there a good reason something like this isn't in the Standard? And
no implementations seem to have a facility like this either.

>>>No one wants it?

Oops, sorry, meant to reply to this bit too...

...and ask: why not? If someone's using a language where they have to
manage memory themselves, it seems quite possible to me that they'd be
generally concerned about resource usage. And in that situation,
surely they'd want something to avoid a 7x wastage of memory?

I'm not at all sure how you get from "as many as seven
extra bytes" to "7x wastage." Are you in politics? ;-)

The average loss for eight-byte alignment, assuming a
population of random string lengths, is (0+1+...+7)/8 = 3.5
bytes per string, quite possibly less space than an int. And
there's no guarantee you could actually reclaim and use the
leftovers even if you wanted to: If you allocate a nine-byte
string (wasting the worst-case seven bytes) and the very next
allocation is for a double, you'll either lose the seven bytes
anyhow or you'll need to manage memory in multiple "arenas"
for different allocations. Some mallocators do in fact use
multiple arenas, but not for this purpose (or at any rate, not
for this purpose alone).

And then there's the matter of malloc's own bookkeeping: It
must leave enough breadcrumbs so free can discover the extent
of the released block given only a pointer to its start. If
(as is often done) these breadcrumbs adjoin the allocated memory,
you'll probably want to ensure that they themselves are properly
aligned; this most likely implies alignment at least good enough
for a size_t. If that's eight-byte alignment you're right back
where you started; if it's four-byte alignment the average
"recoverable loss" is only (0+1+2+3)/4 = 1.5 bytes per string.
We are not talking about a huge savings here ...

Again, I encourage you to spend some time writing a malloc-
workalike of your own. I'm sure it will give you much greater
familiarity with the issues, opportunities, and trade-offs
than you appear to have at the moment.

--
Er*********@sun.com