Numbers non-uniform probability distribution in C++

Let's consider one simple case. If you got:

array = {-10, 3, 9, 0, 111, 99}

and probability distribution

distr = {0.07, 0.2, 0.1, 0.33, 0.07, 0.23}

Can you write C/C++ code (not using C++11) that will guarantee (more or less) that

nextVal() function will return randomly next value from array with given probability ? 

So it means after 100 executions of nextVal more or less you should see that nextVal numbers are aligned with probability distribution: perfectly (7,20,10,33,7,23) .

It is an easy task but if you are struggled , feel free and take a look (it's not optimized):

#include <iostream>

#include <cmath>

#include <time.h>

#include <stdlib.h>

#include <map>

#include <vector>

using namespace std;

#define ARRAY_SIZE(array) (sizeof(array)/sizeof(array[0]))

int checkDistribution(double random, const map<double, vector<int> > &distribution_map)

{

int index = 0;

map<double, vector<int> >::const_iterator it = distribution_map.begin();

for (; it!=distribution_map.end(); ++it)

{

if (random < (*it).first)

{

int randomInternal = 0;

if ((*it).second.size() > 1)

randomInternal = rand() % ((*it).second.size());

index = (*it).second.at(randomInternal);

break;

}

}

return index;

}

void nextNum(int* results, const map<double, vector<int> > &distribution_map)

{

double random  = (double) rand()/RAND_MAX;

int index = checkDistribution(random,distribution_map);

results[index]+=1;

}

int main() {

srand (time(NULL));

int results [] = {0,0,0,0,0};

int numbers [] = {-1,0,1,2,3};

double prob [] =  {0.01, 0.3, 0.58, 0.1, 0.01};

int size = ARRAY_SIZE(numbers);

// Building Distribution

map<double, vector<int> > distribution_map;

map<double, vector<int> >::iterator it;

for (int i = 0; i < size; i++)

{

it = distribution_map.find(prob[i]);

if (it!=distribution_map.end())

it->second.push_back(i);

else

{

vector<int> vec;

vec.push_back(i);

distribution_map[prob[i]] = vec;

}

}

// PDF to CDF transform

map<double, vector<int> > cumulative_distribution_map;

map<double, vector<int> >::iterator iter_cumulative;

double cumulative_distribution = 0.0;

for (it=distribution_map.begin();it!=distribution_map.end();++it)

{

cumulative_distribution += ((*it).second.size() * (*it).first);

cumulative_distribution_map[cumulative_distribution] = (*it).second;

}

for (int i = 0; i<100; i++)

{

nextNum(results, cumulative_distribution_map);

}

for (int j = 0; j<size; j++)

cout<<" "<<results[j]<<" ";

return 0;

}

Patricia/Radix tree - in-memory data manipulation

I was planning to write continuation post about SOA optimizations, but 'accidentally' I had a chance in last few weeks to code something a bit more interesting from my developer perspective. Not well known and not frequently and widely used in most companies (apart from those which are dealing with in-memory operations) : Radix trees!

Storing and retrieving strings in memory is a fundamental problem in computer science. The efficiency of string data structures used for this task is of paramount importance for applications such as in-memory databases, text-based search engines and dictionaries. The burst tree( http://www.cs.uvm.edu/~xwu/wie/CourseSlides/Schips-BurstTries.pdf ) is a leading choice for such tasks, as it can provide fast sorted access to strings. The burst trie, however, uses linked lists as substructures which can result in poor use of CPU cache and main memory. Thus, engineering a fast, compact, and scalable tree for strings remains an open problem. We will take a look here at Radix tree, which is one of possible way how to handle this fundamental problem and you can treat it as introduction to in-memory data handling.

To make a long story short, here is the radix tree structure

Radix tree

As we can see, we have here a kind of structural space optimization, and also quite efficient search structure. Apart from what you see on the picture, it is not binary tree. And here in fact magic happens!

Building a simple radix tree is not much different from non binary tree setup, but if we use this structure wisely we can on top of it create a powerfull searching mechanism that can align our tree to some specific group size, meaning that each tree level will try to be as close to this group size. Is it not fantastic ? Imagine that you are working on a node with limited memory, or when using simple radix tree you want to speed up you searches, for both tasks radix tree level grouping algorithm presented below could be a good choice (But there are better choices also! like HAT-Trie for example)

Comparing this structure with any other balanced tree or hashed structures we are gaining in two places. First is space, and second is number of comparision needed to find desired key. Hashmaps are special here cause you can think that they are faster, which is not necesairlly true if you consider hash algorithm then worst-case time is much higher then the one in radix tree.

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
struct node
{
    string key;
    int len;
    node* link;
    node* next;
    int before;
    node(const string &x) : link(0), next(0)
    {
        len = x.size() + 1; // Used for split purposes,
        key = x;
    }
    node(const string &x, int n) : link(0), next(0)
    {
        key = x.substr(0,n);
        len = n;
    }
    ~node() {}
};
class stringTree
{
    public:
        node* root;
        int target_size;
    public:
        stringTree(int targetSize):root(0), target_size(targetSize){}
        stringTree(const string& x, int targetSize): root(0), target_size(targetSize){root = internal_insert(root,x);}
    public:
        void insert(const string& x)
        {
            if (root)
                internal_insert(root,x);
            else
                root = internal_insert(root,x);
        }
        void display()
        {
            if (root)
            {
                redesign_postorder(root,root,0,0);
                internal_display(root,0);
            }
        }
        bool find(const string &x)
        {
            if (root)
                return internal_find(root, x, 0)==NULL?false:true;
            return false;
        }
    private:
        int countChilds(node* t)
        {
            int size = 1;
            if (t->len == 1 && t->key==" ") // Hack for ' ', same keys are stored as len=1 empty strings
                size--;
            node* iterator = t;
            while (iterator->next)
            {
                if (iterator->next->before < size)
                    iterator->next->before = size;
                iterator = iterator->next;
                size++;
            }
            return size;
        }
        void redesign_postorder(node* oldt, node* t, int levelSize, int groupSize)
        {
            if (t==NULL) return;
            redesign_postorder(t,t->link,levelSize+1,0);
            redesign_postorder(t,t->next,levelSize,groupSize+1);
            if (oldt->link && groupSize==0)
            {
                int numberOf = countChilds(oldt);
                int numberOfInternal = countChilds(t);
                numberOf+=groupSize;
                numberOf+=oldt->before;
                if (numberOf<target_size && ((numberOf+numberOfInternal)<=target_size))
                    join(oldt);
            }
        }
        void internal_display(node* t,int level)
        {
            if (t == NULL) return;
            for (int i = 0; i < level;i++)
                printf("\t");
            printf("node...: %s \n", t->key.c_str());
            internal_display(t->link,level+1);
            internal_display(t->next,level);
        }
        node* internal_insert(node* t, const string &x, int n=0)
        {
            if( !n ) n = x.size()+1;
            if( !t ) return new node(x);
            int k = prefix(x,n,t->key,t->len);
            if( k==0 )t->next = internal_insert(t->next,x,n);
            else if( k<n )
            {
                if( k<t->len )
                    split(t,k);
                t->link = internal_insert(t->link,x.substr(k),n-k);
            }
            return t;
        }
        int prefix(const string &x, int n, const string &key, int m)
        {
            for( int k=0; k<n; k++ )
                if( k==m || x[k]!=key[k] )
                    return k;
            return n;
        }
        void split(node* t, int k)
        {
            node* p = new node(t->key.substr(k),t->len-k);
            p->link = t->link;
            t->link = p;
            string temp = t->key.substr(0,k);
            t->key = temp;
            t->len = k;
        }
        void join(node* t) // Goign to use it during tree merge to met group size conditions
        {
            node* p = t->link;
            string temp = t->key.substr(0,t->len);
            string temp2 = p->key.substr(0,p->len);
            t->key = temp + temp2;
            t->len += p->len;
            t->link = p->link;
            string tempKey = temp;
            int lenghtTemp = t->len;
            while(t->next)
                t=t->next;
            t->next = p->next;
            while(p->next)
            {
                string tempKey2 = p->next->key.substr(0,p->next->len);
                string tempKey3 = tempKey + tempKey2;
                p->next->key = tempKey3;
                p->next->len += lenghtTemp;
                p=p->next;
            }
        }
        node* internal_find(node* t, const string &x, int n=0)
        {
            if( !n ) n = x.size()+1;
            if( !t ) return 0;
            int k = prefix(x,n,t->key,t->len);
            if( k==0 ) return internal_find(t->next,x,n);
            if( k==n ) return t;
            if( k==t->len ) return internal_find(t->link,x.substr(k),n-k);
            return 0;
        }
};

int main() {

    string testowy = "amazon";
    string testowy2 = "amazonadsystem";
    string testowy3 = "amazonwebapps";
    string testowy4 = "amazon";
    string testowy5 = "amazon-adsystem";
    string testowy6 = "amazonwebapps";
    string testowy7 = "aol";

    stringTree test(testowy,3);
    test.insert(testowy2);
    test.insert(testowy3);
    test.insert(testowy4);
    test.insert(testowy5);
    test.insert(testowy6);
    test.insert(testowy7);

    printf("found: %d\n", test.find(testowy2));
    printf("found: %d\n", test.find("bsabsha"));
    printf("============================\n");
    printf("TREE\n");
    printf("============================\n");
   
    test.display();
    
    return 0;

}

Please pay attention that this code is not even close to ideal, it works but it could be done much better in some places. The intention of the code was just to show you how to build such tree. Moreover if you take a closer look at redesign_postorder  function you can clearly see that postorder evaluation is a bit tricky here, cause easier and more intuitive way will be to start from bottom and go level by level up. Can you see some pros and cons of this solution with postorder ? Also did you manage to see that redesign_postorder is indeed doing level grouping here ? Another interesting question could be: Can instead of tree redesign for specific level we can do it during insertion ? More interesting info and interesting structures based on radix trees could be found for example here:

http://lwn.net/Articles/175432/
http://code.dogmap.org/kart/
http://www-db.in.tum.de/~leis/papers/ART.pdf


Comments $\TeX$ mode $ON$

Performance optimizations in SOA - part 1

It's been a while since my last post here, but during my absence I was mainly working on performance optimizations in SOA (Service Oriented Architecture) and I would like to share with you some of my conclusions after those few months.

Whenever you have to deal with Foundation Library ( a kind of library that is widely used by many back-ends) and you want to be sure that pull requests that you are integrating are not decreasing an overall performance of the library , than apart from strict Code Reviews -> MEASURE, measure and one more time measure your library performance. I spent a week or two to build our performance dashboard (Python+JS+CSS/HTML5+C++ for library code) for library that is one of our core libraries, and a key library for data encoding/decoding. Final result looks (more or less) like:

Example of Performance Dashboard for Foundation Library

What to measure ? And how to measure it ?

Well here things starts to be a bit more complicated, depends on the language that you are using, you can or you can not measure memory usage (let's exclude the case when you have your own memory map allocator that pre-allocates memory per object, and you are manually freeing memory from this memory allocator) . So firstly try to measure most common use cases that your library provides. Usually API from Library Manager. Secondly: Do you have a cache system in your library ? If yes than measure first read and second read (from cache). As integrator you have to have a tool that allows you to say that library is heading into wrong/good direction -> Try to build a trend graphs taking into account all previous tests, that after few months you can take a look and say to your manager that the work that you put in place for performance optimizations is going into right/wrong direction ;).

 

Trend graph for library

If you successfully build your Performance dashboard than you have to ensure that tests which you are running are always run in same conditions. Always use same machine with same configuration, for performance measurements, don't do it in core time when other people probably using same machine that you are using for test. Best option here is to have a separated test environment, otherwise use cron and schedule a tests somewhere in nightly hours. To reduce random factors, remove outliers from graph. Never run once if you are building trend graphs, run tests multiple times to build an average that should much better visualize a real library trends. 

Let's say that you succeed and you are able now to monitor you library performance, now its time for graph analysis, which believe me is the most interesting part of work when dealing with huge foundation libraries, as if gives you an idea what is really going on in your library, and how you library behave. Take a look and try to guess what is going on:

Did you see this "fragmentation" jumps ? :)

Any guess ? Well i will answer to this "issue" in the last image,

Two different paths ? What is going on ? :)

 

There could be many reasons for such behavior, but it usually means that some elements are dependent on another elements (when you deal with Lazy Layers its very important to remove such dependencies as much as possible, -> dependency injection could be a good choice here).

Well this one is easy O(n^2)

Frankly speaking I think we all see what is going on here, bad algorithm in BOM model. But maybe we cannot do it better ? If you can.. refactor immediately!

Fragmentation and Cache system looks broken ?

Fragmentation that is observed here is really due to internal STL memory allocation (quite often in this case its connected to boost::multi_index structures, here you can observe how those structures behave) First and second read(from cache) is in this case OK, as cache has been already refilled, this is why its also an important factor to take a look at the numbers on the scale, otherwise we may spend some time searching for an issue where there is no issue at all. Look at the numbers at the scale -> Always.

A so called mess :))))

