Linked List vs Vector – Insert/Remove Performance Comparison

I hope it's ok to answer my own question. I believe I have found the optimal (without overcomplicating the problem) data structure for my problem. There was at least minor idiocy on my part for not recognising this earlier. The data doesn't need to be accessed by (x,y,z) but instead by (x, y, range of z (say 0 - 3)). This give a C++ struct as follows:

struct node {
  struct node *next;
  int zGroup;
  int z;
  50 bytes of misc data };

I can then address this through a 3D dynamic array (vectors):

vector< vector < vector < node* > > > Data;

Any given Data[x][y][zGroup] points to the first element of a linked list, the entirety of which is needed every time one element of it is needed. No value of this array is NULL, every one contains a linked-list of at least one element.

The third dimension of the array - the zGroup has jagged dimensions, but with dynamic arrays this isn't an issue. Given the data and computations being performed on it, I know that the max x and y values are set when the file is read and do not change, neither does the number of z groups on any given (x,y) line, the actual z-values of nodes may change, but they will remain inside the same z-groups, giving a constant-sized, fully populated array.

With the way that the file is structured it is also easy enough to page it in and out of memory if I am brought to do this with much larger data sets.

Just off the top of my head:

1. CPU performance is not the only thing that affects compile times.

2. Benchmarks do not always take into account performance factors that affect real programs.

3. Cache affinity can be a larger factor than CPU speed.

4. Compilers don't always exploit concurrency mechanisms effectively.

5. In general, programs like compilers can be written in such a way that they exploit (or fail to exploit) specific CPU characteristics.

6. Concurrency mechanisms have overhead. If the software is not getting any benefit from the concurrency offered, the result is a net negative.

In short, it's complicated. A highly complex task like compilation is not always well-modeled by benchmarks. You have to consider other real-world factors that affect overall performance, like seek times on hard disks and the manner in which the code is written.

For a simple, but rather dramatic example of this, see here.