For a discontinuous Galerkin-based simulation I need to store cell-based simulation data in memory. Since the order of the polynomial approximation $N_p$ may vary between cells, I wonder what the most efficient data structure would be, if the typical access pattern is a loop over all cells? These are the ideas I had so far:
1) Use an array of cell objects, each object with a pointer to its (individually allocated) simulation data array
Pro: Very easy to handle algorithmically, no headaches when pre-allocating memory for data storage, very easy to store topological relationships between cells (i.e. neighbor information), straightforward direct access of specific cells.
Con: Very (extremely?) slow when looping over all cells as there will probably cache misses every single time.
2) Use an array of cell objects, each object with a pointer to its simulation data array (memory pre-allocated and cell data stored contiguously)
Pro: Same as above. Also probably faster since data is now contiguous in memory.
Con: Still slower than just using arrays, since each cell access still requires the knowledge of $N_p$.
3) Use an array (or an STL container) for each set of cells with common $N_p$
Pro: Each container can contain the data contiguously, thus there will be many cache hits if iterating over $N_p$ first, cell second.
Con: Difficult if memory pre-allocation is desired. Random cell access using only the cell id becomes very expensive.
Does anyone have experience with one of the aforementioned methods, or has an even better alternative in mind? If you need more information on e.g. the data access patterns, please let me know.
Note: This question is similar to this one on Stackoverflow, but rephrased and simplified.