luabind deboostified tips and tricks

luabind deboostified is a fork of the luabind project that helps exposing APIs to Lua. As the name implies, it replaces the boost dependency with modern C++, which makes it a lot more pleasant to work with.

Here are a few tips and tricks I learned while working with it. Some tricks might be applicable to the original luabind – I do not know.

1. Splitting module registration

You can split the registration code for different classes. I usually add a register function per class, like this:

struct A {
  void doSomething();
  static luabind::scope registerWithLua();
};

struct B {
  void goodStuff();
  static luabind::scope registerWithLua();
};

You can then combine their registration code into a single module on the Lua side:

void registerAll(lua_State* L) {
  luabind::module(L)[
    A::registerWithLua(),
    B::registerWithLua()];
}

The implementation of a registration function looks like this:

luabind::scope A::registerWithLua()
{
  return luabind::class_<A>("A")
    .def("doSomething", &A::doSomething);
}

2. Multiple policies and multiple return values

Unlike C++, Lua has real multiple return values. You can use that by utilizing the return value policies that luabind offers. Lets say, you want to write this in Lua:

local x, y = a.getPosition()

The C++ side could look like this:

void getPosition(A const& a, float& x, float& y);

The deboostified fork needs its policies supplied in a type list. Let’s use a small helper meta-function to build that:

template <typename... T>
using joined = 
  typename luabind::meta::join<T...>::type;

Once you have that, you can expose it like this:

luabind::def("getPosition", &getPosition,
              joined<
                luabind::pure_out_value<2>,
                luabind::pure_out_value<3>
              >());

3. Specialized data structures using luabind::object

Using the converters in luabind is not the only way to make Lua values from C++. Almost everything you can do in Lua itself, you can do with luabind::object. Here is a somewhat contrived example:

luabind::object repeat(luabind::object what,
                       int count) {
  // Create a new table object
  auto result = luabind::newtable(
    what.interpreter());
  // Fill it as an array [1..N]
  for (int i = 1; i <= count; ++i)
    result[i] = what;
  return result;
}

This function can then be exported via luabind::def and used just like any other function. This is just the tip of the iceberg, though. For example, you can also write functions that, at runtime, behave differently when a number is passed in as when a table is passed in. You can find out the Lua type with luabind::type(myObject).

Of course, as soon as you want to create new objects to return to Lua, you need the lua_State pointer in that function. Using the interpreter from a passed-in luabind::object is one way, but I have yet to find another pleasant way to do this. It is probably possible to use the policies to do this, and have them pass that in as a special parameter, but for now I am using some complicated machinery to bind lambda functions that capture the Lua interpreter.

That’s it for now..

Keep in mind that these are not thoroughly researched best-practices, but patterns I have used to solve actual problems. There might be better solutions out there – if you know any, please let me know. Hope this helped!

Decoding non-utf8 server responses using the Fetch API

The new Javascript Fetch API is really nice addition to the language and my preferable, and in fact the only bearable, way to do server requests.
The Promise based API is a lot nicer than older, purely callback-based, approaches.

The usual approach to get a text response from a server using the Fetch API looks like this:

let request = fetch(url)
  .then(response => response.text())
  .then(handleText);

But this has one subtle problem:

I was building a client application that reads weather data from a small embedded device. We did not have direct access to changing the functionality of that device, but we could upload static pages to it, and use its existing HTML API to query the amount of registered rainfall and lightning strikes.

Using the fetch API, I quickly got the data and extracted it from the HTML but some of the identifiers had some screwed up characters that looked like decoding problems. So I checked whether the HTTP Content-Type was set correctly in the response. To my surprise it was correctly set as Content-Type: text/html; charset=iso-8859-1.

So why did my Javascript Application not get that? After some digging, it turned out that Response’s text() function always decodes the payload as utf-8. The mismatch between that and the charset explained the problem!

Obviously, I had to do the decoding myself. The solution I picked was to use the TextDecoder class. It can decode an ArrayBuffer with a given encoding. Luckily, that is easy to get from the response:

let request = fetch(url)
  .then(response => response.arrayBuffer())
  .then(buffer => {
    let decoder = new TextDecoder("iso-8859-1");
    let text = decoder.decode(buffer);
    handleText(text);
  });

Since I only had to support that single encoding, that worked well for me. Keep in mind that the TextDecoder is still experimental Technology. However, we had a specific browser as a target and it works there. Lucky us!

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!

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?

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.

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!

Oversimplified C++ Project FAQ 2018

If you are starting a new C++ project, you’re faced with a few difficult decisions. C++ is not a ‘batteries-included’ language, so you need to pick a few technologies before you can start.
Yet worse, the answer to most of the pressing questions is often ‘it depends’ and changing one of the choices mid-project can be very expensive.
Therefore, I have compiled this list to give totally biased and oversimplified to the most important questions. If you want more nuanced answers, feel free to do your own research.
This is meant to be a somewhat amusing starting point.

FAQ

1. Which OS should I pick?

Linux

Rationale

Usually, not a choice you can make yourself – but if you do: dependency management is easier with a package manager, and it seems to be the most dominant OS in the C++ community. Hence you will get the best support and easiest access to technologies.

2. Which build system should I use?

CMake

Rationale

This is what everyone else is using, and those that are not are a real pain. For better or worse, the market is locked in. With target based properties in modern CMake, it’s not even that bad.

3. Which IDE should I choose?

Visual Studio 2017 on Windows, CLion everywhere else.

Rationale

CLion is getting more robust and feature rich with every release. Native CMake support and really cool refactoring capabilities finally make this a valid contender to Visual Studio’s crown. However, the VS debugger is still the best in the game, so VS still comes out on top on Windows – tho not by a huge margin.

4. Which Language version should you use?

C++14

Rationale

C++17 is not quite there yet with library, tool and platform support. Also, people do not really know how to use it well yet. C++14 builds on the now well-established C++11, which a few rather important “fixes” – and support is ubiquitous.

5. Which GUI toolkit should you use?

Qt

Rationale

No other toolkit comes close in maturity. Qt’s signal/slot system almost seamlessly integrates with C++11 lambdas, making the precompile step needed for SLOTs a non-issue. Barring the license costs for closed-source projects, there is really no reason not to use it.

6. Should you use Boost?

No

Rationale

Boost is a huge and clunky dependency that will explode your build times as soon as you even touch it. And it’s ‘viral’ enough that you can distinguish a Boost project from a non-Boost project. Boost.Optional, Boost.Variant and Boost.Filesystem prepare you for a smooth transition to C++17, but there are other more lightweight alternatives available.

Closing thoughts

There you have my totally biased opinion but hopefully entertaining. YMWV, but I think this is a good starting point if you don’t want to exeriment too much.