On Saving Memory: Automatic Data Interning

Context

Imagine you have this project in which you have to manipulate a lot of data. And by a lot, I mean that I am keeping gigabytes of objects in RAM and that the size of my input file directly influences the size of the data I create during my program’s execution. Also, what if a lot of the objects you manipulate actually have the same values but you still need the information? What could we do to reduce the stress on your computer’s resources?

Well, at the office I had to work around such a problem. We are writing a source-to-source compiler of g-code which helps us performing analyses and optimization on 3D prints, it is really cool. However, g-code source files usually weigh millions to billions lines of code. This means that our compiler needs to keep millions of objects of some kind of Instruction type with many parameters. On top of that we add attributes over our instructions to keep track of print information (typically the temperature etc). Moreover, since the vast majority of the code is composed of G1 instructions, that are linear moves (mostly with extrusion of filament), that means we need these ad-hoc attributes attached to, let’s say, 98% of our instructions.

However, most of our ad-hoc metrics do not change from one instruction to the other. Actually, they change when the appropriate instruction is called, e.g. M140, M104, etc. And these instructions are quite rare.¹ This means that an object encapsulating our metrics, let’s say PrintMetrics, that would be created for every instruction of the file, would be an exact copy of millions of other instances of PrintMetrics.

In my humble opinion, this looks like a huge waste of memory. What can we do to reduce the footprint of our PrintMetrics? Let’s investigate that in the next section.

You shall not copy, only bookkeep

What I did in our project is to intern our data type PrintMetrics so that when the user creates a new one or modifies an existing instance, the new object is stored into some database of existing instances and the user is only allowed to add fresh new objects, not copies of existing ones. If the user modifies their object and the resulting object actually exists in the database, the user is provided with a handle to the existing object.

In practice, we now have two types: PrintMetrics and PrintMetricsObject. The PrintMetricsObject is in fact our old PrintMetrics type, it contains all the fields of the old PrintMetrics type:

struct PrintMetricsObject
{
  double m_bed_temperature;
  double m_hotend_temperature;
  // other values...
};

The important thing is that the user now manipulates PrintMetricsObject through the PrintMetrics handle. In other words, PrintMetrics is a proxy to its currently associated PrintMetricsObject. We thus have methods to manipulate it:

class PrintMetrics
{
public:
  double get_bed_temperature() const noexcept;
  double get_hotend_temperature() const noexcept;

  void set_bed_temperature(double value) noexcept;
  void set_hotend_temperature(double value) noexcept;
};

The instance database

No matter how you implement this functionality, you will need some sort of database to hold your instances for you. In the context of our g-code compiler, all we do is load a g-code file, build an AST, do stuff on the AST and so on. It is very unexpected to have an application manipulate very different ASTs², in very different contexts and need to rebuild the database from scratch regularly. Actually even when manipulating multiple files, chances are the values of PrintMetricsObject will be similar and thus the number of instances should not explode.³

For this reason, I chose to keep the same database for the whole execution of the application. Consequently, we can put it into the PrintMetrics class, which should help making the use of the database transparent to the user:

class PrintMetrics
{
private:
  static inline MyDatabase& database()
  {
    static MyDatabase m_db;
    return m_db;
  }
};

The most important part of our work comes now: how do we register objects into the database? Well, two things:

• how do I store them?
• what are the mecanisms of adding and matching objects?

First, since I except my databases not to hold that many items, I chose to store them in a std::unordered_set. Feature-wise it does the job and in terms of cost it is reasonable.

std::unordered_set actually shines when it comes to adding stuff. Look at my beautiful method:

class PrintMetrics
{
private:
  using iterator = std::unordered_set<PrintMetricsObject>::iterator;

  static iterator intern(PrintMetrics&& object) noexcept
  {
    std::pair<iterator, bool> pair = database().insert(object);
    return pair.first;
  }
};

• an iterator to the element you inserted
• a boolean telling you if you inserted your item (true) or if it was already present (false).

In our case, we do not care about inserting or matching, we want an iterator to the object within the collection. Consequently, when creating a new PrintMetricsObject, we just intern() it. When we modified a PrintMetricsObject via the PrintMetrics proxy, we intern it the same way. Thus, the proxy can be implemented this way:

