This post originated from an RSS feed registered with Agile Buzz
by Keith Ray.
Original Post: Really Optimized Memory Allocation
Feed Title: MemoRanda
Feed URL: http://homepage.mac.com/1/homepage404ErrorPage.html
Feed Description: Keith Ray's notes to be remembered on agile software development, project management, oo programming, and other topics.
Travis Griggs tested memory allocation and freeing in C (no garbage collection versus automatic garbage collection) and Smalltalk. His test generates and frees 20,000,000 small objects, with only 1,000 of them being "live" at any time. His results:
9.5 seconds: plain C allocing but never freeing [no gc]
9.5 seconds: plain C with Boehm Garbage Collector
1.0 seconds: Cincom VisualWorks Smalltalk
This goes to show that 20 years of people improving Smalltalk's performance does add up. Unfortunately for C programmers, the fast algorithms used in "Generation Scavenging"(pdf) involve periodically copying small live objects from "new space" to "old space" -- this requires "fixing up" pointers to point to the new location, or the use of "handles" (pointers to pointers). The Boehm garbage collector is not going to fix up pointers, because it must assume that some piece of memory that looks like a pointer might actually be something else. [And C programmers have been known to copy pointers into int variables, etc.] A Java or Smalltalk environment can distinguish between object pointers and other things that may have the same bit-pattern as a pointer, so fixing up object pointers is safe.
The speed of "Generation Scavenging" comes from the simplicity of allocating objects in "new space" -- just increment the pointer that marks the division between the used and un-used part of the "new space" heap (it's more like a stack that never has to be decremented.) In some systems (Sun's HotSpot Java VM?) there's one "new space" per thread to avoid having to synchronize heap access across multiple threads. When the "new space" is filled up, do garbage collection and move "live" objects to "old space" heap (fixing up pointers or handles as needed). Most objects in Smalltalk have short lifetimes, so very few objects are copied. Then reset the "new space" pointer to clear the "new space" heap. Less often, do garbage collection to free up objects in the "old space" heap.
By the way, when I worked at Apple, I improved the performance of malloc/calloc/free in the standard-C library that shipped with (and was used by) the MPW environment and the MrC and MrCpp compilers. Simplifying the code and tuning how it did allocations of small objects improved the speed of the compilers by 5% or more. The changes I made to that library are still shipping in "Classic" MacOS.
Previous Topic
