skip to main content

ToString() Or Not ToString()… Wait, What’s The Question?

July 6, 2016

ToStringOrNotToString

The question today is: can we make ToString() faster? Here’s the code we’re starting from:-

void FName::ToString(FString& Out) const
{
  const FNameEntry* const NameEntry = GetDisplayNameEntry();
  Out.Empty( NameEntry->GetNameLength() + 6);
  AppendString(Out);
}

Looking at it, you might think it’s going to be hard … it’s hardly a complicated function, after all…

But yes. Yes, we can make it faster. Approximately 2.4x faster, as it turns out.

What Does ToString() Do?


Before jumping in, let me give you a little primer about FNames. In the simplest terms, you can consider an FName to be split into two parts with a string at the front, which gets inserted into the NameTable, and an optional number at the end (nb. the string part can, of course, also contain numbers). They’re done this way so that they become very optimal where the string part is reused and the number part changes … for example, if you have:-

  • This_Is_A_Really_Long_Name_For_An_Object_But_We_Dont_Care_Because_FNAME_1
  • This_Is_A_Really_Long_Name_For_An_Object_But_We_Dont_Care_Because_FNAME_2
  • …
  • This_Is_A_Really_Long_Name_For_An_Object_But_We_Dont_Care_Because_FNAME_10000

Then it’s not going to be eating up tons of memory. “This_Is_A_Really_Long_Name_For_An_Object_But_We_Dont_Care_Because_FNAME” ends up in the NameTable, leaving each FName as, effectively, a lookup to the NameTable .. plus a number.

Converting from an FName to an FString, then, is done by copying the string part out and appending the number, if there is one, with an underscore to separate the two. That’s exactly what ToString() does.

Analysing ToString()


Taking a look at the source for ToString(), note that each line – line 3, line 4 and line 5 – call a function. We can ignore the first line for today’s purposes. GetDisplayNameEntry() -can- be optimised – but that’s beyond the remit of our work here.

Moving to line 4 … firstly, note the “+6”. Hard-coded numbers are never a great idea – especially when they’re not backed up with a comment explaining their use. But anyway, let’s forgive that for now – we’ll even forgive that “6” wasn’t always a large enough number for the intent here anyway. Anyway, this line calls GetNameLength():-

int32 FNameEntry::GetNameLength() const
{
  if( IsWide() )
  {
    return FCStringWide::Strlen( WideName );
  }
  else
  {
    return FCStringAnsi::Strlen( AnsiName );
  }
}

Through some hoops, this effectively ends up calling strlen() or functions to that effect.

Finally, on line 5, we have AppendString():-

void FName::AppendString(FString& Out) const
{
  const FNameEntry* const NameEntry = GetDisplayNameEntry();
  NameEntry->AppendNameToString( Out );
  if (GetNumber() != NAME_NO_NUMBER_INTERNAL)
  {
    Out += TEXT("_");
    Out.AppendInt(NAME_INTERNAL_TO_EXTERNAL(GetNumber()));
  }
}

Note that we’re calling GetDisplayNameEntry() again. Not really a huge problem though since it’s such a cheap function.

But… AppendString() calls into AppendNameToString() and AppendInt():-

void FNameEntry::AppendNameToString( FString& String ) const
{
  if( IsWide() )
  {
    String += WideName;
  }
  else
  {
    String += AnsiName;
  }
}

void FString::AppendInt( int32 InNum )
{
  int64 Num = InNum; // This avoids having to deal with negating -MAX_int32-1
  const TCHAR* NumberChar[11] = { TEXT("0"), TEXT("1"), TEXT("2"), TEXT("3"), TEXT("4"), TEXT("5"), TEXT("6"), TEXT("7"), TEXT("8"), TEXT("9"), TEXT("-") };
  bool bIsNumberNegative = false;
  TCHAR TempNum[16]; // 16 is big enough
  int32 TempAt = 16; // fill the temp string from the top down.

  // Correctly handle negative numbers and convert to positive integer.
  if( Num < 0 )
  {
    bIsNumberNegative = true;
    Num = -Num;
  }

  TempNum[--TempAt] = 0; // NULL terminator

  // Convert to string assuming base ten and a positive integer.
  do 
  {
    TempNum[--TempAt] = *NumberChar[Num % 10];
    Num /= 10;
  } while( Num );

  // Append sign as we're going to reverse string afterwards.
  if( bIsNumberNegative )
  {
    TempNum[--TempAt] = *NumberChar[10];
  }

  *this += TempNum + TempAt;
}

