Identifier generator with local static variable - thread safe?

Question

Will the following code snippet work as expected in a multi-threaded script?

int getUniqueID() { static int ID=0; return ++ID; } 

The identifiers are not required to be contiguous - even if it skips the value, this is normal. Is it possible to say that when this function returns, the return value will be unique for all threads?

Answer 1

No, it will not. To run this code, your processor must complete the following steps:

• Selection of ID value from memory to register
• Register increment
• Saving the added value to memory

If a flow switch occurs during this (non-atomic) sequence, the following may occur:

• Thread a selects 1 to register
• Thread a increases the value, so the register now contains 2
• Context switch
• In stream b, the value 1 is selected (which is still in memory)
• Context switch
• Insert storage 2 into memory and return
• Context switch
• Thread b increments the value stored in its register by 2
• Thread b (also) stores the value 2 in memory and returns 2

So both threads return 2.

Answer 2

No, there is still potential for races, because the increment is not necessarily atomic. If you use an atomic operation to increase the ID, this should work.

Answer 3

++ not necessarily atomic, so no, it is not thread safe. However, many temporary C environments provide atomic versions, such as __sync_add_and_fetch() for gcc and InterlockedIncrement() on Windows.

Answer 4

If you just need some monotonically increasing (or very close to it) numbers over N flows, consider this (k is a certain number such that 2 ^ k> N):

 int getUniqueIDBase() { static int ID=0; return ++ID; } int getUniqueID() { return getUniqueIDBase() << k + thread_id; } 

Answer 5

getUniqueID has at least two race conditions. When initializing ID and increasing ID . I rewrote a function to display data calculations more clearly.

 int getUniqueID() { static bool initialized = false; static int ID; if( !initialized ) { sleep(1); initialized = true; sleep(1); ID = 1; } sleep(1); int tmp = ID; sleep(1); tmp += 1; sleep(1); ID = tmp; sleep(1); return tmp; } 

The increment is deceptive; it looks so small as to be considered atomic. However, this is a load-modify-storage operation. Load the value from memory into the CPU register. inc register. Save the register back to memory.

Using the new C ++ 0x, you can just use the std::atomic .

 int getUniqueID() { static std::atomic<int> ID{0}; return ++ID; } 

NOTE: I technically lied. zero initialized global values ​​(including function statistics) can be stored in bss memory and will not be initialized after the program starts. However, growth is still a problem.

Answer 6

Note. The word is almost used, since the global variable will be initialized at the start of the process (i.e., its constructor will be called before the main input), while the static variable inside the function will be initialized the first time the instruction is executed.

From the very beginning, your question is not right:

Identifier generator with local static variable - thread safe?

In C / C ++, a variable, static inside a function or inside a class / struct declaration, behaves (almost) like a global variable, not a local, stack-based one.

The following code:

 int getUniqueID() { static int ID=0; return ++ID; } 

It would be (almost) similar to pseudo-code:

 private_to_the_next_function int ID = 0 ; int getUniqueID() { return ++ID; } 

with the pseudo-keyword private_to_the_next_function making the variable invisible to all other functions, but getUniqueId ...

Here static hides only the variable, which makes it impossible to access other functions ...

But even the hidden variable identifier remains global: if getUniqueId is called by several threads, the ID will be as thread safe as other global variables, that is, it is not thread safe at all .

Edit: lifetime of variables

After reading the comments, I felt that I was not clear enough with my answer. I do not use global / local concepts for their visibility value, but for their vital meaning:

The global one will work as long as the process is running, and the local one that is allocated on the stack will begin its life path when entering the region / function and will cease to exist when the region / function exits. This means that the global will retain its value, and the local - not. It also means that global will be shared between threads, and local will not.

Add the static keyword to it, which has different meanings depending on the context (therefore, the use of static for global variables and functions in C ++ is deprecated in favor of anonymous namespaces, but I cannot exit).

When defining a local variable, this local one ceases to behave as a local one. It becomes global, hidden within a function. Thus, it behaves as if the value of a local variable was remembered magically between function calls, but there was no magic: the variable is global and will remain “alive” until the end of the program.

You can "see" this by registering the creation and destruction of an object declared static inside a function. The construction will occur when the declaration instruction is executed and the destruction occurs at the end of the process:

 bool isObjectToBeConstructed = false ; int iteration = 0 ; struct MyObject { MyObject() { std::cout << "*** MyObject::MyObject() ***" << std::endl ; } ~MyObject() { std::cout << "*** MyObject::~MyObject() ***" << std::endl ; } }; void myFunction() { std::cout << " myFunction() : begin with iteration " << iteration << std::endl ; if(iteration < 3) { ++iteration ; myFunction() ; --iteration ; } else if(isObjectToBeConstructed) { static MyObject myObject ; } std::cout << " myFunction() : end with iteration " << iteration << std::endl ; } int main(int argc, char* argv[]) { if(argc > 1) { std::cout << "main() : begin WITH static object construction." << std::endl ; isObjectToBeConstructed = true ; } else { std::cout << "main() : begin WITHOUT static object construction." << std::endl ; isObjectToBeConstructed = false ; } myFunction() ; std::cout << "main() : end." << std::endl ; return 0 ; } 

If you run an executable file without parameters, execution will never go through the declaration of a static object, and therefore it will never be created or destroyed, as shown in the logs:

 main() : begin WITHOUT static object construction. myFunction() : begin with iteration 0 myFunction() : begin with iteration 1 myFunction() : begin with iteration 2 myFunction() : begin with iteration 3 myFunction() : end with iteration 3 myFunction() : end with iteration 2 myFunction() : end with iteration 1 myFunction() : end with iteration 0 main() : end. 

But if you run it with a parameter, then the object will be created during the third recursive call to myFunction and will be destroyed only at the end of the process, as can be seen from the logs:

 main() : begin WITH static object construction. myFunction() : begin with iteration 0 myFunction() : begin with iteration 1 myFunction() : begin with iteration 2 myFunction() : begin with iteration 3 *** MyObject::MyObject() *** myFunction() : end with iteration 3 myFunction() : end with iteration 2 myFunction() : end with iteration 1 myFunction() : end with iteration 0 main() : end. *** MyObject::~MyObject() *** 

Now, if you play with the same code, but calling myFunction through multiple threads, you will have race conditions on the constructor myObject. And if you call these myObject methods or use the myObject variables in myFunction, called by multiple threads, you will also have race conditions.

Thus, the static local variable myObject is just a global object hidden inside a function.