{"id":79,"date":"2007-10-25T20:28:37","date_gmt":"2007-10-26T04:28:37","guid":{"rendered":"http:\/\/www.airs.com\/blog\/archives\/79"},"modified":"2007-10-25T20:29:27","modified_gmt":"2007-10-26T04:29:27","slug":"single-threaded-memory-model","status":"publish","type":"post","link":"https:\/\/www.airs.com\/blog\/archives\/79","title":{"rendered":"Single Threaded Memory Model"},"content":{"rendered":"

One more round on the parallel programming theme. There has been some recent discussion on the gcc<\/a> and LKML<\/a> mailing lists about an interesting case.<\/p>\n

\n

static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
\nstatic int acquires_count = 0;<\/p>\n

int
\ntrylock()
\n{
\n int res;<\/p>\n

res = pthread_mutex_trylock(&mutex);
\n if (res == 0)
\n ++acquires_count;<\/p>\n

return res;
\n}\n<\/p><\/blockquote>\n

On x86 processors, current gcc will optimize this to use a comparison, an add with carry flag, and an unconditional store to acquires_count<\/code>. This eliminates a branch, but it means that the variable is written to even if the lock is not held. That introduces a race condition.<\/p>\n

This is clearly permitted by the C language standard, which in general describes a single threaded model. The standard says nothing about precisely when values are written to memory. It simply says that if you assign a value to a global variable, then when you read the global variable you should see that value.<\/p>\n

It may seem that this should be an invalid optimization: the compiler should not move stores out of a conditionally executed basic block. Several people have reacted to this test case in this way. However, note that the first function call could be anything–it could even be a test of a global variable. And note that the store could be a load–we could load a global variable twice, protected by some conditional both times. If we require that this code be safe in a multi-threaded environment, then we can not coalesce the loads. That would be OK with people who write C as a fancy assembly language. But it would significantly hurt performance for complex programs, especially in C++, in which the conditionals would be in different functions and then inlined together.<\/p>\n

So what should the compiler do, given a choice between optimizing complex C++ code and helping to generate correct complex multi-threaded code? Complex C++ code is much more common than complex multi-threaded code. I think the compiler is making the right choice. And it conforms to the language standard.<\/p>\n

For this code to be correct in standard C, the variable needs to be marked as volatile<\/code>, or it needs to use an explicit memory barrier (which requires compiler specific magic–in the case of gcc, a volatile asm<\/code> with an explicit memory clobber). But many people don’t see that–including Linus Torvalds<\/a>.<\/p>\n

I think this is a nice example of my earlier point, which is that our current models of parallel programming are generally too hard for people to use.<\/p>\n","protected":false},"excerpt":{"rendered":"

One more round on the parallel programming theme. There has been some recent discussion on the gcc and LKML mailing lists about an interesting case. static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; static int acquires_count = 0; int trylock() { int res; res = pthread_mutex_trylock(&mutex); if (res == 0) ++acquires_count; return res; } On x86 processors, current […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-79","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/posts\/79","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/comments?post=79"}],"version-history":[{"count":0,"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/posts\/79\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/media?parent=79"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/categories?post=79"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.airs.com\/blog\/wp-json\/wp\/v2\/tags?post=79"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}