Provide a condition variable with zero-overhead performance penality

[maxim.yegorushkin@…]

In boost versions prior to 1.45 condition_variable was a zero-overhead thin wrapper over pthread_cond_t.

In version 1.45 an internal mutex was added to condition_variable to improve thread cancellation support as described elsewhere (can't add the link to gmane archive because Trac thinks it's spam).

Since version 1.45 calling condition_variable::wait*() and condition_variable::notify*() lock the internal mutex. Doing so causes performance regressions for latency sensitive applications that don't use thread cancellation. To put it in other words, condition_variable was essentially turned into condition_variable_any.

Could the old version of condition_variable be added back please?

A good idea seems to be requiring a macro, for example BOOST_THREADS_REQUIRE_THREAD_CANCELLATION, to be defined for condition_variable to include the internal mutex or be an alias for condition_variable_any. A call to thread::interrupt() would fail at compile time if BOOST_THREADS_REQUIRE_THREAD_CANCELLATION is not defined. Things may get more complicated if any compiled boost libraries use condition_variable though.

[viboes]

Replying to maxim.yegorushkin@…:

In boost versions prior to 1.45 condition_variable was a zero-overhead thin wrapper over pthread_cond_t.

In version 1.45 an internal mutex was added to condition_variable to improve thread cancellation support as described elsewhere (can't add the link to gmane archive because Trac thinks it's spam).

Since version 1.45 calling condition_variable::wait*() and condition_variable::notify*() lock the internal mutex. Doing so causes performance regressions for latency sensitive applications that don't use thread cancellation. To put it in other words, condition_variable was essentially turned into condition_variable_any.

Could the old version of condition_variable be added back please?

As Anthony explained in the link you mention, we can not do that without breaking existing code. I don't know if defining an additional basic_condition_variable will respond to you expectations?

In any case, I don't see as a bug, except if you can find in the documentation a reference to the zero-overhead.

A good idea seems to be requiring a macro, for example BOOST_THREADS_REQUIRE_THREAD_CANCELLATION, to be defined for condition_variable to include the internal mutex or be an alias for condition_variable_any. A call to thread::interrupt() would fail at compile time if BOOST_THREADS_REQUIRE_THREAD_CANCELLATION is not defined. Things may get more complicated if any compiled boost libraries use condition_variable though.

Well this is a different feature that should merit a specific ticket.

[viboes]

Hi, I have started to implement in trunk #7594 Allow to disable thread interruptions. I need to make some tests, but please, could you check if this will work for you.

[maxim.yegorushkin@…]

I can't comment on the actual code changes since I am not familiar well enough with all the internals (the threads library has grown quite significantly over the years).

Do I correctly understand that the users should define BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS macro when compiling boost and using the headers? If so, I couldn't ask for more. Thanks a lot.

[viboes]

Replying to maxim.yegorushkin@…:

I can't comment on the actual code changes since I am not familiar well enough with all the internals (the threads library has grown quite significantly over the years).

Do I correctly understand that the users should define BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS macro when compiling boost and using the headers? If so, I couldn't ask for more. Thanks a lot.

Could you check if this works for you in trunk?

[maxim.yegorushkin@…]

boost build log

[maxim.yegorushkin@…]

I checked out trunk and tried building it.

It builds fine when BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is not defined.

When BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is defined boost fails to compile. Please see the earlier attached build log.

[maxim.yegorushkin@…]

Patch to fix the build when macro BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is defined.

[maxim.yegorushkin@…]

I managed to successfully build boost from trunk with macro BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS defined.

When running tests from boost_trunk/libs/thread/test by invoking b2 in this directory it runs tests and they seem to freeze. I may be invoking the tests incorrectly. How do you run tests please?

I also re-built my proprietary applications against this version of boost and ran unit tests that passed. They do use boost::condition_variable internally, but obviously they don't stress test it.

[viboes]

I'm passing the regression test and there are some issues, between others it is needed to lock in the internal mutex

