2
\$\begingroup\$

I have a list of objects that must be updated after some time, but this time varies from object to object, and there are objects that don't need to be updated. So I firstly put all of them into a list of BaseObject, and if the object must be updated, it inherits the interface IUpdatable. The class that holds the list iterates over every object, checks if it inherits the interface and if so, the Update method is called:

public void Update() {
    _tick += deltaTime; // Here I increase the _tick by the amount of time that has passed.
                        // deltaTime = how much time since the last frame.

    if (_tick >= 5000) {
        // If _tick is bigger than 5000 (ms), then we do something here and
        // reset the counter, so we only do it again later, after 5 seconds
        DoSomething();
        _tick = 0;
    }
}

The problem comes when I have a lot of objects (and I will have), the system will waste time updating objects that doesn't even need to be updated, or won't do anything in the current frame, just increase a variable. So I created a kind of manager class, it allows me to register objects on itself and the manager will take care of calling the Update method when it is needed, instead of every frame. Here is how it looks like (I commented the max I could):

public class ObjectUpdateManager
{
    private readonly List<ObjectUpdateEntry> _entryList;
    private readonly List<ObjectUpdateEntry> _entriesToAdd;

    public ObjectUpdateManager()
    {
        // Initialize the lists
        _entryList = new List<ObjectUpdateEntry>();
        _entriesToAdd = new List<ObjectUpdateEntry>();
    }

    // We register the object with the interval that it will take to update
    public void RegisterObject(IUpdatable obj, float interval)
    {
        // We must check if there is a entry that already have the interval
        // requested, so find first on the main list
        var entry = _entryList.FirstOrDefault(x => x.Interval == interval);
        if (entry == null)
        {
            // Then find on the "entries to add" list, because it may not have been
            // added to the main list yet
            var entryToAdd = _entriesToAdd.FirstOrDefault(x => x.Interval == interval);
            if (entryToAdd == null)
            {
                // There is no entry with the interval requested yet, so we create a
                // new one
                step = new ObjectUpdateEntry(interval);
                step.RegisterObject(obj); // Here we include the object on the entry
                                          // so it will be updated
                _entriesToAdd.Add(step);
            }
            else
            {
                // The entry already exists, so we just include the object on the entry
                entryToAdd.RegisterObject(obj);
            }
        }
        else
        {
            // Same here, we just register as the entry already exists
            step.RegisterObject(obj);
        }
    }

    public void UnregisterObject(IUpdatable obj, float interval)
    {
        // This methods only finds the entry with the desired interval
        // and removes the object from it, if the entry is found
        var step = _entryList.First(x => x.Interval == interval);
        step?.UnregisterObject(obj);
    }

    // This method is called every frame
    public void Update()
    {
        // We iterate through every entry backwards, so we can
        // remove entries without creating aditional lists
        for (var i = _entryList.Count - 1; i >= 0; i--)
        {
            var entry = _entryList[i];

            // If the entry doesn't have any objects, we remove it
            if (entry.NumObjects == 0)
            {
                _entryList.RemoveAt(i);
                continue;
            }

            entry.CurrentTick += Time.deltaTime;
            if (entry.CurrentTick >= entry.Interval)
            {
                // The entry must be updated, so we reset the timer variable
                // and call the Update method. It causes every object registered
                // to be updated too.
                entry.CurrentTick = 0;
                entry.Update();
            }
        }

        // Here we just check if we need to add any new entries to the main list
        if (_entriesToAdd.Count > 0)
        {
            _entriesToAdd.ForEach(entry => _entryList.Add(entry));
            _entriesToAdd.Clear();
        }
    }
}

And the ObjectUpdateEntry (pretty straightforward):

public class ObjectUpdateEntry
{
    public float Interval { get; }
    public float CurrentTick { get; set; }

    private readonly List<IUpdatable> _objects;

    public int NumObjects => _objects.Count;

    public ObjectUpdateEntry(float interval)
    {
        CurrentTick = 0;
        Interval = interval;

        _objects = new List<IUpdatable>();
    }

