C++ Programming: False Sharing in Multi-threaded Programming, and a Glance at the C++0x std::thread

A glance of C++0x std::thread
False Sharing and Benchmark
Some other thoughts, helpful resources

A glance of C++0x std::thread

One of the major changes with the new C++ Standard is the support of concurrency ---- the new C++ thread library, std::thread. It is said [1] that the library is heavily based upon the existing Boost thread library, many classes and data structures share the same name with the corresponding ones in Boost. One particularly important benefit of using std::thread is the Resource Acquisition Is Initialization (RAII) design, such like the locks: std::lock_guard, std::unique_lock, etc, to ensure that mutexes are unlocked when the current scope is exited. The library efficiency, abstraction penalty, atomic operation, etc, all have been taken care of. For more information, http://www.stdthread.co.uk/doc/ can be a helpful resource.

In this article, I will use the following classes, template classes, and member functions:

std::thread

std::mutex

std::condition_variable

std::unique_lock

std::thread::detach()

condition_variable::notify_one()

condition_variable::wait()

False sharing, examples and benchmark

Processor caches handle blocks of memory called cache lines rather than individual memory locations. Because of this cache-line-sized blocks of memory making of the fundamental units that the Processor caches handle, small size data items in adjacent memory locations will be in the same cache line. Thus if data items in a cache line are independently processed by different threads, the cache hardware will have to play "cache ping pong". e.g. the cache line is shared by multi processors, and this is called "false sharing" because even the data are processed independently by different processors, the processors have to access the same cache line in turn. This "false sharing" effect can significantly slow down multi-threading execution as we will see in the following example. One solution is structure the data so that data items that are to be accessed by separating threads are far away from each other in cache-line-sized blocks, and the data items more likely to be stored in separate cache lines. As a result, the data process and cache lines access are all independent, and true multi-threading can be achieved.

The following snippet of code illustrates:

A bad designed data structure leads to false sharing. i.e. in class Shared_Work, data n1 and n2 are placed next to each other and most likely are in the same cache line.

An optimized data structure improves the efficiency significantly. A chunk of size 64* char is placed in between n1 and n2 to separate them.

Comparison of the two is shown. Several non-trivial loops run long enough to distinguish the difference between "false sharing case" and "optimized case".

Environment:,Memory 2.0GiB, 2 cores: Processor 0: Intel(R) Pentium(R) 4 CPU 3.00GHz, Processor 1: Intel(R) Pentium(R) 4 CPU 3.00GHz.

To compile: g++ -O0 -Wall -std=c++0x -pthread falsesharing.cpp .

Here -std=c++0x is for the std::thread library and -pthread must be linked.

#include <thread>
#include <iostream>
#include <ctime>
#include <memory>

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

const double M=8e8;

//Shared_Work holds the work need to be done
//part1() and part2() separates the work half-and-half
//n1 and n2 are data items
//chunk[64] is the separation attempt.
class Shared_Work {
public:
    Shared_Work():n1(1),n2(1),flag1(0),flag2(0) {}

    void part1() {
        for(; n1<M; n1+=n1%3);
        flag1=1;
        cond.notify_one();
    }

    void part2() {
        for(; n2<M; n2+=n2%3);
        flag2=1;
        cond.notify_one();
    }

    long int result() {
        std::unique_lock<std::mutex> lk(mt);
        while(flag1==0||flag2==0)
            cond.wait(lk);
        return n1+n2;
    }

private:
    std::mutex mt;
    std::condition_variable cond;
    long int n1;
    //char chuck[64];//cache line seperation
    long int n2;
    bool flag1;
    bool flag2;
};

//a template class for generating threads with different member functions
//"action _fptr" will be instantiated by &Shared_Work::part1 and part2.
template<class T>
class Do_Work {
public:
    typedef void (T::*action)();
    Do_Work(std::shared_ptr<Shared_Work>& x, action y):_p(x),_fptr(y) {}
    void operator()() {
        (*_p.*_fptr)();
    }
private:
    std::shared_ptr<Shared_Work> _p;
    action _fptr;
};

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



time_t start, end;
double diff;

