Question:
How do I improve an integer set’s performance when it is used in multithreaded environment?

Answer:
Many factors affect a multithreaded application’s performance: the operating system, the duration of context switches between threads, the synchronization mechanism used (e.g., critical section vs. lock), the number of threads, system load, and the actual code that each thread executes. Note that the very use of threads increases the overall execution time because of the context switches’ overhead. The more context switches your application has, the higher the overhead, unless you’re using a multiprocessor machine.

Remember that standard C++ doesn’t specify whether STL containers are thread-safe. Different STL implementations use different thread-safety levels, and their performance varies accordingly. Therefore, if you have the time and patience, you can measure one or two more implementations of STL and see how they affect performance.

But before you do that, remember that even if each thread has its own set object, every STL container allocates memory from the heap, which is still shared by all threads. Therefore, if your sets reallocate storage often, your threads still block each other frequently. To avoid this, you can insert all the elements at once during the set’s construction:

int arr[1000];//.. fill arr with valuesstd::set < int > s(arr,arr+1000);//initialize s with arr

You can assign new values to the elements later, without being blocked by reallocation.