Is It A Drive? Is It A Directory? No, It’s…

June 28, 2017

Nb. the changes described in this blog are available in the following Github Pull Request: github.com/EpicGames/UnrealEngine/pull/3724

So, where were we again? Ah, right.. while developing our improvements to MallocProfiler (Malloc Profiler 2) we found that IPlatformFileCreateDirectory(), and within that FPaths::IsDrive(), was making ~1 million allocations (out of a total of 53 million) during a full cook of KiteDemo. Not ground-breaking – but significant enough that it needed looking at.

Digging into the codebase turned up two issues. FPaths::IsDrive() is a very long function, around 100 lines – but whatever it’s original purpose was, all it is really being used for currently is checking for a Windows drive letter (e.g. ‘Q:/’) at the start of a path. Basically, the functions calling it wanted to know if it was safe to ignore a colon being used in a path due to it being part of a Windows drive letter. A minimum of two FStrings (and their associated memory allocations) were being instantiated for each call to the function and then the search criteria were being applied.

bool FPaths::IsDrive(const FString& InPath)
{
  FString ConvertedPathString = InPath;

  ConvertedPathString = ConvertedPathString.Replace(TEXT("/"), TEXT("\\"), ESearchCase::CaseSensitive);
  const TCHAR* ConvertedPath= *ConvertedPathString;
...
}

As IsDrive() is only actually being used for a very particular purpose, and the concept of a drive is really a Windows specific concept, we have replaced the function with FPaths::IsWindowsDrivePath(). This now does a few simple length checks and character comparisons to determine if it has been passed a string of the form ‘Q:/’ without copying the input string. The four existing usages of IsDrive() (three in IPlatformFileSandboxWrapper.cpp and one in Paths.cpp) have been replaced with IsWindowsDrivePath() or FPaths::IsRelative() (which nearly, but not quite, duplicates the functionality) as appropriate.

The second problem we found was that IPlatformFile::CreateDirectoryTree() was calling IsDrive() iteratively within the recursive directory creation algorithm it implements. This code was stepping through the input directory name, copying each character individually to a new buffer and checking if this new buffer contained a valid path each time it reached a directory separator, creating the directory if it didn’t exist.

for (TCHAR Full[MaxCharacters + 1] = TEXT( "" ), *Ptr = Full; Index < MaxCharacters; *Ptr++ = *LocalPath++, Index++)
{
  if (((*LocalPath) == TEXT('/')) || (*LocalPath== '\0'))
  {
    *Ptr = '\0';
    if ((Ptr != Full) && !FPaths::IsDrive( Full ))
    {
      if (!CreateDirectory(Full) && !DirectoryExists(Full))
      {
        break;
      }
      CreateCount++;
    }
    ...
  }
}

The result of this was that for every path passed to this function, each subsection was being passed to the inefficient IsDrive() function. Directory creation is done at the start of an if statement but, given that CreateDirectory() will return true if a path is valid, we don’t need to care if the path we pass it happens to be a drive (or root – hence the ‘Ptr != Full’ check) path, and if CreateDirectory() returns false, DirectoryExists() isn’t ever going to return true! So a lot of these branching statements are superfluous. There’re a few more holes we could point at in this implementation (eg. CreateCount appears to be someone’s debugging variable that’s been left in for example), but suffice to say it’s not a very nice function.

What it is attempting to do is check for the existence of each directory in a given path and create it if needs be. If we’re sneaky we can actually do this using a single string and a few pointers. We can iterate through the string containing the input directory name, replace each directory separator (‘/’) in turn with ‘\0’, and call CreateDirectory() on the artificially terminated string until it returns true. Once we’ve reached a directory we can create (implying the parent directory already existed) we can reverse the process, replacing instances of ‘\0’ with ‘/’ and creating the child directories.

First we create a string from the input directory name and normalise this path, then instantiate pointers to the beginning and end of the string, and a mutable iterator pointer which will start at the existing terminating ‘\0’ character of InDirectory:-

bool IPlatformFile::CreateDirectoryTree(const TCHAR* Directory)
{
  FString InDirectory(Directory);
  FPaths::NormalizeDirectoryName(InDirectory);
  // Const Ptr to start of Directory string
  const TCHAR* StartPtr = *InDirectory;
  // Mutable IteratorPtr starting at terminating '\0' character of Directory string
  TCHAR* IteratorPtr = InDirectory.GetCharArray().GetData() + InDirectory.Len();
  // Const Ptr to end of Directory string
  const TCHAR* EndPtr = IteratorPtr;

  bool bDirectoryExists = false;

Then we call CreateDirectory() with the pointer to the first position of our string as a parameter. While this returns false we iterate back through the string and artificially terminate it at each directory separator before calling CreateDirectory() again:-

do
{
  bDirectoryExists = CreateDirectory(StartPtr);
  if (!bDirectoryExists)
  {
    // Decrease pointer 'till we find a directory separator and replace this
    // with '\0' artificially terminating the InDirectory string. Continue
    // 'till we get to a directory we can create (and create it). 
    do
    {
      IteratorPtr--;
    } while (*IteratorPtr != TEXT('/') && IteratorPtr > StartPtr);
    *IteratorPtr = TEXT('\0');
  }
  else
  {
    break;
  }
} while (IteratorPtr > StartPtr);

Once CreateDirectory() returns true we can reverse the process and replace the path dividers one by one creating all of the child directories:-

  do
  {
    if (bDirectoryExists)
    {
      // Providing we're not going past the end of the InDirectory string,
      // increase the pointer 'till we find '\0' and replace with '/' allowing
      // iterative directory creation.
      while (*IteratorPtr != TEXT('\0') && IteratorPtr < EndPtr)
      {
        IteratorPtr++;
      }
      // Don't replace the original terminating '\0' character!
      if (IteratorPtr != EndPtr)
      {
        *IteratorPtr = TEXT('/');
        bDirectoryExists = CreateDirectory(StartPtr);
      }
    }
    else
    {
      break;
    }
  } while (IteratorPtr < EndPtr);
  return bDirectoryExists;
}

So with that we’ve simplified, and drastically reduced the use of, a convoluted piece of legacy code as well as slimming down the memory footprint of a relatively heavily used function. The result of our fixes is a reduction in the total number of memory allocations by ~4% in a cook of KiteDemo (dropping from 52.8 to 50.5 million) and CreateDirectoryTree() dropping from 129Mb to 45Mb of allocations.

And that wraps up this blog post! As always, please feel free to comment below.

Credits:
Programming/Research: Josef Gluyas (Coconut Lizard)
Mentoring: Gareth Martin, Joe Tidmarsh, Robert Troughton, Lee Clark (Coconut Lizard)