It Will Never Work in Theory

Parallelism in Open Source Projects

Posted Jun 12, 2016 by Greg Wilson

| Parallelism |

Marc Kiefer, Daniel Warzel, and Walter Tichy: "An Empirical Study on Parallelism in Modern Open-Source Projects". SEPS'15, October 2015, https://ps.ipd.kit.edu/backend/index.php/veroeffentlichungen-details/items/3803.html.

We present an empirical study of 135 parallel open-source projects in Java, C# and C++ ranging from small (<1000 lines of code) to very large (>2M lines of code) codebases. We examine the projects to find out how language features, synchronization mechanisms, parallel data structures and libraries are used by developers to express parallelism. We also determine which common parallel patterns are used and how the implemented solutions compare to typical textbook advice.

The results show that similar parallel constructs are used equally often across languages, but usage also heavily depends on how easy to use a certain language feature is. Patterns that do not map well to a language are much rarer compared to other languages. Bad practices are prevalent in hobby projects but also occur in larger projects.

I wrote my first parallel program in 1986 on an ICL DAP with 4096 bit-serial processors. I wrote my second in Occam the following spring for a 16-transputer machine, and spent the next ten years thinking, "There has to be a better way." Two decades later, the answer to that is still, "Not yet," but in those years parallelism of various kinds has gone from esoteric to everyday.

But how do we actually use it? And how well? To answer those questions, the authors of this paper explored open source programs written in several different languages. Here are a few of their findings (the figures for Java are omitted, since those tables are larger than the ones for C# and C++ combined):

Use of High-Level Constructs Use of Synchronization Primitives
Language Feature # projects % of total Language Feature # projects % of total
C# Task 33 73.33% C# lock() 42 93.33%
ThreadPool 19 42.22% ManualResetEvent 22 48.89%
TaskScheduler 10 22.22% Monitor 17 37.78%
Parallel.For 8 17.78% AutoResetEvent 16 35.56%
BlockingCollection 6 13.33% ReaderWriterLockSlim 15 33.33%
Parallel.ForEach 6 13.33% WaitHandle 13 28.89%
TaskFactory 5 11.11% EventWaitHandle 10 22.22%
Parallel.Invoke 1 2.22% Mutex 10 22.22%
ManualResetEventSlim 8 17.78%
Barrier 7 15.56%
Semaphore 6 13.33%
SpinWait 4 8.89%
CountdownEvent 3 6.67%
ReaderWriterLock 3 6.67%
SemaphoreSlim 3 6.67%
MethodImplOptions Synchronized 2 4.44%
Interlocked.MemoryBarrier 1 2,22%
SpinLock 0 0.00%
C++ #pragma omp parallel for 6 13.64% mutex 39 88.64%
future/promise 3 6.82% condition variable 28 63.63%
#pragma omp parallel 2 4.55% Semaphore 18 40.91%
packaged task 0 0.00% CriticalSection 17 38.64%
shared future 0 0.00% unique lock 16 36.36%
lock guard 12 27.27%
barrier 5 11.36%
#pragma omp critical 3 6.82%

But these tables don't tell the most important parts of the story. For that, we have to look at patterns:

Pattern Java C# C++
Master-worker 29 23 23
Producer-consumer 10 5 5
Pipeline 8 9 8
Parallel Loop 1 8 5
Fork-join 3 1 1

But the authors go even further and look at where programmers do things they shouldn't:

  • "Smaller projects tend to reimplement slight variations of existing functionality, while projects with a larger codebase often reuse existing functionality and extend these classes via subclassing."
  • "An exception is the master-worker pattern. It seems that it is such an intuitive pattern, that some developers seem to implement it by accident. Unexperienced developers just create threads and distribute their work to them. In larger projects comments and class naming suggests that they are aware of the master-worker pattern and implement it on purpose..."
  • "Prime examples of bad pratice are the synchronized() and lock() features in Java and C#. Both language references strongly advise against locking on publicly accessible types or classes. Nevertheless this is what happens in most instances in both Java and C# regardless of the size of the project."

It's easy to say this means we need better documentation—better, but wrong. Just as you can't refactor your way to better security, you can't document your way to better usability. Knowing what people use, how they use it, and how they mis-use it could and should inform the design of the next generation of parallel programming tools. And if that's too optimistic, we can at least hope that it will give the builders of the next generation of program checking tools a larger list of things to look for...

Comments powered by Disqus