I'm implementing a bounding volume hierarchy in F#. Since it would be for a game, I want the garbage collector to be as quick and infrequent as possible.

It seems though that I may have to pull some whacky tricks, probably pre-allocating everything. That means that I can't have many things immutable, and that I have to know up front how large my tree will be -- a major annoyance.

I'll probably end up biting the bullet and doing just that (or maybe just go back to C++), but for the record, are trees inherently bad for GC performance? They would seem to be, considering the mark stage would have to traverse a lot of nodes.

  • I don't see why they would be inherently bad (and if you reasoning is correct, there this isn't specific to trees - everything with a lot of small seperate objects is affected, especially all kinds of collections containing reference types). It depends on a lot on how they are used. Allocating a thousand nodes per frame is bad, but so is allocating a thousand-element array per frame. Mostly reusing the same tree and occasionally inserting a new node can easily be faster than re-allocating a new array on each insertion. – user7043 Jan 2 '12 at 10:11
  • You say that you're making a game... What are you deploying to? The GC for some devices (ie. phone/xbox vs PC) operate very differently. – Steven Evers Jan 2 '12 at 15:37
  • @SnOrfus Windows for now -- WP7 and Xbox would be nice in the future, but yeah, knowing that their GCs kind of suck, I may just forego those targets entirely. – Rei Miyasaka Jan 2 '12 at 18:16
  • @ReiMiyasaka: Yea, their GCs do kinda suck. The benefit is, though, that if you code for performance on the phone/360, then you'll get performance on the PC. – Steven Evers Jan 2 '12 at 19:06

I understand that you are concerned about this issue not because you suffer from the premature optimization syndrome, but because you are worried that this potential performance issue might need to be taken into consideration in order to make the right choices of technologies in the very beginning of the project.

If that is your concern, there is no answer "oh, yes, that's really going to kill the GC" or "no, don't worry, everything will be fine" that you should really depend on.

Just implement a test scenario, and see for yourself how it performs.

(My guess is that there will be no problem whatsoever. Even in conditions 10x worse than your projected usage.)

  • 1
    Imma try it out and see what happens. I figured out a way to make the BVH code fairly modular whilst keeping overhead low. – Rei Miyasaka Jan 3 '12 at 23:11

They are. However, the CLR GC is way too smart for this. Once the tree nodes survive a collection, the generational aspect will kick in and prevent it from needlessly marking the tree over and over again. You'd need a big-ass tree to mark a noticable slowdown.

Edit: Remember, trees are very common structures. The CLR GC designers will have considered and profiled this situation extensively over the past decade.

  • What if I'm moving things around a lot, especially near the root? BVH trees change quite often. – Rei Miyasaka Jan 2 '12 at 10:22
  • Reordering a tree (or any other graph) should not involve the creation of new nodes; it merely alters members of existing nodes. – MSalters Jan 2 '12 at 10:39
  • @MSalters In BVH, leaf nodes are created/destroyed only in conjunction with game object -- which isn't too bad. It's the intermediate nodes that go in and out all the time depending on the relative spatial distances of all the nodes in that tree. – Rei Miyasaka Jan 2 '12 at 18:29

The "whacky tricks" you mention are not so whacky. Given the content, and the date of the article, it appears to be based on another blog article written by Shawn Hargreaves - who was well known for his work on XNA (until very recently, as he moved to the windows phone team).

One of the main reasons why GC performance is a big deal is because devices that run the compact framework (phones, xbox) don't have the same kind of generational garbage collection as the PC/Server versions of the GC do. They do a full collection every time (see here).

To directly answer your "for the record" though: No, they're not inherently bad. You do have to take your deployment platform into account, no matter what you're making though. Consider that even games written in C++ or without a garbage collection have to consider when they create and delete resources, or framerates will suffer. That's why we have loading screens and why resource streaming technologies are so interesting and difficult to implement.

  • That's not even remotely related. Loading screens are waiting for the HDD or DVD drive to serve up data, not for the code to operate on it. If C++ code is waiting on the memory manager, then it's bad C++. – DeadMG Jan 2 '12 at 16:38
  • @DeadMG: I'm not sure what you mean. If you take a look at the linked articles, the first method (ie. shooting for the fewest possible collections) concerns itself with pre-loading resources and holding onto them - this almost always comes from fixed media. This is what happens during loading screens. Operating on that data can, and does, happen for certain types of resources (look at generated textures/substances from allegorithmic for an example - they can be transformed/generated on-the-fly, or during a loading operation). – Steven Evers Jan 2 '12 at 18:17
  • Yeah, I saw that article too. With all this dancing around the GC though, at some point, it starts to feel like maybe I might as well go back to C++. Not that C#/F# doesn't have its advantages, but so many of the resources out there are C++ anyway, and the decision to stay on .NET is becoming harder and harder. – Rei Miyasaka Jan 2 '12 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.