class PrintMetrics
{
public:
  void set_bed_temperature(double value) noexcept
  {
    PrintMetricsObject obj = *m_iter; // note the copy here.
    obj.bed_temperature = value;

    m_iter = intern(std::move(obj));
  }

  // The same goes for the other methods.

private:
  iterator m_iter;
};

IDs, iterator and naked pointers

Ok I lied. We cannot use iterator like this. Sadly, std::unordered_set::iterator is invalidated on insertions, that means that each time we add an element to our database, all the iterators we had would be invalidated. To counter that, we actually do not store iterators, but naked pointers to our objects. :D

Note that it is absolutely not a problem:

• The handle never manages the objects it points to, so it will never delete it by accident.
• The handle is provided valid iterators by the database, so it will never point to garbage.
• The objects live forever in our static database.

Moreover, and it is the most important piece of information in my opinion: we are sure the PrintMetrics is the same size as a pointer. That means it can hardly be smaller now.

Thread-safety

In our project we use a lot of threads to speed-up the processing of these millions of instructions. For this reason, we want to ensure that the interning process, that involves the unique, static database, is thread-safe. Well, that’s easy. Remember the method intern()? Here it is:

static const PrintMetricsObject* intern(PrintMetrics&& object) noexcept
{
  static std::mutex mutex;
  std::scoped_lock<std::mutex> lock(mutex);

  std::pair<iterator, bool> pair = database().insert(object);
  return &(*pair.first);
}

Also, note how I change the signature of the method to return a pointer to the object, just like I said previously.

How to generalize that

Now that I am not working on this anymore at work, I have been bugged for a moment on my sofa, crocheting my cardigan, about one question: how can I generalize this mecanism smoothly in C++?

Until now, I have worked on a precise type, implementing precise methods, and so on. But now, what I want is to tell the compiler “hey objects of this type should be interned” and everything would fall into place.

All what you read previously was the introduction to the real project, now comes the real stuff. Let’s talk about how to automatically intern objects using simple and reasonable hypotheses.

The interface I want

Since we are talking about telling the compiler the class we are defining should implement an interning mecanism, I thought about using the Curiously Recurring Template Pattern of C++. This pattern allows us to define a class A that inherits the instanciation of another class B using A as template parameter. In other words, we can write this:

class MyObject : public Interned<MyObject>
{
};

A first try at implementing Interned would be the following:

template <typename T>
class Interned
{
public:
  using Container = typename std::unordered_set<T>;
  using Handle = const T*;

protected:
  template <typename ...Args>
  constexpr Interned(Args... args) {}

  static inline Container& database() noexcept
  {
    static Container m_db;
    return m_db;
  }

  static Handle intern(T&& obj) noexcept
  {
    static std::mutex mutex;
    std::scoped_lock<std::mutex> lock(mutex);

    std::pair<typename Container::iterator, bool> pair =
      database().insert(std::forward(obj));
    return &(*pair.first);
  }
};

1. I added some convenient type names. The container used by the interning mecanism is aliased as Container. The type provided to manage the object is named Handle.
2. I added a weird variadic template empty constructor. I will explain it later when we will try to inherit Interned, it will prove itself useful.
3. The database and the intern() methods are the same as before.

The first things we could miss here are the following:

• T must implement an operator== and there must be an instanciation of std::hash for T too.
• std::unordered_set is not only template over T, but over a few more parameters too, among them: Hash and Compare.

Fortunately, these two points complete each other very well. I like the idea that the user may want to provide the hash and equality algorithms and thus, I want to template Interned on these too:

template <typename T,
          typename Hash = std::hash<T>,
          typename Compare = std::equal_to<T>>
class Interned
{
public:
  using Container = std::unordered_set<T, Hash, Compare>;
  // ...
};

template <...>
class Interned
{
public:
  using value_type = typename std::remove_cvref_t<T>;
  using Container = typename std::unordered_set<value_type, Hash, Compare>;

protected:
  static Handle intern(value_type &&obj) noexcept
  {
    // ...
  }
};

Inheritance, visibility and evil

