Build speed again: intuition lies to you

The problem

Suppose you have a machine with 8 cores. Also suppose you have the following source packages that you want to compile from scratch.

eog_3.8.2.orig.tar.xz
grilo_0.2.6.orig.tar.xz
libxml++2.6_2.36.0.orig.tar.xz
Python-3.3.2.tar.bz2
glib-2.36.4.tar.xz
libjpeg-turbo_1.3.0.orig.tar.gz
wget_1.14.orig.tar.gz
grail-3.1.0.tar.bz2
libsoup2.4_2.42.2.orig.tar.xz

You want to achieve this as fast as possible. How would you do it?

Think carefully before proceeding.

The solution

Most of you probably came up with the basic idea of compiling one after the other with ‘make -j 8′ or equivalent. There are several reasons to do this, the main one being that this saturates the CPU.

The other choice would be to start the compilation on all subdirs at the same time but with ‘make -j 1′. You could also run two parallel build jobs with ‘-j 4′ or four with ‘-j 2′.

But surely that would be pointless. Doing one thing at the time maximises data locality so the different build trees don’t have to compete with each other for cache.

Right?

Well, let’s measure what actually happens.

timez

The first bar shows the time when running with ‘-j 8′. It is slower than all other combinations. In fact it is over 40% (one minute) slower than the fastest one, although all alternatives are roughly as fast.

Why is this?

In addition to compilation and linking processes, there are parts in the build that can not be parallelised. There are two main things in this case. Can you guess what they are?

What all of these projects had in common is that they are built with Autotools. The configure step takes a very long time and can’t be parallelised with -j. When building consecutively, even with perfect parallelisation, the build time can never drop below the sum of configure script run times. This is easily half a minute each on any non-trivial project even on the fastest i7 machine that money can buy.

The second thing is time that is lost inside Make. Its data model makes it very hard to optimize. See all the gory details here.

The end result of all this is a hidden productivity sink, a minute lost here, one there and a third one over there. Sneakily. In secret. In a way people have come to expect.

These are the worst kinds of productivity losses because people honestly believe that this is just the way things are, have always been and shall be evermore. That is what their intuition and experience tells them.

The funny thing about intuition is that it lies to you. Big time. Again and again.

The only way out is measurements.

 

Serialising any C++ data structure to disk with ~20 lines of code

We all like C++’s container classes such as maps. The main negative thing about them is persistance. Ending your process makes the data structure go away. If you want to store it, you need to write code to serialise it to disk and then deserialise it back to memory again when you need it. This is tedious work that has to be done over and over again.

It would be great if you could command STL containers to write their data to disk instead of memory. The reductions in application startup time alone would be welcomed by all. In addition most uses for small embedded databases such as SQLite would go away if you could just read stuff from persistent std::maps.

The standard does not provide for this because serialisation is a hard problem. But it turns out this is, in fact, possible to do today. The only tools you need are the standard library and basic standards conforming C++.

Before we get to the details, please note this warning from the society of responsible coding.

evil

What follows is the single most evil piece of code I have ever written. Do not use it unless you understand the myriad of ways it can fail (and possibly not even then).

The basic problem is that C++ containers work only with memory but serialisation requires writing bytes to disk. The tried and true solution for this problem is memory mapped files. It is a technique where a certain portion of process’ memory is mapped to a backing file. Any changes to the memory layout will be written to the disk by the kernel. This gives us memory serialisation.

This is only half of the problem, though. STL containers and others allocate the memory they need through operator new. The way new works is implementation defined. It may give out addresses that are scattered around the memory space. We can’t mmap the entire address space because it would take too much space and serialise lots of stuff we don’t care about.

Fortunately C++ allows you to specify custom allocators for containers. An allocator is an object that does memory allocations for the object it is tied to. This indirection allows us to write our own allocator that gives out raw memory chunks from the mmapped memory area.

But there is still a problem. Since pointers refer to absolute memory locations we would need to have the mmapped memory area in the same location in every process that wants to use it. It turns out that you can enforce the address at which the memory mapping is to be done. This gives us an outline on how to achieve our goal.

  • create an empty file for backing (10 MB in this example)
  • mmap it in place
  • populate the data structure with objects allocated in the mmapped area
  • close creator program
  • start reader program, mmap the data and cast the root object into existance

And that’s it. Here’s how it looks in code. First some declarations:

*mmap_start = (void*)139731133333504;
size_t offset = 1024;

template <typename T>
class MmapAlloc {
  ....
  pointer allocate(size_t num, const void *hint = 0) {
    long returnvalue = (long)mmap_start + offset;
    size_t increment = num * sizeof(T) + 8;
    increment -= increment % 8;
    offset += increment;
    return (pointer)returnvalue;
  }
  ...
};

typedef std::basic_string<char, std::char_traits<char>,
  MmapAlloc<char>> mmapstring;
typedef std::map<mmapstring, mmapstring, std::less<mmapstring>,
  MmapAlloc<mmapstring> > mmapmap;

First we declare the absolute memory address of the mmapping (it can be anything as long as it won’t overlap an existing allocation). The allocator itself is extremely simple, it just hands out memory offset bytes in the mapping and increments offset by the amount of bytes allocated (plus alignment). Deallocated memory is never actually freed, it remains unused (destructors are called, though). Last we have typedefs for our mmap backed containers.

Population of the data sets can be done like this.

int main(int argc, char **argv) {
    int fd = open("backingstore.dat", O_RDWR);
    void *mapping;
    mapping = mmap(mmap_start, 10*1024*1024,
      PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0);
    if(mapping == MAP_FAILED) {
        printf("MMap failed.\n");
        return 1;
    }
    mmapstring key("key");
    mmapstring value("value");
    if(fd < 1) {
        printf("Open failed.\n");
        return 1;
    }
    auto map = new(mapping)mmapmap();
    (*map)[key] = value;
    printf("Sizeof map: %ld.\n", (long)map->size());
    printf("Value of 'key': %s\n", (*map)[key].c_str());
    return 0;
}

We construct the root object at the beginning of the mmap and then insert one key/value pair. The output of this application is what one would expect.

Sizeof map: 1.
Value of 'key': value

Now we can use the persisted data structure in another application.

int main(int argc, char **argv) {
    int fd = open("backingstore.dat", O_RDONLY);
    void *mapping;
    mapping = mmap(mmap_start, 10*1024*1024, PROT_READ,
     MAP_SHARED | MAP_FIXED, fd, 0);
    if(mapping == MAP_FAILED) {
        printf("MMap failed.\n");
        return 1;
    }
    std::string key("key");
    auto *map = reinterpret_cast<std::map<std::string,
                                 std::string> *>(mapping);
    printf("Sizeof map: %ld.\n", (long)map->size());
    printf("Value of 'key': %s\n", (*map)[key].c_str());
    return 0;
}

Note in particular how we can specify the type as std::map<std::string, std::string> rather than the custom allocator version in the creator application. The output is this.

Sizeof map: 1.
Value of 'key': value

It may seem a bit anticlimactic, but what it does is quite powerful.

Extra evil bonus points

If this is not evil enough for you, just think about what other things can be achieved with this technique. As an example you can have the backing file mapped to multiple processes at the same time, in which case they all see changes live. This allows you to have things such as standard containers that are shared among processes.