13
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Manu
    Apr 8, 2015 at 13:23
  • $\begingroup$ 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". $\endgroup$
    – jbapple
    Apr 8, 2015 at 14:47
  • $\begingroup$ 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. $\endgroup$
    – jbapple
    Apr 8, 2015 at 15:03
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.