Graph Engine vs. C++ unordered_map: memory consumption test

"How is Graph Engine K/V store different from a... C++ map?"

Well, virtually they do the same thing after all: to store key-value pairs. So why bother using Graph Engine against the other? I'm not going to talk about remote access, fault tolerance and other fancy stuff for now... Let's take a look at a much easier, but critical factor: memory consumption.

Data structures

First let's calibrate our data structures. For the Graph Engine side, we drop TSL (wait didn't you just write a long post about the importance of TSL?) and leave only the bare metal memory cache. It stores cell IDs (keys), cell types (unsigned short values), cell blob location and cell size. To simulate this, we use the following data structure in C++:

 struct CellEntry
{
    void*    ptr;
    int32_t  len;
    uint16_t cellType;
};
 

Initially I picked map<K,V> instead of unordered_map<K,V>. After watching it crawling bytes at 20MB/s for minutes... ^C^C^C^C^C.

And here's the code.

C++:

 #include <vector>
#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <ctime>
using namespace std;

#define ENTRY_SIZE 314 
#define ENTRY_COUNT (1<<20)*64

struct CellEntry
{
    void*    ptr;
    int32_t  len;
    uint16_t cellType;
};
unordered_map<long, CellEntry> LocalStorage;

int _tmain(int argc, _TCHAR* argv[])
{
    srand(time(NULL));

    for (int i = 0; i < ENTRY_COUNT; ++i)
    {
        long id = rand() * rand();
        void* p = new char[ENTRY_SIZE];
        LocalStorage[id] = { p, ENTRY_SIZE, /*cellType:*/0 };
        if (rand() % 3 == 0)
        {
            LocalStorage.erase(id);
            delete[] p;
        }
    }
    return 0;
}
 

C# w/ Graph Engine:

 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Trinity;
namespace MemoryConsumptionTest_CSharp
{
    internal class Program
    {
        const int ENTRY_SIZE = 314;
        const int ENTRY_COUNT = (1 << 20) * 64;
        static void Main(string[] args)
        {
            Random r = new Random();
            byte[] buf = new byte[ENTRY_SIZE];
            TrinityConfig.CurrentRunningMode = RunningMode.Embedded;

            for (int i = 0; i < ENTRY_COUNT; ++i)
            {
                long id = r.Next() * r.Next();
                Global.LocalStorage.SaveCell(id, buf, 0, ENTRY_SIZE, cellType: 0);

                if(r.Next(3) == 0)
                {
                    Global.LocalStorage.RemoveCell(id);
                }
            }
        }
    }
}
 

We store cells with a fixed length 314, 64 millions of them. Both C++ and C# will assure that the allocated memory gets committed unlike the malloc() function, which would need a memset() to trigger that. Also, along cell insertions, we randomly remove entries with the probability 1/3... This is to test their behaviors with regard to the memory fragmentations introduced by removals.

If the environment is correctly set up, the two programs should have the same semantics (remember to compile 64-bit programs, and make sure your machine can handle that ~20GB of memory allocation). The following performance data is acquired on a server with Xeon X5650@2.67Ghz and 96GB of RAM:

The "Raw performance data" row shows the screen shots of the task manager memory window during the two runs. Notice that for GE, there's a slight memory usage drop (only about a hundred of megabytes). This is due to the garbage collector running in the background collecting the space taken by the removed entries. I will go into the details of our garbage collector in another post.

As we can see, Graph Engine outperforms the unordered_map in both memory consumption (nearly 2GB less space) and speed (nearly 20 seconds faster).
And we're talking about the comparison between a full-fledged key-value store and a data structure...