A note for C programmers

[rbarreira]

More quotes from Bob at the goldmine that is the OpenChess thread:

Sorry, my man page does NOT say "don't do this". It says "the behavior is undefined." The behavior in Mavericks is NOT "undefined". You get a message that says "Abort" with no explanation as to why.

If you had programmed for a long time, the reason for the suggested usage is well-documented... If you do strcpy(s+n, s) a right-to-left copy (the only reasonable way to copy a null-terminated string) can cause problems. The only requirements to produce a potential problem are that source and destination overlap, and the length of source + source pointer >= original destination pointer. A straightforward case. If you avoid that, strcpy works just fine with overlaps.

Yeah, this is not a person who understands what undefined behavior means.

[mar]

Don't know about C11, but in C++11, concurrent data structures should use a boost::shared_mutex<uint64_t> to implement shared hash tables. This allows multiple readers and a single writer to safely (i.e. without UB) access a global hash table from multiple threads. In this C++ book on concurrency, such an example is worked out in detail.

Now I'm a bit puzzled. I just looked at boost::shared_mutex implementation and it's a plain class, not a template. It uses pthreads or WinAPI on windows.
Ronald already said that you have no guarantee that threads will be able to see the same memory according to the standard.
This bothers me as I always thought that in multi-cpu environment, you are guaranteed that a process can run on exactly one CPU and threads are serviced by individual cores of that CPU.
Is there a standard way to collect results from individual threads? You will need shared memory for that. I have never worked with a multi-CPU machine before so I may be wrong.

[Rein Halbersma]

Now I'm a bit puzzled. I just looked at boost::shared_mutex implementation and it's a plain class, not a template. It uses pthreads or WinAPI on windows.
Ronald already said that you have no guarantee that threads will be able to see the same memory according to the standard.
This bothers me as I always thought that in multi-cpu environment, you are guaranteed that a process can run on exactly one CPU and threads are serviced by individual cores of that CPU.
Is there a standard way to collect results from individual threads? You will need shared memory for that. I have never worked with a multi-CPU machine before so I may be wrong.

Sorry, I indeed wrote the wrong class. Your data entry (or bucket of entries) can be plain Key, Value pair, supplemented with a std::mutex (per bucket or per pair). You can also use a boost::shared_mutex, which will become std::shared_mutex in C++14. WIth the mutex, you have to lock/unlock that mutex in every member function of your hash table.

I am not very proficient in multi-threaded code either, but the C++ Standard does not mandate on which core a thread is run. The OS has a lot of leeway in determining that. But that doesn't really matter, since the std::mutex does guarantee the memory consistency of simultaneous read/write attempts.

[mar]

EDIT: it seems clang has -fcatch-undefined-behavior, I will try it to see if it works

It works, thanks to clang I removed undefined behavior from my engine (left shifts of negative signed integers
=> used to do x86 assembly in the past, I will be very careful with that from now on).
I measured no performance hit whatsoever.

[mar]

Sorry, I indeed wrote the wrong class. Your data entry (or bucket of entries) can be plain Key, Value pair, supplemented with a std::mutex (per bucket or per pair). You can also use a boost::shared_mutex, which will become std::shared_mutex in C++14. WIth the mutex, you have to lock/unlock that mutex in every member function of your hash table.

I am not very proficient in multi-threaded code either, but the C++ Standard does not mandate on which core a thread is run. The OS has a lot of leeway in determining that. But that doesn't really matter, since the std::mutex does guarantee the memory consistency of simultaneous read/write attempts.

What I don't like about locking is that it pauses other threads accessing the hashtable simultaneously (the same lock in fact). I like bob's xor trick because it's completely lock-free.
What might work (and I bet others are doing it as well) would be to use a pool of spinlocks (or mutexes) indexed by n bits of the hash key. Maybe that's what you meant.
The advantage of this would be that you'd only lock if you access the same entry (actually entries with same m-n bits of the hash key) and you don't lock the whole TT.
Whether it's worth the effort (bob's solution is much simpler than that) and how much impact it would have on performance is another question (OTOH it would avoid data races completely).
I will probably try it someday.

[syzygy]

Ronald already said that you have no guarantee that threads will be able to see the same memory according to the standard.

But then I'm not talking about C11, because C11 is aware of threads.

This bothers me as I always thought that in multi-cpu environment, you are guaranteed that a process can run on exactly one CPU and threads are serviced by individual cores of that CPU.

But then programs will need to rely on a bit more than just the C99 standard.

[syzygy]

Sorry, I indeed wrote the wrong class. Your data entry (or bucket of entries) can be plain Key, Value pair, supplemented with a std::mutex (per bucket or per pair). You can also use a boost::shared_mutex, which will become std::shared_mutex in C++14. WIth the mutex, you have to lock/unlock that mutex in every member function of your hash table.