int main(int argc, char* argv[]) {

    std::shared_ptr<Shared_Work> p(new Shared_Work);
    Do_Work<Shared_Work> d1(p, &Shared_Work::part1);
    Do_Work<Shared_Work> d2(p, &Shared_Work::part2);

    time(&start);
    std::thread t1( d1 );
    std::thread t2( d2 );
    t1.detach();//release the ownership to C++ runtime library.
    t2.detach();//release the ownership to C++ runtime library.
    cout<<p->result()<<endl;
    time(&end);
    diff=difftime(end, start);
    cout<<diff<<" seconds elapsed for 2 threads calculation."<<endl;

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

}

The cache-line-sized blocks memory are typically 32 or 64 bytes in size, so the chunk is set to be: Shared_Work::chunk[64]. First, the "char chunk[64]" line is commented out. The running result is shown in the following figure. As can be seen, the multi-threading performance (41 seconds) now is far more inefficient than single threading (10 seconds). Although the processors are running to their most, false sharing induced cache ping pong introduces significant amount of redundant instructions. Now let's add "char chunk[64]" to the code and the result is shown in the following figure. Now, multi-threading consume 8 seconds and single threading consumes 10 seconds. We get 20% improvement using multi-threading! And because now the chuck[64] separates the data n1 and n2.

Some other thoughts, helpful resources

1. If the -O3 is turned on in g++, it seems to me that the chunk[64] is not needed and compiler can place the n1 and n2 in different cache line automatically.

2. If n1 and n2 are not int, but double, and the operations such like "n1%3"are changed to "(long long int) n1%3", then the multi-threading performance is going to be almost twice as fast as single threading case. My guess is that the cpu will bind the calculation more tightly in this case and "cpu affinity" [2] can play a key role now.

3. It seems there is no " semophore" in std::thread and I asked Anthony Williams who is the author of the c++ thread library. Here is his reply: "A semaphore is a low-level, multi-purpose synchronization tool. As such it is hard to use correctly. The C++ thread library does not provide a semaphore. Instead it provides the things you would build with semaphores --- mutexes, condition variables and futures. "

4. For more information, you can go to

http://www.stdthread.co.uk/

http://www.justsoftwaresolutions.co.uk/publications.html or register to be Anthony's blog reader at:

http://www.justsoftwaresolutions.co.uk/2010/07/

Reference:

[1]http://www.stdthread.co.uk/

[2]http://www.linuxjournal.com/article/6799

Addendum:

to time the time consumption, clock() is not used here. Because clock() will count the cpu ticks and not the real time. In multi-core case, clock() will count all cpu ticks and thus not a good candidate to do real world timing. If more precise timing is needed, the timer function has to be carefully picked for particular operation systems, but the C++ standard library, so far as i know, doesn't provide a universal one that can count to millisecond.



About the Author

Botao Jia

Botao Jia is currently a graduate student in the PhD program at Duke University (USA) physics department. One of his research project was to develop a simulation package for Duke SRFEL. He finished a physics bachelor degree and a computer science bachelor degree at University of Science and Technology of China (USTC). He also has a Master of Science degree at Duke University statistical science department. He is preparing to finish his PhD in the year of 2011. His physics research related publications can be found at: http://prst-ab.aps.org/abstract/PRSTAB/v13/i6/e060701 and at: http://prst-ab.aps.org/abstract/PRSTAB/v13/i8/e080702

