The Pure Fabrication Tax

Last week, I attended the Maexle event of the C++ user group in Karlsruhe. The Maexle event is basically a programming contest where your program plays the Mia dice game against other programs. You have to implement a simple network protocol to join games, announce rolls and call bluffs. Your program earns points for every game it has participated and not lost. So there is a strong emphasis on starting early and staying in the game, even if your program doesn’t perform the best.

Since it was an event of the C++ user group, the programming language to be used was C++. I’m certainly no C++ hero and knew I couldn’t compete, so I joined the fun with an espionage role and programmed an observing bot that doesn’t play, but gathers data on the players. I chose Java for the task. My observer was online after two minutes, the first real player joined the server after 20 minutes. It turned out to be written in Python. The first real C++ bot was online after 35 minutes, the last one played its first round after two hours.

I listened closely to the problems the teams around me tackled and noticed something strange: Nobody talked about the actual game (Maexle/Mia). Every task was a technical one. Let’s talk about why that’s a problem.

Three Definitions

Before I dive into the subject, I want to define some terms that I’ll use to help you understand my point. It’s entirely possible to look at the story above and see a bunch of engineers having fun with some engineering tasks.

  • First, I value the economics of my customer. In this case, the customer is a lonely server on the LAN that wants to host some games of Maexle for bots. Like, lots of games. Thousands of games. The customer gives points for early market entry, so time to market is an economic factor (or a key performance indicator, some might say). You can roughly say that being online early means you can make bucks longer. The second key performance indicator is uptime. You want to stay in the game as long as you don’t lose all the time. There are some more KPI, but the two I’ve listed should have a major impact in your programming approach – if you value the economics.
  • Second, I don’t care about tools. A programming language is a tool. A compiler is a tool. Your IDE or text editor is a tool. Use your preferred tooling as long as it suits your needs. That means explicitely as long as it doesn’t actively work against your other values like the customer’s economics. This blog post is definitely not about Java or Python being “better” or “better suited” than C++. They aren’t. The first two bots (observer and player) were programmed by participants that had prior experience with the event. It wasn’t the tool that made them fast, it was the absence of rookie errors in the domain and its technical structure.
  • Third, I will explain my point with the concept of “pure fabrication. Pure fabrication is everything that is not specified by the customer, but necessary to fulfill the specification. It’s the code you write because your customer wants to persist some data. He never ordered you to write SQL statements or “open a connection to the database”, maybe he didn’t even know what a database was. Your customer wanted the data stored somehow. The code that enables you to actually program the storage is “pure fabrication” in terms of the domain. Think of it as a scaffolding holding your domain code in place. If you hire a painter to color your house, he will scaffold the walls to reach every spot with ease. You didn’t hire him to set those structures up, they are just necessary for the task. The difference to most of our code is that the painter removes the scaffolding afterwards.

Pure Fabrication vs. Domain

So, if I would have been a customer on the Maexle event, paying for a competitive Maexle bot, I would be very surprised about the actual construction process. Up to two hours into a three-hours event, my programmer would solve apparently hard and important problems, but not my problems. In fact, I wouldn’t even understand the relation between the attempted problems and my required solution. And I would have to have blind faith for more than half my money that something useable will come out of this.

This is the effect of too much pure fabrication in the programming approach. I’m all for solving hard programming problems, but I’m not interested in solving them over and over again. After some iterations, they become solved problems or, essentially, tools. And I don’t care about tools as long as they get their job done. If your domain problem requires a better tool, then we can put the programming problem on our todo list again. Otherwise, we are not valueing our customer’s economics, we are showing off to our peers.

If you program a simple game of Maexle with a heavy emphasis on time to market and even after the initial ramp up aren’t able to reason about your code using language from the domain (like game, dice, roll, bluff, double and, of course, mia), you are staying in pure fabrication land. That’s the level of programming where it matters if you used an integer or freed that memory. That’s when you pay the Pure Fabrication Tax to the fullest. Because your code now does something valueable in the domain, but the distance between your customer’s language and your code’s language is an hindrance. And this distance will demand its tax with every new feature, every change request and every bug.

