Thursday, January 31, 2013

Garbage Collection and Memory Allocation Sizes

As a performance conscious programmer in a soft-realtime environment I've never been too fond of garbage collection.

Incremental garbage collectors (like the one in Lua) make it tolerable (you get rid of the horrible garbage collection stalls), but there is still something unsettling about it. I keep looking at the garbage collection time in the profiler, and I can't shake the feeling that all that time is wasted, because it doesn't really do anything.

Of course that isn't true. Garbage collection frees the programmers from a lot of busywork. And the time they gain can go into optimizing other systems, which leads to a net performance win.

It also simplifies some of the hairy ownership questions that arise when data is transferred between systems. Without garbage collection, those questions must be solved in some other way. Either by reference counting (error-prone) or by making local copies of the data to assume ownership (ugly and costly).

But still, there is that annoying performance hit.

I was pretty surprised to see that the developers Go, a language that looks well-designed and targets low-level programmers, decided to go with garbage collection rather than manual memory management. It seemed like a strange choice.

But recently I've started to see things differently.

One thing I've noticed as I delve deeper and deeper into data-oriented design is that I tend to allocate memory in much larger chunks than before. It's a natural consequence of trying to keep things continuous in memory, treating resources as large memory blobs and managing arrays of similar objects together.

This has interesting consequences for garbage collection, because when the garbage collector only has to keep track of a small number of large chunks, rather than a large number of small chunks, it can perform a lot better.

Let's look at a simple example in Lua. Say we want to write a class for managing bullets. In the non-data-oriented solution, we allocate each bullet as a separate object:

function Bullet:update(dt)
    self.position = self.position + self.velocity * dt
end

function Bullets:update(dt)
    for i,bullet in ipairs(self.bullets) do
        bullet:update(dt)
    end
end

In the data-oriented solution, we instead use two big arrays to store the position and velocity of all the bullets:

function Bullets:update(dt)
    for i=1,#self.pos do
        self.pos[i] = self.pos[i] + dt * self.vel[i]
    end
end

I tested these two solutions with a large number of bullets and got two interesting results:

  • The data-oriented solution runs 50 times faster.

  • The data-oriented solution only needs half as much time for garbage collection.

That the data-oriented solution runs so much faster shows what cache coherence can do for you. It is also a testament to how awesome LuaJIT is when you give it tight inner loops to work with.

Note that in this test, the Bullet code itself did not create any garbage. The speed-up comes from being faster at collecting the garbage created by other systems. And the reason for this is simply that with fewer, larger memory allocations, there is less stuff that the garbage collector has to trawl through. If we add in the benefit that the data-oriented solution will create fewer objects and generate less garbage, the benefits will be even greater.

So maybe the real culprit in isn't garbage collection, but rather having many small memory allocations. And having many small memory allocations does not just hurt the garbage collector, it is bad for other reasons as well. It leads to bad cache usage, high overhead in the memory allocator, fragmentation and bad allocator performance. It also makes all kinds of memory problems harder to deal with: memory leaks, dangling pointers, tracking how much memory is used by each system, etc.

So it is not just garbage-collected languages like Lua that would benefit from allocating memory in larger chunks, but manually managed languages like C++ as well.

Recently, I've come to think that the best solution to memory management issues in C++ is to avoid the kitchen-sink global memory allocator as much as possible and instead let each subsystem take a much more hands-on approach to managing its own memory.

What I mean by this is that instead of having the sound system (for example) send lots of memory requests to the kitchen-sink memory manager, it would only request a few large memory blocks. Then, it would be the responsibility of the system to divide that up into smaller, more manageable pieces that it can make practical use of.

This approach has a number of advantages:

  • Since the system knows the usage patterns for its data, it can arrange the memory efficiently. A global memory allocator has no such knowledge.

  • It becomes much easier to track memory use by system. There will be a relatively small number of global memory allocations, each tagged by system. It becomes obvious how much memory each system is consuming.

  • Memory inside a system can be easily tracked, since the system knows what the memory means and can thus give useful information about it (such as the name of the object that owns it).

  • When a system shuts down it can quickly and efficiently free all of its memory.

  • Fragmentation problems are reduced.

  • It actively encourages good memory behavior. It makes it easier to do good things (achieve cache locality, etc) and harder to do bad things (lots of small memory allocations).

  • Buffer overflows will tend to overwrite data within the same system or cause page faults, which will make them easier to find.

  • Dangling pointer access will tend to cause page faults, which will make them easier to find.

