Lost in Translation: Production Code Efficiency
When software engineers re-implement a high-performance research prototype code, one often observes one to two orders of magnitude drop in performance. This holds even if both implementations use the same language. The gap is even wider when one goes from a simple language (e.g., C++) to a more sophisticated one (e.g., Java).
One of the root causes of this phenomenon is the misinterpretation by software engineers of what they learn in school. Theoretical computer scientists ignore constant factors for the sake of machine-independent analysis. Programming language researchers focus on compilers that automatically handle low-level OS and architectural issues such as memory management. Software engineering professors emphasize abstraction and re-usability. Many software engineers learn to ignore constant factors, rely on compilers for the low-level efficiency, and use generic primitives for re-usability. This is tempting to do as one has to worry about fewer issues when coding, and one needs to know fewer primitives and data structures.
However, in practice constant factors do matter, compilers do not always take advantage of computer architecture features, and generic primitives may be less efficient than the simple ones sufficient for the task. Ignoring these issues can lead to significant loss of computational efficiency and increased memory consumption. Power consumption also increases significantly.
In this talk we give several examples of inefficient program fragments and discuss them. These examples show that software engineers need to pay attention to low-level details when choosing data structures and programming primitives, and avoid some inefficient coding practices.
Andrew Goldberg is a Senior Principal Scientist at Amazon.com, Inc. His research interests are in design, analysis, and computational evaluation of algorithms and data structures, algorithm engineering, computational game theory, electronic commerce, and parallel and distributed algorithms, and complexity theory. His algorithms are widely used in industry and academia. Goldberg got his Ph.D. degree in Computer Science from MIT in 1987, where he was a Hertz Foundation Fellow. Before joining Amazon in 2014, he worked at GTE Laboratories, Stanford University, NEC Research Institute, InterTrust Technologies, Inc., and Microsoft Research. Goldberg received a number of awards for his research contributions, including the NSF Presidential Young Investigator Award and the ONR Young Investigator Award. He is a Fellow of ACM and SIAM.
Lunch available to talk attendees at 12:00pm