Let’s say we have some input that can contain comments and we want to intern these comments because we expect them to be quite redundant⁵. We can have a class Comment that embeds an std::string and we will intern it:

class Comment : public Interned<Comment>
{
public:
  const std::string& get() const
  {
    return m_string;
  }

  inline bool operator==(const Comment& other) const noexcept
  {
    return m_string == other.m_string;
  }

private:
  std::string m_string;
};

1. We have our private field m_string and a convenient getter function.
2. We have the mandatory operator== function that allows us to compare Comment instances, as required by Interned<Comment>.
3. We lack a constructor.
4. We lack an instanciation of std::hash<Comment>.

Implementing std::hash

First of all, we can implement the specialization of std::hash for Comment. The tricky part is that we need it declared before Comment for it to be found by our template:

template <typename T,
          typename Hash = std::hash<T>,
          typename Compare = std::equal_to<T>>
class Interned;

template <>
struct std::hash<Comment>
{
  // We first declare the operator().
  std::size_t operator()(const Comment& comment) const noexcept;
};

// Then our class.
class Comment : public Interned<Comment>
{
  // ...
};

// Now that the class is fully defined, we can implement std::hash.
std::size_t std::hash<Comment>::operator()(const Comment& comment) const noexcept
{
  return std::hash<std::string>()(comment.get());
}

How to construct Comment objects

The naive solution would be to add a public constructor that allows us to create a Comment object. However, that would give the responsability to the user to intern the object themself to get a valid Handle over it. Moreover, since intern() needs to object to be moved, we cannot use it in the constructor of Comment.

A better solution would be to provide the user with a feature that enables them to create a new object using the Interned class to ensure that it interns the object correctly and returns only a Handle to it. That is easy to do using our design. We can add a static method to Interned:

template <typename T,
          typename Hash = std::hash<T>,
          typename Compare = std::equal_to<T>>
class Interned
{
public:
  template <typename ...Args>
  static Handle make(Args... &&args)
  {
    T obj(std::forward<Args...>(args...));
    return intern(std::move(obj));
  }
};

We need a smart way to get access to a constructor while keeping it out of the user’s hand’s distance. The naive solution - again - would be to require the interned class to befriend Interned and make the constructor protected or private:

class Comment : public Interned<Comment>
{
  friend class Interned<Comment>;

private:
  Comment(const std::string& str) : m_string(str) {}
};

Comment(const std::string& str) : Interned(), m_string(str) {}

But now, we have another problem: we need to make Interned a friend of Comment and I do not want that either.

The evil side of CRTP

There is another - absolutely not - elegant solution to our problem. This article presents a smart and creative pattern that allows a CRTP base class - Interned here - to somehow force the template parameter - Comment here - to befriend it. Actually, what we need is simply an access to the constructor, in order to create an instance of our type. The solution given in the article is the following:

1. We add the protected constructor in Comment.
2. We create a class derived from Comment that would befriend Interned, giving it access to said derived class and thus to Comment.
3. We provide this class with the needed constructor.

Here is how I did it:

template <typename T,
          typename Hash = std::hash<T>,
          typename Compare = std::equal_to<T>>
class Interned
{
private:
  struct Evil : public T
  {
    friend class Interned;

    template <typename ...Args>
    inline Evil(Args... args) : T(args...) {}
  };

public:
  template <typename ...Args>
  static Handle make(Args... args)
  {
    Evil obj(args...);
    return intern(std::move(obj));
  }
};

The only real limitation of this approach is that we cannot really manipulate objects from classes derived from T. But honestly, using Interned::make(), one wants to create a T, not a U derived from T, so it is not really a problem.

We nonetheless have a usable version of Interned now and we can create instances of Comment:

Comment::Handle comment = Comment::make("Hello world!");

What about handles?

Actually, we have something that works relatively well. Nonetheless, there is a last thing we have not talked about and is now of utter importance: handles. We have worked with an abstract type we call Handle whose job is to serve as a proxy to a concrete interned object. Until now, we have used const Interned::value_type* as handle because it allows the user to access the inner value freely without much restrictions. Moreover, since the pointed object is marked as constant, it is normally not possible to modify it so we are guaranteed that we will not corrupt the database through a handle.

