Move semantics with containers and algorithms

Move semantics is one of the coolest new features of (the-now-so-not-that-new) C++11. The main idea is the ability to steal the implementation (the guts) of temporary objects and therefore be able to avoid creating object copies. This of course is very important for performance; while it is true that many mainstream C++ compilers have been able to optimize away such copies (e.g. return value elimination), move-semantics gives us developers an explicit way of controlling it.

Another important aspect of move-semantics is that it allows definition of move-only data types, a.k.a. objects that cannot be copied but only moved. An example for all, move-semantics makes possible the definition of the std::unique_ptr<T> data type.

Let us consider a simple ADT, called Object, with properties very similar to the ones of an std::unique_ptr. As you can see it is a simply wrapper for a string literal allocated on the heap that only offers move semantics (no copying is allowed). It additionally contains a type that will be useful later.
We can use it populate a container as shown in the main function. emplace_back allows for the object to be built in place so no copy constructor is going to be invoked.

Real problems start when we want to use this container with standard algorithms. If the algorithm uses move-semantics then there are no issues, for example trying to sort the array can be achieved with the following code:
If we print the addresses at which each message is allocated we see that it is indeed the same before and after sorting. This happens because std::sort internally uses std::swap which uses move-semantics.

// before sorting
obj(1st message) addr(str): 0x12a9030
obj(2nd message) addr(str): 0x12a9080
obj(3rd message) addr(str): 0x12a9010
obj(4th message) addr(str): 0x12a90f0
// after sorting
obj(1st message) addr(str): 0x12a9030
obj(4th message) addr(str): 0x12a90f0
obj(2nd message) addr(str): 0x12a9080
obj(3rd message) addr(str): 0x12a9010

So far so good! However, when trying to use algorithms which require copy, i.e. std::copy, std::copy_if & friends, the compiler is going to give us a nasty error message (which may change depending on your compiler, I am using GCC 4.9.2):

In instantiation of ‘_OIter std::copy_if(_IIter, _IIter, _OIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator

Which basically means the algorithm is trying to copy an instance of the Object class, but that is not allowed since we deleted the copy constructor. How to solve it? Well, you could write your implementation of std::copy_if and explicitly use std::move to promote the operation to move semantics, e.g.:
However there is an easier and cleaner way of achieving the same behaviour, behold the std::move_iterator. It is an adaptor for iterators which yields an R-value reference when the dereference operator (i.e. *) is used. That means using std::copy_if on a container with only moveable objects is as easy as:
Printing the dst_objs array yields the following:

obj(1st message) addr(str): 0x12a9030
obj(4th message) addr(str): 0x12a90f0

No object have been copied, mission accomplished! :)

It has to be added that

C++ <3

A type-safe definition for OpenCL's enqueue_kernel function

I want to share with you something that I initially thought it wouldn't work... but it does. No reason behind it, just to prove (once again) that C++11 is indeed fantastic and it can handle (almost) whatever you throw at it.

Since 1 year the OpenCL 2.0 standard was ratified. The thing which is most exciting for me is device-side enqueue. This is a functionality which allows a kernel to submit new work directly on the device without the need for host intervention.

However there is something fishy with the way the function is defined and I am going to explain why. The new enqueue_kernel function (defined in the OpenCL 2.0 language specification) has several overloads:

Ok, we like it. But wait for the next two ones:
Emh.. wait a second.. what? How many variadic arguments are in there?

The issue here are the two sets of "...". How many arguments should we accept? It is funny since the specs are not saying much about these additional arguments. However the only way to read this in a way that makes sense (in my understanding) is the following:

"If a closure function (or block) is passed which accepts N OpenCL "local" pointers, then their size is defined by an equal number of unsigned values (i.e., size0,..., sizeN-1). It is responsibility of the runtime support to allocate memory before the nested kernel is executed."

All of this to say that the length of the two variadic argument lists (the lambda's and the one internal to enqueue_kernel) must match. This means that it is responsibility of the compiler to perform this additional check. 

I can see many people being happy with this...  but couldn't we use the type system to enforce that? Can our beloved meta-programming fix this? Let's assume we were in C++? Would the API designer able to to express this concept (number of arguments in the closure equal number of arguments passed) just with the means of the type system? You will be glad to ear that with C++11, YES WE CAN! ...and I am going to show you how to do that.

For this example we use the sizes as input to the lambda (not for allocating device local memory as the actual implementation of enqueue_kernel is supposed to do). This is just a proof of concept, we are not interested in the actual implementation of OpenCL's device-side enqueue. Execution of the program will produce the following expected output:

> 10
> 20
> 30
> Calling closure
> Computed value: 60

This highlight the power of the ... expansion operator of C++11 variadic templates. For example if we try to call this function using an invalid number of sizes a compiler error will be generated:

@ThinkPad-X1-Carbon:~$ g++ -std=c++11 test.cpp 

test.cpp: In function ‘int main(int, char**)’:

test.cpp:25:10: error: too few arguments to function ‘int enqueue_kernel(std::function<void(Args ...)>, typename to_int<Args>::type ...) [with Args = {int, int, int}]’

    10, 20);

          ^

test.cpp:10:5: note: declared here

 int enqueue_kernel(std::function<void (Args... )> block, typename to_int<Args>::type... sizes)

     ^

And there you have it. A type-safe definition of OpenCL's enqueue_kernel using C++11. Just because in C++11 we can! Hate on that C lovers! :)

C++ <3

Serious programming on ChromeOS

In my previous post I explained how to get a working OpenCL for ARM's Mali GPUs on the Samsung Chromebook 2. That's great I know and you are very welcome. :) 

However, do you seriously want to write OpenCL goodness on that small 11" screen? And don't get me started on the keyboard... I mean the Samsung Chromebook 2's keyboard is not that bad considering this a 250$ laptop we are talking about... however I am currently typing on a Lenovo X1 carbon chiclet style keyboard and the experience is the closest thing to a nerdgasm (nerd-orgasm... yeah I just made it up, deal with it! ...ah no actually it already exists).  