These both use FString +=, too, so let’s take a look at that as well:-

FORCEINLINE FString& operator+=( const TCHAR* Str )
{
  checkSlow(Str);
  CheckInvariants();

  AppendChars(Str, FCString::Strlen(Str));

  return *this;
}

The only line of any huge significance here is line 6 which calls into AppendChars() – but note that another Strlen() is done first…:-

FORCEINLINE void AppendChars(const TCHAR* Array, int32 Count)
{
  check(Count >= 0);

  if (!Count)
    return;

  checkSlow(Array);

  int32 Index = Data.Num();

  // Reserve enough space - including an extra gap for a null terminator if we don't already have a string allocated
  Data.AddUninitialized(Count + (Index ? 0 : 1));

  TCHAR* EndPtr = Data.GetData() + Index - (Index ? 1 : 0);

  // Copy characters to end of string, overwriting null terminator if we already have one
  CopyAssignItems(EndPtr, Array, Count);

  // (Re-)establish the null terminator
  *(EndPtr + Count) = 0;
}

All in all, ToString() has turned out to be quite an expensive and complicated operation..!

If you look back at line 4 of ToString(), you’ll note the call to Empty(). The intent with this line is to pre-allocate enough memory for the final output – so that, hopefully, reallocations aren’t needed as the work is carried out. That all kind of goes out of the window, though, as if you trace through ToString() and all the called functions, memory is allocated, reallocated, copied around and freed several times over.

Optimising ToString()


In order to make ToString() optimal, I realised that I’d need to be able to simplify several of the operations.

As an old-school programmer, I tend to try to simplify operations by looking at what their ultimate outcome should be, considering the variables that we have to get there.

In the case of ToString(), what we really want to do is this:-

  • Determine whether we’re dealing with a Name_Number type of FName or a simple Name;
  • Allocate an appropriate amount of memory for the output FName. To do this, we would need:-;
    • The Name length;
    • If there is one, the number of digits in Number.
  • Copy the Name part;
  • Copy the _Number part, if appropriate;
  • Null terminate.

That’s it. When you put it down like that, is it really all that complicated..?

So… I coded this up. I won’t go into great detail … but, essentially, I looked to reduce the code down so that the same calculations weren’t being repeated and so that we wouldn’t keep reallocating memory and moving it around. Instead, I’d determine the output size we’d need ASAP – and then simply copy the elements directly into there. Here’s what I ended up with…

Towards the top of UnrealNames.cpp, I added a define for enabling/disabling my new ToString():-

#define USE_NEW_TOSTRING 1

The bulk of the code was placed right before the original ToString():-

