How could a compiler break the lockless hashing method?

[bob]

The C standard in fact agrees with you:

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (A summary of the sequence points is given in annex C.)

So I don't think eliminating the xor-operations is allowed by the C standard.

What does "modifying an object" mean exactly?

Look at the following transcript of a shell session I just did. Notice that even though I write two values to a, only one of them is actually written.

Code: Select all

$ cat a.c
#include <stdio.h>

static int a;

int main &#40;void&#41;
&#123;
        a = 0;
        a = 1;
        return a;
&#125;

$ gcc -O3 a.c -o a

$ gdb a
GNU gdb 6.8-debian
Copyright &#40;C&#41; 2008 Free Software Foundation, Inc.
License GPLv3+&#58; GNU GPL version 3 or later <http&#58;//gnu.org/licenses/gpl.html>
This is free software&#58; you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu"...
&#40;no debugging symbols found&#41;
&#40;gdb&#41; disassemble main
Dump of assembler code for function main&#58;
0x08048380 <main+0>&#58;    lea    0x4&#40;%esp&#41;,%ecx
0x08048384 <main+4>&#58;    and    $0xfffffff0,%esp
0x08048387 <main+7>&#58;    pushl  -0x4&#40;%ecx&#41;
0x0804838a <main+10>&#58;   mov    $0x1,%eax
0x0804838f <main+15>&#58;   push   %ebp
0x08048390 <main+16>&#58;   mov    %esp,%ebp
0x08048392 <main+18>&#58;   push   %ecx
0x08048393 <main+19>&#58;   movl   $0x1,0x8049580
0x0804839d <main+29>&#58;   pop    %ecx
0x0804839e <main+30>&#58;   pop    %ebp
0x0804839f <main+31>&#58;   lea    -0x4&#40;%ecx&#41;,%esp
0x080483a2 <main+34>&#58;   ret
End of assembler dump.
&#40;gdb&#41;

That;s an acceptable optimization. but add a function call between those two assignments and both will be done, as required...

[bob]

You can not remove XORs on volatile data. You can't remove anything. If the XORs happened back to back, with NO intervening code, you STILL can not eliminate them if the target is a volatile variable.

So is crafty's hashtable declared as volatile? I don't see it.

For hashing, no. Why?

Duh. You're saying "there is no problem for volatile data". What kind of argument is that if we are not talking about volatile data?

Not using volatile reduces the optimization limits. It doesn't break the code. You guys talk about toy examples where you need volatile to make it work. In any procedure, any write done to global memory MUST be completed before the procedure returns. No choice. With volatile, it actually has to be done where it appears in the program, further restricting the optimizer. Lockless hashing doesn't depend on any of that.

Other parts of crafty depend on volatile heavily.

Simple enough now?

[bob]

The C standard in fact agrees with you:

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (A summary of the sequence points is given in annex C.)

So I don't think eliminating the xor-operations is allowed by the C standard.

What does "modifying an object" mean exactly?

An object is an area of memory. It's somewhere in the standard.

Look at the following transcript of a shell session I just did. Notice that even though I write two values to a, only one of them is actually written.

There is no sequence point between the two stores.

Are you sure? Seems to me there is, according to what I've read on sequence points.

No. But any functional call inserted between the two lines will establish one. Right now there is NOTHING between the two writes.

[bob]

Unless I'm mistaken, the C standard allows the compiler to load a value multiple times. Since the C99 standard does not know about threads, it may load the hash entry, do the xor-trick to verify that the entry can be used, and load the hash entry again. Between the two loads the hash entry may change its content due to other threads. There you go.

Doesn't break a thing, however.

Think about it.

I can only assume you did not read.

A compiler can legally rewrite:

Code: Select all

    word1 = htable->word1;
    word2 = htable->word2 ^ word1;
    if (word2 == temp_hashkey)
      break;

as

Code: Select all

  word2 = htable->word2 ^ htable->word1;
  if (word2 == temp_hashkey)
    break;
  word1 = htable->word1;

See the problem?