I am not very proficient in multi-threaded code either, but the C++ Standard does not mandate on which core a thread is run. The OS has a lot of leeway in determining that. But that doesn't really matter, since the std::mutex does guarantee the memory consistency of simultaneous read/write attempts.

What I don't like about locking is that it pauses other threads accessing the hashtable simultaneously (the same lock in fact). I like bob's xor trick because it's completely lock-free.
What might work (and I bet others are doing it as well) would be to use a pool of spinlocks (or mutexes) indexed by n bits of the hash key. Maybe that's what you meant.
The advantage of this would be that you'd only lock if you access the same entry (actually entries with same m-n bits of the hash key) and you don't lock the whole TT.
Whether it's worth the effort (bob's solution is much simpler than that) and how much impact it would have on performance is another question (OTOH it would avoid data races completely).
I will probably try it someday.

Personally I will continue to rely on data race when accessing the hashtable (and I won't use the xor-trick either). I promise I will not complain when a new compiler version breaks my code.

[wgarvin]

Only just now I became aware of this paralell thread, containing passages such as:

I clearly DO understand what "undefined behavior" means. I, unlike yourself, apparently, ALSO understand WHY the warning about overlapping source/destination is discouraged. I, unlike yourself, am perfectly capable of avoiding that particular pitfall, which lets me use strcpy() in a way that will absolutely NOT fail.

Ouch.

Wow, yeah, that thread has some real head-scratchers in it. If only I had read that one first, I could have saved some time writing reply posts in this thread. Its obvious bob has backed himself into a corner and needs to "win" the argument, and no amount of persuasion or even outright ridicule will overcome this. Myself, I would rather admit when I am wrong... learning new things is easier that way.

I just hope he's not teaching dangerously-wrong ideas about undefined behavior and program correctness to his C programming students.

I know if I was interviewing a job candidate and he told a story like the one that has unfolded here, and the punch-line was "they broke my code, NEVER break working code, even though my code was invoking undefined behavior its obviously their fault because the program _worked_" .. I would not hire that candidate, because of their dangerously wrong ideas about whose responsibility it is to avoid undefined behavior.

Only the programmer has the power to write correct programs. Compilers can't take an incorrect program and paper it over to make it look like a correct one, nor should they try. Programs can appear to be correct even when they aren't; those are not working programs, they are broken programs with time-bombs in them, and "Works on my machine" is a mediocre retort after it has been pointed out that the program is incorrect.

[bob]

Please stop writing the nonsense about race conditions. The compiler can't even RECOGNIZE them, much less do anything with 'em.

Some race conditions can be detected trivially. First of all, we need to be talking C11 or talking about threads does not even make sense. In C11, just let one thread create another thread and let both threads at some point access the same variable. If there are no synchronisation primitives on the paths towards these accesses, you have a data race. C11 defines the synchronisation primitives, so the compiler can recognise their absence.

Will compilers actively look for data races? Probably not. But they can assume that they won't happen and optimise your code in ways that you certainly are not expecting.

Sorry, we are talking pure C. C as is used in Crafty. Threads DO make sense, there is a native thread library for every machine I have used.

Your example fails pretty miserably however.

1. You might not do the lock/unlock in the procedure where the variable is modified. I do this when I split in Crafty, in fact.

2. Since the source files are compiled separately, the compiler has no clue if there is a lock set outside this procedure or not. It therefore has no clue as to whether there is a race condition or not. The compiler simply can not determine whether this sort of undefined behavior-causing construct is being used or not.

So even in C11 it is hopeless. As it is in C90 and earlier. This is not going to get fixed because it is unfixable. BTW just because two threads modify a shared value without a lock does NOT mean "race". And even if they do use a "lock" the compiler can't recognize it since there are software locking mechanisms that work on X86 without depending on the lck prefix or on the usual exchange idea.

Not going to happen.

[bob]

The problem is that the only way that might work for detecting races at compile time would be static analysis. But it's very expensive and unreliable.
I very much doubt any compiler will do that.

Such technology is becoming mainstream
http://clang.llvm.org/docs/ThreadSanitizer.html

it is not becoming mainstream. It was already impossible. Thread sanitizer fails for our hash table idea. You can verify that for yourself. It introduces SO MUCH overhead, for such a short possible race condition, it does not get detected. That is not exactly "mainstream". It might detect an occasional horribly ugly race. But not the place where the compiler simply outputs two consecutive quadword mov instructions to write a hash entry.

And, of course, you DO realize that threads are not the only way to introduce a race? I can start two separate instances of a program and let them interact through either mmap() or shmat(). The compiler has no clue what the "other" process is doing.