use boost::bind to implement callbacks

#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <boost/function.hpp>
#include <boost/bind.hpp>
class Foo
{
public:
    typedef boost::function<void(int)> CB;
    CB cb_;
    void setCb(CB cb)
    {
        cb_ = cb;
    }

    void produce()
    {
        this->cb_(30);
    }

};

class Test
{
public:
    void onData(int k)
    {
        std::cout << "callback with " << k << std::endl;
    }
};

int main()
{
    Foo f;
    Test t;
    f.setCb(boost::bind(&Test::onData, &t, _1));
    f.produce();
}

How does cache line cause false sharing?

 http://drdobbs.com/go-parallel/article/217500206?pgno=1

"In two previous articles I pointed out the performance issue of false sharing (aka cache line ping-ponging), where threads use different objects but those objects happen to be close enough in memory that they fall on the same cache line, and the cache system treats them as a single lump that is effectively protected by a hardware write lock that only one core can hold at a time. [1,2] This causes real but invisible performance contention; whichever thread currently has exclusive ownership so that it can physically perform an update to the cache line will silently throttle other threads that are trying to use different (but, alas, nearby) data that sits on the same line. It's easy to see why the problem arises when multiple cores are writing to different parts of the same cache line, because only one can hold the exclusive hardware lock at a time. In practice, however, it can be even more common to encounter a reader thread using what it thinks is read-only data still getting throttled by a writer thread updating a different but nearby memory location, because the reading thread has to invalidate its copy of the cache line and wait until after the writer has finished to reload it.

A number of readers have asked for more information and examples on where false sharing arises and how to deal with it. I mentioned one concrete example in passing in [3] where Example 4 showed eliminating false sharing as one of the stages of optimizing a queue.

This month, let's consider a concrete example that shows an algorithm in extremis due to false sharing distress, how to use tools to analyze the problem, and the two coding techniques we can use to eliminate false sharing trouble.  "

Word Alignment

Word alignment is not a particularly difficult concept, but it is fairly important, because it does show up in unusual places.

What you know

We've defined a word to mean 4 bytes. To store a word in byte-addressable memory (i.e. where each element of memory is one byte), you have to break up the 32 bit quantity into 4 bytes. Thus, if the word was 0x01ab23cd, it's broken up into 0x01, 0xab, 0x23, 0xcd. You can store this in two ways. If it's big endian, than the most significant byte (i.e., 0x01) is stored in the smallest of four consective addresses. The data 0xab, 0x23, 0xcx are stored in the following three memory addresses. Thus, if you stored the first byte in address 1000, the remaining bytes are stored in addresses 1001, 1002, and 1003.
For little endian, you store the least significant byte (0xcd) in the smallest address (in our example, this is address 1000), then 0x23, 0xab, and 0x01. Thus, it's stored in reverse order.
Even though it's somewhat inaccurate to say this, we say a word is stored at, say, address 1000. That is, we pick the smallest address, and say that's where the data is located in memory. Thus, if the data has N bytes, then it is stored in address A to A + N - 1, and we say that the data is at address A.

Word alignment

However, there's a second issue. For reasons of making hardware simpler (and sometimes because the ISA defines it this way), words are often stored at word aligned addresses. Word-aligned means the address is stored at an address that's divisible by 4. If you look at an address that's divisible by 4 and written in binary, you see that the last two bits are 0.
Why is this interesting? Whenever you're dealing with word quantities they must appear at word aligned addresses. Consider the following structure (written in C++):

struct Foo {
   char x ;  // 1 byte
   int y ;   // 4 byte, must be word-aligned
   char z ;  // 1 byte
   int w ;   // 4 byte, must be word-aligned
} ;

In C/C++, data is stored in the order declared. Thus, x, y, z, and w appear in that order in memory. In principle, the amount of memory needed by Foo should be 10 bytes (1 byte for each char, 4 bytes for each int variable).
However, due to word aligment, it will probably take more than 10 bytes. In particular, if y and w are both word aligned, and z is in between, there will be 3 unusued bytes. Thus, the structure may be 13 bytes large, with 3 filler bytes, used for padding.
To see this in action, try declaring a structure or class as above, then use the sizeof operator, and see how many bytes it has.
Byte quantities can be stored at any address in memory. Halfword quantities (16 bits) are often stored at half-word aligned addresses (addresses divisible by 2). Doubleword quantities (64 bits) are often stored at double-word aligned addresses (addresses divisible by 8). You see these restrictions most often on a RISC ISA.
CISC ISAs may not necessarily require alignment of words, etc.

Chart

This chart summarizes the characteristics of word-alignment.