Don't see any problem at all. Doesn't change a thing. Next line after exiting the loop access word1, so it has to load word 1 anyway. This is a bad optimization, btw, it saves nothing whatsoever and adds the extra code to load word one after the loop breaks rather than within the loop. Don't need that kind of anti-optimization and I don't believe any good compiler would choose to do something so broken...

It can also choose to read htable->word1 at a later point in HashProbe() instead of accessing the local variable word1.

Again, won't change a thing. I could even FORCE it to re-read it later by referring to it as volatile. But I don't care...

[Aaron Becker]

The C standard in fact agrees with you:

Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment. Evaluation of an expression may produce side effects. At certain specified points in the execution sequence called sequence points, all side effects of previous evaluations shall be complete and no side effects of subsequent evaluations shall have taken place. (A summary of the sequence points is given in annex C.)

So I don't think eliminating the xor-operations is allowed by the C standard.

What does "modifying an object" mean exactly?

An object is an area of memory. It's somewhere in the standard.

Look at the following transcript of a shell session I just did. Notice that even though I write two values to a, only one of them is actually written.

There is no sequence point between the two stores.

Are you sure? Seems to me there is, according to what I've read on sequence points.

No. But any functional call inserted between the two lines will establish one. Right now there is NOTHING between the two writes.

There is a sequence point between any two statements, by definition (see Annex C of the C11 standard). The presence of a sequence point doesn't mean that the compiler can't optimize away the first write, because the only guarantee about program behavior is that observable results agree with the abstract machine defined in the standard. Section 5.1.2.3 of the standard is the relevant part: http://www.open-std.org/jtc1/sc22/wg14/ ... /n1570.pdf

[Aaron Becker]

On a side note, you can find a good overview of potential pitfalls in the use of volatile variables here: http://blog.regehr.org/archives/28. Items 5-8 are especially relevant. I think people often overestimate the guarantees that volatile variables provide, and the insides of modern superscalar multicore processors are scary places to reason about.

[wgarvin]

On a side note, you can find a good overview of potential pitfalls in the use of volatile variables here: http://blog.regehr.org/archives/28. Items 5-8 are especially relevant. I think people often overestimate the guarantees that volatile variables provide, and the insides of modern superscalar multicore processors are scary places to reason about.

That link didn't work because of the period at the end.

Here it is again: Nine ways to break your systems code using volatile


It reminds me of that paper they did about many compilers mis-compiling code with volatile qualifiers in it. That was a few years ago though, hopefully that situation is better now. (I don't know.)

[hgm]

A C99-compliant compiler does not need to care about other processes and shared memory. The standard does not know about those.

(But I do agree it must store the expected values, because C99 requires it.)

But those designing the standard did know about those. And I think it is a save bet they did not want to make a standard that would render C99 completely useless to anyone. So they have hidden the need to make sure multi-threaded C99 applications would work, by explicitly phrasing the conditions that would ensure it. Such as that the optimizer is not allowed to mess with values stored in global variables.

[hgm]

You are forgetting that many modern compilers use whole-program optimization. Even if they didn't it wouldn't matter for this discussion, as we're talking about what a compiler could do, as opposed to what current compilers do.

How do you imagine a compiler could do 'whole-program optimization' if it only gets to see part of the program, in search.c? Even when I write "gcc -c *.c" so it can peek in the other .c files, it MUST generate code that allows me to link the produced search.o file with whatever other .o files generated from other compilers or assembly. If it didn't, it would just be a broken compiler.

Are you implying that at the linking stage, writing "gcc *.o" would allow the compiler to do anything else then just call the linker with the required libraries and stubs to collect the mentiones *.o files, but could completely redo the *.o files? I would consider that very reprehensible behavior.

[Rein Halbersma]

Are you implying that at the linking stage, writing "gcc *.o" would allow the compiler to do anything else then just call the linker with the required libraries and stubs to collect the mentiones *.o files, but could completely redo the *.o files? I would consider that very reprehensible behavior.

You can read about gcc -flto here: http://gcc.gnu.org/onlinedocs/gcc-4.8.1 ... tions.html IIUC, it will never to this with -O3 alone, you need to explicitly pass -flto to both compiler and linker.