--- title: The Double Headed Stack Allocator | daily.dev description: A veteran game programmer explains stack (bump) allocators, a technique for fast memory allocation where allocation is a simple integer add and deallocation... canonical: https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4 twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: The Double Headed Stack Allocator | daily.dev og:description: A veteran game programmer explains stack (bump) allocators, a technique for fast memory allocation where allocation is a simple integer add and deallocation... og:url: https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4 og:image: https://api.daily.dev/og/posts/HmGTFOcR4.png og:image:alt: The Double Headed Stack Allocator og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # The Double Headed Stack Allocator **[Bottom of the sea](https://daily.dev/sources/demofox)** · 8 min read · 0 upvotes · 0 comments ## Summary A veteran game programmer explains stack (bump) allocators, a technique for fast memory allocation where allocation is a simple integer add and deallocation resets a single index. Drawing on experience from Midway/Surreal Software's animation system and Blizzard's StarCraft 2 team, the post describes the basic single-headed stack allocator, then extends it to a double-headed variant where two allocators grow from opposite ends of a shared memory block to solve fragmentation problems in streaming open-world and shapeshifting character systems. It also covers a pattern for storing variable-sized objects with random access using a paired offset table, and notes these techniques work in multithreaded contexts via atomic increments. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### What is a double headed stack allocator and how does it prevent memory fragmentation? A double headed stack allocator uses one block of memory with two stack pointers (tos values) growing toward each other from opposite ends, one for each independent system, such as level geometry and a character. Each side can reset its own pointer to reallocate without fragmenting the other's memory, since allocations from each side stay contiguous and growth direction is fixed. Out-of-memory occurs when the two pointers cross. _Engineers designing engine memory systems can find implementation patterns like this one on daily.dev._ ### How does a simple stack (bump) allocator implement allocation and deallocation so cheaply? Allocation is just adding the requested size to an integer top-of-stack (tos) variable and returning the previous tos as the pointer, making it essentially free compared to general-purpose allocators. Deallocation of everything is a single assignment setting tos back to zero. Partial deallocation is possible by remembering and restoring an earlier tos value, useful for recursive allocation patterns. _Developers chasing allocation hot spots in profilers can track techniques like this via daily.dev._ ### How can you store variable sized objects with random access in a fixed memory region using a stack allocator? Use two stacks from a double headed stack allocator: one stack holds the actual variable-sized object data, while the other stack holds an array of integer offsets pointing to each object's location. A separate counter or a sentinel value, such as all 1s, tracks how many offsets exist, and removing or moving objects just requires updating the offset table. _Developers designing compact indexed memory layouts can revisit patterns like this through daily.dev._ ## Community take How the wider developer community reacted, aggregated from 2 discussions and 31 comments across hackernews (as of 2026-10-15). **TL;DR:** Technical discussion largely treats the double-headed stack allocator as a neat, well-understood technique, with most debate centered on how to make it safe and efficient under multithreading, and whether it's actually better than alternatives like separate stacks or ring buffers. **Sentiment:** 25% positive · 55% mixed · 20% skeptical **The case for** - The double-headed design is strictly better than two separate half-size stacks since it supports more allocation sequences without fragmentation. - Stack-based deallocation is effectively very fast garbage collection compared to mark-sweep approaches. - A similar high-address allocation trick was useful in a real ordinary allocator to avoid fragmentation between transient and persistent data. **The pushback** - The multithreading claim is questioned since safely updating two counters atomically together is tricky and the article doesn't explain how. - Some argue the two-stack-vs-double-headed tradeoff reasoning is flawed since bounding each side separately is easier to prove correct than bounding their sum. - Alternatives like cyclic/ring allocators or bipartite buffers may be better suited for streaming world geometry than a stack allocator. - The pattern only scales to two categories; it's unclear how to extend it to three or more object types. - Manual memory management of this kind is seen by some as a luxury not worth the complexity compared to just using GC. **By community** - hackernews (mixed): Appreciation for the technique is mixed with substantial pushback and technical scrutiny, especially around its multithreading safety claims and comparisons to alternative allocation strategies. **Hottest debate:** Whether the double-headed allocator is genuinely safe and well-justified for multithreaded use, given the article's unexplained claim that CAS-based synchronization isn't needed. **Open questions** - How exactly can two stack pointers be updated safely without a compare-and-swap loop, as the article claims? - How would this pattern be extended to handle three or more distinct object categories? - Is a cyclic/ring buffer allocator actually a better fit than a stack allocator for streaming open-world geometry? **Highlights** > I think it's OK to increment/decrement the ends past each other as long as you detect that and fail the allocation for at least one end. It's a little tricky with memory orders since you are synchronizing on two different locations. The simplest thing is to make all atomic accesses seqcst, but I think a single fence(seqcst) before checking overlap is sufficient in this case and will use fewer synchronizing instructions. The overflow checks are also tricky. We want to make sure that if an allocation fails, subsequent allocations also fail (even on other threads), and overflow might allow them to think they succeeded by incrementing again back into a valid range. This means you generally can't use fetch_add in a thread-safe bump allocator and instead need to use a CAS loop where you detect overflow before writing. Since you are doing a CAS loop anyway and always accessing both variables, it might actually be faster to combine both variables, especially if you typically allocate from both at the same time. E.g. if you pack two offsets into a 64-bit CAS word, you can still address 4GB, and you can get even more by aligning allocations. You also don't have to worry about seqcst. > — [singron on hackernews · 1 comments](https://news.ycombinator.com/item?id=50099318) > The single stack allocator seems to be an arena by other terms, but the double headed version is pretty neat. Is the final pattern described actually safe for multi-threaded use? Something like the stack has exactly 1 byte left, T1 allocates the dynamic end with 1 byte (dynamic object just happened to be 1 byte, say) and T2 allocates the fixed size end with 1 byte. Wouldn't they end up overlapping in that case? > — [tyushk on hackernews · 3 comments](https://news.ycombinator.com/item?id=50098682) > The system in TFA can only handle 2 "categories". Note that there could be many distinct types in each category; the important thing about categories is that everything in the same category should share an allocation/deallocation timeline. If this holds separately for each category, there will be no fragmentation. For this 2-category case, the double-headed stack is strictly better than maintaining 2 separate half-size stacks, since it permits every sequence of allocations and deallocations that the latter permits, while there are sequences that it permits that the latter does not permit (namely, any sequence in which more than half the memory is temporarily needed by one of the categories, and the other category is temporarily not using it). > — [akoboldfrying on hackernews](https://news.ycombinator.com/item?id=50101283) > The full quote from the article is: > Just like the other stack allocators we talked about, this one can also work in a multi threaded environment. You might be tempted to make the two updates transactional – like with a compare and swap loop – but it isn’t needed. Unfortunately they don't explain HOW this is going to work... > — [moring on hackernews](https://news.ycombinator.com/item?id=50099955) > This kind of pattern is pretty common when dealing with pipelining of some kind. Another solution I’ve implemented before when dealing with streaming weights into a GPU is that you mirror map the region twice and hand out pointers in order from the first region but allowing it to wrap around to the front using virtual addressing. I’ve found this to be slightly more powerful as it allows for allocating multiple stages ahead, since you don’t run out of “sides” to allocate from. The double sided allocator unfortunately only really allows for 1 extra stage for your pipeline. > — [saagarjha on hackernews · 1 comments](https://news.ycombinator.com/item?id=50098885) **Source threads** - [hackernews](https://news.ycombinator.com/item?id=50098274) · 82 points · 31 comments - [hackernews](https://news.ycombinator.com/item?id=49965728) · 2 points · 0 comments ## Similar posts on daily.dev - [Why malloc is doing more than I asked for](https://daily.dev/posts/why-malloc-is-doing-more-than-i-asked-for-fjox6za3e) · Hacker News · 6 upvotes · 0 comments --- Tags: [#performance](https://daily.dev/tags/performance), [#game-development](https://daily.dev/tags/game-development), [#c++](https://daily.dev/tags/c++) [View this post on daily.dev](https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"The Double Headed Stack Allocator","url":"https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4"},"datePublished":"2026-10-03T14:54:42.668Z","dateModified":"2026-10-15T14:57:25.305Z","description":"A veteran game programmer explains stack (bump) allocators, a technique for fast memory allocation where allocation is a simple integer add and deallocation...","image":"https://media.daily.dev/image/upload/s--1KxV4ohY--/f_auto/v1722860400/public/Placeholder%2007","thumbnailUrl":"https://media.daily.dev/image/upload/s--1KxV4ohY--/f_auto/v1722860400/public/Placeholder%2007","isAccessibleForFree":true,"articleSection":"Bottom of the sea","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Bottom of the sea","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/a3f6624fe4c24a4691dd5be6fd5a548c","url":"https://daily.dev/sources/demofox"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"performance,game-development,c++","timeRequired":"PT8M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Bottom of the sea","item":"https://daily.dev/sources/demofox"},{"@type":"ListItem","position":3,"name":"The Double Headed Stack Allocator"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/the-double-headed-stack-allocator-hmgtfocr4#faq","mainEntity":[{"@type":"Question","name":"What is a double headed stack allocator and how does it prevent memory fragmentation?","acceptedAnswer":{"@type":"Answer","text":"A double headed stack allocator uses one block of memory with two stack pointers (tos values) growing toward each other from opposite ends, one for each independent system, such as level geometry and a character. Each side can reset its own pointer to reallocate without fragmenting the other's memory, since allocations from each side stay contiguous and growth direction is fixed. Out-of-memory occurs when the two pointers cross. Engineers designing engine memory systems can find implementation patterns like this one on daily.dev."}},{"@type":"Question","name":"How does a simple stack (bump) allocator implement allocation and deallocation so cheaply?","acceptedAnswer":{"@type":"Answer","text":"Allocation is just adding the requested size to an integer top-of-stack (tos) variable and returning the previous tos as the pointer, making it essentially free compared to general-purpose allocators. Deallocation of everything is a single assignment setting tos back to zero. Partial deallocation is possible by remembering and restoring an earlier tos value, useful for recursive allocation patterns. Developers chasing allocation hot spots in profilers can track techniques like this via daily.dev."}},{"@type":"Question","name":"How can you store variable sized objects with random access in a fixed memory region using a stack allocator?","acceptedAnswer":{"@type":"Answer","text":"Use two stacks from a double headed stack allocator: one stack holds the actual variable-sized object data, while the other stack holds an array of integer offsets pointing to each object's location. A separate counter or a sentinel value, such as all 1s, tracks how many offsets exist, and removing or moving objects just requires updating the offset table. Developers designing compact indexed memory layouts can revisit patterns like this through daily.dev."}}]} ```