Not Your Father’s Complexity


The traditional proxy for the duration of program execution, the number of instructions executed, is being made inadequate by the increasing importance of caches in modern processor architectures. A program that is sympathetic to caching requirements, for example by respecting data and instruction locality and minimising false sharing, will outperform another that may execute many fewer instructions if it uses cache less efficiently. What does this mean for the Java programmer? The Java Collections Framework, used daily by every working Java programmer, is interface-based: its design assumes that you will choose an interface—Set, List, or Map—according to the functional requirements of your application, and an implementation of that interface guided by the expected usage scenarios. But we can’t any longer use algorithmic complexity—the big-O characteristic of an algorithm–as the only, or even the main, way of choosing between collection implementations. In this talk we’ll look at some common Java collections in the light of this new way of judging efficiency, and explore the implications for the working Java programmer.