4 ms·

If 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 me

If 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 ago
No, it is not wasted. The "holes" come with exact allocation. Making malloc block granularity bigger reduces memory internal fragmentation.
- haberman 12y ago
  Leaving holes is not free. There is an inherent tradeoff. That is all I am saying.
  - kllrnohj 12y ago
    The 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
      It's not as simple as that, because pages are more than one byte long. 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.
PythonicAlpha 12y ago
More discussion would really help here. 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.
- userbinator 12y ago
  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.)
  - PythonicAlpha 12y ago
    The "one size fits it all" notion of malloc/free/realloc is just wrong. When you want optimal allocation performance, you can't get around specialized allocators of various sorts for various needs.
X-Istence 12y ago
malloc() is already going to be randomized though for security reasons. The test just verifies that the randomization also leaves enough space for a realloc() to be fast and efficient rather than having the randomization putting all of the malloc() calls into a very small area, thereby making realloc() always move the data to a new location.

faragon 12y ago

No, it is not wasted. The "holes" come with exact allocation. Making malloc block granularity bigger reduces memory internal fragmentation.

haberman 12y ago
Leaving holes is not free. There is an inherent tradeoff. That is all I am saying.
- kllrnohj 12y ago
  The 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
    It's not as simple as that, because pages are more than one byte long. 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.

PythonicAlpha 12y ago

More discussion would really help here. 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.

userbinator 12y ago
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.)
- PythonicAlpha 12y ago
  The "one size fits it all" notion of malloc/free/realloc is just wrong. When you want optimal allocation performance, you can't get around specialized allocators of various sorts for various needs.

X-Istence 12y ago

malloc() is already going to be randomized though for security reasons. The test just verifies that the randomization also leaves enough space for a realloc() to be fast and efficient rather than having the randomization putting all of the malloc() calls into a very small area, thereby making realloc() always move the data to a new location.