Quantity	Address divisible by	(Binary) address ends in
Byte	1	anything
Halfword (16 bits)	2	0
Word (32 bits)	4	00
Doubleword (64 bits)	8	000

Specific structure packing when using the GNU C Compiler

The GNU C compiler does not support the #pragma directives. In particular it does not support the "#pragma pack" directive. So when using the GNU C compiler, you can ensure structure packing in one of two ways

• Define the structure appropriately so that it is intrinsically packed. This is hard to do and requires an understanding of how the compiler behaves with respect to alignment on the target machine. Also it is hard to maintain.
• Use the "packed" attribute against the members of a structure. This attribute mechanism is an extension to the GNU C compiler. An example of how you would do this is below.

  struct test
   {
           unsigned char  field1 __attribute__((__packed__));
           unsigned short field2 __attribute__((__packed__));
           unsigned long  field3 __attribute__((__packed__));
   } var1, var2;
  
  

  Note the use of the keyword "__attribute__" with the attribute "__packed__" within the double brackets (before the terminating semicolon of each member variable declaration).
  An alternate way of doing the above is as below.
  

  struct test
   {
           unsigned char  field1;
           unsigned short field2;
           unsigned long  field3;
   } __attribute__((__packed__));
   
   typedef struct test test_t;
   
   test_t var1, var2;
  

  This will ensure that all members of the structure are packed. Note that this doesn't seem to work right if you try to combine the typedef and the struct definition or if you combine variable declarations with the structure definition.
  

select, poll or epoll

For very small numbers of sockets (varies depending on your hardware, of course, but we're talking about something on the order of 10 or fewer), select can beat epoll in memory usage and runtime speed. Of course, for such small numbers of sockets, both mechanisms are so fast that you don't really care about this difference in the vast majority of cases.

One clarification, though. Both select and epoll scale linearly. A big difference, though, is that the userspace-facing APIs have complexities that are based on different things. The cost of a select call goes roughly with the value of the highest numbered file descriptor you pass it. If you select on a single fd, 100, then that's roughly twice as expensive as selecting on a single fd, 50. Adding more fds below the highest isn't quite free, so it's a little more complicated than this in practice, but this is a good first approximation for most implementations.

The cost of epoll is closer to the number of file descriptors that actually have events on them. If you're monitoring 200 file descriptors, but only 100 of them have events on them, then you're (very roughly) only paying for those 100 active file descriptors. This is where epoll tends to offer one of its major advantages over select. If you have a thousand clients that are mostly idle, then when you use select you're still paying for all one thousand of them. However, with epoll, it's like you've only got a few - you're only paying for the ones that are active at any given time.

All this means that epoll will lead to less CPU usage for most workloads. As far as memory usage goes, it's a bit of a toss up. select does manage to represent all the necessary information in a highly compact way (one bit per file descriptor). And the FD_SETSIZE (typically 1024) limitation on how many file descriptors you can use with select means that you'll never spend more than 128 bytes for each of the three fd sets you can use with select (read, write, exception). Compared to those 384 bytes max, epoll is sort of a pig. Each file descriptor is represented by a multi-byte structure. However, in absolute terms, it's still not going to use much memory. You can represent a huge number of file descriptors in a few dozen kilobytes (roughly 20k per 1000 file descriptors, I think). And you can also throw in the fact that you have to spend all 384 of those bytes with select if you only want to monitor one file descriptor but its value happens to be 1024, wheras with epoll you'd only spend 20 bytes. Still, all these numbers are pretty small, so it doesn't make much difference.

And there's also that other benefit of epoll, which perhaps you're already aware of, that it is not limited to FD_SETSIZE file descriptors. You can use it to monitor as many file descriptors as you have. And if you only have one file descriptor, but its value is greater than FD_SETSIZE, epoll works with that too, butselect does not.

Randomly, I've also recently discovered one slight drawback to epoll as compared to select orpoll. While none of these three APIs supports normal files (ie, files on a file system), select andpoll present this lack of support as reporting such descriptors as always readable and always writeable. This makes them unsuitable for any meaningful kind of non-blocking filesystem I/O, a program which uses select or poll and happens to encounter a file descriptor from the filesystem will at least continue to operate (or if it fails, it won't be because of select or poll), albeit it perhaps not with the best performance.

On the other hand, epoll will fail fast with an error (EPERM, apparently) when asked to monitor such a file descriptor. Strictly speaking, this is hardly incorrect. It's merely signalling its lack of support in an explicit way. Normally I would applaud explicit failure conditions, but this one is undocumented (as far as I can tell) and results in a completely broken application, rather than one which merely operates with potentially degraded performance.

