Part 1: Uninitialized Variables

Greetings everyone!

In this developer diary we want to give you insight into some of the more fundamental programming issues we are facing with the source code right now, how they affect game stability and performance, and what we are doing to resolve those problems.
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.

We split the story in three parts. This is the first part: "Uninitialized Variables".

The Issue
Variables in programming serve a similar purpose to variables in mathematics (which is where most of you likely know the term from): They can hold a distinct value from a certain range of values, and they are used in calculations, and more generally processing, as a ‘placeholder’ for explicit values.

In C++, every variable requires two items of information:
- A type. This tells the compiler (that’s the program that translates the code we programmers type into something that the computer can actually run) which value range the variable can represent. Is this a piece of text? Or is it a whole number? Or does it represent an entire in-game character?
- A name. This is then used by programmers to actually access the variable in code. Usually it’s either something short, similar to mathematics (‘x’, ‘i’, etc…), or something more descriptive (like ‘playerCharacter’ or ‘secretSocietyContainer’, etc…).
By typing the appropriate statements into your code you can get the C++ compiler to carve out a tiny slice of memory and label it with the name you provided.

As you can see above, an initial value is NOT a requirement in C++. You can happily declare to the compiler that you want a variable representing a whole number named ‘myWholeNumber’ without telling the compiler which value it has. After all, you might not care about the value that is in the variable at this point in time, and only later assign something to it. However, you can read from a variable as soon as you have declared it. But which value does it have if nothing has ever been assigned to it? Some programming languages initialize all variables to a default value - for numerical variables this is usually zero. C++ does not do this. The value you get when reading from an uninitialized variable in C++ is whatever previously was in the memory location that is now occupied by your variable - essentially, it’s random. Quite frequently it will actually be zero, which can lead to a false sense of correctness.

There are valid reasons for this, which in the end all boil down to a very fundamental mantra of C++: “You don’t pay for what you don’t use”, or in other words, the language will try very hard to not impose extra rules or requirements on your code that would incur extra runtime cost over what you actually wrote.

The Effect
What it ultimately means is that in C++ you have to take care to appropriately initialize variables yourself, and you have the option to skip initialization if you know you can. Forgetting to do this can result in errors that appear very randomly, and are difficult to track down. An example would be the “winter disco lighting” bug we had a while ago, which ultimately was caused by a very specific color variable not being initialized. We also had several bugs because of this that we caught internally before shipping the builds, like the game suddenly thinking that there are no male children in the game anymore.

The Solution
What can we do to avoid and fix these issues? The main course of action is of course to not cause any issues in the first place by diligently making sure everything gets initialized properly. There are guidelines and best practices that should be followed, which help ensure no uninitialized variables can creep into your code.

To find existing issues, there are three main options:
- Manually check code. We are doing this whenever we touch a new area of the code, checking if anything has been left uninitialized. This is not really a good option for finding many issues at once, since our code base is very large and manually checking through everything would take a prohibitive amount of time.
- Use static code analysis. This means that we use special tools that analyze the code to find issues like uninitialized variables (they can also help find other difficult to track down issues). For those more interested in the matter, we’ve been using “clang tidy” and so far have had a good experience with it - it helped uncover many issues (you can read more about this tool here: http://clang.llvm.org/extra/clang-tidy/)
- Use memory fuzzing tools, that intentionally fill memory with garbage values before allowing our game access to it, helping uncover the common case I mentioned above where those issues go undetected because everything is just filled with zero by default. Valgrind ( http://valgrind.org/) would be a very popular free option available for Linux, but there are similar tools for windows. We haven’t taken this step (yet).

If our explanation confused you more than it helped, then maybe this Wikipedia article can help, as it explains the issue rather well: https://en.wikipedia.org/wiki/Uninitialized_variable

If you have problems with the links in the text above, then you can also visit our official homepage and use the links in the posting there.

We will soon continue this dev diary story with "Memory Leaks". Stay tuned.

Part 2 - Memory Leaks
We posted the first part about "Uninitialized Variables" on Monday October 1st 2018. This is the second part: "Memory Leaks"."

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
“Leaking memory” sounds very unpleasant, and it truly is a nasty problem. To understand this (and the next) issue, we first should quickly discuss how memory is used by our game, and indeed pretty much any program. To do this, I’ll employ a little analogy:

Imagine your PC is a library. The hard disks and other permanent storage are the shelves of books along the walls and in the library vaults, where knowledge and data is stored for long durations. Every running program is a visitor to this library. To actually do anything with all the information, the programs first have to retrieve it from long term storage and get it into their personal ‘work space’, one or more reading tables that are used for interacting with the information. This is essentially the purpose that your computer’s main memory serves.

Some programs might require only very little information, so they only need a tiny slice of memory (a small table somewhere in the corner, in our library analogy). Others operate on huge amounts of data at once and therefore their workspace spans several desks or even desks in multiple rooms, all littered with open books and loose pages.

Of course, as a good citizen, whenever you are done with working on a book retrieved from storage, you should return it. Not only so that someone else can work on it, but also so that you don’t keep eating up more and more space in the library, filling desk after desk with books that you don’t need anymore.

The Effect
This is, however, exactly what happens if someone talks about a ‘memory leak’. A program has to request memory from the operating system before it can use that memory for storing data - data like textures, meshes, program code, script files, sounds, and whatever else needs to be worked on. The operating system happily fulfils those requests, but it also expects the program to return memory that is no longer used. If this doesn’t happen, then the memory usage will continuously swell up.

Nowadays, thanks to virtual memory and 64 bit operating systems, it is quite difficult to actually run out of memory. You have to do some pretty outrageous things before the operating system will actively deny more memory for a program. What happens instead is that performance will degrade over time, while memory usage slowly grows to epic proportions. Before long, the program will become essentially unusable, and the user will kill it.

The Solution
Writing modern code in C++ makes it fairly easy to avoid memory leaks. The straight “I forgot to return memory to the operating system” case I mentioned above is usually not what happens. What happens more frequently is that ‘stale’ data is kept in memory. No one really needs this data anymore, but someone somewhere is ‘keeping it alive’.

These issues are very annoying and time consuming to fix. There aren’t really any tools or automated helper programs we can use. Rather, we have to make sure to always do diligent bookkeeping, keeping only the data around that is really needed, and properly freeing unused memory so it can go back into the operating system.

If you are interested to find out more about the issue of memory leaks, this Wikipedia article is a good location to get started: https://en.wikipedia.org/wiki/Memory_leak

We will soon continue this dev diary story with "Memory Fragmentation". Stay tuned.

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: [url=https://en.wikipedia.org/wiki/Fragmentation_(computing]https://en.wikipedia.org/wiki/Fragmentation_(computing[/url])
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