But we have a problem: our objects are indeed impossible to modify. More precisely, in order to create an object derived from another object (a mutation), we need to extract as much information as possible by hand in order to feed it to Interned::make(). It is not always possible nor reasonable. Maybe we can fix this limitation with a proper Handle type.

First things first, what can we expect from our handles?

1. It must continue to serve as a proxy/kind of pointer to a concrete interned object.
2. It must allow to mutate an object while enforcing a database safety. This means that when mutating an object through a handle, the actual object stays the same, but the handle must now point to the mutated object, regardless of if it is new or a copy of another existing object.
3. Any mutation of an object manipulated through a handle must be propagated to the database.

My idea is the following:

• A Handle class inside Interned in order to keep the same interface as before - e.g. Comment::Handle
• The Handle class contains operators such as operator* and operator-> enabling the user to manipulate the object.
• A move constructor for Handle that allows to pass an object to it so that it gets interned and pointed to, e.g. Comment::Handle h(std::move(some_comment));
• Copy constructors to allow the creation of handles from other handles.

First API

We can first implement my idea this way:

// Inside Interned
class Handle
{
  friend class Interned;

public:
  constexpr Handle(const Handle &other) noexcept = default;
  inline Handle(Interned::value_type &&obj) noexcept : Handle(Interned::intern(std::move(obj))) {}

  Handle& operator=(const Handle &other) noexcept
  {
    m_ptr = other.m_ptr;
    return *this;
  }

  const Interned::value_type& get() const noexcept
  {
    return *m_ptr;
  }

  constexpr const Interned::value_type& operator*() const noexcept
  {
    return *m_ptr;
  }

  constexpr const Interned::value_type* operator->() const noexcept
  {
    return m_ptr;
  }

private:
  constexpr Handle(const T* ptr) : m_ptr(ptr) {}

  // The inner pointer to the object.
  const Interned::value_type* m_ptr;
};

Second API

We can add an extra layer of indirection for when we want to modify an object. This layer can be a mutator object whose job is to manipulate a copy of said object and ensure it will be interned automatically when the mutator goes out of scope.

// Still in Interned
class Mutator
{
  friend class Interned;
  friend class Interned::Handle;

public:
  constexpr Mutator(Handle &handle) : m_handle(handle), m_copy(handle.get()) {}
  ~Mutator()
  {
    m_handle = Interned::intern(std::move(m_copy));
  }

  constexpr value_type* operator->() noexcept
  {
    return &m_copy;
  }

  constexpr value_type& operator*() noexcept
  {
    return m_copy;
  }

  Mutator(const Mutator &) = delete;
  Mutator(Mutator &&) = delete;

private:
  Handle &m_handle;
  value_type m_copy;
};

• We can construct a Mutator using a Handle. This stored a reference to the handle for future use and create a copy of the object.
• We can access the copy of the object through operator* and operator-> and perform mutations.
• When the Mutator goes out of scope and is destructed, the copy object is interned and the handle is updated.
• I deleted the copy and move constructors to prevent multiple mutators on the same handle to concurrently mess with it.

With this new class we can add the following methods to Handle:

constexpr Mutator operator*() noexcept
{
  return Mutator(*this);
}

constexpr Mutator operator->() noexcept
{
  return Mutator(*this);
}

Conclusion

In this post, we have developed a class whose job is to be derived from using CRTP in order to enable automatic interning of instances to said derived class. We defined this class and explained the requirement (a hash algorithm and an equality test). Moreover we went further into the details to ensure the user cannot create instances of their class that would not be interned as intended. Our approach uses handles and a mutator type to manipulate the objects safely.

While this post decribed longly our sophisticated approach, we did not go much into the details of the actual gain in terms of memory usage. I did not create an application just to verify my claims, however I am still convinced by data interning given my experience. Indeed, I began working on this on a real concrete project and data that needed interning. On my test g-code file and an application based on the compiler I presented at the beginning of this post, I could save about 2.6 GB of RAM (out of the ~14 GB in use). On top of that, string interning is a pattern that is already used in many interpreters such as Lua or Ruby to reduce to a minimum the RAM consumption of strings. One can also draw a parallel between our data interning pattern and the common flyweight design pattern.