In practice, the only place I've seen this come up is when interacting with stdio. A user might redirect stdin or stdout from/to a normal file. Whereas previously stdin and stdout would have been a pipe -- supported by epoll just fine -- it then becomes a normal file and epoll fails loudly, breaking the application.

oprofile

Profiling code to find performance bottlenecks is a relatively common operation. My goal here isn’t to give you a detailed understanding of OProfile. I just want to convey to you that it’s incredibly easy to use and extremely powerful. If you don’t know much about profiling, or use only gprof because it’s the only profiler you know, please read on.
OProfile is a system-profiler for the Linux platform that has been my absolute favorite tool for profiling code. I have no idea why it’s not more popular or so unknown (maybe I just don’t run in the right circles). OProfile does have somewhat onerous setup requirements but it has become standard fair for many distributions that now have excellent support for it. It’s become substantially easier to get set up over the past few iterations of my favorite distributions (why am I lying? I only really use Ubuntu… but it’s still true!). For many distributions, it’s become trivial to setup and use. It should be a standard part of any Linux developer’s toolkit. (Windows and Mac developers have similar tools that work on similar principles: V-Tune and Shark.)
The most commonly used profiler is gprof. Most programmers tend to know about gprof and can probably profile something given enough googling. In my opinion, given the choice, OProfile is a far superior tool. I’d like to first discuss the primary differences between profilers like gprof and profilers like OProfile. If you happen to be a gprof ninja and notice any mistakes, please let me know. Hopefully, though, I can convince you that OProfile is both technically superior and easier to use.

OProfile vs gprof

The Inner Workings

Both OProfile and gprof work based on a statistical sampling method. They periodically poke into your program(s), figure out what code is currently being called, and increment the counter for that symbol. If you let this run long enough, with a high enough sample rate, and you’ll get a pretty accurate distribution of how the code works. The primary difference, however, between OProfile and gprof, is what triggers these samples.
Gprof uses a special system call that will periodically sample the currently running process only. This means gprof will only be aware of things that happen in “user time” for your process. You will not see bottlenecks that occur in external shared libraries (like libc) or the kernel. This can result in gprof’s results being very skewed for certain types of bottlenecks (page faults, file i/o, memory fragmentation, etc.).
If you are using gprof and the ‘time’ command doesn’t agree with gprof’s cumulative total time, you’ve likely hit this limitation.
OProfile, on the other hand, is a system-wide profiler that triggers on hardware events and will record not only all of the current symbols being executed but also which process they belong to. This means OProfile sees all. If your code is causing a major bottleneck in the kernel or in libc, OProfile will see it and gprof will not. The downside of this kind of omniscience is that OProfile requires special permissions. Typically, this means the sudo password. If you are doing computational optimization, this is usually not a problem.

Call Graphs

Gprof requires code be built with the -pg flag. This instruments the actual code with information that will help build an accurate call graph. The upside here is you get your call graph and you also have cumulative timings (how much time did we spend inside this function, and all of its children functions). The downside is that you have to instrument your code and you also need to recompile it with special flags. There’s two issues here that are worth noting. First, the -pg flag can interfere with other flags (like -fomit-frame-pointer). This can make certain bits of code no longer compile or work correctly (for example, inline assembly). Second, adding instrumentation to the code can cause fundamental changes. There is a Heisenberg effect that by trying to measure your code, you affect its true performance.
OProfile, on the other hand, requires no instrumentation of the code. This means OProfile does not need your code to be recompiled with any special flags (so long as the binary in question hasn’t had the symbols stripped). Since OProfile’s only source of information is the hardware-based event sampling, it doesn’t have any real information about call graphs. OProfile is able to build “statistical” call graphs where it can make guesses about which functions are calling which. This typically requires some interpretation on your part to fully decipher. If you need an accurate call graph, OProfile might not be the best tool.

Multithreaded Code

I have no idea if this issue is resolved in gprof yet but gprof does not (or, at least, did not) support multithreaded code. Oprofile does.

Summary

OProfile pros:

1. Supports hardware based events (more than just CPU clock cycles: cache misses, etc.)
2. Supports multi-threaded code.
3. Sees all processes and will find bottlenecks in other places (like kernel and libc).
4. Does not require any special compilation flags, or even recompiled code.

Cons:

1. Requires root access
2. Requires kernel support
3. Does not provide (precise) call graphs nor cumulative timings
4. Not portable (Linux only)

Setting Up OProfile

