Two Lists containing an interface versus one List containing a struct with two interfaces

Question

I have two interfaces. ICacheHolder is going to be implemented by a class implementing the logic of an game object and IVisualizer which is going to be the visual representation.

public interface ICacheHolder
{
    void updateCacheWithCurrentState(int chachFrame);

    void resizeCache(int newSize);

    T getCacheFrame<T>(int cacheIndex, float interpolationToNext) where T : struct;
}

public interface IVisualizer
{
    void updateVisualization(ICacheHolder cacheHolder, int cacheIndex, float interpolation);
}

Every ICacheHolder connects to one IVisualizer object the relation is 1 to 1. I'm trying to determine if its better (performance/memory wise) to store them in two separate Lists or in one List as struct. Would make a big difference at all? Would there be boxing happening if I use the struct version? I recon the size of the list will be from 100 up to 1000.

Version 1:

public class CacheFramework
{
private List<ICacheHolder> cacheHolders = new List<ICacheHolder>();
private List<IVisualizer> visualizers = new List<IVisualizer>();
...
}

Version 2:

struct SimulationObject
{
    public ICacheHolder CacheHolder;
    public IVisualizer Visualizer;
}
public class CacheFramework
{
private List<SimulationObject> cacheHolder = new List<SimulationObject>();
...
}

Operations like Add and Remove won't be done very frequently. Only at the beginning of the game there might be a lot add calls.

Version 1:

private bool AddSimulationObject(ICacheHolder cacheHolder, IVisualizer visualizer)
{
    if (!cacheHolders.Contains(cacheHolder) && !visualizers.Contains(visualizer))
    {
        cacheHolders.Add(cacheHolder);
        visualizers.Add(visualizer);
        return true;
    }
    return false;
}

Version 2:

private bool AddSimulationObject(ICacheHolder cacheHolder, IVisualizer visualizer)
{
    int index = simulationObjects.FindIndex(
        delegate (SimulationObject simulationObject)
        {
            return simulationObject.CacheHolder == cacheHolder || simulationObject.Visualizer == visualizer;
        }
        );

    if (index >= 0 )
    {
        SimulationObject newObject;
        newObject.CacheHolder = cacheHolder;
        newObject.Visualizer = visualizer;
        return true;
    }
    return false;
}

The List will be accessed at least every frame through its index.

Additional info: Each class using ICacheHolder will contain a List<struct> with data like position, rotation or health. Each list element will be a snapshot in time. The target is it to move through time back and forth.

Edit 1:

Fixed error in AddSimulationObject Version 2.

As pointed out AddSimulationObject Version 2 could be:

private bool AddSimulationObject(ICacheHolder cacheHolder, IVisualizer visualizer)
{
    SimulationObject newObject = new SimulationObject { CacheHolder = cacheHolder, Visualizer = visualizer };
    if (simulationObjects.Contains(newObject))
    {
        simulationObjects.Add(newObject);
        return true;
    }
    return false;
}

But in this case I would need to make sure that cacheHolder and visualizer not appear in any other combination.

Edit 2:

I'm using Unity3D which supports mostly NET. 3.5

As pointed out it might be better to use a .NET collection with a faster lookup than List. Or if the list is sortable use List.BinarySearch.

Edit 3:

I'm going to use the struct version. I'm not jet sure how many lookups are going to be there. I might change to another .NET collection if its going to be an issue.

Answer 1

The Eric Lippert comment is very true. In this case there is no real need to even try and compare the performance difference, as the collections are so small, so no need to worry about cpu time.

Memory wise...list structures use contiguous memory blocks and only becomes a memory issue when they are really really big. (I mean millions.)

Only other suggestion: If every game cycle you are going to perform a search in those lists you could simply choose another structure that is optimized for lookups. Dictionary is a lot more effective at retrieving items as the find does a lookup from an index, whereas the list will perform a traversal of the items.

Answer 2

I would recommend you to use the struct approach, for two reasons:

• In .NET, structs generic type parameters are treated specially, and no boxing will occur.
• That approach will ensure by structure you have matching elements together. For me it feels like it's more easy to reason about.

So, when it comes to the question whether to use list of structs or struct of lists, I would certainly prefer using list of structs, even when it causes a little performance drop. In your case, I expect the list of structs version to perform better, however I cannot guarantee it. You can run profiling anytime. But one thing is sure: the performance difference is much smaller than the cost of the linear search in AddSimulationObject.