Checking up on realloc efficiency
tedunangst.com
tedunangst.com
It's frankly boring that 20 years later we still feel attracted to discuss any of this stuff. It's not like the machines or the code running on them have fundamentally changed in the interim..
Another example, I might be wrong here though, is the ooold disk handling code in BSD, where you had to specify cylinders, heads and other things, and the OS tried to optimize performance based on closeness. See here for more info: http://www.cdf.toronto.edu/~csc369h/fall/lectures/w10/DiskIO...
Today, I imagine most I/O interfaces use a large block index instead of cyl/disk/head and other ancient specifications. All the optimizations about head and so on is device dependent and is best handled by the disk itself.
Imagine the feeling of being able to delete old code in the disk subsystem and get a cleaner and more abstract view of the disk.
Isn't that a tradeoff of memory utilization vs. CPU? The memory holes you leave sitting around for a potential realloc() is memory that will be wasted if realloc() never comes, or if the new size is too big to fit anyway.
Any because of cache behavior, bad memory utilization is a CPU efficiency issue too.
So what's the right tradeoff here? That's what I was hoping to see in this article, but I didn't see any evaluation of that tradeoff. Since it is inherently a tradeoff, it seems like it needs to be a data-driven decision rather than working exclusively from first principles.
On 32-bit systems that fragmentation could potentially be a problem, but it's unlikely. The problem would come up if you did something like allocate 1GB worth of small allocations then suddenly tried to allocate a single 1GB allocation.
In practice this tends to not really happen, either, so the holes remain free.
Note that there is no scenario in which the holes cost actual RAM usage. It's purely the usage of the virtual address space, no machine resources are ever consumed by the holes.
If pages were one byte long, what you say would be (mostly) true. For every allocation, you would just map in some memory at some random place in the address space, and you would map in precisely as many bytes as were requested. You would literally waste no memory, and your reallocs would never need to move memory. Life would be bliss.
But pages are not one byte long. They are usually something like 4k. So if you fulfill a 1-byte malloc() with a 4k page (to leave room for realloc()), you are wasting nearly 4k bytes of real physical memory.
Also: mmap() system calls have CPU overhead, and I highly suspect that two non-contiguous mapped pages create more kernel overhead than two contiguous mapped pages.
Holes are not free.
I think, in some cases, spaced allocation will come (nearly) for free, since with 64bit addressing, there is enough space reserve (most processors can only use a fraction of this space as physical RAM). The other point is, that with the use of MMUs and a proper spacing (regarding the MMUs page size), the gaps come nearly "for free".
But I think, that needs very careful thought, to make it right and not unnecessarily introduce new tradeoffs, as you very talking about.
What you should not do, is use such spacing for small allocations. An other point would be, to inform the allocator, that it is likely/unlikely that a reallocation will be done ... in most cases, such information is available.
I agree. A lot of blocks which get allocated are never resized (e.g. objects), while other blocks may be subjected to frequent resizing - expanding buffers and strings being the most common example. malloc()/realloc() are very simple APIs, and work for the general purpose of "I want to allocate some memory/resize it", but this simplicity also means that they can't take advantage of specific usage patterns very well.
Working with data of indeterminate size is always going to involve more complexity, and while it may look like a solved problem (just resize when there is not enough space left) as evidenced by the proliferation of string implementations in various languages, the efficiency aspects are more subtle and still well within the area of "programmer must know what he/she is doing". Designing systems and protocols that don't need resizing of allocations, for example (how long something is, is easily calculated and known in advance.)