Bugs are another area where the distance is measureable. If you can’t explain your bugs to the customer, you’ve made them in the pure fabrication part of your code. If you can never explain your bugs, your domain code is hidden between lines and lines of source code with lots of special characters, brackets and magic numbers. Just imagine your hired painter tries to tell you why your house is now pink instead of white or yellow: “It was a small mishap in the way we constructed the scaffolding, we used an E5 steel beam instead of a rail clamp and forgot to perform a hammer check on it”. The last part is totally made up, but I’m sure that’s how we sound for non-programmers.

Exemptions from the Tax?

What solution would I suggest? I don’t think there is a definite solution to the problem. You can’t go full Domain Driven Design on a three-hour Maexle event. By the time you’ve built your fancy Domain Specific Language to write code with the customer besides you, everybody else has gathered their game points and gone home. If you switch to a language that has a string tokenizer in its standard library, you can speed up your programming, but maybe just produce a bigger heap of slightly less low-leveled pure fabrication code.

I don’t want to advocate a solution. My attempt is to highlight the problem: The Pure Fabrication Tax. Given the right (or wrong) amount of extrinsic (or intrinsic) motivation, we are able to produce a mess in just a few hours without really connecting to the domain we produce the mess for. If we didn’t program a Maexle bot that night, but a poker bot or a chat bot, most if not all of the problems and bugs would have been the same. This is not a domain-specific problem. It’s our problem. We probably just like to pay the tax.

What are your thoughts on the Pure Fabrication Tax? Can you see it? Do you have an idea for a solution approach? Leave your comment below!

Disclaimer

And to counter everybody who thinks I’m just bashing the other participants on the event: I was the first one online on the server, with a task that requires virtually no effort and doesn’t even participate directly in the competition, with tools that solved nearly all my pure fabrication problems and still managed to create a program that contained less than five domain terms and was useless for its intended purpose. I said I value the economics of my customer (even if there was none), so I know that I failed hardest on the event. And I had prior knowledge. There was just nobody to compare my mess to.

Game Optimization Resolved

In my last blog post, I explained a performance problem in my game abstractanks but not how I solved it.

So I had not done any optimization work in a while, so the first thing I did turned out to be an error. And not only in hindsight – I actually knew how to tackle a problem like that – I just temporarily forgot at that point.

Going down the rabbit hole

Where we left off, my profiler showed FriendlyUnitOccupies as the culprit. That function basically does circle/circle collision detection using a quad-tree as the spatial acceleration structure. Looking at the samples from my profiler, I could see that that it was descending into the tree quite deeply. Like all tree structures, a quad-tree does pointer-chasing which is very bad for modern CPUs. So I figured I should look at how to optimize that. The data structure was implemented in a hurry, so there seemed plenty to do:

  • Instead of recursing into each node, use tail-call optimization and early culling to speed up traversal.
  • Pre-cache the query with the max-search radius and the other requirements to the units, e.g. not dead, same team, etc.. and then use that to build a new tree for the actual queries.

Because the data structure was pretty non-generic, I started to basically rewrite it to use it in this scenario. While I was about half way through with that, it dawned on me that I was barking at the wrong tree.

Taking a step back

The excellent book Video Game Optimization has some great advice on which level to attack an optimization problem.

  1. System-level. Can you change the system to do something differently and still solve your problem?
  2. Algorithm-level. Are you using the most efficient right algorithm for the data you have?
  3. Micro-level. Are you not wasting any processing power on the lower levels?

I was already on the algorithm level. So I went back to the systemic level: What if the AI did not try to change the target position that often, maybe just every few seconds? That effectively meant lowering the AIs APM. It’s not a bad solution, especially since that makes the AI behave more human. But on the other hand, real-time games, as the name implies, have a soft real-time requirement. So you generally like to avoid huge workloads that go over your frame budget. With how slow the algorithm was, that could easily be the case. The solution is then to do the work concurrently, either by splitting it up or doing it in the background. Both solutions seemed difficult, since the AI code does currently not allow for easy concurrency. So that idea was out.

What if the parking-positions where cached? Subsequent calls to get parking positions could probably reuse a lot of the positions that were computed in previous frames, given that the target point only moves by a little bit each frame. I figured that might work, but it requires more housekeeping and data-dependencies – the result of the previous query needs to be used for the next. That seemed complex and therefore brittle.

