7 ms·
Checking up on realloc efficiency
- hosay123 12y agoTed's C programming posts make me feel really old, because I can remember exactly the same programming topics being discussed in the mid 90s. And that's C development for you, really.. every old bug is new again. 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..
- Flow 12y agoNot fundamentally changed, but some things have become more expensive so old assumptions and optimisations should be re-evalued, it's just sound engineering really.
- userbinator 12y agoOne of the best examples of this being the increasing gap between memory and CPU speeds. Good cache usage is far more important than before.
- Flow 12y agoYes, I had that example in mind. 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.pdf 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.
- haberman 12y agoIf I'm reading this right, it is advocating that malloc() calls be spaced in memory to increase the likelihood that realloc() won't need to relocate/copy the memory. 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.
- faragon 12y agoNo, it is not wasted. The "holes" come with exact allocation. Making malloc block granularity bigger reduces memory internal fragmentation.
- haberman 12y agoLeaving holes is not free. There is an inherent tradeoff. That is all I am saying.
- kllrnohj 12y agoThe only cost is virtual address space fragmentation. Which, if you're 64-bit, is pretty much a non-existent problem as the address space is so absurdly larger than the amount of memory you have. Meaning the holes are entirely free. 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.
- haberman 12y ago