If you get a graphs like the last one, than you are definitely not the happiest man on the earth. Cause analysis of such graphs is usually highly complicated. We can say that something is happening with library when we reach a specified number of Elements ~2000, but to find out what is really going on and from where those outliers comes from, you have to spent a bit more time with tools like valgrind, and dig deep inside the code. But hey! at least you know where to look for, without measurements you won't be able reveal most of those performance issues.

Always Measure!

PLT (Procedure Linkage Table) and tcmalloc part 3

Here we go again!
This time let's take a look what PLT and GOT has to do with tcmalloc at all ? Should we worry when going to production with our new tcmalloc allocator ?

In short terms YES we should.. Why ? Well lets find out.

At the beginning we need some basic knowledge about dynamic linking under Linux system with glibc, so lets start with that. To keep it simple I will only consider DT_RUNPATH, not the old and currently deprecated DT_RPATH (but please pay attention that in production environment its quite common to have old deprecated variables..). So when ld.so is trying to load dynamic shared library, there are few paths that ld.so will consider taking into consideration the following order, and indeed this very important to understand it when you deals with shared libraries:

• firstly path from the environment $LD_LIBRARY_PATH
• than paths from the caller's (the ELF object that require the library load through ELF dependency or dlopen) DT_RUNPATH. 

• DT_RUNPATH is a set of paths, hardcoded in the binary at link time, that are here to help in the path resolution of dynamic library at runtime. At link time, it's controlled by the -rpath ld flag, or then environment variable LD_RUN_PATH 

