1
\$\begingroup\$

I'm working on an apllication that needs to process a lot of objects in realtime. I've separated the logic from the UI so that it isn't as much of a mess. The basic idea is that every tick I'm trying to populate a list of objects to process and once they are processed I update the UI accordingly.

I've written this collection class for use in the main processing loop. Here is the reasoning behind some of my decisions:

  • The objects are processed sequentially in a loop. I only care for fast sequential reading so I've decided to use arrays at the base of it all hoping to get some kind of cache hit benefit.

  • The maximum amount of objects is known at compile time so I've tried to avoid rapid heap allocations by pooling my data objects. I allocate a maximum amount but only use the amount that is active.

  • I needed a way to correlate the logical objects with the presentation layer, so I've decided to use identifiers. These identifiers allow me to know what actual UI object the data belongs to.

Through basic stopwatch benchmarking I've arrived to the following solution:

class FixedCapCollectionIntGuids<T> where T : struct
{
  public T[] m_array;
  Dictionary<int, int> m_guidToIDs;
  int[] m_idToGuids;
  int m_capacity;

  public int Size { get; private set; }

  public FixedCapCollectionIntGuids(int capacity)
  {
    Size = 0;
    m_capacity = capacity;
    m_array = new T[capacity];
    m_guidToIDs = new Dictionary<int, int>(capacity);
    m_idToGuids = new int[capacity];
  }

  public T this[int key]
  {
    get
    {
      Debug.Assert(key < Size, "Illegal read");
      return m_array[key];
    }
  }

  public void Add(T value, int guid)
  {
    Debug.Assert(!m_guidToIDs.ContainsKey(guid), "Double insertion");
    m_array[Size] = value;
    m_guidToIDs[guid] = Size;
    m_idToGuids[Size] = guid;
    ++Size;
  }

  public void Remove(int guid)
  {
    Debug.Assert(m_guidToIDs.ContainsKey(guid), "Not found");
    int i = m_guidToIDs[guid];
    int lasti = Size - 1;
    int lastGuid = m_idToGuids[lasti];
    m_array[i] = m_array[lasti];
    m_guidToIDs.Remove(guid);
    m_guidToIDs[lastGuid] = i;
    m_idToGuids[i] = lastGuid;
    --Size;
  }
}

Please try to ignore the dumb naming, this is WIP so I didn't put much thought into what the best names for variables and classes are at this point.

My benchmarks show that this approach appears to be faster than just having a dictionary for reading(presumably because an array is cache friendlier), but slower for adding\removing(presumably because I'm maintaining 3 separate collections instead of one). I'm somewhat fine with this because addition and removal is going to be less frequent than iteration, but I'm still wondering whether I've solved the problem in a stupid way or not. Can it be done better?

\$\endgroup\$
  • \$\begingroup\$ What do you need the dictionary and the other array for? You're not using them anywhere. All you are doing is assingn values to them but you never read them. \$\endgroup\$ – t3chb0t Mar 15 at 12:24
  • \$\begingroup\$ Not quite. Look closer at the code of the Remove function. I get the index of the data array from the specified guid using the dictionary. Without the dictionary I can't identify where the object is in the array. The other array is the reverse of the dictionary - it lets me quickly identify which guid the object at index has. Otherwise I would need to iterate the values of the dictionary which I believe is slower. \$\endgroup\$ – CodeMolester69 Mar 15 at 12:37
  • \$\begingroup\$ "My benchmarks show that this approach appears to be faster than just having a dictionary for reading" That would probably depend on what kind of data you're storing as well. How did you benchmark, or can you share a representative example of your input? \$\endgroup\$ – Mast Mar 19 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.