First thing... we need to enable ssh server. Lucky enough, ChromeOS comes by default with an ssh daemon (/usr/sbin/sshd) , however it is not enabled by default. The way to enable it is described in [1,2]. For short there are the steps:

1. Remove rootfs verification (!!please backup your stuff!!):

$ sudo /usr/share/vboot/bin/make_dev_ssd.sh --remove_rootfs_verification --partitions 4
$ reboot

2. Mount the rootfs in rw mode (remember you will need to do this every time you reboot the device and want to write in the root partition):

   $ sudo mount -o remount,rw /
   

3. Generate SSH keys:

$ sudo mkdir /mnt/stateful_partition//etc/ssh
$ ssh-keygen -t dsa -f /mnt/stateful_partition//etc/ssh/ssh_host_dsa_key
$ ssh-keygen -t rsa -f mnt/stateful_partition/etc/ssh/ssh_host_rsa_key

4. Allow incoming traffic on PORT 22:

$ sudo /sbin/iptables -A INPUT -p tcp --dport 22 -j ACCEPT

5. We can now create a new user used to remotely login (alternatively you can set the chronos user password). To create a new user you need to follow these steps:

   
   $ sudo useradd -G wheel -s /bin/bash mali_compute
   $ sudo passwd mali_compute
   $ sudo mkdir /home/mali_compute
   $ sudo chown /home/mali_compute mali_compute
   
   

   Now we have a user, however the user cannot run sudo and we already know we need to be able to run sudo in order to enter the Arch linux chroot. To solve this we need to make user belonging to the wheel group part of the sudoers. This is done using the visudo command.

   $ sudo su
   $ visudo
   

   Search and uncomment one of following lines:

   ## Uncomment to allow members of the group wheel to execute any command
   # %wheel ALL=(ALL) ALL
   
   ## Same thing without a password
   # %wheel ALL=(ALL) NOPASSWD: ALL
   

...and voila' you are done.

Now get your ip address using the ifconfig command

chronos@localhost / $ ifconfig 
lo: flags=73  mtu 65536
        [...]

mlan0: flags=4163  mtu 1500
        inet 192.168.1.80  netmask 255.255.255.0  broadcast 192.168.1.255
        ether xxx:xxx:xxx:xxx  txqueuelen 1000  (Ethernet)
        RX packets 1908  bytes 802994 (784.1 KiB)
        RX errors 0  dropped 0  overruns 0  frame 0
        TX packets 1524  bytes 415774 (406.0 KiB)
        TX errors 4  dropped 0 overruns 0  carrier 0  collisions 0

Now from your desktop machine simply type:

$ ssh mali_compute@192.168.1.80
motonacciu@ThinkPad-X1-Carbon:~$ ssh chronos@192.168.1.80
The authenticity of host '192.168.1.80 (192.168.1.80)' can't be established.
RSA key fingerprint is ...
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '192.168.1.80' (RSA) to the list of known hosts.
Password: 
mali_compute@localhost ~ $ uname -a
Linux localhost 3.8.11 #1 SMP Tue Sep 30 23:28:35 PDT 2014 armv7l SAMSUNG EXYNOS5 (Flattened Device Tree) GNU/Linux

Super cool right? ...well.. not really! Unfortunately you are going to loose the configuration once you reboot your chromebook. Or better, you will need to rerun the iptables and sshd commands manually if you wish to enable the daemon again. No worry, we can automatically start the SSH daemon by adding a script under the /etc/init directory, e.g., sshd.conf; it should contain the following lines (remember to remount the rootfs in rw mode in the case you rebooted the device in the meantime).

start on started system-services
script
     /sbin/iptables -A INPUT -p tcp --dport 22 -j ACCEPT
     /usr/sbin/sshd
end script 

You should be able to login again from your next reboot.

Great, we can login into the super underpowered ChromOS shell... what's the deal? Right, but we are not done yet. The 'prestige' hasn't come yet :). Well, the idea of the last step is to let the user we just created jump into the Arch Linux chroot at login and therefore bypass the ChromeOS shell. This is rather simple to do as well (assuming you have created the chroot, otherwise go here):

$ su mali_compute
$ echo "sudo enter-chroot" > ~/.bash_profile

That's it! Wonder what's going to happen next time you log into your chromebook?

motonacciu@ThinkPad-X1-Carbon:~$ ssh mali_compute@192.168.1.80
Password: 
Last login: Mon Oct 13 22:17:40 BST 2014 from 192.168.1.71 on pts/1
Entering /mnt/stateful_partition/crouton/chroots/arch...
mali_compute@arch ~ $ uname -a
Linux arch 3.8.11 #1 SMP Tue Sep 30 23:28:35 PDT 2014 armv7l GNU/Linux

Limited chrosh... gone!! Welcome to fully fledged Linux environment! :)

[1]: http://www.de7ec7ed.com/2013/05/ssh-daemon-samsung-chromebook-exynos.html

[2]: https://sites.google.com/site/cr48ite/getting-technical/remove-rootfs-verification-make-read-write

C++ <3

Run OpenCL on the new Samsung Chromebook 2 in 5(-ish) simple steps

Recently a colleague and friend of mine posted a great tutorial on how to run OpenCL on Samsung's Chromebook in 30 minutes. He has tested this tutorial on the older (Series 3) Chromebook.

I bought myself the newer version, the Samsung Chromebook 2 (11" version). The main difference between these two laptops is that the former chromebook hosts a Mali-T604 GPU while the latest model uses a bifier Mali T628-MP6 chip. The Mali-T604 GPU has 4 cores vs the 6 in the latest chip. The latter is definitely an interesting chip for OpenCL's folks since the 6 cores are going to be split into two physical devices with 4 and 2 cores respectively.

In this blog I will present a slightly different way of setting up a working OpenCL environment for the Chromebook 2 (which should be also working on the former chromebook).

Prerequisites

• A Samsung Chromebook 2 (or any other ARM-based device running ChromeOS)
• Some free space on your drive (2/4 GBs)
• Knowledge of Arch Linux package manager (pacman)
• Optional: I will install the development system in the internal SSD. If you think you are going to need more space for development, then you can use the microSD)

Step 1: Enable Developer mode

Enter Recovery Mode by holding the ESC and REFRESH (↻ or F3) buttons, and pressing the POWER button. In Recovery Mode, press Ctrl+D and ENTER to confirm and enable Developer Mode.

Step 2: Install chroarg

chroarg is a fork of the cruton process. It is based on the chroot command available in ChromeOS which allows to spawn lightweight virtual OSs, a more technical explanation follows:

What's a chroot?

Like virtualization, chroots provide the guest OS with their own, segregated file system to run in, allowing applications to run in a different binary environment from the host OS. Unlike virtualization, you are not booting a second OS; instead, the guest OS is running using the Chromium OS system. The benefit to this is that there is zero speed penalty since everything is run natively, and you aren't wasting RAM to boot two OSes at the same time. [...] 

source: https://github.com/dnschneid/crouton

While cruton will install by default Ubuntu, chroarg is based on Arch Linux. I personally prefer Arch Linux, but if you feel more confident with Ubuntu feel free the use cruton. Follows the creation of a chroot (more options are available from the project github page)

1. Launch a crosh shell (Ctrl+Alt+T, you can paste in the console using Ctrl+Shift+V), then enter the command shell.
   
2. Download and extract chroagh:
   

   $ cd ~/Downloads
   $ wget https://api.github.com/repos/drinkcat/chroagh/tarball -O chroagh.tar.gz
   $ tar xvf chroagh.tar.gz
   $ cd drinkcat-chroagh-*
   
   

3. Create the rootfs:
   

   $ sudo sh -e installer/main.sh -r arch -t cli-extra 

The tool will install a minimal Arch, at some point it will ask to give the user name and password for the main user. If everything went fine (it often does), then you are ready to start your Arch installation within ChromeOS.

NOTE: If you want to install the chroot to a different location (e.g., an SD/microSD card or USB) then use the -p option to specify a destination folder.

Step 3: Enter-chroot and environment setup

After chroarg finishes installing a base Arch Linux installation we can enter this virtual environment using the command (from any crosh shell):

$ sudo enter-chroot

You should see the following output:

chronos@localhost ~/Downloads/drinkcat-chroagh-380f361 $ sudo enter-chroot
Entering /mnt/stateful_partition/crouton/chroots/arch...
[motonacciu@localhost ~]$ 

And magic magic, we are not in Arch linux. At this point you can install a bounce of packages which are going to be useful for OpenCL development.

$ sudo pacman -S gcc vim cmake base-devel git opencl-headers

Next (and final) step is downloading the Mali userspace drivers from. They are available from malideveloper.com and continuously updated. This is the moment where you should be aware of the Mali device you have installed in your chromebook. In my case the driver marked as MALI-T62x will do the trick. For the older chromebook the MALI-T604 driver should be used instead. Since we are using the command line we can download the fbdev version of the drivers:

$ wget http://malideveloper.arm.com/downloads/drivers/binary/r4p0-02rel0/mali-t62x_r4p0-02rel0_linux_1+fbdev.tar.gz
$ tar -xf mali-t62x_r4p0-02rel0_linux_1+fbdev.tar.gz
$ ls fbdev
libEGL.so  libGLESv1_CM.so  libGLESv2.so  libmali.so  libOpenCL.so

Next we can either edit the ~/.bashrc file to include this folder among the LD_LIBRARY_PATH, alternatively you can copy the libraries in your /usr/lib folder (but you will need to add the user among the sudoers). Or simply manually specify its path to GCC.

Step 4: Compile and Run your CL program

When you compile your program make sure the linker can find the libmali.so. The libOpenCL.so library is just a wrapper, the only library needed for running CL program is the libmali.so.

Compile your program as follows:

$ g++ -std=c++11 main.cpp -Iinclude -L/home/compute/fbdev -lmali -o clInfo

This is a simple CL program which prints the list of devices. We run using the following command (you can avoid specifying the LD_LIBRARY_PATH if you placed the libmali.so in a default location):

$ LD_LIBRARY_PATH=/home/compute/fbdev/:$LD_LIBRARY_PATH ./clInfo
Total number of CL devices: 2

Device 0 info
 - Vendor:            'ARM'
 - Name:              'Mali-T628'
 - Type:              'CL_DEVICE_TYPE_GPU'
 - Max frequency:     '533'
 - Max compute units: '2'
 - Global mem size:   '2097192960'
 - Local mem size:    '32768'
 - Profile:           'FULL_PROFILE'
 - Driver version:    '1.1'
 - Extensions:        'cl_khr_global_int32_base_atomics cl_khr_global_int32_extended_atomics cl_khr_local_int32_base_atomics cl_khr_local_int32_extended_atomics cl_khr_byte_addressable_store cl_khr_fp64 cl_khr_int64_base_atomics cl_khr_int64_extended_atomics cl_khr_gl_sharing cl_khr_icd cl_khr_egl_event cl_khr_egl_image cl_arm_core_id cl_arm_printf'

Device 1 info
 - Vendor:            'ARM'
 - Name:              'Mali-T628'
 - Type:              'CL_DEVICE_TYPE_GPU'
 - Max frequency:     '533'
 - Max compute units: '4'
 - Global mem size:   '2097192960'
 - Local mem size:    '32768'
 - Profile:           'FULL_PROFILE'
 - Driver version:    '1.1'
 - Extensions:        'cl_khr_global_int32_base_atomics cl_khr_global_int32_extended_atomics cl_khr_local_int32_base_atomics cl_khr_local_int32_extended_atomics cl_khr_byte_addressable_store cl_khr_fp64 cl_khr_int64_base_atomics cl_khr_int64_extended_atomics cl_khr_gl_sharing cl_khr_icd cl_khr_egl_event cl_khr_egl_image cl_arm_core_id cl_arm_printf'

Step 5: Done

Yes, that's all. You can now start writing you multi-device OpenCL codes for ARM's Mali GPU. Let's verify that everything is in order... shall we?