• from ld.so cache. Libraries present in the cache are found from paths given in /etc/ld.so.conf and files from /etc/ld.so.conf.d/
• and /lib and /usr/lib as a last resort

OK we have some basic knowledge, lets briefly explain what PLT is? as we will need this knowledge latter. One more time briefly it's procedure linkage table. This mechanism is used to speed up process startup. It allows position independent code (PIC) object (dynamically linked shared library) to lazily rely on foreign symbols defined by other ELF object. Exactly LAZY, that means PLT symbol is only resolved the very first time it is used at the cost of one more indirection before accessing the GOT (global offset table). If you symbol relies only on GOT its faster in runtime but slower in startup phase, as usually we are using only small subset of symbols, not all of them.
A bit more detailed info here:
http://eli.thegreenplace.net/2011/11/03/position-independent-code-pic-in-shared-libraries/

Some symbols in ELF can be declared as weak objects. It means that its possible to provide that symbol redefinition in another ELF object. This is exactly what static linkage is doing, it will keep only strong symbols after linkage thus there will be no conflict in linkage time. For dynamic libraries everything looks different mainly because dynamic linkage knows nothing about weak and strong symbols. When resolving a symbol dynamicly, the first encountered definition wins, it could be weak or strong it does not matter FIRST win always. Its clear here that order matters when you redefine symbols! So its clear now that if you want to link your tcmalloc dynamically you have to link it before glibc, otherwise you are one more time doomed :-)

Now lets dive deeper..

Do you ever think why you are able to redefine malloc/free/realloc/calloc? If no than maybe you read the the text above ? If yes than you should already know it. Indeed all allocation symbols are marked as weak in glibc, and this is why we are able to use tcmalloc instead of standard one! But this is not the end! Remember that ld.so is still here and it has to call malloc/free also! Which version it will call when resolving dynamic linkage ? Dynamic linker need malloc, but in order to call malloc there must by one already loaded, sounds weird but, well to link something dynamically you at least need one malloc call before you can redefine it. To fix this issue, the glibc always uses calls to the PLT version of malloc/calloc/realloc/free so that the address of the actual implementation can be easily rewritten at runtime with a single write. In a first time, malloc@plt points to the glibc malloc implementation. Later on, when the new malloc implementation is loaded and initialized (http://www.delorie.com/gnu/docs/glibc/libc_34.html), malloc@plt will point to the new implementation. Same for free@plt.

Now its probably a bit more clear comparing to our knowledge from first post about tcmalloc.
Can we now go even deeper ? We can and lets try to find out why you should be very careful when you changing default malloc.

Very early during the process startup, ld.so call _dl_init_paths which initializes the search paths for the current executable we are loading. It allocates through malloc@plt (pointing to glibc malloc) structures to store data from \$LD_LIBRARY_PATH and DT_RUNPATH. When looking for a dynamic object, ld.so sequentially calls open_path with paths from \$LD_LIBRARY_PATH, then DT_RUNPATH. If for some reason we could not load the library using these paths, then the structure if freed using free@plt and assigned to NULL (why its freed?). What is important ?  dlopen! open_path can be called at any time. So if we call this after tcmalloc has been initialized, free@plt points to tc_free, but the data was allocated with glibc's malloc. BAM! core.

What I told you is now fixed in https://www.sourceware.org/ml/libc-alpha/2013-04/msg00308.html 2.18 glibc. But did you checked your glibc version ? :-) If its newer than that forget about it and go to prod without any worries (really? ;-) )

This fix is preventing free@plt calls for DT_RUNPATH (because free@plt could be now tc_free).

Sum up:

• Check your glibc version
• Check your  LD_LIBRARY_PATH and all other paths 
• Take your time to understand how tcmalloc works and why it works at all. Otherwise don't use it, cause you wont be able to say why it fail if it starts to.

What about LD_PRELOAD ? Well just read this (http://lca2009.linux.org.au/slides/172.pdf) presentation to master it.

Credits go to Amadeus MDW team that did a good job investigating some tricky parts that could be presented here now.

Rgds

$(TA)$

Comments $\TeX$ mode $ON$

tcmalloc part 2

We are back again,

In this second 'chapter' about tcmalloc I'm going to show you some results from real production environment code. I will focus on simple comparison of malloc and tcmalloc performance in NO multithreaded software. Is it worth switching from your defaut malloc to custom one ? I told you in first part of malloc post that its not necessarily obvious.. Lets find out.

Firstly lets check how simple glibc malloc behave in our test library:

Lets take a look at some numbers on how long it takes to evaluate some basic library functions:

Performance test create :   0:6000
Performance test pop :      0:18000
Performance test create :   0:5000
Performance test pop :      0:18000
Performance test :          0:93668000
Performance test Cache :    0:142341000
Performance test :          0:150872000 (not hitting the cache)
Performance test for Test : 0:8803000 (hitting cache)
Performance test for Test : 0:8770000 (hitting cache)
Performance test for Test : 0:8797000 (hitting cache)

Take a look at callgrind outputs:

We clearly see that ld lib responsible for dynamic libraries is taking most of the time in processing, but what is also very important malloc itself seems to work very heavily. Can we gain anything in terms of speed when we just simply replace our default malloc by custom tcmalloc ? Well of course there are few possibilities to configure tcmalloc with bigger page size (which in fact will use a bit more memory than we need but should be also a bit faster as less tcmalloc calls are needed in this case). But firstly lets try to look how default tcmalloc with default configuration behave. We will not use dynamic linking here we will try to exploit our test scenario using special LD_PRELOAD variable to be sure that We won't encounter any bad memory deallocation which leads usually to system core.

 For more detailed info about LD_PRELOAD you can go here: https://blog.cryptomilk.org/2014/07/21/what-is-preloading/

In next post I will try to explain how glibc works and why LD_PRELOAD do the job. Also it's not exactly true that tcmalloc replace malloc completely, well its partially true.. but for now lets come back to our tcmalloc scenario.

TCmalloc results:

Performance test create        : 0:5000
Performance test pop           : 0:18000
Performance test create        : 0:5000
Performance test pop           : 0:18000
Performance test               : 0:91996000
Performance test Cache         : 0:138960000
Performance test               : 0:147004000
Performance test for Test      : 0:8265000
Performance test for Test      : 0:8231000
Performance test for Test      : 0:8260000

Sounds promising! 150872000-147004000= 3868000 nanoseconds faster ~ 2.56% faster 

Lets also take a look at our callgrind outputs:

libc has a bit less to do, and you wont find malloc/free/calloc on its list. Those are now handled by tcmalloc. You can clearly see here how tcmalloc behave comparing to simple malloc. And its now quite clear (if it wasn't yet?) that pthread is a must here to use tcmalloc implementation. You can try yourself tcmalloc configuration build with TLS flag off to compare the results. And please share it if you have some, it will be nice to see how it behave. I'm going to test it also in some spare time with various flags.

We've seen that we can gain something even if we are in single threaded library. Some internal tests shows us that we can gain much more when switching to custom malloc in multithreaded environment. The choice is yours! But maybe its good to consider and compare also jemalloc and lockless ? For sure I will post some results from those two in comparison with tcmalloc and malloc. Stay tuned!

In next post I'm going to present you how ld, libc, LD_PRELOAD and free/malloc works when dealing with dynamic and static libraries, and why LD_PRELOAD works at all ?
One more time stay tuned, and follow me on twitter if you don't want to miss it :-)




Rgds
$(TA)$

Comments $\TeX$ mode $ON$.