A Nearly Quadratic Improvement for Memory Reallocation
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910453164146688 |
|---|---|
| author | Farach-Colton, Martin Kuszmaul, William Sheffield, Nathan Westover, Alek |
| author_facet | Farach-Colton, Martin Kuszmaul, William Sheffield, Nathan Westover, Alek |
| contents | In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the sizes of all items present at any time is at most a $(1-\varepsilon)$-fraction of the total size of memory (i.e., the load-factor is at most $1-\varepsilon$). The allocator receives insert and delete requests online, and can re-arrange existing items to handle the requests, but at a reallocation cost defined to be the sum of the sizes of items moved divided by the size of the item being inserted/deleted.
The folklore algorithm for Memory Reallocation achieves a cost of $O(\varepsilon^{-1})$ per update. In recent work at FOCS'23, Kuszmaul showed that, in the special case where each item is promised to be smaller than an $\varepsilon^4$-fraction of memory, it is possible to achieve expected update cost $O(\log\varepsilon^{-1})$. Kuszmaul conjectures, however, that for larger items the folklore algorithm is optimal.
In this work we disprove Kuszmaul's conjecture, giving an allocator that achieves expected update cost $O(\varepsilon^{-1/2} \operatorname*{polylog} \varepsilon^{-1})$ on any input sequence. We also give the first non-trivial lower bound for the Memory Reallocation Problem: we demonstrate an input sequence on which any resizable allocator (even offline) must incur amortized update cost at least $Ω(\log\varepsilon^{-1})$.
Finally, we analyze the Memory Reallocation Problem on a stochastic sequence of inserts and deletes, with random sizes in $[δ, 2 δ]$ for some $δ$. We show that, in this simplified setting, it is possible to achieve $O(\log\varepsilon^{-1})$ expected update cost, even in the ``large item'' parameter regime ($δ> \varepsilon^4$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12152 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Nearly Quadratic Improvement for Memory Reallocation Farach-Colton, Martin Kuszmaul, William Sheffield, Nathan Westover, Alek Data Structures and Algorithms In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the sizes of all items present at any time is at most a $(1-\varepsilon)$-fraction of the total size of memory (i.e., the load-factor is at most $1-\varepsilon$). The allocator receives insert and delete requests online, and can re-arrange existing items to handle the requests, but at a reallocation cost defined to be the sum of the sizes of items moved divided by the size of the item being inserted/deleted. The folklore algorithm for Memory Reallocation achieves a cost of $O(\varepsilon^{-1})$ per update. In recent work at FOCS'23, Kuszmaul showed that, in the special case where each item is promised to be smaller than an $\varepsilon^4$-fraction of memory, it is possible to achieve expected update cost $O(\log\varepsilon^{-1})$. Kuszmaul conjectures, however, that for larger items the folklore algorithm is optimal. In this work we disprove Kuszmaul's conjecture, giving an allocator that achieves expected update cost $O(\varepsilon^{-1/2} \operatorname*{polylog} \varepsilon^{-1})$ on any input sequence. We also give the first non-trivial lower bound for the Memory Reallocation Problem: we demonstrate an input sequence on which any resizable allocator (even offline) must incur amortized update cost at least $Ω(\log\varepsilon^{-1})$. Finally, we analyze the Memory Reallocation Problem on a stochastic sequence of inserts and deletes, with random sizes in $[δ, 2 δ]$ for some $δ$. We show that, in this simplified setting, it is possible to achieve $O(\log\varepsilon^{-1})$ expected update cost, even in the ``large item'' parameter regime ($δ> \varepsilon^4$). |
| title | A Nearly Quadratic Improvement for Memory Reallocation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.12152 |