Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Boost.Flyweight Tutorial: Basics



Contents

Introduction

Suppose we are writing a massive multiplayer online game which has to maintain hundreds of thousands or millions of instances of the following class in memory:

struct user_entry
{
  std::string first_name;
  std::string last_name;
  int         age;
  ...
};

In this kind of environments memory resources are precious, so we are seeking ways to make user_entry as compact as possible. Typically, there exists a very high level of repetition of first and last names among the community users, so an obvious optimization consists in moving user_entry::first_name and user_entry::last_name objects to a common repository where duplicates are avoided, and leaving references to these inside user_entry. This is precisely what Boost.Flyweight does in the simplest possible way for the programmer:

#include <boost/flyweight.hpp>

struct user_entry
{
  flyweight<std::string> first_name;
  flyweight<std::string> last_name;
  int                    age;
  ...
};

Boost.Flyweight automatically performs the optimization just described behind the scenes, so that the net effect of this change is that the memory usage of the program decreases by a factor proportional to the level of redundancy among user names.

flyweight<std::string> behaves in many ways like std::string; for instance, the following code works unchanged after the redefinition of user_entry:

// flyweight<T> can be constructed in the same way as T objects can,
// even with multiple argument constructors

user_entry::user_entry(const char* f,const char* l,int a,...):
  first_name(f),
  last_name(l),
  age(a),
  ...
{}

// flyweight classes have relational operators replicating the
// semantics of the underyling type

bool same_name(const user_entry& user1,const user_entry& user2)
{
  return user1.first_name==user2.first_name &&
         user1.last_name==user2.last_name;
}

// flyweight<T> provides operator<< and operator>> internally
// forwarding to T::operator<< and T::operator>>

std::ostream& operator<<(std::ostream& os,const user_entry& user)
{
  return os<<user.first_name<<" "<<user.last_name<<" "<<user.age;
}

std::istream& operator>>(std::istream& is,user_entry& user)
{
  return is>>user.first_name>>user.last_name>>user.age;
}

Besides, flyweight<T> is convertible to const T&, either implicitly or through the get member function:

std::string full_name(const user_entry& user)
{
  std::string full;

  full.reserve(
    user.first_name.get().size()+   // get() returns the underlying
    user.last_name.get().size()+1); // const std::string&

  full+=user.first_name;            // implicit conversion is used here
  full+=" ";
  full+=user.last_name;

  return full;
}

The most important restriction to take into account when replacing a class with an equivalent flyweight is the fact that flyweights are not mutable: since several flyweight objects can share the same representation value, modifying this value is not admissible. On the other hand, flyweight objects can be assigned new values:

void change_name(
  user_entry& user,
  const std::string& f,const std::string& l)
{
  user.first_name=f;
  user.last_name=l;
}

In general, flyweight<T> interface is designed to make the transition from plain T as straightforward as possible. Check the reference for further details on the interface of the class template flyweight. The examples section explores some common usage scenarios of Boost.Flyweight.

Serialization

flyweight<T> can be serialized by means of the Boost Serialization Library as long as the underlying T is serializable. Both regular and XML archives are supported. In order to use Boost.Flyweight serialization capabilities, the specific header "boost/flyweight/serialize.hpp" must be included.

#include <boost/flyweight/serialize.hpp>

template<class Archive>
void serialize(Archive& ar,user_entry& user,const unsigned int)
{
  ar&user.first_name;
  ar&user.last_name;
  ar&user.age;
  ...
}

Much as using Boost.Flyweight reduces memory consumption due to the internal sharing of duplicate values, serializing flyweights can also result in smaller archive files, as a common value is only stored once and their associated flyweights get saved as references to it. This policy is observed even if flyweight underlying type is not tracked by Boost.Serialization.

See example 6 at the examples section for an illustration of use of Boost.Flyweight serialization capabilities.

Flyweight requirements

For flyweight<T> to be instantiable, T must be Assignable, Equality Comparable and must interoperate with Boost.Hash. The first requirement is probably met without any extra effort by the user, not so the other two, except for the most common basic types of C++ and the standard library. Equality and hashing of T are used internally by flyweight<T> internal factory to maintain the common repository of unique T values referred to by the flyweight objects. Consult the Boost.Hash documentation section on extending that library for custom data types.

As we have seen, equality and hash requirements on T are imposed by the particular type of flyweight factory internally used by flyweight<T>. We will see later how the user can customize this factory to use equality and hash predicates other than the default, or even switch to an entirely different kind of factory which may impose another requirements on T, as described in the section on configuring Boost.Flyweight.




Revised September 1st 2014

© Copyright 2006-2014 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)