A Solution?

Temporal coherency was a pretty good idea though, but not the scale was to big this time. What if I exploited it within a single frame? Now the original code did obscure this, but maybe it gets a little more clear if I write it 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);  
  };
  auto Samples = SampledPositions(Center, SomeRandomness());
  auto Found = find_if(SampledPositions.begin(), SampledPositions.end(), CheckPosition(Position));
  
  return (Found != SampledPositions.end()) ? *Found : none;
}

Now as I explained in the previous post, this was called in a loop for each unit to be parked.

std::vector<v2> GameWorld::FindParkingPositions(v2 Center, std::size_t N)
{
  std::vector<v2> Results;
  for (std::size_t i = 0; i < N; ++i)
  {
    auto MaybePosition = FindFreePosition(Center, Results);
    if (!MaybePosition) // No more free space?
      break;
    Results.push_back(*MaybePosition);
  }
  return Results;
}

Easy to see: counting the number of CheckPosition calls, this algorithm is O(n) in number of sampled positions. The number of sampled positions depends linearly on the number of units to be parked, because more units obviously need more parking positions, essentially making this O(n²) for the unit count! But the positions get resampled for each unit – with the only change being the little bit of randomness that is injected everytime. In other words, each call would just test false for sampled positions roughly corresponding to the units that are already placed.

So what I did was a very small change: only inject the randomness once and merge the loops:

auto Samples = SampledPositions(Center, SomeRandomness());
std::vector<v2> Results;

for (auto const& Sample : Samples)
{
  if (CheckPosition(Sample))
    Results.push_back(Sample);

  if (Result.size() >= N)
    break;
}
return Results;

And this did the trick! The algorithm’s run-time when below the 1ms range, and the smaller variation in randomness is not really visible.

Conslusions

I was thrown off-track be the false conclusion that CheckPositions was too slow when it was in fact just called too often. Context is key! Always approach these things outside-in.
Using less-than-optimal abstractions obscured the opportunity to hoist out the sample generation from me. Iteration is always a separate concern, even when it is not on containers!

Entity Framework migrations with multiple database contexts

The .NET Entity Framework provides functionality for automatic database migrations. Every time your application code requires a change of the database schema you should create a migration, so that the existing database schema is updated when a new version of the application is deployed. Examples for such changes are new entity classes or the addition and removal of properties of existing entity classes. The Entity Framework functionality for database migrations is called Code First Migrations.

Code First Migrations are managed via the so-called Package Manager Console. That’s how it’s called in Visual Studio, because its usually used for package management, but it’s basically a general Power Shell command line interface. After you have created the database context class and the entity model classes for your application, you create an initial migration (usually called InitialCreate), which captures the original state of the database schema for your application:

Add-Migration InitialCreate

This will create a new migration class called InitialCreate in the Migrations folder. The filename is prefixed with a timestamp: 201810702207458_InitialCreate.cs. Each migration class has an Up() method, which applies the migration and a Down() method, which rolls the migration back.

Each subsequent migration only describes the difference to its predecessor migration. For example, you add a new string property Email to your User entity class and add a new migration:

Add-Migration AddUserEmail

The tool will scan your entity classes, compare the current state to the state of the previous migration, calculate the difference and create a new migration class, which adds a new column to the database schema.

When the migrations are run on the target system they are tracked in a special database table called __MigrationHistory.

Multiple database contexts

The above usage of Code First Migrations is well documented. Here I want to describe a feature, that is documented in less detail, because it’s less commonly used: migrations with multiple database contexts.

Let’s assume you have two database contexts: CoreDataContext and MeasurementDataContext. In this case you have to create two migration configuration classes, which inherit DbMigrationsConfiguration. You want to create two subdirectories under the Migrations directory, one for each database context:

In each subdirectory you create a migrations Configuration class, one for each database context:

namespace Migrations.CoreData
{
  internal sealed class Configuration : DbMigrationsConfiguration<CoreDataContext>
  {
    public Configuration()
    {
      MigrationsDirectory = "Migrations\CoreData";
      AutomaticMigrationsEnabled = true;
    }
  }
}

and

