malloc seems to be designed without free or realloc in mind. it only returns the pointer to the start of the memory block but free and realloc especially both require knowledge of the size of the block.
This requires that the allocator keeps meta data somewhere about the block size at the very least. Most often as a prefix. But that muddles things like keeping alignment and changes the optimal allocation sizes to something less than multiple of a power of 2.
A common construct using a general allocator is a dynamically allocated array (like std::vector), which would benefit from knowing the actual size of the block it allocated which make it automatically use the optimal allocation size.
I believe a simple change to the api would help with that:
change malloc to "void* malloc(size_t size, size_t* allocated size)" (or make it return a struct memblock{void*;size_t;}) and free to "void free(void* mem, size_t size)" This size should be between the originally requested size and the allocated size.
A further improvement would be to pass the calling code a pointer to the meta data of the block and require that it passes it back to free and realloc, but making the user code track 2 pointers and requiring that they stay together seems like a recipe for disaster.
This requires that the allocator keeps meta data somewhere about the block size at the very least. Most often as a prefix. But that muddles things like keeping alignment and changes the optimal allocation sizes to something less than multiple of a power of 2.
A common construct using a general allocator is a dynamically allocated array (like std::vector), which would benefit from knowing the actual size of the block it allocated which make it automatically use the optimal allocation size.
I believe a simple change to the api would help with that:
change malloc to "void* malloc(size_t size, size_t* allocated size)" (or make it return a struct memblock{void*;size_t;}) and free to "void free(void* mem, size_t size)" This size should be between the originally requested size and the allocated size.
A further improvement would be to pass the calling code a pointer to the meta data of the block and require that it passes it back to free and realloc, but making the user code track 2 pointers and requiring that they stay together seems like a recipe for disaster.
malloc would be fine if it was just a convenience function in a random lib, but as a crt function it is limiting in both how it dictates through its api how it is going to be implemented and from a flexibility standpoint. In my opinion, the signature of the three allocation functions should look like this:
This lets the library implementers take as many liberties as they want, since neither the size nor the alignment needs to be stored anywhere from their perspective. Note how the alignment is even needed when freeing (this allows stack allocators to be able to free stuff at the back).
Now, supplying the alignment for each invocation might be inconvenient, so one might argue that these functions should always return max_align_t aligned memory (which malloc basically does). This wastes potentially a bit of memory, but is a nicer api, but custom alignments go out the window with that.
New/delete suffer from the same problems. They should too take a size and alignment parameters, they could even have the benefit of supplying the alignment and element size themselves, since they know the type they are allocating. But they don't. (This will be fixed in C++1z afaik, they will be taking an alignment parameter then finally)
1 2 3 | void* malloc( size_t size, size_t alignment ); void* realloc( void* ptr, size_t newSize, size_t oldSize, size_t alignment ); void free( void* ptr, size_t size, size_t alignment ); |
This lets the library implementers take as many liberties as they want, since neither the size nor the alignment needs to be stored anywhere from their perspective. Note how the alignment is even needed when freeing (this allows stack allocators to be able to free stuff at the back).
Now, supplying the alignment for each invocation might be inconvenient, so one might argue that these functions should always return max_align_t aligned memory (which malloc basically does). This wastes potentially a bit of memory, but is a nicer api, but custom alignments go out the window with that.
New/delete suffer from the same problems. They should too take a size and alignment parameters, they could even have the benefit of supplying the alignment and element size themselves, since they know the type they are allocating. But they don't. (This will be fixed in C++1z afaik, they will be taking an alignment parameter then finally)
Edited by TM
on
I'm not 100% convinced that aligned allocation is a primary concern for most developers using malloc, sure its good when you're considering nitty gritty performance tuning but if you're software has other bottlenecks it might be moot to think about, and it almost certainly not the first thing you should be thinking about. Also the standard library does offer an aligned version of malloc. And while I don't have a better API/solution to offer, "void* malloc(size_t size, size_t* allocated size)" still requires user code to keep that allocated size around, so its really same as requesting an allocated size and storing it.
Floresy
And while I don't have a better API/solution to offer, "void* malloc(size_t size, size_t* allocated size)" still requires user code to keep that allocated size around, so its really same as requesting an allocated size and storing it.
that's why I said the calling code could send back any size between the requested and the allocated size inclusive. I did forget to mention the caveat that it must be no less that what was written to. Then you can use some magic values in the preinitialized memory to get the proper size.
This allows calling code to do a free(object, sizeof(*object)) and still work fine.
Hmmm, I take back the "i'm not convinced", and I'd rather say that I just don't get it. I can't quite get my head around what your suggested use case should be, compared to how I understand the current "standard" to be
My current understanding of aligned allocation:
0x---Some Address: start of actually allocated memory
----------
n - 1 bytes of padding
last byte: record of how many bytes were used to pad
----------
0x + n: return value, start of user data of size that user requested...
My current understanding of aligned allocation:
0x---Some Address: start of actually allocated memory
----------
n - 1 bytes of padding
last byte: record of how many bytes were used to pad
----------
0x + n: return value, start of user data of size that user requested...
Floresy
Hmmm, I take back the "i'm not convinced", and I'd rather say that I just don't get it. I can't quite get my head around what your suggested use case should be, compared to how I understand the current "standard" to be
My current understanding of aligned allocation:
0x---Some Address: start of actually allocated memory
----------
n - 1 bytes of padding
last byte: record of how many bytes were used to pad
----------
0x + n: return value, start of user data of size that user requested...
Because when you know the max alignment that will ever be requested then you can do
0x---Some address already aligned by max == return value
...
0x + s end of requested block
bytes filled with values to let free and realloc find the metadata (like number of bytes until start of metadata)
0x + n*align - k end of usable memory, size of it is returned
---
k bytes of meta data
0x + n*align end of block aligned to the max align
This is possible because if you use VirtualAlloc or mmap as the underlying allocator, you will get blocks aligned to page boundaries which is more alignment than you need for most things.
And because of the magic values in the block itself to find the size of the block you don't need to know the alignment of the block to find the meta data.
Edited by ratchetfreak
on
Floresy
I'm not 100% convinced that aligned allocation is a primary concern for most developers using malloc, sure its good when you're considering nitty gritty performance tuning but if you're software has other bottlenecks it might be moot to think about, and it almost certainly not the first thing you should be thinking about. Also the standard library does offer an aligned version of malloc.
Well, memory allocations always need to be aligned, the only reason malloc doesn't take an alignment value is because it always maximally aligns.
The problem with malloc isn't just alignment. If you were to implement malloc as is, you can't write a good performing allocator, just because of the api. Having the allocator store the size of allocated regions is bad. Whenever you free something, more likely than not, that thing you are freeing isn't in the cache. If the allocator then goes and reads from that region to get the size, you get a cachemiss every single time. Even if custom alignment isn't important most of the time, allocator performance itself is.
The api that I suggested makes it so that you as the library implementer are given the most freedom when it comes to implementing an allocator.
Floresy
And while I don't have a better API/solution to offer, "void* malloc(size_t size, size_t* allocated size)" still requires user code to keep that allocated size around, so its really same as requesting an allocated size and storing it.
When has anybody ever allocated memory and not stored the size somewhere? As it is, almost all C programs basically store the size of allocated memory twice in their programs because of C and malloc.
The only usecase for not keeping the size around after allocation is if you are allocating null terminated strings, and that is not a good enough reason. First of all, almost nobody really uses null terminated strings as is. We just enforce a null at the end of strings, but everybody still keeps at least a capacity value around, so that inserting/removing chars doesn't incur an allocation all the time. Second of all, you don't need malloc itself to keep the size information to be able to allocate and free nullterminated strings. Just use a different api for string allocations.
We already treat nullterminated strings differently than memory blocks. There is memchr and strchr, memcpy and strcpy etc etc.
Why not have stralloc and strfree for that single usecase of not needing a size?
Here is an even an implementation using the improved malloc:
1 2 3 4 5 6 7 8 9 10 11 12 | char* stralloc( size_t size )
{
char* result = (char*)malloc( size + sizeof( size_t ), alignof( char ) );
memcpy( result, &size, sizeof( size_t ) );
return result + sizeof( size_t ) );
}
void strfree( char* str )
{
size_t size;
memcpy( &size, str - sizeof( size_t ), sizeof( size_t ) );
free( str - sizeof( size_t ), size, alignof( char ) );
}
|
There you go, malloc is fixed and doesn't treat every single allocation as allocating strings.
CrankyWhen malloc was first implemented memory didn't need to be aligned. It's only later when cache became a thing is that alignment started to matter. (so a load/store only touched one cache line)Floresy
I'm not 100% convinced that aligned allocation is a primary concern for most developers using malloc, sure its good when you're considering nitty gritty performance tuning but if you're software has other bottlenecks it might be moot to think about, and it almost certainly not the first thing you should be thinking about. Also the standard library does offer an aligned version of malloc.
Well, memory allocations always need to be aligned, the only reason malloc doesn't take an alignment value is because it always maximally aligns.
Crankyor the size allocated is static (the size of a specific struct)
Floresy
And while I don't have a better API/solution to offer, "void* malloc(size_t size, size_t* allocated size)" still requires user code to keep that allocated size around, so its really same as requesting an allocated size and storing it.
When has anybody ever allocated memory and not stored the size somewhere? As it is, almost all C programs basically store the size of allocated memory twice in their programs because of C and malloc.
Cranky
The only usecase for not keeping the size around after allocation is if you are allocating null terminated strings, and that is not a good enough reason. First of all, almost nobody really uses null terminated strings as is. We just enforce a null at the end of strings, but everybody still keeps at least a capacity value around, so that inserting/removing chars doesn't incur an allocation all the time. Second of all, you don't need malloc itself to keep the size information to be able to allocate and free nullterminated strings. Just use a different api for string allocations.
We already treat nullterminated strings differently than memory blocks. There is memchr and strchr, memcpy and strcpy etc etc.
Why not have stralloc and strfree for that single usecase of not needing a size?
Here is an even an implementation using the improved malloc:
char* stralloc( size_t size ) { char* result = (char*)malloc( size + sizeof( size_t ), alignof( char ) ); memcpy( result, &size, sizeof( size_t ) ); return result + sizeof( size_t ) ); } void strfree( char* str ) { size_t size; memcpy( &size, str - sizeof( size_t ), sizeof( size_t ) ); free( str - sizeof( size_t ), size, alignof( char ) ); }
There you go, malloc is fixed and doesn't treat every single allocation as allocating strings.
hey look! pascal strings...