#if defined BOOST_THREAD_PROVIDES_INTERRUPTIONS
            //BOOST_THREAD_LOG << BOOST_THREAD_END_LOG;
            detail::interruption_checker check_for_interruption(&internal_mutex,&cond);
#else
            boost::pthread2::pthread_mutex_scoped_lock internal_lock2(&internal_mutex);
#endif

I will commit the fixes as soon as everything is OK.

[viboes]

I have added a patch to ticket #7594 that make it possible to use Boost.Thread defining BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS for the user files. No need to recompile the Thread library.

This doesn't provide a condition variable with zero-overhead performance penality, but it will be easier now to improve the performances.

HTH

[viboes]

It would be great if you could give some performances figures with and without interruptions so that we can see if something more is needed.

[maxim.yegorushkin@…]

Okay, I've made a little benchmark.

Is is a producer-consumer ping-pong benchmark. It aims to benchmark condition variables with and without thread cancellation support by comparing the time it took to complete the benchmark.

Condition variable with thread cancellation support is boost::condition_variable from boost-1.51. Without - std::condition_variable that comes with gcc-4.7.2.

One producer, one to CONSUMER_MAX consumers. The benchmark calls condition_variable::notify_all() without holding a mutex to maximize contention within this function. Each benchmark for a number of consumers is run three times and the best time is picked to get rid of outliers.

The results are reported for each benchmark for a number of consumers. The most important number is (std - boost) / std * 100. Positive numbers are when boost::condition_variable is faster, negative it is slower.

The test shows that boost::condition_variable is around 8% slower than std::condition_variable. I made plots but Trac doesn't allow to post links here.

I ran the benchmark on Fedora 17 with gcc-4.7.2 with real-time FIFO priority in init mode 3.

[maxim.yegorushkin@…]

The benchmark

[maxim.yegorushkin@…]

Compiler log for the benchmark

[maxim.yegorushkin@…]

The output of the benchmark on i870.

[viboes]

Thanks for this benchmark. Please, could you test with Boost.Thread defining BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS. I would expect a little improvement.

I will post my results on MacOS soon.

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Good idea, so I re-ran the benchmark on my Fedora 17 workstation with i7-3820. For these two runs I used boost trunk as of revision 81908. One run with the benchmark and boost built with -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS macro and one without.

(Forgot to mention that in addition to running the benchmark with real-time priority FIFO 99, I also disable CPU frequency scaling to prevent the CPU from shifting gears while benchmarking).