namespace Migrations.MeasurementData
{
  internal sealed class Configuration : DbMigrationsConfiguration<MeasruementDataContext>
  {
    public Configuration()
    {
      MigrationsDirectory = "Migrations\MeasurementData";
      AutomaticMigrationsEnabled = true;
    }
  }
}

For each configuration you have to set the MigrationsDirectory property accordingly. The AutomaticMigrationsEnabled property is optional. If it’s set the migrations will be applied automatically at the start of the application.

Now, if you run a migration command like Add-Migration, you have to add the -ConfigurationTypeName option, which specifies the Configuration class for desired the database context:


Add-Migration InitialCreate -ConfigurationTypeName Migrations.CoreData.Configuration

Add-Migration InitialCreate -ConfigurationTypeName Migrations.MeasurementData.Configuration

Add-Migration AddUserEmail -ConfigurationTypeName Migrations.CoreData.Configuration

Add-Migration AddMeasurementTimestamp -ConfigurationTypeName Migrations.MeasurementData.Configuration

The migration classes will now be created in the correct subdirectories.

Transforming C-Style arrays in java

Every now and then some customer asks us to fix or improve some important legacy application other people have written. Usually, such projects are fun and it is rewarding to see the improvements both in code and value for the users.

In one of these projects there is a Java GUI application that uses C-style arrays for some of its central data structures:

public class LegoBox  {
  public LegoBrick[] bricks = new LegoBrick[8000];
  public int brickCount = 0;
}

The array-length is a constant upper bound and does not denote the actual elements in the array. Elements are added dynamically to the array and it looks like a typical job for a automatically growing Collection like java.util.ArrayList. Most operations simply iterate over all elements and perform some calculations. But changing such a central part in a performance sensitive application is not only a lot of work but also risky.

We decided to take an incremental approach to improve code readability and maintainability and measured performance with a large, representative dataset between refactorings. There are two easy alternative APIs that improve working with the above data structure.

Imperative API

Smooth migration from the existing imperative “ask”-code (see “Tell, don’t ask”-principle) can be realized by providing an java.util.Iterable to the underlying array.


public int countRedBricks() {
  int redBrickCount = 0;
  for (int i = 0; i < box.brickCount; i++) {
    if (box.bricks[i].isRed()) {
      redBrickCount++;
    }
  }
  return redBrickCount;
}

Code like above is easily transformed to much clearer code like below:

public class LegoBox  {
  public LegoBrick[] bricks = new LegoBrick[8000];
  public int brickCount = 0;

  public Iterable<LegoBrick> allBricks() {
    return Arrays.stream(tr, 0, brickCount).collect(Collectors.toList());
  }
}

public int countRedBricks() {
  int redBrickCount = 0;
  for (LegoBrick brick : box.bricks) {
    if (brick.isRed()) {
      redBrickCount++;
    }
  }
  return redBrickCount;
}

Functional API

A nice alternative to the imperative solution above is a functional interface to the array. In Java 8 and newer we can provide that easily and encapsulate the iteration over our array:

public class LegoBox  {
  public LegoBrick[] bricks = new LegoBrick[8000];
  public int brickCount = 0;

  public <R> R forAllBricks(Function<Brick, R> operation, R identity, BinaryOperator<R> reducer) {
    return Arrays.stream(bricks, 0, brickCount).map(operation).reduce(identity, reducer);
  }

  public void forAllBricks(Consumer<LegoBrick> operation) {
    Arrays.stream(bricks, 0, brickCount).forEach(operation);
  }
}

public int countRedBricks() {
  return box.forAllBricks(brick -> brick.isRed() ? 1 : 0, 0, (sum, current) -> sum + current);
}

The functional methods can be tailored to your specific needs, of course. I just provided two examples for possible functional interfaces and their implementation.

The function + reducer case is a very general interface and used here for an implementation of our “count the red bricks” use case. Alternatively you could implement this use case with a more specific but easier to use filter + count interface:

public class LegoBox  {
  public LegoBrick[] bricks = new LegoBrick[8000];
  public int brickCount = 0;

  public long countBricks(Predicate<Brick> filter) {
    return Arrays.stream(bricks, 0, brickCount).filter(operation).count();
  }
}

public int countRedBricks() {
  return box.countBricks(brick -> brick.isRed());
}