    public void Update()
    {
        for (var i = _objects.Count - 1; i >= 0; i--)
        {
            if (_objects[i].Enabled)
            {
                _objects[i].Update();
            }
        }
    }

    public void RegisterObject(IUpdatable obj)
    {
        _objects.Add(obj);
    }

    public void UnregisterObject(IUpdatable obj)
    {
        _objects.RemoveAt(_objects.IndexOf(obj));
    }
}

My concerns are:

  • I created a heavy OOP based approach

    How can I simplify it? It seems too much heavy, and as I am developing a game, I need the things to be as fast as possible. I first through about creating a Dictionary<float, List<ObjectUpdateEntry>>, but just looking at it already makes it seems heavy. The float would be the interval, and the list would hold the objects that must be updated at this interval. The problem is keeping track of how much time has been passed and when I should call the Update method.

  • There are too much lists

    In the first implementation of the manager class, I had 3 lists (one for the main objects, other for the objects to include and another one for objects to remove), but I changed it to 2 after realising that I could change the list while iterating it backwards. Anyway, I through about using a array, but then I would have a limit of how much objects I could have, too much lists is a problem?

Observations

  • The list can be tiny, but will become big as the time goes;
  • I can't establish a limit, the amount of objects can be 10, 50, 3000, it's very unpredictable;
  • The objects change a lot the list, because they register themselves with an interval of 5 seconds, then after that they unregister and register again with an interval of 7 seconds, then 3, then 5, for exemple.
  • It is very likely to have two or more objects with the same interval, that's why I created the ObjectUpdateEntry and can't use Dictionary<float, ObjectUpdateEntry, as the dictionary can only have one key.
\$\endgroup\$
  • 2
    \$\begingroup\$ Been writing similar code recently... the classic approach is to use a Priority Queue (sadly no BCL implementation, but you can throw together a Heap in no time with the right motivation) for such scheduling (i.e. record the time of the next event, stuff it in a queue, and just pull from the queue until you reach the end of the current time frame). If nothing sensible has appeared by tomorrow, I might write up a detailed response when I'm not asleep. \$\endgroup\$ – VisualMelon Sep 16 '17 at 22:51
4
\$\begingroup\$

@Janos has outlined the possibility of using a PriorityQueue, which is absolutely worth investigating if the number of 'intervals' is large, so I'll discuss other stuff.

Note that whenever performance is a concern, you should always profile your code to determine where the tight spots are, and then profile again to determine whether your changes are actually helping your situation. For example, if you used a heap to track which elements to update, but it turns out that most of the elements are being updated each frame, then the overhead of managing the heap will far exceed the cost of iterating over elements that aren't being updated.

Your code is interesting because you lump all the elements that update with the same frequency together, which makes a lot of sense if you can get away with it (and it's a game, so that's basically a design choice).

'Heavy' OOP

This isn't heavy; it is very easy to understand. The interfaces make sense, and you've only got 2 classes here to think about. Lovely. I'd be inclined to better encapsulate ObjectUpateEntries at the moment, but that won't help performance.

Currently, you have the ObjectUpdateEntries stored in a list, so there may be merit in make it a struct (removes one indirection per access, which might remove an indirection at the machine code level; certainly will remove a little overhead on higher-gen (assuming these are long-living objects) collections). If these are added and removed regularly, then you could pool them (i.e. keep track of the end of the list manually, and leave the memory allocated to use when you need it). Obviously, using a struct has all the usual issues associated with mutable structs.

UpdateObjectManager.RegisterObject(IUpdatable,float)

There are a few things to note in this method (and UnregisterObject also). Firstly, you are comparing floats, which is a bit dodgy if any of them are computed values: something to be aware of.

After just discussing use of a List, I'm going to suggest you consider a Dictionary instead.

entryList.FirstOrDefault(x => x.Interval == interval);

This is a linear cost lookup, a Dictionary<float, ObjectUpdateEntry> would provide much better lookup times for non-tiny numbers of entries. I can't quite remember what the cost of enumerating Dictionary.Values is (needed in Update), but I think it's optimal, so shouldn't be a concern. This piece will only be a concern if there are many ObjectUpdateEntries and you regularly added to them; if not, then the benefits will be small (if not negative) and infrequent (not worth caring about).

UnregisterObject(IUpdatable, float)

This API isn't very nice: it means that the object has to know what it's interval is exactly, which means it probably has to store it. Solving this would be non-trivial, and with the current architecture probably require a Dictionary<IUpdatable, ObjectUpdateEntry> or passing back a handle of some sort from RegisterObject.

UpdateObjectManager.Update()

As you don't need to maintain the order of _entryList, you can make each removable a constant cost rather than linear cost by moving the last item in the list into the position of a removed item.

var last = _entryList[_entryList.Count - 1]; // grab last element
_entryList[i] = last; // copy last element into 'removed' space
_entryList.RemoveAt(_entryList.Count - 1); // remove last element

RemoveAt(int) requires shifting all the elements with a higher index down an index, and if this list is long this is a significant operation. I'd consider performing this removal elsewhere (e.g. when you unregister the last IUpdatable), because it is not immediately apparent that this occurs otherwise.

I don't see the point of _entriesToAdd... why not just add them when they are created? This removes one of the lookups in RegisterObject. It is also a little odd that they are only added after updating the entries, and not before.

It is possible that Time.deltaTime is greater than the interval, which suggests that sometimes 2 updates should be performed per tick; in the current implementation they will be done instead exactly once per tick. I would assume this behaviour is acceptable (since this is the highest trick granularity anyway), but it should certainly be documented for the user.

Furthermore, the implementation here suggests a significant possible optimisation, IF Time.deltaTime never changes. Because you simply reset CurrentTick, you can instead translate intervals into integers (i.e. number of ticks between update), and perhaps massively reduce the number of ObjectUpateEntries (e.g. if there are many which have different intervals all less than Time.deltaTime, they will all be lumped into one with interval 1.

If you can provide further constraints on the max interval (e.g. no more than 256 or some other number) then you could pool all of these and never have to allocate them on the fly, and get true O(1) lookup by just stuffing them in an array where the index is the interval. This will only be of use if you expect a wide variety of intervals. (Side note: Lists are thin and fast, unless you know they are presenting a concern, you shouldn't worry about managing your own arrays; the benefit here is the direct lookup time rather than anything else).

ObjectUpdateEntry.Update()

Nothing to say here, except that I have read that iterating backwards has a habit of confusing the JIT and can reduce performance. Probably not a concern.

ObjectUpdateEntry.UnregisterObject(IUpdatable)

You are using a List again to store objects, so you can improve the performance in the same ways described above. Alternatively, a HashSet may be in order: similar concerns to using a Dictionary (measure measure measure), only an issue if the list regularly changes.

Style

Looks great, exposed and internal; inline documentation (///) is always appreciated.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for the detailed review! I tried to switch to struct but it introduced more problems so I will continue with classes as they are more flexible. I wanted to, but I can't use the dictionary the way you described, I updated the question with more details. I use the _entriesToAdd because I can't add new entries to the main list while iterating it, so I must do it outside the loop. Creating a pool for the intervals seems very interesting, and it can be even good for small intervals (like 0 - 100), correct? \$\endgroup\$ – Rafael Almeida Sep 17 '17 at 16:41
  • \$\begingroup\$ I will change the list on ObjectUpdateEntry to a HashSet and remove the backward iteration, it have no meaning there anyway. And rethinking about the pool, it may not be so good because the intervals are very different, like 10, 3, 320, 34, 270, so creating a limited list isn't aplicable. \$\endgroup\$ – Rafael Almeida Sep 17 '17 at 16:44
  • \$\begingroup\$ Oh nevermind, I can't change it to HashSet because I need the list to iterate backwards, as I remove objects from the list while iterating it. \$\endgroup\$ – Rafael Almeida Sep 17 '17 at 16:50
  • \$\begingroup\$ @RafaelAlmeida thanks for the observations! You only remove from the List in ObjectUpdateEntry in UnregisterObject, and you don't need to iterative through it in any particular order, so a HashSet should still work for that (not necessarily faster). Pooling entries may work fine; if they are all different then the array proposal will probably cause more harm than good. You are right that using a Dictionary in UpdateManager won't (easily) work. I still don't see the need for _entriesToAdd, you aren't adding while iterating (or is this used from many threads?) \$\endgroup\$ – VisualMelon Sep 17 '17 at 16:58
  • \$\begingroup\$ That's because I actually didn't show how the registers/unregisters are actually made, my bad. An object registers itself on the manager, then after the interval, it is updated (notice that we already are inside the loop of both ObjectUpdateManager and ObjectUpdateEntry). In the Update method of the object, it unregisters itself (then the UnregisterObject is called in both classes) and registers itself again with a different interval (then RegisterObject is called in both classes, thus having the need to have a list so I don't modify the list while iterating it). \$\endgroup\$ – Rafael Almeida Sep 17 '17 at 17:24
3
\$\begingroup\$

As @VisualMelon wrote in a comment, it seems you're looking for a Priority Queue, implemented as a Min Heap, where entries are ordered by the time they need to be updated. By the property of the heap, the next item will be the one to update next.

So, given a PriorityQueue<Job> pq, you could have this kind of code to check if there is something to update, and if yes, then remove it from the queue and perform the update:

if (!pq.IsEmpty() && pq.Peek().TimeToUpdate < now) {
  pq.Poll().PerformUpdate();
}

Your code will be much simplified. All you need is heap data structure to implement it, and when adding a Job to the queue, calculate the future time-to-update appropriately.

\$\endgroup\$
  • 2
    \$\begingroup\$ Just to add, I think the time complexity is in favour of a linear-pass (it's O(log n) to dequeue from a heap rather than O(1) to set a variable) but if the number of objects is sufficiently large and the rate of update sufficiently low then the heap wins out. A continuous queue also has the nice benefit of performing updates in the right order, which may be useful; but, introduces complexity into the implementation if you need to delete queued messages. \$\endgroup\$ – VisualMelon Sep 17 '17 at 8:15
  • \$\begingroup\$ Great to learn about the Priority Queue, never used one before. I tried to implement it but seems that I must define a limit to the nodes. Unfortunately I don't know how much objects I will have, so I think this solution may not work for me. I updated the question with more observations about the problem. Thank you! \$\endgroup\$ – Rafael Almeida Sep 17 '17 at 16:16
  • \$\begingroup\$ @RafaelAlmeida no, the concept of priority queues doesn't have such limitation that you describe. I don't see anything in your added observations that would rule out using a priority queue. \$\endgroup\$ – Stop ongoing harm to Monica Sep 17 '17 at 16:36
  • \$\begingroup\$ When making an allocation for a growing heap, we just increase size by factor of k = 2 (or any k > 1.0) so amortized cost of insert remains O(log n). Also, if you have a reference to an entry you want to delete, that is straightforward. Either (1) write a tombstone so the entry is ignored when it expires naturally, or (2) update its deadline to be in the past (which involves re-heapifying) and immediately pop it from the front. \$\endgroup\$ – J_H Sep 17 '17 at 16:58
  • \$\begingroup\$ @JH that last part assumes a more complicated heap implementation ;) yeah, it's certainly possible, but more effort (I for one am too lazy to test such a thing). Tombstones certainly work also, but again it means you need a reference table (added complexity) and/or some other twiddling. The first part, I wasn't referring to allocating the Heap, but the cost of rearranging it whenever you pop a value (i.e. every update involves a Pop,O(log n), the OP's code has a constant time 'requeuing') \$\endgroup\$ – VisualMelon Sep 17 '17 at 17:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.