Dev Diary #4 (Part 3 of 3) – September-October 2018

Part 3: Memory Fragmentation

We posted the first part about “Uninitialized Variables” on Monday October 1st 2018. The second part about “Memory Leaks” was postet on Monday October 12th 2018. This is the third and last part: “Memory Fragmentation”.

This diary concerns itself with fairly ‘low level’ topics, but we will try to explain everything so that non-programmers can also follow and get a good idea about what’s going on.
For the programmers among you – we are simplifying a lot here, so please bear with us. The Guild 3 is written in C++, so please put on your C++-tinted glasses while reading this.

The Issue

This is again a pretty tricky issue to explain, and to do that I want to recall the library example from the previous issue.

Imagine that the library visitor (our program) starts working on data, and slowly proceeds to fill the first desk with various books and reference works. Because our visitor is highly organized and methodical, like every program, he wants to lay out his books in a way so that they don’t overlap or have too much free space between them. Each new book that he retrieves is placed neatly next to the existing books already arranged on the desk. Of course there will be gaps and misalignments between some of the books – they are not all of exactly the same size. Also, to not get confused, the visitor will not move a book as long as he requires it. Once placed on a desk it will stay there until returned, even if all neighboring books are returned.

Whenever the visitor is done with a book, it is picked up from the desk and returned to a shelf. If a new book is retrieved, it gets placed into the first free spot large enough to hold the book without overlapping any of the neighboring books.

As you can image, if a very large volume is returned, then a large empty spot is left – a newly retrieved book will easily fit in there, maybe even leaving a gap next to it to hold a second or third book. However, if a small book is returned to the library storage, a small gap is left, and when a new book needs to be placed onto the desk, it very likely will not fit into the gap and will instead be placed somewhere in the free space at the end of the desk, or a new desk if the current desk has no spot large enough to hold the book.

This pattern repeats over time – return unused stuff, leaving empty spaces on the desk, get new stuff which might or might not fit into the empty spaces, and therefore might require our visitor to hog more desks. If this repeats long enough, you will be able to observe a very odd looking reading room in the library:

The visitor will have his work spread across many dozens of desks. The desks might not even be very full – all the books on it will be neatly laid out, however with oddly shaped spaces between them where no real book can fit. Even though the total area taken up by books will be fairly small, the overall number of desks required will be really high.

The Effect

This more or less describes the problem of memory fragmentation: A program frequently requests memory from the operating system, and also returns memory to the operating system. Once memory is in use it can’t be ‘moved around’, so if you remove a bit of information between two adjacent pieces of information, you can’t shove them together to remove the gap. Instead you are left with a small gap that is not really useful to anyone, but inflates the effective memory footprint of the program.

In times past, the result of this would have been that at some point you run out of memory. You want to get a slice of memory, but the operating system tells you ‘there is not enough contiguous space available to satisfy your request’. Overall memory usage might be low, but all the free memory is cut up into tiny, useless pieces stuck between the memory that you are actually using.

On modern systems, this does not happen anymore. 64 bit architectures and virtual memory mean that you can’t really run out of memory anymore. Instead, over time it becomes more and more work to locate a free bit of memory. In Guild 3 this results in degrading performance over time – the longer you play, the slower the game gets, until at some point it becomes unplayable. Restarting the game fixes this, as this gives the program a clean slate to work with.

The Solution

We have already implemented a rather large change that greatly improved the situation on this front. Guild 3 used to have a memory manager that reacted very poorly to highly fragmented memory, which led to a very steep decline in performance over time. We removed this memory manager, instead using Windows’ native low fragmentation heap, which is very good at dealing with this kind of issue (you can read more about this here: https://docs.microsoft.com/en-us/windows/desktop/memory/low-fragmentation-heap ). This was released with version 0.5.4 of Guild 3 and got good feedback.

A main issue remains in that the game is very prone to leaking and keeping stale memory around. This of course exacerbates the problem of memory fragmentation – not only is memory taken up by actively used data, but also by data that no one needs anymore! This situation will improve over time as we weed out unused code and refactor existing functionality.

If you are interested in this topic, I can again recommend the Wikipedia article about fragmentation here: https://en.wikipedia.org/wiki/Fragmentation_(computing)
Also, there is a pretty good and interesting video about a different game that suffered from memory fragmentation here: https://www.youtube.com/watch?v=_zD33Hrbo4Y

Conclusion

I hope this gave you a bit of insight into the work we are doing ‘behind the scenes’. You won’t ever see any of this in any obvious way. Instead, fixing issues like these slowly improves performance and stability over time, leading to an overall improved experience.

Daniel Rind
Programming for The Guild 3
Purple Lamp Studios