Most popular distributions have an OProfile package that can be easily installed. The only caveat is that some distribution flavors come with kernels that don’t have OProfile support built in. This means you’ll need a new kernel (they might offer an alternate in their package system, or else you will have to… compile it yourself… gah). I’ve found over the last few years many of the most popular distributions are shipping with kernels that support OProfile. Ubuntu, for example, has for awhile (while the server version, I believe, does not).
Installing the tool is usually fairly trivial (vanilla Ubuntu users need only: sudo apt-get install oprofile). Once installed the only setup required is:

sudo opcontrol --no-vmlinux

This tells OProfile that you do not have an uncompressed binary of your kernel (your vmlinux file). This means that OProfile will assign all kernel samples to a black-box called “no-vmlinux”. If you see “no-vmlinux” high on the charts, you will know you are having bottlenecks inside the kernel. You can peer into the kernel by telling OProfile where your vmlinux for the kernel can be found. If you build your own kernel, you should already know what to do. By default, however, most distributions ship with only a compressed kernel (vmlinuz). Typically, there is a package that you can download that will also give you an uncompressed version of the kernel. For example, Ubuntu (Hardy Heron) calls it linux-image-debug-{version}. If you install that package, it will put a vmlinux file in /boot/. If you point oprofile to that file, you will be able to get a breakdown of what is happening inside your kernel.
Usually, by default, your system’s prebuilt binaries are stripped of their symbols. This means that all of these applications and libraries will be black boxes to OProfile as well. If, for whatever reason, a particular program seems to be bottlenecked in libc for example, and you want the profiler to break down whats happening in libc, you will need to install the version of libc that contains symbols (look for the -dbg package). Furthermore, if you want to profile some pre-built binary, you will need a version without the symbols stripped out.

Using OProfile

It’s really this simple:

sudo opcontrol --reset
sudo opcontrol --start
./run_my_code
sudo opcontrol --shutdown
opreport -lt1

Those are petty much all of the commands you need to know to use oprofile. You reset and start the profiler, run your code, and then shut it down. The final step is viewing the results. The opreport command in my example has taken two flags. The -l flag shows you inside each process (otherwise you will get just an overview of each process and its respective usage of the system resources). The -t1 flag sets a threshold at 1% so you don’t see every symbol.

Advanced Beginner Usage

Cache Misses

On x86 machines, it’s also fairly easy to track cache misses using OProfile. By default, OProfile tracks CPU_CLK_UNHALTED hardware events. This is really a measure of how long your code takes to run. You can change the hardware event (sudo opcontrol –list-events to see all the other options). In particular, you can switch to the L2_REQUESTS event with a mask that includes only ‘INVALID’ requests. This requires a bit of internet searching, or the Intel optimization manuals. I’ve gone ahead and looked it up for you, though:

sudo opcontrol --event=L2_RQSTS:1000:0xf1

Events are specified in this way with the first number being the count (how many of these events cause a sample to occur, lower is better but requires more overhead). The second number is the unit mask. In this case, the 0xF1 means across all CPUs, but only INVALID L2_RQSTS.

WTF moments

Have you ever built in some complicated new package and aren’t getting results you think you should be? If you are anything like me your first thought is “Am I even running the new code?”. Maybe you open your editor, dig down, and drop in a few printf()s to figure out if you are even calling the new super fantastic function. This obviously isn’t the smartest way to do this. OProfile solves this problem trivially by letting you sample any compiled code. You can just fire up the profiler and actually look at all the symbols that were caught by the profiler. This is usually the fastest way to figure out if the code you wanted to be called is being called.

Default constructors? Don't rely on it, there is no free lunch

C++ provides the following 4 functions if you don't provide one:

• Constructor
• Copy constructor
• Destructor
• Assignment operator

Most time, we think we can use these default constructors and no need to type our own. Since it is free, why not?

But sometimes, depending on the compiler, it may surprise you.  For example, for the following class:

struct Foo
{
    enum Enum
    {
       SIZE = 1024;
     }

 
     char m_buf[SIZE];
};


Is it any different from the following implementation?  Where we just provide a default constructor which does nothing.

struct Foo
{
    Foo()
    {}

    ~Foo()
     {}

    enum Enum
    {
       SIZE = 1024;
     }
 
     char m_buf[SIZE];
};

If you think they are same, you are wrong.  I am not sure whether it is a gcc bug or a C++ feature, but I tried both g++3.4.6 and g++ 4.1.2, the first implementation (without providing the constructor),  it is much much slower than the 2nd version.

If you just do a new, for the first implementation, it can take more than 100ns, and can grow to 300ns if the SIZE becomes 4096;
For the 2nd implementation,  it only take about 40ns, regardless of the size, e.g., either 2 bytes, or 4096 bytes.

From the assembler code, it looks the default constructor does some  memset, while the 2nd one does nothing,  really a surprise.