Performance and memory alignment to cache line size boundaries

Here i would like to show an example of the application where you can see that data aligned to the boundaries of cache line size is accessed much more faster then unaligned:

1. #include "timer.h"
2.  
3. #include <algorithm>
4. #include <iostream>
5.  
6. class A
7. {
8. public:
9.     int x[18];
10.     A* next;
11. };
12.  
13. class B
14. {
15. public:
16.     int x[15];
17.     B* next;
18. };
19.  
20. template<class T>
21. void TestFunc(size_t len, size_t cycles)
22. {
23.     size_t l = sizeof(T);        
24.     std::cout << "Size = " << l << std::endl;
25.  
26.     T* m = new T[len];
27.     for(size_t i = 0; i < len; ++i)
28.     {
29.         m[i].next = 0;
30.         if (i > 0)
31.         {
32.             m[i - 1].next = &m[i];
33.         }
34.     }
35.     parallel::Timer timer;
36.     timer.Start();
37.     for (size_t i = 0; i < cycles; ++i)
38.     {
39.         T* item = &m[0];
40.         while (item != 0)
41.         {
42.             item->x[4] += 5;
43.             item = item->next;
44.         }
45.     }
46.     std::cout << cycles << " cycles in " << timer.End() << " ms\n";
47.     delete[] m;
48. }
49.  
50.  
51. int main(int /*argc*/, char* /*argv*/[])
52. {      
53.     size_t len = 1024;
54.     size_t cycles = 5000;
55.  
56.     TestFunc<A>(len, cycles);
57.     TestFunc<B>(len, cycles);
58.     return 0;
59. }
60.  

Here i assume that the cache line size is 64 bytes. Also I have founded for myself dependency between structure size and access speed - Smaller structures are processed quickly. You can look at this example under ADM CodeAnalyst to see that there are no data cache misses for second function.

Active object and future result TBB implementation

After the reading articles about future results and active objects i have implemented a class which realize these concepts, as threading library i used TBB. Here is a code:
Active.h:

#ifndef _ACTIVE_OBJECT_H_
#define _ACTIVE_OBJECT_H_

#include "Types.h"

#include <functional>
#include <memory>

#include <tbb/tbb.h>

namespace Measurements
{

template <class T>
class FutureResult
{
public:
    FutureResult()
    {
        isAvailable = false;
        haveError = false;
    }

    void SetValue(const T& val)
    {
        tbb::mutex::scoped_lock lock(guard);
        value = val;
        isAvailable = true;
        haveError = false;
    }

    T GetValue() const
    {
        tbb::mutex::scoped_lock lock(guard);
        isAvailable = false;
        haveError = false;
        return value;
    }

    bool IsAvailable() const
    {
        return isAvailable;
    }

    bool HaveError() const
    {
        return haveError;
    }

    std::string GetErrorReport() const
    {
        tbb::mutex::scoped_lock lock(guard);
        return errorReport;
    }

    void SetErrorReport(const std::string& error)
    {
        tbb::mutex::scoped_lock lock(guard);
        errorReport = error;
    }

private:
    T value;
    std::string errorReport;
    mutable tbb::atomic<bool> isAvailable;
    mutable tbb::atomic<bool> haveError;
    mutable tbb::mutex guard;
};

template <class R, class F, class O>
class FunctionRunner : public tbb::task
{
public:
    FunctionRunner(R r, F f, O* p)
        : result(r)
        , func(f)
        , ptr(p)
    {}
    virtual task* execute()  
    {
        try
        {
            result->SetValue((ptr->*func)());
        }
        catch(std::exception& e)
        {
            result->SetErrorReport(e.what());
        }
        return 0;
    }
    R result;
    F func;
    O* ptr;
};

class Active

{

public:

    Active();



    ~Active();



    template<class R, class F, class O>

    std::shared_ptr<FutureResult<R> > ExecuteParallel(F f, O* p)

