<p>Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes of memory.</p>

<p>Additionally, the buddy system achieves this bound and can be done in logarithmic time.</p>

CC BY-SA 3.0
2015-04-08T13:23:25.920Z
Thanks for the reference.  I do allow to move the allocated objects around (otherwise it looks fairly easy to come up with a bad example).  Does the lower bound you mention still apply?
Manu
CC BY-SA 3.0
2015-04-08T14:47:20.330Z
Not to my knowledge. You might want to post a new question about this, since it's so different from how malloc actually operates. One question you'll have to consider, for instance, is the question of what time cost you'll assign to the operation of moving a block of size $m$. You can read a bit about this in [Bender et al.'s "Maintaining Arrays of Contiguous Objects"](https://www3.cs.stonybrook.edu/~bender/newpub/BenderFeKa09-fct.pdf).
jbapple
CC BY-SA 3.0
2015-04-08T15:03:38.730Z
Note that, if the cost of moving a block is linear in its size, and if blocks must be contiguous between calls to malloc/free, then algorithms taking $O(\log n)$ time in the worst case can never move large blocks once they are placed. As a result, patterns like the ones described by Robson may still be possible, thus forcing superlinear space usage.
jbapple
CC BY-SA 3.0
2015-03-31T02:18:38.243Z
2015-03-31T02:34:48.617Z
2015-03-31T02:34:48.617Z
jbapple
<p>This paper, <a href="http://dl.acm.org/citation.cfm?id=3070693" rel="nofollow noreferrer">http://dl.acm.org/citation.cfm?id=3070693</a>, exactly addresses the question of memory allocation where you can move things but at a cost.</p>

CC BY-SA 3.0
2017-07-12T15:26:05.033Z
2017-07-12T15:26:05.033Z
Martin Farach-Colton
<p>Think of the cell-probe model.  Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and executes every operation in <strong>worst-case</strong> deterministic O(log n) time where n is the total size of the memory?</p>

<p>By avoiding memory segmentation I mean that if the total number of free cells is F, then I should be able to allocate a contiguous segment of F cells or about F cells.</p>

<ds.data-structures><memory>
Data structure for dynamic memory allocation
Manu
# Data structure for dynamic memory allocation

(Asked by: username_0 on 2015-03-12)

Think of the cell-probe model. Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and executes every operation in **worst-case** deterministic O(log n) time where n is the total size of the memory?

By avoiding memory segmentation I mean that if the total number of free cells is F, then I should be able to allocate a contiguous segment of F cells or about F cells.

**Tags:** ds.data-structures, memory

---

## 2 answers

### Answer by username_1 on 2015-03-31. Score: 6

Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes of memory.

Additionally, the buddy system achieves this bound and can be done in logarithmic time.

> **Comments:**
> **username_0**: Thanks for the reference.  I do allow to move the allocated objects around (otherwise it looks fairly easy to come up with a bad example).  Does the lower bound you mention still apply?  
> **username_1**: Not to my knowledge. You might want to post a new question about this, since it's so different from how malloc actually operates. One question you'll have to consider, for instance, is the question of what time cost you'll assign to the operation of moving a block of size $m$. You can read a bit about this in [Bender et al.'s "Maintaining Arrays of Contiguous Objects"](https://www3.cs.stonybrook.edu/~bender/newpub/BenderFeKa09-fct.pdf).  
> **username_1**: Note that, if the cost of moving a block is linear in its size, and if blocks must be contiguous between calls to malloc/free, then algorithms taking $O(\log n)$ time in the worst case can never move large blocks once they are placed. As a result, patterns like the ones described by Robson may still be possible, thus forcing superlinear space usage.  

---

### Answer by username_2 on 2017-07-12. Score: 4

This paper, <http://dl.acm.org/citation.cfm?id=3070693>, exactly addresses the question of memory allocation where you can move things but at a cost.


---

