A Game Optimization War Story

As our customers surely know, I’m not working here on fridays. This is because that’s the time I allocate to my side project, an arcade real-time strategy game called abstractanks. It is a passion project above all else, but of course, I am also learning a lot, much of which I can apply to my “day job” here as well. Today I want to share the story of how I optimized a critical bit of code in that game.

The Big Slowdown

While working on scripted missions, one main element I am using is to make a group of units attack when you enter an area (a.k.a. a zone-trigger). This seems easy enough, but was causing massive slowdowns as soon as the enemy group started moving. My average logic frame-time jumped from 0.3 ms to more than 1500 ms, which essentially makes the game unplayable. When seeing a performance problem, your first instinct should always be to profile it. So I booted up WPR/WPA and did just that. Once I had the profile, I followed the most-sampled path in the stack and found my way to the supposed culprit: the parking algorithm.

Context

When optimizing, you need as much context as you possible to find the best possible course of action. So let me explain how that algorithm fits into the broader picture.

Parking

My main game-mechanic is moving around your units. You do this by selecting a group and then clicking somewhere on the map to issue the move-order. In addition to path-finding process, this also runs an algorithm I call park-planning (as in parking a car). It makes sure that the units know to position themselves around the target point in a roughly circular shape once they arrive. It is essential to the interaction of this mechanic with the capturing of objectives, which are circular as well. Before this was implemented, the units would just decelerate after passing the target point. This caused them to “overshot” and miss the objectives, which was frustrating to the players: they clicked in the right place, but the units would not stop there, but slightly behind it. To make things worse, units arriving later, would bump into those that were already there, further pushing them away and clumping up.

AI Moving

In my particular case, the AI enemy was repeatedly issuing move-orders to close in on the intruder – the player. Since the player group usually also moved, the AI was trying to adapt by changing the move order every frame (effectively working at around 2000 APMs).

Diving into the code

My park-planning implementation is divided into two steps: finding enough parking spots, and then assigning units to it. The profiler was showing that the first part was the problem while the assignment was negligible in terms of run-time. Historically, the first step was reusing and extending some code I first wrote for spawning units, which worked like this:

optional<v2> GameWorld::FindFreePosition(v2 Center, std::vector<v2> const& Occupied)
{
  auto CheckPosition = [&](v2 Candiate)
  {
    if (!IsPassable(Candidate))
      return false;

    if (OverlapsWith(Occupied))
      return false;

    return !FriendlyUnitOccupies(Candidate);   
  };

  if (CheckPosition(Center))
    return Center;

  auto Radius = UNIT_SIZE;
  while (Radius < MAX_SEARCH_RADIUS)
  {
    // Roll a random starting angle
    auto AngleOffset = RandomAngle();
    auto Angle = 0.f;
    while (Angle < 2*Pi)
    {
      auto Candidate = Center + AngleVector(Angle + AngleOffset)*Radius;
      if (CheckPosition(Candidate))
        return Candidate;

      // Move along this circle
      Angle += 2*Pi*Radius / UNIT_SIZE / OVERSAMPLING_FACTOR;
    }

    // Increase the Radius
    Radius += UNIT_SIZE;
  }
  return none;  
}

Note that all the functions in the CheckPosition lambda are “size aware” and respect the UNIT_SIZE – so they are slightly more complex than what the pseudo-code here would have you believe.
The occupied parameter was added for the parking-position finding. It successively fills up the std::vector with positions and uses them once it found enough.

Back to the profiling results: They were showing that most of the time was spent in the FriendlyUnitOccupies, followed by IsPassable and and then OverlapsWith. FriendlyUnitOccupies dominated the time by about 8x times the rest. That function uses a quad-tree to accelerate spatial queries for other units.

Next steps

Obviously, this code uses pretty simplistic approach to the problem – basically just brute-forcing it. But that’s good now there are many different paths to take, many optimization opportunities. My approach was a relatively simple change that got the frame time back down below 1 ms, but before I did that, I considered many and tested a few other different approaches. I will talk about that in detail in my next post. How would you approach this?

Handling database warnings with JDBC

Database administrators have the possibility to set lifetimes for user passwords. This can be considered a security feature, so that passwords get updated regularly. But if one of your software services logs into the database with such an account, you want to know when the password expires in good time before this happens, so that you can update the password. Otherwise your service will stop working unexpectedly.