The consumer case is very simple and found a lot in this specific project because mutation of the array elements is a typical operation and all over the place.

The functional API avoids duplicating the iteration all the time and removes the need to access the array or iterable/collection. It is therefore much more in the spirit of “tell”.

Conclusion

The new interfaces allow for much simpler and maintainable client code and remove a lot of duplicated iterations on the client side. They can be introduced on the way when implementing requested features for the customer.

That way we invested only minimal effort in cleaner, better maintainable and more error-proof code. When someday all accesses to the public array are encapsulated we can use the new found freedom to internalize the array and change it to a better fitting data structure like an ArrayList.

What’s your super power?

I believe that every software developer (even every human) has a super power. One (or more) strength which helps his team, his company, his work to be better. It might be hidden or contained but it is there.
One way to find it is to ask your colleagues. Another to identify your contributions in your last projects or to look at what kind of work brings you joy, makes you feel like a fish in the water.
Let me give you an example. My power is to tackle complexity, reduce it to the essence and bring clarity to people. When I see a complex (or complected) network of interchanging applications doing things twice or even thrice, not talking to another, misunderstanding one might feel overwhelmed. I feel the need to dig in and bring out the most important part, the critical path, the essence. This isn’t restricted to software, this could be a group of people as well. I like to understand systems what makes them work and what hinders them. What is wasted and where do we have to make more effort.
Ask yourself: where I am good at? Where do I see things others don’t? Where do I accept the challenge? When do I strive? There might be your super power…

Putting toilet books into practice

I’m reading a lot of books and based on my profession and interests, my list includes many software development and IT books. I want to share how I manage my reading and give some recommendations for a special type of book that I call “toilet book”.

Three books at once

The human mind is a peculiar thing. You’ve probably experienced the effect of getting up to perform some minor task in an other room only to arrive there with no recollection about what you wanted to do. Between the thoughts of “ok, let’s do this now!” and “why did I go here?”, just a few seconds have passed, but another aspect has changed dramatically: your geographic position. As a side note: If you don’t know what I’m talking about, consider yourself lucky. Our memory is often bound to the geographic position and changes when we move. If you want to remember what your forgotten task was, try returning to your original location. You’ll often see me walking around the same way twice within seconds. That’s when I have to rewind my location-based memory.

A particular use case where I leverage my location-based memory is when I read books. I often read three books at once, but strictly separated by location:

  • The first book is the “leisure book“: I will only read it at comfortable locations like the couch, in the sun on the balcony or in the bathtub. This book is often fiction or has at least nothing to do with IT.
  • The second book is the “travel book“: You’ll seldom see me travelling without a book and just a few minutes of tram are sufficient to read some pages. This book is often IT-based, because I read it on my commute to and from work and sometimes in my lunch break.
  • The third book is the “toilet book“: You’ll never see me reading this book, because it is stored besides my toilet and is exclusively read there. Books that are suitable for this task often have a special structure that aligns with the circumstances. More on this in a moment.

By having a clear separation by location for the three books, I’m able to keep their content separated and switch from one reading context to the next without effort. It happens naturally if I refrain from reading my travel book at home or taking my leisure book on the train.

The structure of a toilet book

A good toilet book has a special structure that accommodates for the special timing of a toilet visit. If you spend two minutes on the toilet, the book should have chapters or at least paragraphs that can be read in two minute intervals. Ideally, the book is specifically designed to contain short chapters on different topics that have no strong over-arching story. A typical example of a good non-IT toilet book are comic books like Calvin & Hobbes, The Peanuts or any other comic series that has small self-contained comic strips. You read one or two strips, are amused and interrupt again without having to memorize a complex context. Good toilet books allow for short, context-free reading sessions.

A collection of worthwhile toilet books

Over the years, I’ve read some toilet books with IT and software development topics and want to share my list of books that I enjoyed reading in this fashion:

In short, for me, calling a book a “toilet book” is not a derogatory taunt, but a neutral description that this book is structured in a way to support repeated short-time reading sessions. For me, these books are a good choice for a tertiary reading track.

A call for proposals

Right now, my reading list of good IT toilet books is rather short. If you happen to know a book that fits my description, I would be thankful for a hint in the comments. Thank you!

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?