TY - GEN

T1 - A Nearly Quadratic Improvement for Memory Reallocation

AU - Farach-Colton, Martin

AU - Kuszmaul, William

AU - Sheffield, Nathan S.

AU - Westover, Alek

N1 - Publisher Copyright:
© 2024 ACM.

PY - 2024/6/17

Y1 - 2024/6/17

N2 - 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-ϵ)-fraction of the total size of memory (i.e., the load-factor is at most 1-ϵ). 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(ϵ-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 ϵ4-fraction of memory, it is possible to achieve expected update cost O(logϵ-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(ϵ-1/2∗polylog ϵ-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ϵ-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ϵ-1 ) expected update cost, even in the "large-item"parameter regime (δ> ϵ4).

AB - 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-ϵ)-fraction of the total size of memory (i.e., the load-factor is at most 1-ϵ). 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(ϵ-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 ϵ4-fraction of memory, it is possible to achieve expected update cost O(logϵ-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(ϵ-1/2∗polylog ϵ-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ϵ-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ϵ-1 ) expected update cost, even in the "large-item"parameter regime (δ> ϵ4).

KW - memory reallocation

KW - randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85197439127&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85197439127&partnerID=8YFLogxK

U2 - 10.1145/3626183.3659965

DO - 10.1145/3626183.3659965

M3 - Conference contribution

AN - SCOPUS:85197439127

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 125

EP - 135

BT - SPAA 2024 - Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 36th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2024

Y2 - 17 June 2024 through 21 June 2024

ER -