The array is one of the most used data structure. It consists of a collection of items of the same type, arranged side by side in computer memory. The number of those items is called the size of the array. An array of four items would be stored in computer memory as below.
In computational physics, arrays might be used to store measurements at different positions in time or space. When sampling the pressure of a system every \(\Delta t\) from time \(t_0\) to \(t_0 + n\Delta t\), it is typical to use an array of size \(n+1\) such that \(\verb+p[k]+\) is the pressure of the system at time \(t_k\). Moreover, most mathematical objects such as vectors, matrices and tensors are stored in computer memory using arrays. Introduced in the 1970s, vector processors were optimized for array processing. They were used in supercomputers such as the various Cray plateforms. Today, whether you are reading this on your computer, your tablet or your phone, the processor that powers your device is most likely optimized for array processing. In most programming languages, such as Fortran, Python and C#, arrays are first class citizen. Unfortunately, in C, arrays are extremely fragile as they are closely related to pointers. To overcome this weakness, the C++ standard library provides array containers designed to hide this complexity. Unfortunately, this complexity is still there for compilers and might prevent various optimization.
This series of articles is designed as a journey through the various techniques and tools a programmer might use to debug and optimize his programs based on arrays. We’ll restrict ourselves to the most populars compiled languages used for number crunching: Fortran, C and C++. As many useful features are not provided by the languages themselves but by their implementation, we’ll focus on the latest versions of the following compilers as of september 2014:
- GCC 4.9.1: The compiler suite from the GNU project is the de facto standard compiler on most Unix operating systems, including different flavors of Linux. It is also available on Mac OSX and the Windows plateform. We will use it to compile Fortran, C and C++ programs.
- LLVM/Clang 3.4.2: Started as a research project at the Univeristy of Illinois and subsidised by Apple, LLVM is the default compiler on Mac OSX and iOS devices. It is also available on Linux and Windows. We will use it to compile our C and C++ programs.
- Intel Composer XE 15.0.0: Highly optimized for Intel processors, this compiler suite is available on Linux, Mac OSX and Windows. We will use it to compile our Fortran, C and C++ programs.
The various benchmarks will be done on a MacBook Pro (late 2013), a laptop powered by the Intel Core i7-4850HQ processor. It comes with 4 cores, 6MB of cache and the SSE4.1/4.2, AVX2.0 set of vector instructions.
The outline of this series of blog posts is:
- Memory management: We’ll go through the definition of static, automatic and dynamic arrays. They differ in the way they allocate memory, which has a paramount impact on performance.
- Bound checking: …
I recommend that you run the pieces of code in the following articles through your favorite compiler. Most tools and optimizations techniques presented here might depend on the compiler and might change in future releases.