In this blog post, we’re going to explore how strings and names in UnrealScript work.

Textbook definitions

The official UnrealScript documentation ends up being quite terse:

string
A string of characters.
name
The name of an item in Unreal (such as the name of a function, state, class, etc). Names are stored as an index into the global name table. Names correspond to simple strings of up to 64 characters. Names are not like strings in that they are immutable once created.

This intuitively matches what we expect from those data types:

local name MyName, MyName2;
local string MyString, MyString2;

MyString = "Hi";
MyString2 = MyString;
MyString $= ", ÜC!"; // mutate string
`log(MyString); // ScriptLog: Hi, ÃœC!

MyName = 'Adv';
MyName2 = MyName;
MyName $= 'M1'; //❌ Error, Left type is incompatible with '$='
MyName = 'Other'; // re-assignment isn't mutation

Let’s delve into a bit more detail about how these data types might be implemented under the hood.

Strings

UnrealScript hides a lot of the complexity here but the C++ side needs to allocate memory for every variable. For a 32-bit integer (int), this size is known at compile-time (4 bytes), but a string can have arbitrary length (and grow/shrink at runtime). As a result, the string stores its data as a separate allocation:

With this, the data needed to store the string has a fixed size: A pointer to the actual data and the string length. These strings are terminated with a NUL character, as is common in the C world.

Let’s see what happens when we append the ", ÜC!" to the existing string:

The string re-allocates: It allocates a new, longer block of memory, copies the old data into it, appends the new string, and throws away (“frees”) the old data. That’s why we can freely mutate a string. But this means that creating a copy of the string requires a new allocation and duplicates the string data: If both strings pointed to the same data, changing one string would change the other too – or worse, we would throw away data that the other string is still referring to!

Encoding Woes

Unfortunately, the string isn’t what we expected: Instead of printing as “Hi, ÜC!”, it output “Hi, ÃœC!”. This is a consequence of the Unreal Engine 3 only supporting the ASCII and UTF-16 encodings when the original source file was saved in the UTF-8 encoding.

The Unreal Engine recognizes UTF-16 files by a Byte-Order-Mark (BOM), two unprintable bytes at the beginning of a file that indicate an UTF-16 encoding. An UTF-8 file has no BOM, so the compiler (being part of the engine) believes that the file is ASCII only and interprets the two bytes needed to represent the “Ü” codepoint as two ASCII characters “Ô and “œ”.

Names

Even though the official documentation makes it seem like names are reserved for built-in things, we can use names for anything! Case in point, the XCOM 2 engine uses names for Templates and configuration array entries like loot, loadouts or encounters.

Names have some unique properties not mentioned in the documentation:

• The empty name, '', compares equal to the name 'None'.
• Name comparison is case-insensitive: 'MyName' == 'mYnAmE'.

Let’s look a bit into how this global name table works.

The Name Table

The documentation says that names are stored as an index into the name table. This means that instead of owning the string data, a name is basically just a fancy int. We have a number of requirements for the implementation:

1. Names should reliably and efficiently be comparable: Two names should compare equal if and only if their indices are equal. This means that comparing two names is as efficient as comparing two ints.
2. Names should be efficiently created: No matter how many thousand names we already have, creating a name from a string should always take the same, low amount of time.
3. Names should efficiently be serialized: While storing names as integers is great when the game is running, we should save them as strings when we write them to a file so that we don’t have to rely on the numbers being the same when the game boots up the next time (spoiler: they wouldn’t be).

There are two pieces needed to make this work: The first is a name array; an ever-growing array containing every single name created, without duplicates. Whenever we want to create a name not already present in the name table, we can simply generate a new index by looking at the array length; and we can look up the string behind a name by indexing into this array. This piece already solves (1.) and (3.)!

When creating a name, we have to check if a that name already exists – otherwise, we could end up with the same name twice, and the same name would have a different index. Unfortunately, we’d have to iterate over the whole name array to find a name comparing equal. The Unreal Engine 3 solves this by employing a hash set.

This hash set is a fixed-size array with a comparatively low number of entries (say 32768), and we use a hash function to find the correct entry (“container”, “bucket”) for a given string. When we create a name from a string, we find the correct bucket, and check if the name is already there. If so, we have an existing name and re-use the index. If not, we add the new name to the name array and insert it also into this bucket.

In addition to the special name 'None', we’ll consider the three names from our code snippet: 'Adv', 'M1', and 'Other'. Let’s see what our data structures look like:

In our example, the names were inserted in the afore-mentioned order. 'None' has the hash 0, 'Adv' the hash 2, and 'M1' and 'Other' both share the hash 5. When we created the name Other, M1 was already in that bucket, M1 does not compare equal to Other, so we linked 'Other' before 'M1' and placed 'Other' into that bucket.

Memory leaks

This implementation never reclaims unused name data. Once we create a name, it will reside in the name table (and thus memory) until the game is closed! We can easily test this with the following code:

local string BaseString;
local name TempName;
local int i;

BaseString = "MySomewhatLongerBaseStringForHigherMemoryUsage";

`log("Starting...");
for (i = 0; i < 35000000; ++i)
{
    TempName = name(BaseString $ "_" $ i);
    if (i % 500000 == 0)
    {
      `log(i); // progress indicator and timer
    }
}
`log("Done!");

The measurements were performed on an Intel Core i5-3470 @ 3.20GHz, launched through a console command in TQL (to minimize interference from the game).

• Time: 39.86s
• Memory usage increase: 0MB

Wait, what? Our memory usage had no significant change!

The Number Optimization

Simply put, a _Number suffix is stripped before interning. Our names don’t actually consist of one number, but two numbers instead. The first number is an index into the name array, the second number is the numeric suffix.

Let 'XComLWTuple' be our sixth name. Then the name 'XComLWTuple' would be represented as 6|0 (0 for no suffix). 'XComLWTuple_0' would be represented as 6|1, 'XComLWTuple_1' as 6|2, 'XComLWTuple_345' as 6|346.

Our example code managed to trigger this optimization: Our names are 'MySomewhatLongerBaseStringForHigherMemoryUsage_0', 'MySomewhatLongerBaseStringForHigherMemoryUsage_1', and so on. This means that the game interns the MySomewhatLongerBaseStringForHigherMemoryUsage once and all our synthetic names re-use that index, just with a different number part. Testing two names for equality is thus a matter of comparing the two integers of the two names.

Let’s Break It For Real

With this knowledge, we can try to circumvent this optimization:

local string BaseString;
local name TempName;
local int i;

BaseString = "MySomewhatLongerBaseStringForHigherMemoryUsage";

`log("Starting...");
for (i = 0; i < 35000000; ++i)
{
    //TempName = name(BaseString $ "_" $ i);
    TempName = name(i $ "_" $ BaseString);
    if (i % 500000 == 0)
    {
      `log(i); // progress indicator and timer
    }
}
`log("Done!");

• Time: 848.09s
• Memory usage increase: 3.11GB¹

With this snippet, we leaked more than 3 Gigabytes of memory. This memory is permanently leaked and will not be reclaimed until we close the game.

There is another problem: With every name we synthesize, our hash set becomes less efficient. We never resize the 32768 entries large hash set, so we have more and more collisions, and we have to check longer and longer lists of interned names whenever we create another name. We can plot the elapsed duration over the number of names created:

Of course, 35 million names are a bit extreme, but not that extreme – crash dumps indicate that a normally running game has about three million interned strings.

But this explains why we cannot concatenate names, and have to go through strings: A name type that conveniently allows concatenation and mutation would make it extremely easy to accidentally pollute the name table and inhibit performance until we close the game.

Capitalization

We’ve explored the string -> name conversion in detail, but there’s one pitfall when going from name -> string: We can’t rely on any particular capitalization:

local int MYcUstOMnAmE;
`log('MyCustomName'); // ScriptLog: MYcUstOMnAmE