OpenMP 'matmul_1024x1024' on ARM-CPU   [cores:8] => 16632 msecs
OpenCL 'matmul_1024x1024' on Mali-T628 [cores:2] => 616 msecs
OpenCL 'matmul_1024x1024' on Mali-T628 [cores:4] => 319 msecs

Stay tuned for more experiments!

C++ <3

Generating Flex and Bison rules with X-Macros

Lately I found myself working on a pet project for which I needed a parser for an assembly-like programming language for a real architecture. Since I wanted to use this opportunity to learn something new, I decided to use a combination of tools, i.e. Flex (for lexing) and Bison (for parsing)... obviously in C++ :)

However I found myself facing a pretty interesting problem for which I could not find a workaround, therefore I set myself with the goal of filling that void with this post. 

The problem is easily explained, in the language I am parsing (let's call it X for brevity), there  is a large amount of opcodes, e.g. add, sub, bra. These operations have different properties (e.g. accepting different number and type of parameter) and I wanted to have a centralized specification for those properties which I can pull-out as needed throughout my project. This is a typical case where X-macros should be used. However since flex and bison specification files are not a C-like language, I cannot use the preprocessor capabilities. Before we jump to the problem I wanted to recap what X-Macros are and why they are awesome. 

Let us consider the following example:

By properly defining the two macros in the opcodes.def file, and thus take advantage of the C preprocessor, we can reshape the information in different ways. As an example consider a function which determines if an argument is valid for a given operation:

As you expect the output of the code above is:
Is 'sub(_,_,_,reg)' valid? false
Is 'add(_,reg,_)'   valid? true
Is 'add(_,imm,_)'   valid? false
Is 'sub(_,_,imm)'   valid? true
Is 'sub(_,_,lab)'   valid? false

Cool eh? and think how easy is going to be adding a new opcode or change their semantics. This is quite standard practice in compiler-related project, beware that working with macros can get messy... but what not to love here? If you start to get weird errors by your compiler, sometimes it is instructive to run only through the preprocessor and have a look at the generated code. This can be done in GCC using the -E option (checkout an example for the code above here).
In my experience many programmers consider these meta-programming techniques (i.e., macros and templates) harmful and therefore to avoid like the plague. Of course everyone is entitled to his opinion but in a problem like this one, X-macros can save you an huge amount of time. The generated code is also a lot faster and more memory efficient then any implementation based on lookup tables.

Anyhow I am digressing... I hope all those macro haters have had enough by now and they left this post so that we can start to get things to the next level. Without all those 'C is better than C++' holding us back, can move on solving the actual problem which inspired this post. The idea is to use the the properties of X-macros inside the lexer and parser specification for a language parser. Since we are working in C++, the natural choice of tools is Flex (for lexing) and Bison (for parsing) [another choice could be Boost.Spirit, but I never felt the tool to be mature enough to be practical useful, feel free to comment on this]. For those who are not aware of parser generator tools, these are (meta-)programs which take a language specification (usually in a EBNF form) and produce code to determine whether an input stream matches that specification.

This is not going to be a tutorial on how to use Flex and Bison, there are other tutorials/blogs you can check out for that (Google is your friend). I start by setting up a basic flex and bison specification for parsing our language X. X allows 1 instruction per line, where each instruction is composed by an operator and a list of comma-separated arguments. Labels are allowed as well. For example the following is valid X program:

add r1, r2, r3 
sub r1, r1, #10
bra r1, exit
...
exit:
...

Follows the Flex and Bison specification files for the X language:
and
In order to compile this code we need a Makefile which triggers the generation of the lexer and parser. We are going to base our setup on cmake, checkout the CMakeLists.txt file for details. You can test out the code so far by checking out the following github repository (refer to the no_autogen branch).

You may start to notice the problem now. Our opcodes, which we defined in the opcodes.def file, need to be defined (again and again) both in flex and bison specifications. Since these are not C/C++ files, we cannot rely on the preprocessor for generating these rules automatically. This makes adding new opcodes to the X language very cumbersome since many files need to be modified. However there is my solution to the problem.

The idea is to generate temporary C/C++ files used to reshape the information contained in the opcodes.def file in a form that it is suitable for flex and bison. After that we replace the content generated by X-Macros in the language specification. The workflow is not particularly difficult, however we the main effort would be on automatizing this entire process so that specification files are refreshed when needed (i.e. when we lunch make).

Let's start with the Flex specification file (lexer.ll). My solution of the problem is the following. We define a placeholder, i.e. @@{{OPCODES}}@@ (you can choose any name for the placeholder, however make sure that it is unique within your flex specification),  which we are going to replace with some content automatically generated by the preprocessor. We also rename the file into lexer.in.ll which we are now going to call the template file. Next thing we need to do is to add to CMake the necessary action for generating and replacing the placeholder with content.
Similar thing can be done for the bison specification file. Note that here things are a little bit more complex since we need to declare opcodes both in the token section (line 28 of the parser.y file) and later in the grammar itself within the parsing rules (line 53 of the parser.y file). The full CMakeLists.txt file is available here.

In order to make replacement of placeholders with the preprocessor output I wrote a simple python script (i.e. xmacro_patcher.py). The script does remove empty lines and comments produced by the preprocessor and collapse the lines if needed. I actually spent lot of time finding out a way of doing this without the need of an additional script. I found a command line which will do the same work but unfortunately the way CMake treats the command line arguments in the COMMAND section made it impossible to use (damn you CMake). Anyway, in the case anyone is curious

awk -vf2="$(while read x; do echo $x; done)" '/$1/{print;print f2;next}1' $2

This like will read content from stdin into variable 'f2', then match the input file $2 with the regex provided in $1 and append the content of f2 at that location. The patched file will be retuned on the standard output.

And that's really it. We can now add new operators to our opcodes.def, press make... and our parser will now accept the broader language.

C++ <3

My take on serialization (Part III: deserialize)

After seeing serialization, one fundamental thing is missing, i.e. deserialization!

There is not much to say here, this is the inverse operation we performed during serialization... therefore similar patters apply.

And we are done! 

In the std::tuple<T...> deserializer I would have liked to use the commented line. With that line I could remove 20+ lines of code which are used by the deserialize_tuple method. However, in that way the object is deserialized in the inverse order. The type is correct, but since it seems that the arguments of the make_tuple function are evaluated right-to-left, the resulting elements of the tuple are inverted. Therefore a serialized tuple (1,2,3) is deserialized back as (3,2,1) :(. This is caused by the fact that the apply function has side-effects and in C++ we cannot rely on the evaluation order of the arguments of a function, therefore this code is not safe and better take the safe solution (however it might work in some C++ compiler). 

Just to see if everything is working fine we write our usual test cases using google-test: 

Last thing to do is running a complete benchmark where we serialize and deserialize an object and compare it with boost::serialization. This time I compiled everything with optimizations enabled (-O3) and I am using gcc 4.8.0 20130502 (pre-release).

The code is similar to the one we saw in the previous post this time I add a call to deserialize and a stupid if to be sure the compiler is not doing any dead-code elimination. The code for boost::serialization is similar, just trust me (I know I am Italian... it might be difficult... but come on, as my supervisor says... "give me a break").

The result is well... quite impressive. I didn't do this exercise with performance in mind, rather than my goal was to eliminate a dependency on the boost libraries. Now I realize that boost is definitely doing something really wrong in the serialization library. The added storing of typing info does not justify the huge performance penalty. My solution is 20x faster! Since the messages I produce are half of the size (thanks to the missing typing info) I would expect boost to be twice as slow.

I am frankly quite pleased by the performance improvements I saw within the libWater project after replacing boost::serialization with this solution. We had a 10% performance improvement which in HPC is quite welcome.

The full code, plus the test cases are available on github (under the BSD license): https://github.com/motonacciu/meta-serialization
(contributions are welcome)

Read: PART I: get_size(...)

Read: PART II: serialize(...)

C++ <3

My take on serialization (Part II: serialize)

After discussed the get_size(...) functor, which given an object returns its serialized size in bytes, we can go on and write the serialize function.

We can follow the same pattern of the get_size, but this time we have to store the content to a stream.

As before, we have a specialization of the serialize_helper template for tuples, vectors, strings and POD datatypes. In order to be performance efficient we presize the vector in lines 66-67 (because we know how many bytes we need to store the object) thanks to the get_size predicate.

Let's write some unit tests (because they are very important):

So it's time for running some benchmarks. YAY! Let's compare this serializer with boost and check whether spending time re implementing this was worth some. Since I don't have much time, we only run 1 experiment... if you are interested you can run more :) 

So, as long as size of the serialized stream is concerned, boost uses 63 bytes while ours only 26 bytes (more than half). Performance-wise boost::serialization needs 4.410 secs to run the test, our serialization solution 0.975 seconds, more than 4 times faster. Of course we are not saying that boost::serialization sucks... as a matter of fact it solves a different problem since it also store the typing information which allows everyone (even a Java program) to reload the stream. Our serialization strategy (as I explained in the first post) is based on the fact that the type is known at receiver side (therefore we can avoid to store typing).

Let's show some graphs, comparison of our serialization strategy relative to boost::serialization:

Read: PART I: get_size(...)
Read: PART III: deserialize(...)

C++ <3

My take on C++ serialization (Part I: get_size)

Long time, no see!

Lately I have been busy writing... and writing... and we know that: "All writing and no coding makes Simone a dull boy" :) so I needed to go back to C++ writing... which means new blog entries!

Lately, in a project (libwater, soon released) I have been using boost::serialization in order to transfer C++ objects from one node to another via network. Boost serialization is pretty neat, especially when you are under a deadline, but releasing the code with a dependency on boost is in most of the case an overkill.  Especially when the boost library you are using is not an "header-only" library, which means the user needs it installed in his system. Since the project focuses on large clusters, this is always a big problem because these advanced libraries are in the majority of the cases missing (or a very old version is installed) meaning that the user has to do lot of installation work just to try out our library.

Beside that, boost::serialization was doing more than we actually needed, in fact I am in the particular case where I exactly know the type of the object I am receiving on the remote node, therefore I don't need to store in the serialization stream the type information like boost does. This is typical when for example you are implementing a network protocol where the structure of messages is known. In such case we can assign a tag to each message type and easily assign a C++ type to it. Since the list of messages is known statically, we can use some meta-programming just to have some fun.

Actually I could literally half the size of each transferred message by only storing the object content. Therefore I started to work on a "header-only"  serialization interface... of course it had to involve template meta-programming! :) I am going to post the various pieces of my take on object serialization on multiple posts (otherwise it may get to heavy to read).