#if USE_NEW_TOSTRING
int32 GetNameEntryLength(const FNameEntry* NameEntry, const bool IsWide)
{
  uint32 NameLength = 0;
  if (IsWide)
  {
    const WIDECHAR* pChar = NameEntry->GetWideName();
    while (*pChar++)
      NameLength++;
  }
  else
  {
    const ANSICHAR* pChar = NameEntry->GetAnsiName();
    while (*pChar++)
      NameLength++;
  }
  return NameLength;
}
void NameToTCHARBuffer(const FNameEntry* NameEntry, const bool IsWide, TCHAR* OutChar)
{
  if (IsWide)
  {
    const WIDECHAR* pChar = NameEntry->GetWideName();
    while (WIDECHAR ThisChar = *pChar++)
    {
      *OutChar++ = ThisChar;
    }
  }
  else
  {
    const ANSICHAR* pChar = NameEntry->GetAnsiName();
    while (ANSICHAR ThisChar = *pChar++)
    {
      *OutChar++ = ThisChar;
    }
  }
}
uint32 NumberToTCHARBuffer(uint32 Number, TCHAR* Buffer, const uint32 BufferLen)
{
  uint32 NumberLength = 0;
  TCHAR* Out = &Buffer[BufferLen];
  do
  {
    *(--Out) = '0' + (Number % 10);
    NumberLength++;
    Number /= 10;
  } while (Number > 0);
  return NumberLength;
}
void FName::ToString(FString& Out) const
{
  const FNameEntry* const NameEntry = GetDisplayNameEntry();
  bool IsWide = NameEntry->IsWide();

  // Calculate the length of the name element
  uint32 NameLength = GetNameEntryLength(NameEntry, IsWide);

  // Get the number, if there is one
  uint32 Number = GetNumber();
  uint32 NumberLength = 0;
  const uint32 HasNumber = (Number != NAME_NO_NUMBER_INTERNAL) ? 1 : 0;

  // Calculate the length of the number element
  // Also, pre-fill NumberTC, from the back, with the number in string form
  static const uint32 NumberTC_Len = 16; // max length (10 should've been enough)
  TCHAR NumberTC[NumberTC_Len];
  if (HasNumber)
  {
    Number = NAME_INTERNAL_TO_EXTERNAL(Number); // convert to the number we wish to output
    NumberLength = NumberToTCHARBuffer(Number, NumberTC, NumberTC_Len);
  }

  // Calculate the final string length (Name[_Number]\0)
  uint32 TotalLen = (NameLength)+(HasNumber + NumberLength) + 1;

  // Prepare the memory that we're going to write to (this is "unsafe" because we're guaranteeing that we won't write off the end)
  Out.Empty(TotalLen);
  Out.GetCharArray().SetNumUninitialized(TotalLen);
  TCHAR* OutChar = Out.GetCharArray().GetData();
  OutChar[TotalLen - 1] = 0; // NULL Terminate

  // Copy the string part
  NameToTCHARBuffer(NameEntry, IsWide, OutChar);
  OutChar += NameLength;

  // Copy the number part
  if (HasNumber)
  {
    *OutChar++ = '_';

    TCHAR* pNumberTC = &NumberTC[NumberTC_Len - NumberLength];
    for (uint32 It = 0; It < NumberLength; It++)
    {
      *OutChar++ = *(pNumberTC++);
    }
  }
}
#else // USE_NEW_TOSTRING

And I closed the #if/#else/#endif right after the original ToString():-

#endif // USE_NEW_TOSTRING

Important parts of this function:-

  • Line 52 is our starting point;
  • Line 56 gets the length of our string using GetNameEntryLength() – this is a pretty optimal function that simply counts through to the null terminator
  • Lines 65-71 do two jobs with the Number part, if there is one:-
    • they calculate the number of digits required to store the number;
    • they fill NumberTC, a local array, with our number in TCHAR form – filling from the end – using our function NumberToTCHARBuffer().
  • Line 74 calculates the length of string we need… and lines 77-80 allocate and initialise this, also adding in the null terminator;
  • Lines 83-84 copy the string part in, using NameToTCHARBuffer();
  • Lines 87-96 copy the number part in, copying from NumberTC.

Pretty simple really…

Note: on line 78, we have SetNumUnitialized(). Since we have already allocated space for the string with the previous line, in the call to Empty(), we could in theory use SetNumUnsafeInternal() here – which would be faster… the checkSlow() within that function, though, looks a little too aggressive to me – allowing that the current size of the string can only shrink, never grow (note that Empty() sets the current size to be zero). A point for future investigation, perhaps, as I do wonder whether we’d be ok to change this checkSlow() to validate against ArrayMax rather than ArrayNum…

In order to properly test the performance, I wrote a simple test function that generated 1,000,000 FNames. After looking at the sort of names we’d typically get in our project, I made it so that 50% of the names would have a number attached… of those, 10% would have a single digit, 1% would have double digits, 0.1% triple digits, etc … going right down t0 8-digit numbers (which likely wouldn’t appear in our set of 1,000,000 names). I then created a tight loop that iterated over the names, doing ToString() on each… and a final loop around that to iterate over the set 10 times, reporting the time taken for each (using FPlatformTime::Seconds() and UE_LOG). I’ll leave that as a project for now that you can do yourself if needed…

The average amount of time that ToString() would take to convert 1,000,000 names:-

  • Original ToString(): 0.286 secs
  • New ToString(): 0.118 secs

Our new version of ToString() was just over 2.4x faster!

Not bad, considering the original was “only” 6 lines of code.

Credit(s): Robert Troughton (Coconut Lizard), Arjan Brussee (Boss Key Productions)
Status: Currently unimplemented in 4.12

Facebook Messenger Twitter Pinterest Whatsapp Email
cppdisassemblyfstringinlineinliningmemoryoptimizationue4ue411ue412

© 2015-2024 Coconut Lizard Limited
We are part of Keywords Studios

Go to Top