There is a noticeable 35% improvement in median run-time when macro BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is defined. (Note that I am not being overly scientific here because the analysis of variance is missing, i.e. I can't say I am 95% sure. However on the plot the effect of the macro is quite noticeable)

On the other hand, using boost mutex and condition_variable with BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS defined is still around 5% slower than when using the same primitives from std namespace. (Same caveat)

[Maxim Yegorushkin <maxim.yegorushkin@…>]

The path to the benchmark plot is /spreadsheet/ccc?key=0Ai_v0rSH1AXrdHl2RDN4UkFYNHZ2aXBUUk5VWmNfcXc

It is docs google com.

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Benchmark output on i3820 with boost-trunk

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Benchmark output on i3820 with boost-trunk and -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

Good idea, so I re-ran the benchmark on my Fedora 17 workstation with i7-3820. For these two runs I used boost trunk as of revision 81908. One run with the benchmark and boost built with -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS macro and one without.

Thanks.

(Forgot to mention that in addition to running the benchmark with real-time priority FIFO 99, I also disable CPU frequency scaling to prevent the CPU from shifting gears while benchmarking).

There is a noticeable 35% improvement in median run-time when macro BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is defined. (Note that I am not being overly scientific here because the analysis of variance is missing, i.e. I can't say I am 95% sure. However on the plot the effect of the macro is quite noticeable)

Glad to hear it. Could you run the test 10 times instead of 3 to reduce the variance?

On the other hand, using boost mutex and condition_variable with BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS defined is still around 5% slower than when using the same primitives from std namespace. (Same caveat)

I was sure that there would be other parts that need to be inspected :( I will try to see what I can do.

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

The path to the benchmark plot is /spreadsheet/ccc?key=0Ai_v0rSH1AXrdHl2RDN4UkFYNHZ2aXBUUk5VWmNfcXc

It is docs google com.

Why you can not add the web link?

[maxim.yegorushkin@…]

Trac considers external links spam and offers to confirm something. It is not clear what and how to confirm, could be that the message is truncated.

I should probably run another benchmark against the boost version before when the thread interruption was introduced to see how it compared to the std primitives at that time.

[viboes]

I have run the no-interruptions benchmark (modified to compile on MacOS) using clang-3.2 without setting any special conditions changing 3 parameters:

• CONSUMER_MAX: from 20 to 10
• test iterations: from 3 to 100
• shared_data iteration : from 100000 to 10000.

here are the results:

consumers,(std-boost)/std,std,boost
1,-5.063747,44009306,46237826
2,-1.764249,72169561,73442812
3,5.327530,94552244,89514945
4,0.767002,121827567,120893147
5,1.826591,141517038,138932100
6,0.471998,171223003,170414834
7,-0.937626,187902198,189664017
8,-0.840567,220015472,221864850
9,-3.291703,236884513,244682047
10,0.397024,272506100,271424186

I'm sure that the setting of your special condition would change these results. From these results, I don't see a loss of 5% of Boost respect to std. Please could you run the benchmark with these parameters ans your settings:

• running the benchmark with real-time priority FIFO 99,
• disable CPU frequency scaling to prevent the CPU from shifting gears while benchmarking

How do you do this?

[viboes]

Here are the results with gcc-4.7.2 for 200 test iterations

consumers,(std-boost)/std,std,boost
1,-8.720169,40772444,44327870
2,0.644605,71669162,71207179
3,0.793437,91792637,91064320
4,1.379378,119557914,117908759
5,1.398979,140016424,138057624
6,0.824572,164569134,163212143
7,-0.183305,180981210,181312957
8,3.389641,214427927,207159590
9,-2.147819,227430412,232315206
10,-1.823378,263367555,268169742

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Replying to viboes:

I have run the no-interruptions benchmark (modified to compile on MacOS) using clang-3.2 without setting any special conditions changing 3 parameters:

• CONSUMER_MAX: from 20 to 10
• test iterations: from 3 to 100
• shared_data iteration : from 100000 to 10000.

here are the results:

consumers,(std-boost)/std,std,boost
1,-5.063747,44009306,46237826
2,-1.764249,72169561,73442812
3,5.327530,94552244,89514945
4,0.767002,121827567,120893147
5,1.826591,141517038,138932100
6,0.471998,171223003,170414834
7,-0.937626,187902198,189664017
8,-0.840567,220015472,221864850
9,-3.291703,236884513,244682047
10,0.397024,272506100,271424186

This is quite different from what I observe.

What kind of implementation of std primitives does clang use? Is it from gnu standard C++ library (the same as g++)?

Also the difference may be due to a different process scheduler on Mac OS.

I'm sure that the setting of your special condition would change these results.

You are quite right. Running the benchmark with CPU frequency scaling turned on (the default) makes the results more noisy (increases variance). Running it with the standard scheduler priority also increases variance and make boost primitives perform even worse compared to std ones.

From these results, I don't see a loss of 5% of Boost respect to std. Please could you run the benchmark with these parameters ans your settings:

I ran it with your settings (10 consumers max, 100 repetitions, 10000 iterations) and it didn't change the normalized numbers for me.

• running the benchmark with real-time priority FIFO 99,
• disable CPU frequency scaling to prevent the CPU from shifting gears while benchmarking

How do you do this?

To run it with maximum real-time priority I invoked the benchmark as chrt -f 99 <benchmark>. Depending on your OS settings you may need special privileges to be able to use real-time priorities.

On Linux CPU frequency scaling can be disabled by doing:

for f in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor; do
    echo performance > $f
done

Not sure how it is done on Mac OS.

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

Replying to viboes:

I have run the no-interruptions benchmark (modified to compile on MacOS) using clang-3.2 without setting any special conditions changing 3 parameters:

• CONSUMER_MAX: from 20 to 10
• test iterations: from 3 to 100
• shared_data iteration : from 100000 to 10000.

here are the results:

consumers,(std-boost)/std,std,boost
1,-5.063747,44009306,46237826
2,-1.764249,72169561,73442812
3,5.327530,94552244,89514945
4,0.767002,121827567,120893147
5,1.826591,141517038,138932100
6,0.471998,171223003,170414834
7,-0.937626,187902198,189664017
8,-0.840567,220015472,221864850
9,-3.291703,236884513,244682047
10,0.397024,272506100,271424186

This is quite different from what I observe.

Note that this is similar to what I get for gcc-4.7.2. I will need to check the optimization flags.

What kind of implementation of std primitives does clang use? Is it from gnu standard C++ library (the same as g++)?

I use clang with libc++.

Also the difference may be due to a different process scheduler on Mac OS.

I'm sure that the setting of your special condition would change these results.

You are quite right. Running the benchmark with CPU frequency scaling turned on (the default) makes the results more noisy (increases variance). Running it with the standard scheduler priority also increases variance and make boost primitives perform even worse compared to std ones.

I will check these settings on ubuntu.

From these results, I don't see a loss of 5% of Boost respect to std. Please could you run the benchmark with these parameters ans your settings:

I ran it with your settings (10 consumers max, 100 repetitions, 10000 iterations) and it didn't change the normalized numbers for me.

Did you observe that there where less % with lower/high numbers? Could you post here your results?

• running the benchmark with real-time priority FIFO 99,
• disable CPU frequency scaling to prevent the CPU from shifting gears while benchmarking

How do you do this?

To run it with maximum real-time priority I invoked the benchmark as chrt -f 99 <benchmark>. Depending on your OS settings you may need special privileges to be able to use real-time priorities.

On Linux CPU frequency scaling can be disabled by doing:

for f in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor; do
    echo performance > $f
done

Not sure how it is done on Mac OS.

Thanks anyway.

[Maxim Yegorushkin <maxim.yegorushkin@…>]

To double check numbers I re-ran the benchmarks with boost-1.44 (the last version with no thread interruption support), trunk and trunk with -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS. It was run with your settings (10 consumers max, 100 repetitions, 10000 iterations) again, they seem to reduce variance well.

Median relative times compared to times of std primitives for the three variants respectively are -1.1273285%, -7.804532% and -4.0939795%. The link to plot is the same: /spreadsheet/ccc?key=0Ai_v0rSH1AXrdHl2RDN4UkFYNHZ2aXBUUk5VWmNfcXc on docs.google.com.

The benchmark was compiled with gcc-4.7.2, optimization flags are "-O3 -march=native", Fedora 17 and Intel Core i7-3820 CPU.

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

To double check numbers I re-ran the benchmarks with boost-1.44 (the last version with no thread interruption support), trunk and trunk with -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS. It was run with your settings (10 consumers max, 100 repetitions, 10000 iterations) again, they seem to reduce variance well.

Median relative times compared to times of std primitives for the three variants respectively are -1.1273285%, -7.804532% and -4.0939795%. The link to plot is the same: /spreadsheet/ccc?key=0Ai_v0rSH1AXrdHl2RDN4UkFYNHZ2aXBUUk5VWmNfcXc on docs.google.com.

Thanks for all these figures. I suspect that you mean boost-1.34, isn't it? I think that I have an hint for a possible performance improvement. The implementation since 1.35 is using an additional mutex which I need to see if it can be removed when interruptions are not provided.

pthread_mutex_t internal_mutex;

[Maxim Yegorushkin <maxim.yegorushkin@…>]

I suspect that you mean boost-1.34, isn't it?

Well, it was definitely boost-1.44, because I wanted to test a version just before thread interruption support was introduced in boost-1.45.

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

I suspect that you mean boost-1.34, isn't it?

Well, it was definitely boost-1.44, because I wanted to test a version just before thread interruption support was introduced in boost-1.45.

I'm seen them introduced in 1.35 "http://www.boost.org/doc/libs/1_35_0/doc/html/thread/thread_management.html#thread.thread_management.this_thread"

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Replying to viboes:

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

I suspect that you mean boost-1.34, isn't it?

Well, it was definitely boost-1.44, because I wanted to test a version just before thread interruption support was introduced in boost-1.45.

I'm seen them introduced in 1.35 "http://www.boost.org/doc/libs/1_35_0/doc/html/thread/thread_management.html#thread.thread_management.this_thread"

Oh, I see.

The critical point was when condition_variable became essentially condition_variable_any, and, if I understand correctly, that happened in boost-1.45.

[viboes]

Hi,

I have reached to improve the performances by removing the internal_mutex (see the attached patch). Here they are the results for clang-3.2:

consumers,(std-boost)/std,std,boost
1,3.163455,442899995,428889051
2,0.416842,736341309,733271929
3,1.203291,941092107,929768034
4,-0.029287,1217358160,1217714683
5,0.896356,1422949963,1410195269
6,0.315211,1734865379,1729396900
7,1.033687,1882941043,1863477335
8,-0.355615,2217150537,2225035057
9,1.051769,2378341849,2353327192
10,0.500550,2721524297,2707901713

I suspect that I have no compiled the library libc++ in release mode :(

Please, could you give a try to this patch?

[Maxim Yegorushkin <maxim.yegorushkin@…>]

With this patch boost::condition_variable performs better than std one in the benchmark:

consumers,(std-boost)/std,std,boost
1,1.738797,17452356,17148895
2,0.818735,26905168,26684886
3,0.909335,58318561,57788250
4,0.929148,45236280,44815968
5,1.255012,54510018,53825911
6,1.410902,63880220,62978933
7,1.094065,72988694,72190150
8,1.073388,82271239,81388149
9,0.915663,91362805,90526230
10,0.991684,100724122,99725257

(I also updated that spreadsheet on docs.google.com)

Nicely done!

In the patch condition_variable always has internal_mutex member, is it intended?

[viboes]

Replying to Maxim Yegorushkin <maxim.yegorushkin@…>:

With this patch boost::condition_variable performs better than std one in the benchmark:

consumers,(std-boost)/std,std,boost
1,1.738797,17452356,17148895
2,0.818735,26905168,26684886
3,0.909335,58318561,57788250
4,0.929148,45236280,44815968
5,1.255012,54510018,53825911
6,1.410902,63880220,62978933
7,1.094065,72988694,72190150
8,1.073388,82271239,81388149
9,0.915663,91362805,90526230
10,0.991684,100724122,99725257

(I also updated that spreadsheet on docs.google.com)

Nicely done!

Glad to see these nice figures ;-)

In the patch condition_variable always has internal_mutex member, is it intended?

No. I left it to preserve the layout of condition_variable in case I reach to be able to have a single library able to manage with both configurations, but it needs a lot of changes. So for the time been, users will need a build the library with -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS and internal_mutex will not be defined.

I appreciate a lot this long walk co-working with you to achieve these results, that I hope are good enough for your application.

I will commit it as soon as all the regression test pass and I hope I would be able to merge it the release 1.53.

[viboes]

Committed revision [82094].

[Maxim Yegorushkin <maxim.yegorushkin@…>]

Benchmarks on the plot

[viboes]

Committed merge from trunk [82159].