OpenImageIO/oiio — pull request #611 by lgritz (2013-06-10 06:03:15+00:00)
Title: Unordered concurrent map for texture cache

I'll cut to the chase with this old/new comparison of texture system performance (work is scaled by number of threads, so having identical wall clock times for each thread count would be 100% efficiency for utilizing additional threads):

OLD NEW
threads time (s) efficiency time efficiency
-------- -------- ---------- ----- ----------
1 4.30 100.0% 4.50 100.0%
2 4.33 99.2% 4.67 96.3%
4 4.92 87.3% 4.79 94.0%
6 7.32 58.7% 4.77 94.5%
8 13.70 31.4% 4.83 93.2%
10 19.94 21.5% 4.99 90.3%
12 26.25 16.4% 5.13 87.8%

Beyond 4 threads, the threads were blocking each other waiting for access to the tile cache. This shows up most prominently on benchmarks that isolate the texture system. We (SPI) had not really seen numbers anywhere this bad in production, though other users of OIIO's texture system have reported problems with many threads.

The problem is that the tile cache is implemented mostly as a unordered_map (hash map) which is protected by a reader-writer spin mutex, and the more threads are added, the more likely it is that several threads will want access to the tile map at the same time and block each other.

We observe that Java supplies a ConcurrentHashMap that largely solves this problem, and so we model an unordered_map_concurrent with the same basic principle: we split the big hash map protected by a single lock into several smaller hash maps (we call them "bins"), each of which is protected by its own lock. Two threads looking for (or modifying) separate keys are likely to find the keys in different bins, and thus neither thread will block the other. Of course, it's possible that two threads could coincidentally look for keys in the same bin (even the same key!), but that's the rare case, and so most of the time the operation is wait-free. The API for the umc looks very similar to an unordered_map, including the availabilities of iterators that are smart enough to walk through the map, stepping from one bin to another, unlocking and locking the correct bins as it goes.

The results, as above, speak for themselves.

It appears to be a few percent slower for 1-2 threads. First of all, these timings are very hard to get exact, since they involve disk and network I/O as well as thread timing vagueries; I'm not sure we should consider them accurate to more than 0.1-0.2 seconds. Second, 1-2 threads is an increasingly unimportant case, and I feel fairly comfortable trading 5% of performance for that rare situation for astonishingly better (up to 5x) thread scalability for greater number of threads.

The implementation of unordered_map_concurrent is via a template that is completely generic, not in any way tied to the texture system. (The texture system just uses it as a replacement for the original unordered_map.) Therefore, the umc is ready to be applied elsewhere in OIIO or in your own projects, if you have another use of a hash map that is becoming a thread bottleneck.