    {

        std::shared_ptr<FutureResult<R> > result(new FutureResult<R>());

        

        tbb::task& tbbTask = *(new(parent->allocate_child())

                               FunctionRunner<decltype(result),F,O>(result, f, p));  

        parent->increment_ref_count();  

        parent->spawn(tbbTask);  



        return result;

    }



    void WaitAll() const;



private:



    Active(const Active&);

    void operator= (const Active&);



private:

    tbb::empty_task* parent;

};

}

#endif

Active.cpp:

#include "Active.h"

namespace Measurements
{
/*******************************************************************************/
Active::Active()

{

    parent = new( tbb::task::allocate_root() ) tbb::empty_task;  

    parent->set_ref_count(1);

}

/*******************************************************************************/

Active::~Active() 

{

    parent->wait_for_all();
    parent->destroy(*parent);

}
/*******************************************************************************/
void Active::WaitAll() const
{
    parent->wait_for_all();
    parent->set_ref_count(1);
}
/*******************************************************************************/
}

Debug STL with GDB

I've found very useful script for viewing STL containers under GDB here is link. Also i duplicated them here :

##########################################
# #
# STL GDB evaluators/views/utilities #
# #
##########################################
#
# The new GDB commands:
# are entirely non instrumental
# do not depend on any "inline"(s) - e.g. size(), [], etc
# are extremely tolerant to debugger settings
#
# This file should be "included" in .gdbinit as following:
# source stl-views.gdb or just paste it into your .gdbinit file
#
# The following STL containers are currently supported:
#
# std::vector -- via pvector command
# std::list -- via plist command
# std::map -- via pmap command
# std::multimap -- via pmap command
# std::set -- via pset command
# std::multiset -- via pset command
# std::deque -- via pdequeue command
# std::stack -- via pstack command
# std::queue -- via pqueue command
# std::priority_queue -- via ppqueue command
# std::bitset -- via pbitset command
# std::string -- via pstring command
# std::widestring -- via pwstring command
#
# The end of this file contains (optional) C++ beautifiers
#
##########################################################################
# #
# CopyRight @ 2008 - Dan C Marinescu - All Rights Reserved under GPL V3. #
# #
# Email: dan_c_marinescu.RemoveThis@yahoo.com #
# #
##########################################################################



#
# std::vector<>
#

define pvector
if $argc == 0
help pvector
else
set $size = $arg0._M_impl._M_finish - $arg0._M_impl._M_start
set $capacity = $arg0._M_impl._M_end_of_storage - $arg0._M_impl._M_start
set $size_max = $size - 1
end
if $argc == 1
set $i = 0
while $i < $size printf "elem[%u]: ", $i p *($arg0._M_impl._M_start + $i) set $i++ end end if $argc == 2 set $idx = $arg1 if $idx < 0 || $idx > $size_max
printf "idx1, idx2 are not in acceptable range: [0..%u].\n", $size_max
else
printf "elem[%u]: ", $idx
p *($arg0._M_impl._M_start + $idx)
end
end
if $argc == 3
set $start_idx = $arg1
set $stop_idx = $arg2
if $start_idx > $stop_idx
set $tmp_idx = $start_idx
set $start_idx = $stop_idx
set $stop_idx = $tmp_idx
end
if $start_idx < 0 || $stop_idx < 0 || $start_idx > $size_max || $stop_idx > $size_max
printf "idx1, idx2 are not in acceptable range: [0..%u].\n", $size_max
else
set $i = $start_idx
while $i <= $stop_idx printf "elem[%u]: ", $i p *($arg0._M_impl._M_start + $i) set $i++ end end end if $argc > 0
printf "Vector size = %u\n", $size
printf "Vector capacity = %u\n", $capacity
printf "Element "
whatis $arg0._M_impl._M_start
end
end

document pvector
Prints std::vector information.
Syntax: pvector
Note: idx, idx1 and idx2 must be in acceptable range [0...size()-1].
Examples:
pvector v - Prints vector content, size, capacity and T typedef
pvector v 0 - Prints element[idx] from vector
pvector v 1 2 - Prints elements in range [idx1..idx2] from vector
end



#
# std::list<>
#

define plist
if $argc == 0
help plist
else
set $head = &$arg0._M_impl._M_node
set $current = $arg0->_M_impl->_M_node->_M_next
set $size = 0
while $current != $head
if $argc == 2
printf "elem[%u]: ", $size
p *($arg1*)($current + 1)
end
if $argc == 3
if $size == $arg2
printf "elem[%u]: ", $size
p *($arg1*)($current + 1)
end
end
set $current = $current->_M_next
set $size++
end
printf "List size = %u \n", $size
if $argc == 1
printf "List "
whatis $arg0
printf "Use plist to see the elements in the list.\n"
end
end
end

document plist
Prints std::list information.
Syntax: plist : Prints list size, if T defined all elements or just element at idx
Examples:
plist l - prints list size and definition
plist l int - prints all elements and list size
plist l int 2 - prints the third element in the list (if exists) and list size
end



#
# std::map and std::multimap
#

define pmap
if $argc == 0
help pmap
else
set $tree = $arg0
set $i = 0
set $node = $tree->_M_t->_M_impl->_M_header->_M_left
set $end = $tree->_M_t->_M_impl->_M_header
set $tree_size = $tree->_M_t->_M_impl->_M_node_count
if $argc == 1
printf "Map "
whatis $tree
printf "Use pmap to see the elements in the map.\n"
end
if $argc == 3
while $i < $tree_size set $value = (void *)($node + 1) printf "elem[%u]->left: ", $i
p *($arg1*)$value
set $value = $value + 4
printf "elem[%u]->right: ", $i
p *($arg2*)$value
if $node->_M_right != 0
set $node = $node->_M_right
while $node->_M_left != 0
set $node = $node->_M_left
end
else
set $tmp_node = $node->_M_parent
while $node == $tmp_node->_M_right
set $node = $tmp_node
set $tmp_node = $tmp_node->_M_parent
end
if $node->_M_right != $tmp_node
set $node = $tmp_node
end
end
set $i++
end
end
if $argc == 4
set $idx = $arg3
set $ElementsFound = 0
while $i < $tree_size set $value = (void *)($node + 1) if *($arg1*)$value == $idx printf "elem[%u]->left: ", $i
p *($arg1*)$value
set $value = $value + 4
printf "elem[%u]->right: ", $i
p *($arg2*)$value
set $ElementsFound++
end
if $node->_M_right != 0
set $node = $node->_M_right
while $node->_M_left != 0
set $node = $node->_M_left
end
else
set $tmp_node = $node->_M_parent
while $node == $tmp_node->_M_right
set $node = $tmp_node
set $tmp_node = $tmp_node->_M_parent
end
if $node->_M_right != $tmp_node
set $node = $tmp_node
end
end
set $i++
end
printf "Number of elements found = %u\n", $ElementsFound
end
if $argc == 5
set $idx1 = $arg3
set $idx2 = $arg4
set $ElementsFound = 0
while $i < $tree_size set $value = (void *)($node + 1) set $valueLeft = *($arg1*)$value set $valueRight = *($arg2*)($value + 4) if $valueLeft == $idx1 && $valueRight == $idx2 printf "elem[%u]->left: ", $i
p $valueLeft
printf "elem[%u]->right: ", $i
p $valueRight
set $ElementsFound++
end
if $node->_M_right != 0
set $node = $node->_M_right
while $node->_M_left != 0
set $node = $node->_M_left
end
else
set $tmp_node = $node->_M_parent
while $node == $tmp_node->_M_right
set $node = $tmp_node
set $tmp_node = $tmp_node->_M_parent
end
if $node->_M_right != $tmp_node
set $node = $tmp_node
end
end
set $i++
end
printf "Number of elements found = %u\n", $ElementsFound
end
printf "Map size = %u\n", $tree_size
end
end

document pmap
Prints std::map or std::multimap information. Works for std::multimap as well.
Syntax: pmap

Here is "False sharing" example, you can try it in VS with enabled OpenMP flag. Also if you enable speed optimization for compiler single thread version will be faster, but you can see false sharing effect too.

#include <iostream>
#include <ctime>
#include <omp.h>

using std::cout;
using std::endl;

const double M=8e8;

//single thread work to do
void one_thread() 
{
    long int n1=1, n2=1;
    for(; n1<M; n1+=n1%3);
    for(; n2<M; n2+=n2%3);
    cout << "Sum = " << n1 + n2 << endl;
}


//multi thread work to do
void multi_thread() 
{
    struct T
    {
        long int n1;
        char chuck[64];//should be commented to see false sharing effect
        long int n2;
    } t;
    t.n1 = 1;
    t.n2 = 1;
    #pragma omp parallel num_threads(2) shared(M,t)
    {
        #pragma omp sections
        {
            #pragma omp section
            for(; t.n1<M; t.n1+=t.n1%3);

            #pragma omp section
            for(; t.n2<M; t.n2+=t.n2%3);
        }
    }
    cout << "Sum = " << t.n1 + t.n2 << endl;
}

time_t start, end;
double diff;

int main(int argc, char* argv[]) 
{
    time(&start);
    multi_thread();
    time(&end);
    diff=difftime(end, start);
    cout<<diff<<" seconds elapsed for multi thread calculation."<<endl;

    time(&start);
    one_thread();
    time(&end);
    diff=difftime(end, start);
    cout<<diff<<" seconds elapsed for 1 thread calculation."<<endl;
    return 0;
}

Again about rvalues

You can use rvalues for creating move semantics - remove copy constructors for temporaries. Example:

#include <iostream>

class A
{
public:
    A()
    {
        x = new int[1];
        x[0] = 1;
        std::cout << "new\n";
    }
    ~A()
    {
        delete[] x;
    }

    A(const A& a)
    {
        x = new int[1];
        x[0] = a.x[0];
        std::cout << "new\n";
    }

   /* A(A&& a) //move constructor
    {
        x = a.x;
        a.x = 0;
    }*/
private:
    int *x;
};

A GetA()
{
    A a;
    return a;
}

//if you want to use movable object as member in another object you should declare move constructor
//and use std::move
class B
{
public:
    B(){}
    B(B&& b) //move constructor
    {
        a = std::move(b.a);
    }
    A a;
};

B GetB()
{
    B b;
    return b;
}

int main(int, char*[])
{
    B b = GetB();
    {
        A a = GetA();
        A a2(a);
        std::cout << "scope\n";
    }
    return 0;
}

New web page

I have updated my personal page. You can find updated demo section there.

C++0x multi-threading

If you want to play with new functionality for multi-threading in C++ for free you need gcc-4.5 and Linux, MinGW currently doesn't support this functionality (but it has all required headers). To compile programm you need to specify complier flag -std=c++0x and linker flag -pthread. VC++ currently have not this functionality too. Here is small example:

#include <thread>
#include <mutex>
#include <iostream>
#include <unistd.h>

class MyJob
{
public:
    MyJob(std::mutex* m) : m(m){}
    void operator()()
    {
        for (int i = 0; i < 5; ++i)
        {
            {
                std::lock_guard<std::mutex> lock(*m);
                std::thread::id id = std::this_thread::get_id();
                std::cout << "Thread " << id << std::endl;
            }
            sleep(1);
        }
    }
private:
    std::mutex* m;
};

int main()
{
    std::mutex m;
    std::thread t1{MyJob(&m)};
    std::thread t2{MyJob(&m)};

    t1.join();
    t2.join();

    return 0;
}