The Unreal Engine uses names to represent the name of (among other things) local variables, so when the compiler encounters the 'MyCustomName' string, the name has already been interned as "MYcUstOMnAmE". The name -> string conversion uses the first representation of the name it encountered, and that’s MYcUstOMnAmE.

Flash UI

You can actually cause breakage with this if even if you personally never interact with any code that relies on capitalization! Here’s a super cursed hack you can try in the Highlander:

// in CHDLCInfoTopologicalOrderNode.uc
var bool LeftPanel;

And suddenly we broke our loadout menu:

This is because UIArmory_Loadout has this code:

EquippedListContainer = Spawn(class'UIPanel', self);
EquippedListContainer.bAnimateOnInit = false;
EquippedListContainer.InitPanel('leftPanel');

This creates a UIPanel that links up with a panel of the name leftPanel on the Flash side – except Flash is case-sensitive even though Firaxis’ API takes names! The compiler parses our LeftPanel first, and when it encounters the leftPanel, LeftPanel is the interned representation.

Warning, INI file contains an incorrect case for

There is a particularly annoying compiler warning that sporadically appears for some config variables:

//⚠️ Warning, INI file contains an incorrect case for (CoverType) should be (coverType)
var config ECoverType coverType;

This warning references an INI file even when we haven’t modified any config files at all! This warning should better be described with

Warning, config variable coverType actually named CoverType

because the compiler had, at some point (perhaps even in XComGame) seen the name CoverType, so this variable is actually called CoverType. In fact, the compiler seemingly records this mismatch because config files are actually case-sensitive, and the runtime is clever enough to not use an arbitrary string representation of the variable name when loading from config.

To “fix” it, either follow the opposite of the advice and call it CoverType, or choose an entirely different name.

Closing Words

That’s it for the first entry in the series! If there is anything you’d like to have clarified regarding this topic, feel free to reach out in the comments!

Similarly, I’m open to suggestions for topics to cover next.