Why volatile keyword is used?

Question

I'm curious as to why libstdc++ is using a RB-tree to implement std::set (details here
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/std/set and here https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/stl_tree.h ),
when there are faster alternatives?

I'm mainly curious, because from all the people I've asked there hasn't been a single answer in favor of RB-trees, other than "they're already popular" or "easy to implement".

If you'd like more details on that, here's a link to my question on stackexchange http://cs.stackexchange.com/questions/41969/why-are-red-black-trees-so-popular,
where nobody has yet answered as well.

Using a variant of B-tree (or (a,b)-tree) should be faster, and everyone seems to suggest so, which makes me wonder what is the reason for picking RB-trees? This is not a question about their theoretical speed, but about real world behavior on real hardware with respect to CPU caches, etc.

Answer 1

The volatile modifier is a directive to the compiler’s optimizer that operations involving this variable should not be optimized in certain ways.

There are two special cases in which use of the volatile modifier is desirable. The first case involves memory-mapped hardware (a device such as a graphics adaptor that appears to the computer’s hardware as if it were part of the computer’s memory), and the second involves shared memory (memory used by two or more programs running simultaneously).

Answer 2

The answer is perfectly right...Just to make it easy to understand i would like to add few points.
There could be many situation where the compiler imposes optimization on a particular object or variable.. for example it could keep the variable copy in the register in case it is frequently used and the value retrieved for computation is from the register or cache rather than memory. Now consider that the variable or object in our case is part of shared memory, so if Process 1 modifies the variable which now should be used for Computation being performed for process 2...the value of the variable will be one in the register or cache not from the memory... resulting in incorrect computation.
So U see why here it is necessary to use Volatile........
There are lot many different examples where declaring a variable as volatile is necessary.

Comments

thanks Prakash, Salil.
->Salil, can you share example for the first case that you have mentioned ?

Answer 3

Most of the times compilers optimize to the code to speed up the program.

Ex:
    int a = 10;
    while( a == 10){
    // Do something
    }

compiler may think that value of 'a' is not getting changed from the program and replace it with 'while(true)', which will result in an infinite loop. In actual scenario the value of 'a' may be getting updated from outside of the program.Volatile keyword is used to tell compiler that the variable declared using volatile may be used from outside the current scope so that compiler wont apply any optimization. This matters only in case of multi-threaded applications.