The first thing (which I will introduce today) was defining a functor which given an object returns the size (in bytes) of its serialized representation, I called it size_t get_size(const T& obj). This is some easy code which needs to be written, so let's get to it.

Stated that the types I deal with are (for now) restricted to std::string, integral types (uint8_t, uint16_t, uint32_t, uint64_t), std::vector<T> and std::tuple<T...>, this code should make the trick. While for tuples and integral types we directly store the value, for vectors and string we prepend the number of elements which will be stored (since this information is not explicit in the type). 

For tuples I I hope I had a better solution using template expansion. This could be possible if for example the get_size was more like sizeof... which means it can be computed based on the object type . This would allow me to write something like this: std::sum(sizeof(T)...).

However, since we may have strings and vectors as elements of the tuple, this is not possible because we would need to also unpack the elements of the tuple (not only the type). Actually I would appreciated anyone that could give me a better solution for that. 

A simple test:

Read: PART II: serialize(...)

Read: PART III: deserialize(...) 

C++ <3

The Wonderful World of C++11's Smart Pointers

While I was reading the C++11 my attention was caught by the std::weak_ptr<T> class. Let's rewind a little bit and explain what smart pointer are. The C++03 introduced the std::auto_ptr<T> class which was meant to be a basic implementation of smart pointer. A smart pointer is an object which behaves like a pointer but it doesn't need to be manually cleaned because the pointed are of memory is automatically freed when the pointer object is destroyed. It is quite handy especially in those situation where you want to throw an exception and you don't want to leak any memory. 