I'm tempted to go so far as to only allow whole page allocations on the global level. I.e., a system would only be allowed to request memory from the global manager in chunks of whole system pages. Then it would be up to the system to divide that up into smaller pieces. For example, if we did the bullet example in C++, we might use one such chunk to hold our array of Bullet structs.

This has the advantage of completely eliminating external fragmentation. (Since everything is allocated in chunks of whole pages and they can be remapped by the memory manager.) We can still get address space fragmentation, but using a 64-bit address space should take care of that. And with this approach using 64-bit pointers is less expensive, because we have fewer individually allocated memory blocks and thus fewer pointers.

Instead we get internal fragmentation. If we allocate the bullet array as a multiple of the page size (say 4 K), we will on average have 2 K of wasted space at the end of the array (assuming the number of bullets is random).

But internal fragmentation is a much nicer problem to deal with than external fragmentation. When we have internal fragmentation, it is one particular system that is having trouble. We can go into that system and do all kinds of things to optimize how its handling memory and solve the problem. With external fragmentation, the problem is global. There is no particular system that owns it and no clear way to fix it other than to try lots of things that we hope might "improve" the fragmentation situation.

The same goes for out-of-memory problems. With this approach, it is very clear which system is using too much memory and easy to fix that by reducing the content or doing optimizations to that system.

Dealing with bugs and optimizations on a system-by-system simplifies things enormously. It is quite easy to get a good grasp of everything that happens in a particular system. Grasping everything happens in the entire engine is a superhuman task.

Another nice thing about this approach is that it is quite easy to introduce it on a system-by-system basis. All we have to do is to change one system at a time so that it allocates its memory using the page allocator, rather than the kitchen-sink allocator.

And if we have some messy systems left that are too hard to convert to this approach we can just let them keep using the kitchen-sink allocator. Or, even better, we can give them their own private heaps in memory that they allocate from the page allocator. Then they can make whatever mess they want there, without disturbing the other systems.

