In my code I don't use allocated_length and used_length seperately in dynamic vectors. Simply realloc() every time one element is added. No measurable difference in speed, and code is much more clean.
I just tried some simple "I want to grow my block of memory" test cases. A malloc of 1000 bytes couldn't be increased by a single byte without being moved to a new location. An allocation of 1 million bytes couldn't be increased by 1% without being moved to a new location.
#include <stdio.h>
#include <stdlib.h>
int main(){
int same=0;
int moved=0;
char* temp=malloc(16);
for(int i=0; i<10000; i++){
char* temp2=realloc(temp,(i+2)*16);
if(temp!=temp2){
moved++;
temp=temp2;
}
else same++;
}
printf("ptr moved %d, reused %d times\n",moved,same);
}
But, what you want to test is what you identify as your need.
No point in explaining more.
This only works with some malloc implementations. There are platforms where this will result in quadratic behavior, so don't do this if you want to write portable code.
Interesting idea to skip explicitly tracking capacity with realloc though. That does seem convenient, and if the allocator is fast, sure, why not?
That’s true.
> Most of the time it will simply bump up the allocation end point
That depends on your allocator and usage patterns. I would think that, in real world usage, it will reallocate fairly frequently, but don’t have and can’t find data on that.
Reason is that I would expect the allocator to, normally, allocate blocks tight together and most reallocations to grow the size by more than the granularity of the memory allocator (which typically is in the order of 16 bytes)
The latter often applies too if you “don't use allocated_length and used_length seperately in dynamic vectors. Simply realloc() every time one element is added”
Or am I wrong? How large is your initial alloc?
Edit: slab allocators may show such good behavior.
Zero. Most of the time. When I don't know the exact requirement before hand.
> Reason is that I would expect the allocator to, normally, allocate blocks tight together and most reallocations to grow the size by more than the granularity of the memory allocator
Now look at it like this. Even if I wrote my own allocator with malloc(), free() and realloc(), I would have written it such a way that the first time I found a pointer getting realloc()-ed I would have added an extra 60% at its end assuming this pointer has a trend to grow. And for subsequent small increment calls use space at the end.
I don't see why C library's allocator writers wouldn't have thought the same. Even if on some platform it's not done for some reason, that can be replaced with your own implementation.
Add with it the fact that OS is also optimizing your memory usage, your allocs are virtual pages mapped to actual physical ram. And who knows how deep these caches go at processor level. You are basically caching over caching and so on.
This is similar to "reading a file in memory" because "accessing from disk is so slow". That's so much 90s thought. Your file will be cached in memory by the OS whenever you access it the first time and you have sufficient free RAM available for cache.
But one doesn't need to assume the above to be true. Simply measure and check for yourself. If your findings don't match your understandings, there are alternate explanations.
Isn't this exactly what is done in the submitted post?
> But one doesn't need to assume the above to be true. Simply measure and check for yourself. If your findings don't match your understandings, there are alternate explanations.
The problem with this is that this costs extra work to assert, and to assert that it stays true over time.
I know it's the right thing to integrate tightly within a platform, especially when the application has to coexist with others (like in Desktop apps, unlike in Games). But when one doesn't exactly know the platform that the code is going to be running on, or when it needs to run on a multitude of platforms, this integration can be painful.
That's why I often prefer interfaces that give me a lot of control over what happens, or that specify exactly what the implementation does, including the performance characteristics.
And, as far as I can tell on the most common implementations, `realloc` just does a pointer adjustment when you shrink[1] the array, so the next `realloc` to expand the array again simply does the pointer bump thing.
Over time[2], you effectively get a arena allocator from that single realloc()ed block just by expanding and shrinking the array.
[1] Just don't call `realloc (0, ...)`
[2] For my next project I'm going to make an arena-allocator interface that is just a thin wrapper around realloc.