Since its introduction, the std::auto_ptr<T> class had several problems (a brief history of std::auto_ptr<T> I found interesting is from Scott Mayers' (C++ God level) blog. One of the main problem is that auto_ptr is not reference counting, which means that there is only one smart pointer owning the reference of memory location. Whenever an object a (of type std::auto_ptr<T>) is copied into b the ownership of the pointer is transferred. 

That means that after the assignment the object a will be an invalid pointer (therefore it will not perform the cleanup of memory) while the pointer b now owns the reference to the memory and he should take care of performing the delete operation. std::auto_ptr<T> for example to be used with containers. Indeed every attempt to access element x of a std::vector<std::auto_ptr<int>> will transfer the ownership of the object in the array to the left side of the assignment leading to disasters. 

The C++11 finally solved this problem. First of all C++11 introduces several smart pointers, exactly 3: std::unique_ptr<T>, std::shared_ptr<T> and std::weak_ptr<T>.

• std::unique_ptr<T> is very similar to std::auto_ptr<T> of C++03. However because of the introduction of move semantics in C++11 (for which I promised to post something and yet didn't do it) the implementation is more safe. For example now it is possible to have containers of unique_ptrs. In the case you want more details on this have a look to this blog post. 
• std::shared_ptr<T> in an implementation of a smart pointer with reference counting. This means that dislike std::unique_ptr<T>, a std::shared_ptr<T> can be copied and assigned. Every time the pointer is copied the object keeps track of how many smart pointer objects are pointing to the same memory location. When the smart pointer goes out of scoped and its distructor gets invoked the object checks whether he is the last smart pointer owning a reference to that memory, if this is the case the delete operation is invoked. 

And finally we arrive at the std::weak_ptr<T> which is the main reason why I started this post in the first place. :) When I first read the definition of a weak_ptr on che C++11 standard I said to my self... nah you will never use this... what are the odds of you needing a weak_ptr??. And I indeed was wrong, couple of days ago I stumble upon a problem that really required to use a weak_ptr, true story. 

It all started with a simple problem. I wanted to have an instance manager handling a number objects. These objects need to refer to other instances of the instance manager. I am not a fan of using pointer, therefore I start with a simple structure which turned to be a disaster :) 

Can you see it? Yep, it always gets me. The main problem is that vectors expands during execution. When an array expand its content is relocated in memory. The array begins its life with a certain capacity. Although the size is zero, the capacity is usually larger than that. Every time the push_back method is invoked the size of the array increases. When the size reaches the capacity the vector needs to be expanded so that more elements can be append. The content of the array is therefore copied over the new allocated memory and the original location is deleted. In my implementation I keep a pointer to an element of the array but surprise surprise... that pointer is going to be invalid if too many elements are pushed into the array.

A workaround is to keep the instances in a std::vector<Instance*>.  However in the era of C++11 goodies we don't want to take care of pointers ourselves, therefore the use of smart pointer is screaming out. My second try was by using a shared_ptrs. Now there it is the implementation which uses shared_ptrs, where is the problem now?

I tricked a little bit the code to make it clear what can go wrong with this implementation. When the instance manager goes out of scope is freed. This means that the repos array gets deallocated. However here something nasty happens, a circular dependency can generate among Instance objects. Indeed we end up in a situation where the first two elements of the vector refers, the situation in memory is the following:

When the first element of the array is removed the pointer has reference counting 2, therefore the number is decreased and the object is not removed. We move on to the second element and same repeats. We therefore end up loosing any reference to the two instances and leak memory. Valgrind should be quite angry if you run this code :). Where do we do now?

That's it. That the reason why C++11 also has std::weak_ptr<T>. Their purpose is to be used in such situation to break cycles. This kind of smart pointer holds a non-owning ("weak") reference to an object that is managed by std::shared_ptr<T>. It must be converted to std::shared_ptr<T> in order to access the referenced object.

The weak_ptr is quite easy to use. You can construct a weak_ptr from a shared_ptr. Every time you want to access the pointed object you need to obtain a shared_ptr. This is done through the lock() method. The lock method requires the object to be valid. The validity of a weak_ptr can be tested using the expired() method. The use of weak_ptr makes Valgrind happy and concludes this post. 

C++ <3

Speeding up quicksort with template meta-programming

As you may have realized by now I am a little bit fanatic of C++ templates. I indeed have really a hard time listen to programmers saying: "I do program in C++ but I am not using templates". I swear I heard such statement several times in my life, and it is such a pity there is a number of C++ programmers avoiding templates like they are a disease. Templates are awesome and template meta-programming is way beyond awesomeness (at least for me). From my point of view (involved in compiler design), C++ meta-programming gives me a way to interact with the compiler in a much closer way... and this allows you to test out new compiler transformations before implementing them in the compiler itself. 

Anyhow, this week I spend some spare time trying to make a point (mostly just for the sake of this post), my point is the following: "if you want speed... you shall go crazy with meta-programming". Forget your beloved C (I know several people will not agree on this statement, but seriously guys, C is just a subset of C++). Therefore, I was thinking an algorithm I could speedup with template meta-programming and I thought the most relevant thing would be some kind of sorting algorithm. Indeed there is lot of research around sorting algorithms, mostly related to the computational complexity of algorithm. However, most of the time people forgets that their algorithm is running on top of a super-scalar architecture which, as we seen in the last post, is not that found of conditional jumps. 

Among the myriad of sorting algorithms I choose the quicksort because it's complexity is O(n logn) and in practice, because the sorting is done in-place therefore it plays well with the cache, it performs better than other sorting algorithm with same computational complexity. As prove of its relevance note that the C library provides the std::qsort function and the C++ STL std::sort method also uses a combination of quicksort and introsort. Here it follows the classic implementation of quicksort:  

I tested the execution time of the three sorting routines using the following code. I generate a vector of N elements and initialize each value randomly. Afterwards I sort the same array for 1 million times and sum the total execution time. At the end of the loop I divide by the number of iterations in order to obtain the execution time of a single invocation of the sorting routine. The skeleton of the testing code is the following (ITER = 1000000):
Compared to std::sort and std::qsort our method is not that bad. 

The major differences with the std::qsort (which is a C implementation) is that the C version uses a memcpy operation to perform the swap operation. This is very inefficient especially if compared to the C++ std::swap which uses move semantics (another wonder introduced with C++11) eliminating any need of creating a temporary copy (we will cover move semantics and R-value references in a later post). 


My implementation of quicksort is however not faster than std::sort for larger arrays, this might be caused by std::sort function to switch to the introsort algorithm for such arrays. 


Nevertheless this implementation is a good starting point for start playing with templates (YAY). Indeed the compiler is not able to inline recursive functions, however if we know statically the size of the array we are going to sort we can inline entirely the computation of the quicksort therefore optimizing the sorting for pipeline usage. It is worth noting that not all the control flow statements can be eliminated as the comparison between array elements (which are not known at compile time) needs to be performed at runtime when we actually know the value of the array elements. 


A way of writing the template version of the quicksort algorithm is the following:
Compiling this version of the quicksort is more demanding than the previous one. Indeed the recursive invocation is unrolled at compile time which means the compiler needs to generate an awful amount of code. For example compiling the quicksort for arrays of 50 elements requires 7 minutes and GCC uses around 1.3GB of main memory. The produced binary is 4 MB compared to 27KB which is the size of the executable obtained when the previous sorting function is invoked. 


However if we run the template-based quicksort (template_sort), we obtain the following performance results:

Clearly there is an advantage for arrays up to 25 elements. The template quicksort is 2 times faster than the standard std::sort. Note that the same algorithm is utilized, the only difference is that we optimized the pipeline usage by eliminating recursive function calls by completely unwinding the call stack at compile time. However there is a drawback, because of the size of the generated code, the program doesn't fit into the cache anymore and therefore we miss-utilize L1 Instruction cache. However until 25 elements the generated code is small enough to fit into the instruction cache and the benefits of unrolling are clearly visible. 


The nice thing is that we doubled the performance of the quicksort using an high level language without messing with any assembly instruction. Also the template code is not that different than the trivial implementation of the quicksort. 


C++ <3

A generic loop unroller based on template meta-programming

Loop unrolling (or unwinding) is code transformation used by compilers to improve the utilization of functional units present in modern super-scalar CPUs. Indeed, processors have a pipelined architecture consisting of multiple staged (minimum are 5). While the CPU is executing the instruction in one of the stages he can simultaneously load and decode the next operation pointed by the program counter. However, in the presence of branch instructions, the CPU needs to wait the decode stage in order to know whether the branch has been taken or not in order to adjust the program counter and correctly load the next assembly instruction. Over the years several architectural optimizations have been introduced to reduce the problem (e.g. branch prediction units), however in specific situation the CPU can loose up to 20 cycles because of a branch instruction. 

For this reason it is very important to reduce the amount of branched in the input code. This is the job of the compiler since it is the software agent closest to the actual hardware and it can produce code which better fits the underlying CPU. However, compilers are quite complex and often they even fail in applying elementary optimizations. An example is loop unrolling. Because the compiler often fails to produce such transformation, developers, especially in High Performance Computing (HPC), tend to tune their code by manually unroll loops. This is (in my opinion) a bad practice since the tuned code is not portable anymore (the optimal unroll factor for one machine can be bad for another). A second problem is that by manually unrolling a loop the body is replicated many times which is never a good thing if a bug shows up.

However we don't necessary have to renounce to performance if we want code readability and structure. With C++11 we can have them both. :) The idea is to have an meta-function which we call unroller, this class takes care of unrolling N invocations of a generic functor like below:

This simple function takes care of unrolling N function calls. Because we use inline, the generated code will actually not contain function calls. The next code snippet shows how we can use the unroller: 

And that's it. You can now control the unrolling factor using the pre-processor directive UnrollFactor, which means you can either define it in your code or provide a value through a Makefile in order to fit the target architecture. 

The next question comes natural, how slower this loop is going to be compared with the C-like version which uses no lambda and which can be unrolled by the underlying compiler? This is a legittimate question and that's why we are going to do some old good benchmarking right now! :)

The loop our unroller will fight against is the following:  

The unroller turned out to be pretty awesome. As expected we have a 2.5 speedup. The amount of computation in the loop body is enough that we start seeing improvements starting from an unrolling factor of 2 or 5. However depending on the number of iteration of the loop and the amount of computation the best unrolling factor may change.  

C++ <3

decltype Insanity... a.k.a. when the return type depends on the function itself?

In a previous post I introduced basic usage of the auto and decltype keywords. In most cases the use of auto or decltype is a shortcut to avoid to manually write down the type of an object. However these two new keyword enables new capabilities of the C++ language. 

During this week I stumble on one of those cases. I don't want to overload you with the details of the specific problem I was solving therefore I will use an equivalent example just for the sake of presentation. What I want to achieve is the following, I want to write a meta-function which takes a variable number of types as input and returns a type structured as a (degenerated) binary tree. An example follows:

The way we want to write this in C++ is by defining a function which makes use of variadic templates (a feature introduced in C++11). In this way we can have a typed function accepting an unbounded number of arguments. However if you start declaring the function signature you will soon realize that you cannot write the return type of this function:

How get around this? So, first of all we have to realize that the return type depends on the type and number of the parameters of the function. Fortunately, C++11 introduced the so called trailing return types, which, as the name suggests, enable the return type of a function to be specified after the input parameters (so that the actual function parameter types can be used in the return type). A second thing we must do, because meta-programming is heavily based on recursion, we must define a termination case for the recursion which, in this case boils down to a function accepting 2 arguments and returning the composition of the two bundled into a pair object.
Now the only thing remaining is to write down the return type of this function. Basically what we want to write in the return type is that my return type is a pair object where the first argument is the type of Arg1 while the second argument is the return type of the recursive invocation of the same function on the rest of the provided arguments. And, thanks to decltype, we can write it down as:
Now we can test whether everything is working by using the following simple main:

I have to admit I was quite impressed for a couple of seconds when I saw the first two tests working, I suppose at this point I have to point out which kind of C++ compiler I am using. Currently in my machine I have installed GCC 4.7.1. Considering that many C++ compilers are still struggling to support variadic templates and GCC can already eat code like this, it is quite cool. As my research activity mostly focuses around compilers, I was wondering how could GCC internally determine the type of the makeTree function considering that the type depends on itself. However I soon find out that GCC is not that smart, indeed if we try to invoke the function with more that 3 arguments the compiler generates the following error:

test.cpp: In function ‘int main(int, char**)’:
test.cpp:26:22: error: no matching function for call to ‘makeTree(int, int, int, int)’
test.cpp:26:22: note: candidates are:
test.cpp:8:24: note: template<class LhsTy, class RhsTy> std::pair<_T1, _T2> makeTree(const LhsTy&, const RhsTy&)
test.cpp:8:24: note:   template argument deduction/substitution failed:
test.cpp:26:22: note:   candidate expects 2 arguments, 4 provided
test.cpp:13:6: note: template<class Arg1, class Arg2, class Arg3, class ... Args> std::pair<Arg1, decltype (makeTree(arg2, arg3, makeTree::args ...))> makeTree(const Arg1&, const Arg2&, const Arg3&, const Args& ...)
test.cpp:13:6: note:   template argument deduction/substitution failed:
test.cpp: In substitution of ‘template<class Arg1, class Arg2, class Arg3, class ... Args> std::pair<Arg1, decltype (makeTree(arg2, arg3, args ...))> makeTree(const Arg1&, const Arg2&, const Arg3&, const Args& ...) [with Arg1 = int; Arg2 = int; Arg3 = int; Args = {int}]’:
test.cpp:26:22:   required from here
test.cpp:13:6: error: no matching function for call to ‘makeTree(const int&, const int&, const int&)’
test.cpp:13:6: note: candidate is:
test.cpp:8:24: note: template<class LhsTy, class RhsTy> std::pair<_T1, _T2> makeTree(const LhsTy&, const RhsTy&)
test.cpp:8:24: note:   template argument deduction/substitution failed:
test.cpp:13:6: note:   candidate expects 2 arguments, 3 provided

Which made me very sad. Now I wonder if the C++ code I wrote fails because of a faulty implementation of the GCC compiler or if what I wrote is not valid C++11 code. Comments are welcome. 

C++ <3

Printing tuples

One of the power tools of C++11 standard library are tuples... a.k.a. std::tuple<Args...>. It was not possible to have such utility in C++98 because of the lack of variadic templates. Indeed the std::tuple object heavily relies on this feature which has been introduced with the C++11 standard.

Tuples are collections composed of heterogeneous objects of pre-arranged dimensions. A tuple can be considered a generalization of a struct's member variables. It's use is very similar to the std::pair class which was available since C++98, however while pairs can only contains 2 generic elements, a tuple can be of undefined size. 

The standard way of using tuples in C++11 is the following:

Tuple t1 is constructed using the std::make_tuple function is an utility which easy the construction of tuples without worrying about the type of the single elements which is instead inferred thanks to the template mechanism. Another way to build a tuple is shown for tuple t2 for which we use the tuple class constructor. It is worth noting that we use an initializer list ( { } ) which is again one of the new feature of the C++11 standard (which we will cover one day). When building this tuple, the type of the first element is a const reference to the first element of the tuple t1. At last, tuple t3 is constructed using the std::tie function which creates a tuple of lvalue references. Therefore by writing the first element of tuple t3 we indeed propagate the value to both t1 and t2. And the assert in the last line of the code snippet is satisfied. 

When working with tuples, it is sometimes useful, for debugging purposes for example, to print their values to an output stream. This can be done by overloading the << operator, however, because the access to the tuple's elements is strongly typed, we need some metaprogramming magic in order to be able to print each tuple element. The problem is the following, accessing an element of the tuple is only possible via the std::get method which takes a constant teamplate parameter representing the index of the the value we want to access. Because this value needs to be a constant expression (otherwise the compiler would not be able to determine the return value of the function) we cannot simply iterate through the elements of a the tuple using a loop iterator. What instead we need to do is use recursion:
This method is generic in the sense that it can be used to print any tuple, the output obtained by printing the tuples t1, t2 and t3 at the exit of the program is:
 
Easy, isn't it? :)


C++ <3

Once you go 'decltype'...

Since C++11 became available several things have changed in C++ and also the way you used to solve problems now changes. It is indeed an interesting time for C++ developers because it's time to forget old practices and embrace the new features since C++11 is truly awesome.

I want to start this blog introducing decltype, a new keyword of the language which given an expression returns its type.

For example, in C++11 you can write this:

The type of b will be derived from a, therefore it will be int. decltype accepts any expression, therefore it is also possible to write:

In this way we don't need to infer what would be the type of the expression, but we let the compiler do the job considering that it has this knowledge. Although useful, the syntax is quite cumbersome since we have to write the expression twice and this is not probably handy to use in real codes. A better way to obtain the same result is by using the auto keyword, which is also part of the new C++11 standard. With auto declaring b is as easy as follows:

The combination of auto and decltype allows the developer to take advantage of type inference information derived by the compiler. It also allows you to do more with much lesser code. An example I found myself using lately is the declaration of sets/maps which requires to explicitly provide a comparator. The common way of doing this before C++11 was basically in two ways, either by providing a function which implements the key comparator, e.g.:  

Or by using a functor object as follows:

The advantage of using a functor object is that the comparator can have state. Similar behavior can be obtained using a function if static or global variables are being used.  

In C++11, the same thing can be coded with less effort as follows:

We take advantage of the auto initializer to define a lambda function (which I will cover in the future) and using the decltype keyword we get its type (which it would not be trivial to write down ourselves considering that it could be implementation dependent). 


This is just a basic introduction to the wonders of decltype, there is much more to unveil, however, as we say in italian... "you cannot start running if you didn't learn to walk in the first place". Indeed, decltype might seem pretty lame and not useful alone, but combined with other features of C++11 it becomes a very powerful tool. Stay tuned for more C++ love. 


C++ <3