41 comments:

  1. The main reason Go uses garbage collection from what I gathered is to make it easier for developer to use the goroutines (which can capture variables etc.) and channels as well. Without this, you would have to do a lot of memory management yourself. This choice makes a lot of sense with this in mind :)

    ReplyDelete
  2. I think the method you're referring to for memory management in C++ is RAII (http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization)

    ReplyDelete
  3. Norton.com/Setup is best antivirus available in the market. If you want to protect your system online or locally from any unforeseen events Norton is is a must have software in your PC or Mac. Activate your Norton.com/Setup to protect yourself ad your data from your system from malware and antivirus. Browse internet without any hesitation norton will take care of all malicious antiviruses floating all over internet.

    Office.com/Setup is a software which is used by almost all company and business and even by individuals For all their office activities or for personal use. It has excels, word, add ppt as their constituent are most widely used apps. For any concern and help just visit website for
    Office.com/Setup help and key activation. You can do it by yourself if you know how to install office.com/Setup on your PC or Mac or you can call third party companies as well who can do it on your behalf.up.

    ReplyDelete
  4. The detoxification time frame is hard for the individual experiencing liquor fixation since it is joined by extraordinary withdrawal side effects. These side effects negatively affect the patient both genuinely and intellectually. Hence, a liquor rehab focus additionally gives close patient checking and help during this period.
    beating addiction quotes
    drug addiction recovery quotes

    ReplyDelete
  5. The primary concern you'll see when you pull up YesPornPlease is, you gotten it, a great deal of porn. The screencaps don't move when you coast over them, yet they're all new, capable shots from colossal studios. Brazzers, Mofos, BangBros, and RealityKings are just two or three the indisputable names on the main page. It may be free, anyway you're not getting off-brand bitches snapping dicks behind a 7-11 for meth money. This is the worthy stuff.
    yespornplease

    ReplyDelete
  6. It's really an amazing article post great to get the relatives information through your website posts for all the people, I appreciate your efforts and suggtions. Thank you for sharing your knowledge and experience with everyone. australia assignment help -
    Assignment Help Melbourne -
    Assignment Help Perth

    ReplyDelete
  7. This is a Lovely blog and how nicely you posted. Nice topic and writing. I am also available here to provide information about
    McAfee Antivirus, It is one of the best to keep your devices safe and secure weather PC laptops or smartphones it's free to use and easy to handle.
    Activate McAfee Activate 25 Digit Code [url=https://e-mcafee.com/activate]McAfee Total Protection[/url]

    ReplyDelete
  8. My Assignment Help is an incomparable online assignment writing service delivering excellent assignment help service. We have the best in-house team specialist to take complete care of assignment within provided time limit. Convince yourself only after looking at the list of our free samples talking of our quality and expertise.

    ReplyDelete
  9. Being a Digital Marketer and Software Engineer by profession. My core interests include programming, troubleshooting and blogging. Check me out below:
    We've already written a few posts on how to fix these problems and easily install Office on your PC/Mac by simply clicking the below links:
    office.com/setup
    office.com/setup
    office.com/setup
    office.com/setup

    ReplyDelete
  10. We write blogs about how to use Microsoft Office software, how to install it on different computers, and how to unlock it. Microsoft Office, as we all know, is a massive piece of software, and installing it can be difficult. We've already written a few posts on how to fix these problems and easily install Microsoft Office on your PC.
    www.office.com/setup
    www.office.com/setup
    www.office.com/setup
    www.office.com/setup

    ReplyDelete

  11. Office.com/setup | Activate Your Office Setup with Product Key
    office.com/setup
    office.com/setup login

    ReplyDelete
  12. How to Get Microsoft Office works for Windows?
    Click Below Links:
    buymicrosoft365
    msofficeworks
    microsoft365.com

    ReplyDelete
  13. Our aim is to provide the best quality services at the best price. If you are seeking for, then you are at the right place. We provide first copy watches in Mumbai. We have more than 10+ years of experience in this business. Our customer care services are available 24/7 to assist all your needs. You can get the best quality Replica watches in India at the best price. Just visit and choose according to your need and budget. 100% secured online payment gateway.

    ReplyDelete
  14. I found this one interesting and it should be added to my collection. Good job! It must be a popular blog. Your article is very informative, thanks for sharing. Here are some articles about Typing speed online. Check out my latest post Typing speed test related to this.

    ReplyDelete
  15. With our biostatistics assignment help programs, we aim to enable learners to hit the professional ladder's highest rung. Biostatistics is considered an important and useful degree because it allows students to become effective practitioners in their rights and work in health and make meaningful improvements. We are at assignment help . Assignment helps under our Biostatistics assignment help so that students can complete their assignment on time and score good marks.

    ReplyDelete
  16. I am very embarrassed to know this fact how can write research paper. But, I do not get the right solution on right time. After reading this post, I will familiar with hidden art to write compelling and long lasting content. Visit our Assignment Help link to know more information.

    ReplyDelete

  17. ufa888

    มาลองเล่นกันดูเลย

    ReplyDelete

  18. ufa888

    ฝากเท่าไหร่ได้2เท่า

    ReplyDelete
  19. Keep up the good writing. please visit our beautiful website, spread the love, thankyou! 카지노사이트

    ReplyDelete
  20. Hello! This is my first visit to your blog! We are a group of volunteers and starting a
    new initiative in a community in the same niche. Your blog provided us
    valuable information to work on. You have done a marvellous
    job! 바카라사이트

    ReplyDelete
  21. Iwas more than happy to find this site. 스포츠토토
    I want
    to to thank you ffor your time for this particularly
    wonderful read!! I definitely savored every little bit of it and i also have yyou saved
    aas a favorite to check out new stuff in your website.

    ReplyDelete
  22. 토토사이트 Completely awesome posting! Bunches of helpful data and motivation, both of which we all need!Relay welcome your work

    ReplyDelete
  23. MLA is a very popular citation style. However, if you are unsure which citation style to use in your paper, ask your instructor. There are many different citation styles and using the style your instructor or institution has established correctly can have a positive impact on your grade. We are at assignment help . Assignment helps under our Citation machine assignment help so that students can complete their assignment on time and score good marks.

    ReplyDelete
  24. You made some good points there. I did a Google search about the topic and found most people will believe your blog. 메이저사이트

    ReplyDelete
  25. Self Defense training near me for Martial Arts is defending yourself from an opponent’s attack in any situation. Most of our students joined our Academy to learn Self Defense training by teaching the different methods using Strike techniques, Kick techniques, Escaping techniques, prevention tips and more. Self Defense Classes in dehradun

    ReplyDelete
  26. This has been an adventure to visit your blog and read this informative post.

    Check 99CarRentals for cab services in India.

    ReplyDelete
  27. I accidentally searched and visited your site. I still saw several posts during my visit, but the text was neat and readable. I will quote this post and post it on my blog. Would you like to visit my blog later? keonha cai


    ReplyDelete
  28. When I read your article on this topic, the first thought seems profound and difficult. There is also a bulletin board for discussion of articles and photos similar to this topic on my site, but I would like to visit once when I have time to discuss this topic. 먹튀검증업체I think it would be nice if you come to if you can solve my problem.


    ReplyDelete