I'm rewriting the UnitCollection regression test for the old UnitCollection and the new one. It's pretty nifty right now but all it does is basically what the old one did, add and remove. I'd like to incorporate more operations, any suggestions?
Right now my std:: UnitCollection is within a second of the old one adding and removing a list of 6000 units.
I did notice that the old UnitCollection will return a unit that has been killed () if it's the first unit in the list. I've been debating to avoid that or not.
You should also keep some iterators around during the add/remove operations, like python would be doing.
The iterator doesn't really do much, so adding, removing and keeping iterators should be all you need.
As far as the killed() behavior, it doesn't seem to be making a difference... so perhaps killed units are removed from their unit collections, or it must be checking for it somewhere.
Unless it happens that the first unit never dies..
Advantages:
less code. Currently the code is about the same both in source and compiled, but UnitIterator will be losing much of the code currently residing in it, and UnitCollection will gain none.
Stable code. STL has had countless programmers crawling over it since it's inception, making the containers pretty much bulletproof in so far as they're defined to function. We can be pretty sure that if there is a problem with the lists/iterators, it's in our implementation, and not the list itself. My tests have shown that the old UnitCollection does exibit inconsistent behavior when dealing with lists > 10,000 units. Some listnode's are lost. The new one does not.
Maintainable. The new list consists of 3 classes, two iterator and a collection class. The code is straight forward in every member function except erase() in UnitCollection, of which is only semi-complicated. All of the list maintenance is done by STL.
logical. The iterator in the new UnitCollection is nothing more than an iterator in STL's containers. It operates just like them. The collection is _the_ list. The list doesn't really exist in a list of nodes that it has no real grasp over in entirety.
Reverse lookups. The list can access the iterators linked to it. Allowing reverse communication to the iterators from the list if need be, like when the list is deleted.
Disadvantages:
Overhead. The overhead of utilizing an abstraction (optimized may it be) layer of the list is limiting. Let me explain.
At 10,000 units, the new unitcollection is less than a second difference at randomly removing all those nodes with 18 concurrent iterators. What this means is that if i create 18 nested iterators all trying to randomly remove units from the list, the new list is less than a second from the old UnitCollection.
The speed difference gets smaller the less concurrent iterators are active. At a one to one test, the time difference is nil. At 15 it's less than half a second.
If we increase the list to 60,000 units, and the concurrent iterators to about 50, the time difference is about 1-1.5 seconds, with the new unitcollection being the slower one. This constitutes a very broken situation that would never really occur.
At worst, we'll see maybe a dozen iterators active on a single list at the same time, and at most a 10,000 unit list (a size not seen yet in vegastrike). In which case, the performance of the new unitcollection is nearly the same.
Now, the above all dealt with just erasing as fast as possible, all of the units in a list randomly. This involves traversing a great deal more than what you'll see in the game, and traversing is where the STL container i'm using (list) is bad at. Performance differences can be nothing but smaller for any cases not traversing as much as possible (you'll never see that type of activity in the game).
For all other operations tested thus far, the performance is the same all the way up to 60,000 units.
non-custom container: Since the container is built by other programmers, and is often compiler dependent. The eventual performance of the new UnitCollection will in the end depend on the compiler used to build vegastrike. It's hard to say what the performance differences could be from worst case compiler to the best, but if your compiler has such badly performing STL implementations, it's likely that the entire program will be horribly slow beyond making the UnitCollection class the limiting factor anyway.
Eventual API changes: The new Unitcollection is intended to mimic STL containers, not the old UnitCollection. This means eventually the python code will need to be updated to reflect the new unitIterator and UnitCollection api. For now, PythonUnitIter can act as a compatibility layer offering both sets of api's but steps will have to be taken to deprecate the redundent functions.
oh, btw, the performance test results I mentioned above aren't from the current "new" unitcollection. I have a local changeset that i'm readying for commit that will drastically change the performance of the UnitCollection to that of the results listed above.
I'm still currently trying to profile vegastrike to figure out the ancient stuttering problem. In my travels I noticed something strange in the total_war.py module
Inside the Execute function, we loop through all the units ...but do nothing with them. This becomes a huge problem as the list grows. Why do we do this?
I currently commented this loop out and UnitIterator::advance is called like 150 million times less.
total_war was written ages ago, and it was meant to be a stress test.
It's very possible that some python module (a mission) will end up going through all units each loop, so it is somewhat valid simulation to call UnitIterator. For example, patrol might want to loop through all units to see how close you are to them.
If creation and destruction of iterators is actually a problem, it might make sense to keep a cache of iterators at least to the main drawlist.
I don't think that the unit iterators from python are going to cause the problem... hopefully creating one new iterator during each call to python will not noticeably affect the speed or cause stuttering. But if it does, then that would be a huge problem.
I would leave it uncommented in the long term to keep that as a benchmark.
But I would still be interested to see how much of an effect that has on performance.
I noticed no difference, but the hits to the advance function decreased dramatically as far as the profile was concerned.
traversing every unit to see how close you are to them is a bad setup when we start talking about units numbering in the ten thousand range. There has to be a way to keep a local list of units within an arbitrary distance from the current unit within that unit. The same issue exists for missile explosions. All of this traversing every unit and checking works so long as we keep our list small. But bring that list up to 10,000 units, and you could have the fastest list in the world but if you gotta traverse the entire list multiple times a frame you're going to have serious problems.
Sounds like this might be one of the culprits for the slowdowns/stuttering that is being reported for massive amounts of ships just going around and fighting each other (I've experienced this a little too.)
I guess there really is no better way. But what we could do is for those types of checks, we utilize a const iterator so that the erase function isn't called to clear out a killed() unit. I can overload the = operator in constIterator to allow converting to a regular iterator once a match is found and we may want to alter the container or unit held in the const_iterator.
