Boost C++ Libraries: Ticket #7422: Provide a condition variable with zero-overhead performance penality

viboes — Wed, 26 Sep 2012 19:05:06 GMT

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.

owner, status changed

viboes — Wed, 26 Sep 2012 19:06:14 GMT

owner changed from Anthony Williams to viboes
status new → assigned

type, summary changed

viboes — Sat, 29 Sep 2012 18:41:37 GMT

type Bugs → Feature Requests
summary condition_variable performance regression → Provide a condition variable with zero-overhead performance penality

cc changed

viboes — Mon, 05 Nov 2012 01:21:57 GMT

cc viboes added

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@… — Mon, 05 Nov 2012 17:40:08 GMT

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 — Sat, 01 Dec 2012 11:51:39 GMT

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?

attachment set

maxim.yegorushkin@… — Sat, 01 Dec 2012 13:58:37 GMT

attachment → build.log.bz2

boost build log

maxim.yegorushkin@… — Sat, 01 Dec 2012 14:00:05 GMT

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.

attachment set

maxim.yegorushkin@… — Sat, 01 Dec 2012 14:13:49 GMT

attachment → build.patch

Patch to fix the build when macro BOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS is defined.

maxim.yegorushkin@… — Sat, 01 Dec 2012 16:52:27 GMT

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 — Sat, 01 Dec 2012 19:11:00 GMT

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 — Sat, 01 Dec 2012 22:54:49 GMT

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 — Sat, 08 Dec 2012 13:47:57 GMT

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@… — Thu, 13 Dec 2012 13:41:41 GMT

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.

attachment set

maxim.yegorushkin@… — Thu, 13 Dec 2012 13:42:37 GMT

attachment → test.cc

The benchmark

attachment set

maxim.yegorushkin@… — Thu, 13 Dec 2012 13:43:11 GMT

attachment → ping-pong-compilation.log

Compiler log for the benchmark

attachment set

maxim.yegorushkin@… — Thu, 13 Dec 2012 13:44:13 GMT

attachment → ping-pong-i870.txt

The output of the benchmark on i870.

viboes — Thu, 13 Dec 2012 15:05:35 GMT

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.

Thu, 13 Dec 2012 20:55:07 GMT

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)

Thu, 13 Dec 2012 20:58:44 GMT

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

It is docs google com.

attachment set

Thu, 13 Dec 2012 21:09:03 GMT

attachment → ping-pong-i3820.txt

Benchmark output on i3820 with boost-trunk

attachment set

Thu, 13 Dec 2012 21:09:39 GMT

attachment → ping-pong-i3820-no-interruptions.txt

Benchmark output on i3820 with boost-trunk and -DBOOST_THREAD_DONT_PROVIDE_INTERRUPTIONS

viboes — Thu, 13 Dec 2012 21:14:56 GMT

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 — Thu, 13 Dec 2012 21:15:41 GMT

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@… — Thu, 13 Dec 2012 23:04:34 GMT

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 — Fri, 14 Dec 2012 07:40:52 GMT

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 — Fri, 14 Dec 2012 08:03:00 GMT

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

Fri, 14 Dec 2012 10:02:34 GMT

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 — Sat, 15 Dec 2012 08:25:33 GMT

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.

Mon, 17 Dec 2012 21:11:30 GMT

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.

attachment set

Mon, 17 Dec 2012 21:12:02 GMT

attachment → ping-ping-boost-1.44.log

attachment set

Mon, 17 Dec 2012 21:12:19 GMT

attachment → ping-ping-boost-trunk.log

attachment set

Mon, 17 Dec 2012 21:12:30 GMT

attachment → ping-ping-boost-trunk-ni.log

viboes — Mon, 17 Dec 2012 23:40:48 GMT

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;

Tue, 18 Dec 2012 08:09:55 GMT

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 — Tue, 18 Dec 2012 12:45:46 GMT

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"

Tue, 18 Dec 2012 13:29:21 GMT

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 — Tue, 18 Dec 2012 16:24:43 GMT

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?

attachment set

viboes — Tue, 18 Dec 2012 16:25:31 GMT

attachment → 7422_trunk.patch

Tue, 18 Dec 2012 20:03:51 GMT

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 — Tue, 18 Dec 2012 21:26:58 GMT

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 — Wed, 19 Dec 2012 10:52:49 GMT

Committed revision [82094].

milestone changed

viboes — Wed, 19 Dec 2012 11:13:40 GMT

milestone To Be Determined → Boost 1.53.0

attachment set

Wed, 19 Dec 2012 11:36:22 GMT

attachment → chart1.png

Benchmarks on the plot

status changed; resolution set

viboes — Fri, 21 Dec 2012 22:17:05 GMT

status assigned → closed
resolution → fixed

Committed merge from trunk [82159].