See also: Norman R. Nielsen. Dynamic memory allocation in computer simulation. Communications of the ACM, 20(11):864–873, November 1977. This was the first place I saw this result. A later improvement was realizing this allowed headerless BIBOP organization of allocated memory.
I think the first malloc/free-compatible GC/allocator that used BIBOP like this was the Boehm-Weiser conservative collector: Hans Boehm and Mark Weiser. Garbage collection in an uncooperative environment. Software, Practice and Experience, pages 807–820, September 1988. I used the technique in a performance-tuned malloc at Sun back in the early 90s, and its fragmentation was entirely acceptable; not as good as Cartesian trees (best non-compacting fragmentation at the time) but not much worse, and far faster. On Tuesday, May 16, 2017 at 3:26:42 PM UTC-4, Rick Hudson wrote: > > The Johnstone / Wilson paper "The memory fragmentation problem: solved?" > [1] is the original source. > > Modern malloc systems including Google's TCMalloc, Hoard [2], and Intel's > Scalable Malloc (aka Mcrt Malloc [3]) all owe much to that paper and along > with other memory managers all segregate objects by size. Many languages, > most notable C/C++, use these fragmentation avoidance memory managers to > build large system without the need for copy compaction. > > [1] Mark S. Johnstone and Paul R. Wilson. 1998. The memory fragmentation > problem: solved?. In Proceedings of the 1st international symposium on > Memory management (ISMM '98). ACM, New York, NY, USA, 26-36. DOI= > http://dx.doi.org/10.1145/286860.286864 > > [2] Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. > Wilson. 2000. Hoard: a scalable memory allocator for multithreaded > applications. SIGPLAN Not. 35, 11 (November 2000), 117-128. DOI= > http://dx.doi.org/10.1145/356989.357000 > > [3] Richard L. Hudson, Bratin Saha, Ali-Reza Adl-Tabatabai, and Benjamin > C. Hertzberg. 2006. McRT-Malloc: a scalable transactional memory allocator. > In Proceedings of the 5th international symposium on Memory management > (ISMM '06). ACM, New York, NY, USA, 74-83. DOI= > http://dx.doi.org/10.1145/1133956.1133967 > > On Tuesday, May 16, 2017 at 12:48:38 PM UTC-4, Zellyn wrote: >> >> Thanks for the enlightening and interesting reply, Ian. >> >> One quick question: do you have a link or a short description of why >> “modern memory allocation algorithms, like the tcmalloc-based approach used >> by the Go runtime, have essentially no fragmentation issues”? >> >> I was curious, but a quick search for [tcmalloc fragmentation] yielded >> mostly people struggling with fragmentation issues when using tcmalloc. >> >> Zellyn >> >> -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
