StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSafe parallel read-only access to a STL container
text
Body
copied!<p>I want access a STL based container <strong>read-only</strong> from <strong>parallel</strong> running threads. Without using any user implemented locking. The base of the following code is C++11 with a proper implementation of the standard.</p> <p><a href="http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_concurrency.html">http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_concurrency.html</a><br> <a href="http://www.sgi.com/tech/stl/thread_safety.html">http://www.sgi.com/tech/stl/thread_safety.html</a><br> <a href="http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html">http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html</a><br> <a href="http://www.open-std.org/jtc1/sc22/wg21/">http://www.open-std.org/jtc1/sc22/wg21/</a> (<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf">current draft</a> or <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf">N3337</a>, which is essentially C++11 with minor errors and typos corrected) </p> <blockquote> <p>23.2.2 Container data races [container.requirements.dataraces]</p> <p>For purposes of avoiding data races (17.6.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].</p> <p>Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the con- tained object in different elements in the same sequence, excepting vector<bool>, are modified concurrently.</p> <p>[ Note: For a vector<int> x with a size greater than one, x[1] = 5 and *x.begin() = 10 can be executed concurrently without a data race, but x[0] = 5 and *x.begin() = 10 executed concurrently may result in a data race. As an exception to the general rule, for a vector<bool> y, y[0] = true may race with y[1] = true. — end note ]</p> </blockquote> <p>and</p> <blockquote> <p>17.6.5.9 Data race avoidance [res.on.data.races] 1 This section specifies requirements that implementations shall meet to prevent data races (1.10). Every standard library function shall meet each requirement unless otherwise specified. Implementations may prevent data races in cases other than those specified below.</p> <p>2 A C++ standard library function shall not directly or indirectly access objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s argu- ments, including this.</p> <p>3 A C++ standard library function shall not directly or indirectly modify objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s non-const arguments, including this.</p> <p>4 [ Note: This means, for example, that implementations can’t use a static object for internal purposes without synchronization because it could cause a data race even in programs that do not explicitly share objects between threads. — end note ]</p> <p>5 A C++ standard library function shall not access objects indirectly accessible via its arguments or via elements of its container arguments except by invoking functions required by its specification on those container elements.</p> <p>6 Operations on iterators obtained by calling a standard library container or string member function may<br> access the underlying container, but shall not modify it. [ Note: In particular, container operations that invalidate iterators conflict with operations on iterators associated with that container. — end note ]</p> <p>7 Implementations may share their own internal objects between threads if the objects are not visible to users and are protected against data races.</p> <p>8 Unless otherwise specified, C++ standard library functions shall perform all operations solely within the current thread if those operations have effects that are visible (1.10) to users.</p> <p>9 [ Note: This allows implementations to parallelize operations if there are no visible side effects. — end note ]</p> </blockquote> <p><strong>Conclusion</strong><br> Containers are not thread safe! But it is safe to call <strong>const functions</strong> on containers from multiple parallel threads. So it is possible to do <strong>read-only</strong> operations from parallel threads without <strong>locking</strong>. Am I right?</p> <p>I pretend that their doesn't exist any faulty implementation and every implementation of the C++11 standard is correct.</p> <p>Sample:</p> <pre><code>// concurrent thread access to a stl container // g++ -std=gnu++11 -o p_read p_read.cpp -pthread -Wall -pedantic && ./p_read #include <iostream> #include <iomanip> #include <string> #include <unistd.h> #include <thread> #include <mutex> #include <map> #include <cstdlib> #include <ctime> using namespace std; // new in C++11 using str_map = map<string, string>; // thread is new in C++11 // to_string() is new in C++11 mutex m; const unsigned int MAP_SIZE = 10000; void fill_map(str_map& store) { int key_nr; string mapped_value; string key; while (store.size() < MAP_SIZE) { // 0 - 9999 key_nr = rand() % MAP_SIZE; // convert number to string mapped_value = to_string(key_nr); key = "key_" + mapped_value; pair<string, string> value(key, mapped_value); store.insert(value); } } void print_map(const str_map& store) { str_map::const_iterator it = store.begin(); while (it != store.end()) { pair<string, string> value = *it; cout << left << setw(10) << value.first << right << setw(5) << value.second << "\n"; it++; } } void search_map(const str_map& store, int thread_nr) { m.lock(); cout << "thread(" << thread_nr << ") launched\n"; m.unlock(); // use a straight search or poke around random bool straight = false; if ((thread_nr % 2) == 0) { straight = true; } int key_nr; string mapped_value; string key; str_map::const_iterator it; string first; string second; for (unsigned int i = 0; i < MAP_SIZE; i++) { if (straight) { key_nr = i; } else { // 0 - 9999, rand is not thread-safe, nrand48 is an alternative m.lock(); key_nr = rand() % MAP_SIZE; m.unlock(); } // convert number to string mapped_value = to_string(key_nr); key = "key_" + mapped_value; it = store.find(key); // check result if (it != store.end()) { // pair first = it->first; second = it->second; // m.lock(); // cout << "thread(" << thread_nr << ") " << key << ": " // << right << setw(10) << first << setw(5) << second << "\n"; // m.unlock(); // check mismatch if (key != first || mapped_value != second) { m.lock(); cerr << key << ": " << first << second << "\n" << "Mismatch in thread(" << thread_nr << ")!\n"; exit(1); // never reached m.unlock(); } } else { m.lock(); cerr << "Warning: key(" << key << ") not found in thread(" << thread_nr << ")\n"; exit(1); // never reached m.unlock(); } } } int main() { clock_t start, end; start = clock(); str_map store; srand(0); fill_map(store); cout << "fill_map finished\n"; // print_map(store); // cout << "print_map finished\n"; // copy for check str_map copy_store = store; // launch threads thread t[10]; for (int i = 0; i < 10; i++) { t[i] = thread(search_map, store, i); } // wait for finish for (int i = 0; i < 10; i++) { t[i].join(); } cout << "search_map threads finished\n"; if (store == copy_store) { cout << "equal\n"; } else { cout << "not equal\n"; } end = clock(); cout << "CLOCKS_PER_SEC " << CLOCKS_PER_SEC << "\n"; cout << "CPU-TIME START " << start << "\n"; cout << "CPU-TIME END " << end << "\n"; cout << "CPU-TIME END - START " << end - start << "\n"; cout << "TIME(SEC) " << static_cast<double>(end - start) / CLOCKS_PER_SEC << "\n"; return 0; } </code></pre> <p>This code can be compiled with <strong>GCC 4.7</strong> and runs fine on my machine. </p> <p>$ echo $?<br> $ 0</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload