Loop Recognition in C++/Java/Go/Scala
Abstract
In this experience report we encode a well specified, compact benchmark in four
programming languages, namely C++, Java, Go, and Scala. The implementations each
use the languages’ idiomatic container classes, looping constructs, and
memory/object allocation schemes. It does not attempt to exploit specific language
and runtime features to achieve maximum performance. This approach allows an almost
fair comparison of language features, code complexity, compilers and compile time,
binary sizes, runtimes, and memory footprint. While the benchmark itself is simple
and compact, it employs many language features, in particular, higher-level data
structures (lists, maps, lists and arrays of sets and lists), a few algorithms
(union/find, dfs / deep recursion, and loop recognition based on Tarjan), iterations
over collection types, some object oriented features, and interesting memory
allocation patterns. We do not explore any aspects of multi-threading, or higher
level type mechanisms, which vary greatly between the languages. The benchmark
points to very large differences in all examined dimensions of the language
implementations. After publication of the benchmark internally at Google, several
engineers produced highly optimized versions of the benchmark. While this whole
effort is an anectodal comparison only, the benchmark and subsequent tuning effort
might be indicatie of typical performance pain points in the respective languages.