Of course, you can mark the date in your calendar in order to be reminded beforehand, and you probably should. But there is an additional measure you can take. The database administrator can not only set the lifetime of a password, but also a “grace period”. For example:

ALTER PROFILE app_user LIMIT PASSWORD_LIFE_TIME 180 PASSWORD_GRACE_TIME 14;

This SQL command sets the password life time to 180 days (roughly six months) and the grace period to 14 days (two weeks). If you log into the database with this user you will see a warning two weeks before the password will expire. For Oracle databases the warning looks like this:

ORA-28002: the password will expire within 14 days

But your service logs in automatically, without any user interaction. Is it possible to programmatically detect a warning like this? Yes, it is. For example, with JDBC the following code detects warnings after a connection was established:

// Error codes for ORA-nnnnn warnings
static final int passwordWillExpireSoon = 28002;
static final int accountWillExpireSoon = 28011;

void handleWarnings(Connection connection) throws SQLException {
    SQLWarning warning = connection.getWarnings();
    while (null != warning) {
        String message = warning.getMessage();
        log.warn(message);

        int code = warning.getErrorCode();
        if (code == passwordWillExpireSoon) {
            System.out.println("ORA-28002 warning detected");
            // handle appropriately
        }
        if (code == accountWillExpireSoon) {
            System.out.println("ORA-28011 warning detected");
            // handle appropriately
        }
        warning = warning.getNextWarning();
    }
}

Instead of just logging the warnings, you can use this code to send an email to your address, so that you will get notified about a soon-to-be-expired password in advance. The error code depends on your database system.

With this in place you should not be unpleasantly surprised by an expired password. Of course, this only works if the administrator sets a grace period, so you should agree on this approach with your administrator.

Analysing a React web app using SonarQube

Many developers especially from the Java world may know the code analysis platform SonarQube (formerly SONAR). While its focus was mostly integration all the great analysis tools for Java the modular architecture allows plugging tools for other languages to provide linter results and code coverage under the same web interface.

We are a polyglot bunch and are using more and more React in addition to our Java, C++, .Net and “what not” projects. Of course we would like the same quality overview for these JavaScript projects as we are used to in other ecosystems. So I tried SonarQube for react.

The start

Using SonarQube to analyse a JavaScript project is as easy as for the other languages: Just provide a sonar-project.properties file specifying the sources and some paths for analysis results and there you go. It may look similar to the following for a create-react-app:

sonar.projectKey=myproject:webclient
sonar.projectName=Webclient for my cool project
sonar.projectVersion=0.3.0

#sonar.language=js
sonar.sources=src
sonar.exclusions=src/tests/**
sonar.tests=src/tests
sonar.sourceEncoding=UTF-8

#sonar.test.inclusions=src/tests/**/*.test.js
sonar.coverage.exclusions=src/tests/**

sonar.junit.reportPaths=test-results/test-report.junit.xml
sonar.javascript.lcov.reportPaths=coverage/lcov.info

For the coverage you need to add some settings to your package.json, too:

{ ...
"devDependencies": {
"enzyme": "^3.3.0",
"enzyme-adapter-react-16": "^1.1.1",
"eslint": "^4.19.1",
"eslint-plugin-react": "^7.7.0",
"jest-junit": "^3.6.0"
},
"jest": {
"collectCoverageFrom": [
"src/**/*.{js,jsx}",
"!**/node_modules/**",
"!build/**"
],
"coverageReporters": [
"lcov",
"text"
]
},
"jest-junit": {
"output": "test-results/test-report.junit.xml"
},
...
}

This is all nice but the set of built-in rules for JavaScript is a bit thin and does not fit React apps nicely.

ESLint to the recue

But you can make SonarQube use ESLint and thus become more useful.

First you have to install the ESLint Plugin for SonarQube from github.

Second you have to setup ESLint to your liking using eslint --init in your project. That results in a eslintrc.js similar to this:

module.exports = {
  'env': {
    'browser': true,
    'commonjs': true,
    'es6': true
  },
  'extends': 'eslint:recommended',
  'parserOptions': {
    'ecmaFeatures': {
      'experimentalObjectRestSpread': true,
      'jsx': true
    },
    'sourceType': 'module'
  },
  'plugins': [
    'react'
  ],
  'rules': {
    'indent': [
      'error',
      2
    ],
    'linebreak-style': [
      'error',
      'unix'
    ],
    'quotes': [
      'error',
      'single'
    ],
    'semi': [
      'error',
      'always'
    ]
  }
};

Lastly enable the ESLint ruleset for your project in sonarqube and look at the results. You may need to tune one thing or another but you will get some useful static analysis helping you to improve your code quality further.

C++ header-only libraries are bad

A somewhat more recent trend in the C++ community is the popularity of header-only single-file libraries. Prominent examples are catch2, JSON for Modern C++ and spdlog. These are all great, modern and popular libraries, and I personally enjoy using all of them.

But back to the provoking title. This may be a bit of an over-generalization, and it is meant to be a little bit ambiguous. Mathieu Ropert already pointed out that header-only files are but a symptom of the whole C++ modules and package misery. The aforementioned libraries are all great pieces of software but it is bad that:

  • they are exclusively header-only
  • header-only is seen as a sign of quality these days

Historically, header-only libraries have been a thing in C++ because of templates. Templates are not functions or variables that can be referenced by the linker. No, as the name so fittingly suggests, they are just templates for those, with the potential to become, or better, be instantiated into, something that actually survives the trip to the executable code. Header-only libraries used to be code that could only materialized in the context of other code.

But the focus has shifted to portability. I guess by coincidence, people discovered that header-only libraries are also relatively easy to import into your project.

It is actually about inlining

Splitting code between headers and implementation files is a trade off, one that is often synonymous with marking functions inline or not. Inlining is just one more fine-tuning tool that C++ programmers have at their disposal to make the resulting application behave as they want. Carefully considering whether to inline helps to manage compile times, transitive dependencies and code-bloat.

Even for template-heavy libraries, not all of it has to to be inlined. It is often beneficial for compilation-time, code-size and run-time to use techniques such as thin templates to make sure some of the code is properly insulated.

Another way?

Promoting “header-only” as the new buzzword for portability has the side-effect of implying which code is not marked as inline: None.

That is just ignorant of that dimension of the code. It is equivalent to not making a choice about insulation and inlining.

Sure, header-only is marginally better for dropping into your code, but adding a portable implementation file should be just as easy. Why not deliver portable libraries as a single implementation file and a single header instead? Those could easily be generated by a preprocessing step E.g. catch2’s single-header is generated anyways, so it should not be much harder to split that output into two files. Of course the implementation file should be able to work within your compilation environment. But the same restrictions apply to the single-header file, so there’s really no additional difficulty. And it is really easy to go from the two-file version to the single file by just marking everything in the implementation file as inline and including it in the header.

.NET Core for platform independent web development

Several of our projects are based on the .NET platform. Until recently all of them used the classic .NET Framework. With a new project we had the opportunity to give .NET Core a try. The name stands for a moderized variant of the .NET Framework. It is developed by The .NET Foundation and Microsoft as a platform independent open-source project.

Not every type of project is currently suitable for .NET Core. If you want to develop a Windows desktop application (WinForms, WPF) you still have to use the classic .NET Framework. However, for server based applications .NET Core is a really good fit. Our application, for example, is implemented as a JSON API server with .NET Core and a React/Redux based client interface.

The Benefits

Since .NET Core is platform independent it runs on Linux, MacOS and Windows. We no longer need a Window machines to build the project from our CI server. Microsoft provides Docker images for building and running .NET Core projects.

ASP.NET Core applications are no longer bound to Microsoft’s IIS or IIS Express. You can also host them on Apache or Nginx servers as well.

With .NET Core you also have a vast choice of IDEs. Of course, you can use Visual Studio on Windows. But you also have the option to use JetBrains’ Rider (on any platform), Visual Studio for Mac or Visual Studio Code (Mac, Linux, Windows). If you don’t want to use an IDE for everything .NET Core also has a nice command-line interface. For example, the following command sets up a new ASP.NET Core project with React and Redux:

$ dotnet new reactedux

To compile an run the project:

$ dotnet run

The Entity Framework Core also has a feature I missed in the Entity Framework for the classic .NET Framework: a pure in-memory database provider, which is very useful for testing.

The Downsides

When you browse the NuGet packages list you have to be aware that not every package is compatible with .NET Core yet, but the list is growing. And, as mentioned above, you can’t develop desktop GUI applications with .NET Core.

Ansible in Jenkins

Ansible is a powerful tool for automation of your IT infrastructure. In contrast to chef or puppet it does not need much infrastructure like a server and client (“agent”) programs on your target machines. We like to use it for keeping our servers and desktop machines up-to-date and provisioned in a defined, repeatable and self-documented way.

As of late ansible has begun to replace our different, custom-made – but already automated – deployment processes we implemented using different tools like ant scripts run by jenkins-jobs. The natural way of using ansible for deployment in our current infrastructure would be using it from jenkins with the jenkins ansible plugin.

Even though the plugin supports the “Global Tool Configuration” mechanism and automatic management of several ansible installations it did not work out of the box for us:

At first, the executable path was not set correctly. We managed to fix that but then the next problem arose: Our standard build slaves had no jinja2 (python templating library) installed. Sure, that are problems you can easily fix if you decide so.

For us, it was too much tinkering and snowflaking our build slaves to be feasible and we took another route, that you can consider: Running ansible from an docker image.

We already have a host for running docker containers attached to jenkins so our current state of deployment with ansible roughly consists of a Dockerfile and a Jenkins job to run the container.

The Dockerfile is as simple as


FROM ubuntu:14.04
RUN DEBIAN_FRONTEND=noninteractive apt-get update && apt-get -y dist-upgrade && apt-get -y install software-properties-common
RUN DEBIAN_FRONTEND=noninteractive apt-add-repository ppa:ansible/ansible-2.4
RUN DEBIAN_FRONTEND=noninteractive apt-get update && apt-get -y install ansible

# Setup work dir
WORKDIR /project/provisioning

# Copy project directory into container
COPY . /project

# Deploy the project
CMD ansible-playbook -i inventory deploy-project.yml

And the jenkins build step to actually run the deployment looks like


docker build -t project-deploy .
docker run project-deploy

That way we can tailor our deployment machine to conveniently run our ansible playbooks for the specific project without modifying our normal build slave setups and adding complexity on their side. All the tinkering with the jenkins ansible plugin is unnecessary going this way and relying on docker and what the container provides for running ansible.

uninitialized_tag in C++

No doubt, C++ is one of those languages you can use to squeeze out every last drop of your CPU’s processing power. On the other hand, it also allows a high amount of abstraction. However, micro-optimization seldom works well with nice abstractions.

The dilemma

One such case is the matter of default-initialization with “math types”, such as three-dimensional vectors used in computer graphics. Do you let your default constructor zero initialize by default or do you leave the elements uninitialized and risk undefined behavior?

One way around this dilemma is to use tag dispatching to enable both:

template <class T> struct v3 {
  v3(T v={}) : x{v}, y{v}, z{v} {}
  v3(uninitialized_tag) {}
  T x,y,z;
};

Now a v3 zero-initializes by default, while you can still avoid the initialization costs by calling it with:

v3<float>{uninitialized_tag{}};

Drawbacks

This approach is not without drawbacks. It’s a bit of an uphill battle to find a good test for this. You need to overwrite the values before you use them, or the compiler is free to do whatever it wants when you use them. It’d be undefined behavior. But you also do not want it to figure out that you are overwriting all the values – because in that case, it can optimize out the zero-initialization anyways.
It does work for a few simple cases though, and you scan see the zero-initialization getting removed, e.g. in the compiler explorer.

However, it will often not let you do what you set out to do – leave some some vectors uninitialized. Consider this:

std::vector<v3<float>> v(N, uninitialized_tag{});

This does not, in fact, transport the uninitialized_tag to the v3 constructor. It first converts the tag to a v3, and then uses that value to initialize all the other N elements with the uninitialized data. This is actually a lot of copying, and creates a whole lot more code than the zero initialization would have. You can get this to work with a container that uses the given initializer value to initialize the elements without converting first. You’re probably better of with a mechanism like the std::vector::reserve that essentially gives you the ability to leave elements uninitialized.

Conclusion

This is a very specialized method for very few niche cases, and you need to carefully select your infrastructure to see any gain that cannot be achieved by simpler means. Use with caution!