Comments

  • Alle topkwaliteit door Dr Dre koptelefoon

    Posted by mrswanzi on 06/06/2013 05:10pm

    [url=http://koptelefoon-monsterbeats.weebly.com/]beats by dre[/url] Wij raden je aan om bij een van de onderstaande webshops te bestellen. Bij deze shops weet je zeker dat je vertrouwd je Beats kunt kopen met een goede prijs, snelle verzending en goede garantie. Geniet volledig in stijl en draadloos van je favoriete muziek met de Beats by Dr. Dre Wireless [url=http://koptelefoon-monsterbeats.cabanova.com/]beats by dre[/url] Wij raden je aan om bij een van de onderstaande webshops te bestellen. Bij deze shops weet je zeker dat je vertrouwd je Beats kunt kopen met een goede prijs, snelle verzending en goede garantie. Geniet volledig in stijl en draadloos van je favoriete muziek met de Beats by Dr. Dre Wireless [url=http://koptelefoon-monsterbeats.weebly.com/]beats by dre kopen[/url] Het toestel komtondersteunt zowel Bluetooth als NFC en komt met ingebouwde microfoon, zodat je je telefoongesprekken via het toestel kan voeren. Naast de Executive lanceert Beats ook een draagbare muziekspeler: de Beats Pill. Die kreeg zijn naam dankzij zijn langwerpige, afgeronde vorm. Beat by dre hoofdtelefoons hebben iets speciaals. De meeste muziek producers en artiesten steken veel moeite in hun opnamesessies om hun sound te perfectioneren. Helaas zullen deze geluiden het grootste deel van de tijd hun luisteraars nooit bereiken, dit komt door de lage kwaliteits koptelefoons die worden gebruikt door de luisteraars.

    Reply
  • You crave some tomato basil and mozzarella. In favour of indoor from, these slippers are as phosphorescence and manueverable as sneakers.

    Posted by Soaceddew on 04/25/2013 06:41am

    Has upright released respective chic color Democratic Inneva Woven shoes, Nike recently with another direction to bring shoes with distinguishable styling to all [url=http://markwarren.org.uk/goodbuy.cfm]nike free[/url] eyes. This brings steadfast issue Free Inneva Woven is a White Label of works in the series, represents shoes Italian made the assurance. Latest Free Inneva Woven jet and bawdy are on tap in two color schemes, to hand-knit Woven vamp in summing-up to infiltrated Italy's [url=http://fossilsdirect.co.uk/glossarey.cfm]nike huarache free[/url] finest crafts, meanwhile gives athletes closed to the foot of ease, the most consequential possibility a affairs is the outclass of Unused 5 configuration, barefoot be aware it desire allure cannot be ignored. Nike Free Inneva Woven SP Pale-complexioned Characterization Compact on Parade 16 at outlets about the [url=http://turbo-vac.co.uk/components_13.cfm]nike free 4.0 v2[/url] trade-mark on the shelves, and on trade in minimal sort, interested friends should settle terminate ralame to Nike announced the news.

    Reply
  • Nike Draught Max+instagram, wishes you contain the color to be in on your feet!

    Posted by madytreathy on 04/21/2013 12:45am

    Remember in 2008, if not earlier, when Nike launched up ahead of the independent shoe color projects, the catchword "Shoot Your Colours", "Nike PhotoiD" scheme, [url=http://markwarren.org.uk/goodbuy.cfm]nike free run[/url] return has not been as avid as expected. Have in mind, 2008 Canon IXUS 80 IS Digital file card arcade but contrariwise 8 million pixels, Nokia, the facile phone superstore is the one governorship, NikeiD was boost to color in the photos as a basis quest of sneakers custom color, although provocative, but does provoke some. Instagram which communicate this article make sport and fundamental, Nike PHOTOiD homeopathic upgrade customization services, recently [url=http://markwarren.org.uk/goodbuy.cfm]nike free run[/url] released a fresh plan. That such iD can you appliance pictures as instagram account shoe color, little while put up Nike Mood Max shoes and Nike Air Max 1, Nike Feeling Max 90 953 options. Interested in children's shoes, you [url=http://markwarren.org.uk/goodbuy.cfm]nike free uk[/url] can ever vanish into thin air's proper website photoid.Nike.com, in beyond to browse other people's artistic industry, or you can make an effort to upload your own instagram photo, erect your own Nike Hauteur Max.

    Reply
  • You crave some tomato basil and mozzarella. To indoor utilization, these slippers are as be exposed and manueverable as sneakers.

    Posted by Soaceddew on 04/20/2013 04:21am

    Has honourable released several different color Let off Inneva Woven shoes, Nike recently with another direction to discuss shoes with distinguishable styling to all [url=http://northernroofing.co.uk/roofins.cfm]nike free run uk[/url] eyes. This brings special print run Unfastened Inneva Woven is a White Call of works in the series, represents shoes Italian made the assurance. Latest Allowed Inneva Woven swart and blue are on tap in two color schemes, to hand-knit Woven vamp in summing-up to infiltrated Italy's [url=http://markwarren.org.uk/property-waet.cfm]air max 90 uk[/url] finest crafts, for the moment gives athletes terminate to the foot of comfort, the most important opportunity is the outclass of Loose 5 configuration, barefoot consider it resolution give birth to cannot be ignored. Nike Free Inneva Woven SP White Identify Wedge on Parade 16 at outlets around the [url=http://northernroofing.co.uk/roofins.cfm]nike free[/url] trade-mark on the shelves, and on trade in narrow bearing, interested friends should produce results terminate notice to Nike announced the news.

    Reply
  • cheap hats

    Posted by xxds3aw on 04/01/2013 05:59am

    [url=http://bestbaseballcap.webs.com]wholesale baseball caps[/url] wholesale baseball caps m fvmd [url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks for sale[/url] cheap snapbacks for sale i aoyx[url=http://bestbaseballcap.webs.com]wholesale snapback caps[/url] wholesale snapback caps t pxhc[url=http://cheapsnapbackshat.webs.com]cheap snapbacks hats[/url] cheap snapbacks hats v bqzq[url=http://snapbackhatwholesale.webs.com]wholesale snapbacks[/url] wholesale snapbacks f xyca[url=http://wholesalefittedhat.webs.com]snapbacks wholesale[/url] snapbacks wholesale s qqpr [url=http://bestbaseballcap.webs.com]wholesale hats[/url] wholesale hats l qbzx [url=http://cheapsnapbackshat.webs.com]cheap hats online[/url] cheap hats online k dcpv[url=http://goodsnapbackhatscheap.webs.com]cheap snapbacks[/url] cheap snapbacks l awgd[url=http://snapbackswholesalezone.webs.com]snapbacks wholesale[/url] snapbacks wholesale o nqwy[url=http://snapbackswholesalezone.webs.com]fitted hats wholesale[/url] fitted hats wholesale a darv[url=http://cheapsnapbackshat.webs.com]cheap snapbacks hats[/url] cheap snapbacks hats x esrx [url=http://cheapsnapbackshat.webs.com]cheap snapbacks hats[/url] cheap snapbacks hats u fskn [url=http://cheapsnapbackshat.webs.com]cheap hats for sale[/url] cheap hats for sale v mjho[url=http://snapbackswholesalezone.webs.com]snapback hats wholesale[/url] snapback hats wholesale u yujl[url=http://wholesalefittedhat.webs.com]snapbacks wholesale[/url] snapbacks wholesale b ewmr[url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks online[/url] cheap snapbacks online b cfpb[url=http://wholesalefittedhat.webs.com]fitted hats wholesale[/url] fitted hats wholesale n brgl

    Reply
  • http://www.oakleysunglassesoutc.com/ ivawqg

    Posted by http://www.oakleysunglassesoutc.com/ Suttonkff on 03/29/2013 05:44am

    ghd,ghd hair straightener can responsibly say, the quantity of relief, no one can be more than Dr HO, although the specific amount has long been unknown, although Mr. Ho also never statistics this figure, but only took office five months has signed the 1900 life-saving visas. During this period from the domestic government to administrative pressure, physical threat from the Gestapo, ridicule from peers puzzled, but as a safeguard life and the good nature from him devoid and a the justice struggles ground hero buried is too long! cheap ghd memories of the last generation.ghd australia, Until 2000, the Israeli authorities only officially approved awarded the Righteous Among the Nations title.ghd hair straightener, Can be as early as in 1997, the elderly had died in San Francisco, because Israel provides only awarded to rescue the Jews of the Righteous Among the Nations award must meet several conditions: non-Jews; any harm to the Jews; Jews risked help; never receive money reward.

    Reply
  • cheap snapbacks free shipping

    Posted by xxds5tv on 03/28/2013 11:59pm

    [url=http://cheaphatsmall.webs.com]snapbacks for cheap[/url] snapbacks for cheap v duvk [url=http://cheapsnapbackshat.webs.com]cheap snapbacks hats[/url] cheap snapbacks hats g ewpt[url=http://wholesalefittedhat.webs.com]wholesale fitted hats[/url] wholesale fitted hats o cvkj[url=http://wholesalefittedhat.webs.com]wholesale fitted hats[/url] wholesale fitted hats q qsdf[url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks for sale[/url] cheap snapbacks for sale u gmqx[url=http://snapbackswholesalezone.webs.com]fitted hats wholesale[/url] fitted hats wholesale j zydz [url=http://wholesalefittedhat.webs.com]snapback wholesale[/url] snapback wholesale e ekku [url=http://goodsnapbackhatscheap.webs.com]cheap snapbacks[/url] cheap snapbacks v vhmd[url=http://snapbackswholesalezone.webs.com]fitted hats wholesale[/url] fitted hats wholesale p psyh[url=http://snapbackhatwholesale.webs.com]snapback hats wholesale[/url] snapback hats wholesale o addb[url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks free shipping[/url] cheap snapbacks free shipping f zcng[url=http://snapbackswholesalezone.webs.com]fitted hats wholesale[/url] fitted hats wholesale n mfoe [url=http://cheapsnapbacksforsalezone.webs.com]snapback hats cheap[/url] snapback hats cheap w xuzt [url=http://bestbaseballcap.webs.com]wholesale snapback caps[/url] wholesale snapback caps j ymsg[url=http://cheaphatsmall.webs.com]snapbacks for cheap[/url] snapbacks for cheap o ghcd[url=http://cheaphatsmall.webs.com]snapback hats cheap[/url] snapback hats cheap m wupo[url=http://wholesalefittedhat.webs.com]fitted hats wholesale[/url] fitted hats wholesale t dcpy[url=http://bestbaseballcap.webs.com]wholesale hats[/url] wholesale hats b fesg

    Reply
  • cheap ray ban

    Posted by vgliliImpumpwjo on 03/28/2013 09:58pm

    http://bestsunglassesshop.webs.com - fake oakleys oakley sunglasses cheap http://onlineguciisunglass.webs.com - cheap wayfarer sunglasses replica sunglasses http://sunglasswholesaleofgucci.webs.com - cheap oakleys for sale fake ray ban http://bestsunglassesshop.webs.com - cheap fake oakley sunglasses cheap ray ban http://wholesalesunglassescool.webs.com - sunglasses wholesale cheap sun glasses

    Reply
  • wholesale beanies

    Posted by xxds8md on 03/28/2013 07:19am

    [url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks online[/url] cheap snapbacks online w havt [url=http://cheapsnapbacksforsalezone.webs.com]cheap snapbacks free shipping[/url] cheap snapbacks free shipping k xylf[url=http://goodsnapbackhatscheap.webs.com]snapback hats cheap[/url] snapback hats cheap q yzgh[url=http://snapbackswholesalezone.webs.com]snapback hats wholesale[/url] snapback hats wholesale j exuu[url=http://snapbackhatwholesale.webs.com]wholesale fitted hats[/url] wholesale fitted hats q iehb[url=http://snapbackswholesalezone.webs.com]snapback wholesale[/url] snapback wholesale m rrqc [url=http://snapbackhatwholesale.webs.com]wholesale snapbacks[/url] wholesale snapbacks v ykyw [url=http://snapbackhatwholesale.webs.com]wholesale fitted hats[/url] wholesale fitted hats o fpxd[url=http://cheapsnapbacksforsalezone.webs.com]snapback hats cheap[/url] snapback hats cheap q dedh[url=http://cheaphatsmall.webs.com]cheap snapback hats[/url] cheap snapback hats j eoih[url=http://bestbaseballcap.webs.com]wholesale baseball caps[/url] wholesale baseball caps d tssz[url=http://goodsnapbackhatscheap.webs.com]cheap snapback hats[/url] cheap snapback hats c xdkt [url=http://cheapsnapbacksforsalezone.webs.com]snapback hats cheap[/url] snapback hats cheap u kfal [url=http://cheaphatsmall.webs.com]cheap snapback hats[/url] cheap snapback hats w ohls[url=http://cheaphatsmall.webs.com]cheap snapback hats[/url] cheap snapback hats j fdcm[url=http://goodsnapbackhatscheap.webs.com]cheap snapbacks[/url] cheap snapbacks l tcql[url=http://bestbaseballcap.webs.com]wholesale hats[/url] wholesale hats m qjdo[url=http://snapbackhatwholesale.webs.com]wholesale snapback hats[/url] wholesale snapback hats u kjxl

    Reply
  • ugg boots bxhtmd

    Posted by Mandyxuk on 02/18/2013 10:22pm

    cheap nike shoes ascuavgw nike factory pynusytq nike online store vtgboklr nike outlet online awaxdtcz nike outlet store srdrxefa nike outlet swbimeaa nike running shoes cozynlir nike shoes nexqmmfw nike store unudhlks

    Reply
  • Loading, Please Wait ...

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Packaged application development teams frequently operate with limited testing environments due to time and labor constraints. By virtualizing the entire application stack, packaged application development teams can deliver business results faster, at higher quality, and with lower risk.

  • Agile development principles have gone from something used only by cutting-edge teams to a mainstream approach used by teams large and small. If you're not using agile methods already though, or if you've only been exposed to agile on small projects here and there, you may wonder if agile can ever work in your environment. Read this eBook to learn the fundamentals of agile and how to increase the productivity of your software teams while enabling them to produce higher-quality solutions that better fulfill …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds