moving to std::list ....with any luck

Post by **safemode** » Tue May 29, 2007 3:00 am

That's a possibility.. Though I check for end of list in my erase function both in UnitIterator and UnitColleciton.

My only guess if it's not my own functions at fault, is that the python code is Copying the UnitIterator object, erasing the current element with one copy and then trying to erase it again with the other. This in certain situations could cause my erase function to allow the iterator to make it to std::list::erase ....how it handles being sent an invalid iterator is unknown to me. I would think it would handle the error gracefully, not try to free it regardless.

In any case, the changes i made to UnitCollection in the last patch are definitely bugfixes.

EDIT: I have some more changes i am pretty sure are fixes as well, but it doesn't fix the segfault in privgold. No issues at all so far in data4.x though.

Post by **safemode** » Tue May 29, 2007 3:20 pm

Couple things i've had questions about regarding unitcollection

1. Why does UnitIterator's postfix and prefix ++ operators return Unit* rather than UnitIterator& ? That doesn't make much sense.

2. I really dont see the point in having a wrapper function in the Unititerator class. I'm going to just put all the code in GetNextValidUnit in advance(). Guess that wasn't really a question.

3. Is it even possible to kill then NULL (destroy) a unit without doing so through the list? I have a lot of code designed to check to make sure the unit in the list isn't null, but it doesn't seem like it should be possible to NULLify the unit until hes' out of the list, since the list would keep at least 1 reference active. So I should be able to remove all checks for null (they seem to have been holdovers from the old UnitCollection class where null meant the end of the list)

On a different topic, why do we not allow linking to the dist libboost if available? Is there some sort of modification done to our local copies? It seems to be a hold-over from when libboost was rare on a system.

Post by **ace123** » Tue May 29, 2007 10:33 pm

I don't understand all the pecularities of the existing UnitIterator... really, I don't understand why it can't use a normal STL iterator class instead of making our own.

The good thing about taking out the NULL checks is that it will crash if we have such problems.

The boost library was a remnant of when libboost was older (the glorious days of GCC 2.95).

But that's not the only problem... certain versions of Boost are not compatible with other versions.

In addition, not all versions of boost work with all compilers... there may be internal compiler errors at times, so it's good to have more options.

Anyway, while I do not see a really good version to take boost out, it makes sense to provide the option, such as --with-boost-libs and --with-boost-includes=

Post by **safemode** » Tue May 29, 2007 10:59 pm

Some further optimizations and cleanups to the UnitCollection class.

back out all previous unitcollection related patches (patch to vanilla) and apply this .

Latest Unitcollection Patch

An additional file is touched with this patch from last patches. It appears that base_maker.cpp redefines a function from UnitCollection::UnitIterator to be empty. Not sure why as it doesn't call it anywhere in that source file. I removed it.

I feel comfortable now with this patch to have it represent what i'd like for inclusion. Gemini Gold aside, i've seen no bugs related to the class in svn of data4.x. And the gemin gold bug isn't reliably reproducable.

I have noticed a really annoying bug especially in the Enyo system for data4.x . I've noticed that my SPEC drive goes crazy and puts me in reverse at fantastic speeds. My nav computer tells me to go in one direction, but the distance between me and the target increases until i "wrap" around and then it starts going down... and i'm never off the cross-hairs. My regular speed also sometimes goes nuts and allows me to go very fast.

I'm not sure if these bugs i experience are my fault or not, I assume not because i dont know how they would correlate.

Post by **safemode** » Wed May 30, 2007 12:00 am

The only reason we need a UnitIterator instead of using std::list::iterator is because the python code doesn't check for Killed and it requires certain functions, (functions that should be in UnitCollection only)

Removing UnitIterator would be possible but not without heavy modifications to python and other parts of the base source.

As it is now, we basically use stl iterator's anyway. We only slightly wrap it in the UnitIterator class. I believe the overhead is minimal compared to some of the other stuff we do that wastes cycles (stdout/stderr output everywhere).

My last patch for UnitCollection should be what you review for inclusion into svn. It represents about all I can do while remaining 100% backwards compatible. I really need to grab the last release version of Vegastrike and apply this patch and test to compare stability and bugs.

Oh,
I like the idea of --with-boost-libs etc.

Post by **safemode** » Thu May 31, 2007 11:24 pm

OK, UnitCollection seems squared away. I can find no bugs related to it and nobody else has either as far as I know.

I'm moving on to unit_generic.cpp/h now. I really want to clean this file up and get as much code out of the header as possible, fix it's namespace pollution and remove any headers that aren't actually needed. It's really hard to tell with patch files if indents are really tabs or just spaces... if anyone finds in my UnitCollection patch indents that aren't tabs, please let me know. I may have to use a different editor.

I'm just going to move along through src/cmd and start cleaning up files now. I intend to create a separate patch for each pair of source files. I'll start a new thread for that endeavor. This one will be for any further std::list issues.

Post by **safemode** » Sun Jun 03, 2007 4:02 am

Ok, During my cleanup of unit_generic I decided i didn't like PlanetIterator and those stupid virtual iterators in iterator.h So i fixed it.

This is the new incarnation of UnitCollection::UnitIterator. Well, not really new so much as enhanced.

What really sets this off from previous versions is that it's no longer 100% backwards compatible. I just had to fix the retardedness of the postfix and prefix ++ operators. We have a function already that does what the code that used the ++ operators wanted, next().

Anyways, Here is the patch. It should be against the latest svn pull.

(EDIT:)
I removed this patch because it was incomplete. Try next patch instead.

stdlist_unitcollection_6-2-07.patch

It removes all mention of iterator.h in headers and source files. It changes any instances of UnIterator to un_iter. It changes any use of Unit* = ++un_iter to Unit* = un_iter.next() and it modifies the UnitCollection::UnitIterator/ConstIterator classes to have virtual functions for PlanetIterator (though nobody seems to use PlanetIterator anyway). It also makes some minor updates to the ++ operators in UnitIterator.

In any case, I highly recommend checking it out. It should be the last change to the patch for a while as i'm going full tilt into cleaning up unit_generic from now on.

Edit: Oh btw, make install-strip automatically strips all bins. I'm just so used to "make install" stripping on it's own. Definitely a good target to know about when developing.

Post by **safemode** » Sun Jun 03, 2007 6:58 pm

The last patch was incomplete. it left the inline function in unit_generic.h

Try this one instead (as posted in janitorial thread)

stdlist_unitcollection_6-3-07.patch

that should be it for UnitCollection for a while (for real this time).

Post by **safemode** » Thu Jun 14, 2007 4:44 am

the UnitCollection patch is available on svn now. you can grab it at

https://vegastrike.svn.sourceforge.net/ ... /safemode/

rev 10977 if you just want the UnitCollection std::list patches.

Post by **safemode** » Sun Jun 17, 2007 5:17 pm

I've merged my UnitCollection patch into the trunk, so you can get it when you svn grab the trunk now.

During the week i'm going to be making some changes in my branch to UnitCollection. I plan on making the iterator's do just that, iterate, nothing else. I want them to be as light weight as possible. The UnitCollection class will have all normal std:: type container functions. end(), begin(), clear(), erase(),insert(), etc. Plus a couple of the convenience functions that lots of python code uses in it.

What this means is that python and other code will have to operate with UnitIterator's like they would a std::iterator. *iter for value, ++iter to increment, etc. If they want to remove it they'd have to call UnitCollection::erase(iter) and such.

I'm hoping that this can reduce the cpu intensiveness of all our tight loops dealing with UnitIterators, mainly by reducing the size and complexity of our UnitIterator class which gets created much more often than UnitCollection.

What i really need to do is profile the code a bit and find out where all our cpu time is being spent during unit creation and deletion.

Post by **safemode** » Wed Jun 20, 2007 3:05 am

In an effort to lessen the weight of UnitCollection and UnitIterator, i've decided to start breaking backwards compatibility.

I'm heading towards my initial goal of making UnitIterator just simply iterate. This should make it lighter and faster to create/destroy. Then i want to reduce the functions in UnitCollection

rather than prepend and append and preinsert and such I'd like to make it more of an std like container.

push_front, push_back, insert, erase, remove, clear, size, splice, begin,end,empty, and a couple additional functions outside of what an std container would have but are necessary for our class.

I'll change all the in-source code to use the new functions as i change them over, and i'll make patches and possibly geta branch of data4.x using it as needed. I may make a compatibility class for PythonUnitIter that can be selected at compile time so that older mods can use the newer vegastrike (though without any possible benefits from being more streamlined and such, since the pythonUnitIter compat class would have to implement those functions no longer existing).

I expect to be making a pretty big svn branch commit to safemode within the week.

charlieg · Post by **charlieg** » Wed Jun 20, 2007 12:59 pm

When you have gotten further in such work, I'd like to see this be organised into some kind of preview release (combined with rebalanced work from SVN) so people can try it and stress test it a bit.

Post by **safemode** » Thu Jun 21, 2007 12:33 am

you can "preview release" it on the svn, i linked it on the janitor thread.

plus, most is already in the SVN head.

charlieg · Post by **charlieg** » Thu Jun 21, 2007 1:32 am

There's no way I'm building SVN myself. I'm too busy to get into all that just to playtest a game.

Post by **safemode** » Thu Jun 21, 2007 2:12 am

Making you a binary would require dist info, version, etc. Or ask your dist to build an svn pkg.

In any case, it only takes 14 minutes on a somewhat modern computer.

Post by **safemode** » Wed Jul 25, 2007 4:51 am

update to UnitCollection:

UnitCollection, in it's current incarnation utilizes a lazy removal scheme somewhat like the original unitcollection. this eliminates almost all of the additional overhead compared to the original unitcollection.

The current UnitCollection utilizes 4 containers. 1 static vector, containing a list of units that are to be unref'd. 1 vector containing a list of positions in the list to be removed. 1 std::list containing the collection. Finally, 1 vector containing all the active iterators against the list.

The good part is most of those aren't used in the most common operations. Erasing being the exception. Right now, even with all these container members, the new unitcollection operates at almost exactly the same speed as the old unitcollection, even with a list of 10,000 units.

See the UnitCollection testing thread on the other advantages / disadvantages of the current UnitCollection.

Basically, I wanted to let everyone know that eventually I plan on deprecating most of the member functions of UnitIterator.

For now though, it seems that UnitCollection has finally stabilized and streamlined (more room still avail). I plan on moving on to other areas to work on. Please report any bugs on svn pulls >= 11143

Post by **loki1950** » Wed Jul 25, 2007 3:04 pm

Thx for the heads up safemode

Enjoy the Choice

Post by **safemode** » Thu Jul 26, 2007 3:57 pm

crap. I just realized I dont need a static list of removed units. I can just unref them when i null them in the list, I automatically clean the list when my unitIterators get down to 1 or less active. I do this in the UnitIterator destructor. This probably means i can get rid of the removedUnits vector and code related to it. I forgot that UnitContainer holds a ref, so unreffing on list "removal" wont cause undefined pointer accesses in python land.

I came to this conclusion after seeing what seemed to be regular ships flying around jumppoints, but was unable to shoot them. It seems that by not UnRef()ing them when I nulled them in the main list, some code continued to use the pointer it retrieved prior to nulling. This seems to indicate a bug in python, utilizing a unit pointer across frame maybe... just a guess.

In any case, when i get home i will make some changes and comit if things are good. Should speed up things even more too.

Post by **safemode** » Sun Jul 29, 2007 7:33 pm

There was an issue that wasn't being handled when the first position of the Unitcollection was "removed" but not actually removed. This would mean createIterator() would return an iterator that had a NULL unit. Now it doesn't do this. createIterator() will cycle through the list until it finds a non-null unit or the end(). Performance shouldn't really be effected at all. I also had to fix some privatization issues with unitcollection and unitIterators. I included two new functions to Unitcollection, front() and back(). They do what you would expect in an std:: container.

I'm currently experimenting with making various commonly used small functions inline. I'd really rather not have any implementation in the header file but in this case, the frequency of the function calls becomes a speed factor.

Post by **safemode** » Sat Aug 04, 2007 7:37 pm

I increased the performance of UnitCollection yesterday. There is still some room to spare, since it's not -quite- as fast as the old UnitCollection for advancing through the list ...mostly for one reason. Removed iterators are nulled, not removed, so that you still have to traverse null/empty positions until such a time as they get removed (right now that's when the number of iterators to the list is 0).

Basically, I'm trying to figure out a way to auto-clean the list without increasing the runtime of every call to advance. Once the list is in the tens of thousands of units, and there are still multiple pythonUnitIter's active in it, my collection becomes significantly slower than the old one, since i can't remove positions. I'm hoping to squash this problem this weekend. It's a very frustrating little issue that may need to be solved by creating an "iterator reference" in Unit. This will allow UnitCollection to reclaim and really remove positions from the list as soon as possible automatically, with very little overhead. Since it's likely to occur as needed, rather than all at once, it shouldn't impact latency during gameplay either.

Note: You will never experience that type of load on UnitCollection in any imaginable gameplay in the near-far future.

Post by **safemode** » Sun Aug 05, 2007 1:04 am

Well, profiling vegastrike is fun. But, after a couple days of some fairly major behind the scenes changes to UnitCollection, and UnitIterator i've come to my current incarnation.

The New UnitCollection/UnitIterator is now _faster_ than the old unitcollection at advancing through the list and handling the removal of units from it.

the old UnitIterator::advance() took roughly 3.25772880481122e-08 seconds per call to run.

the new UnitIterator::advance() takes roughly 2.84906531687001e-08 seconds per call to run.

These numbers were done on an absolute worst case scenario for the size of the list. That is to say, it was done on a modified total_war_python.mission file where every frame hundreds of ships were added. In both cases, advance() was allowed to be called for about 215860000 times.

I'll be making a commit to my branch shortly...after some tests and then sync to svn head.

Post by **ace123** » Sun Aug 05, 2007 5:50 am

That's really good to hear.

About the pausing... that is quite annoying. But that has been around for a long time...
Now it's possible that the intermittent slowness is being caused by python scripts ...
Unfortunately I don't know how to tell what is causing it, since it is probably too infrequent to be noticed by profiling.

Another possiblity is related to collisions. The collision system is organized into pools, where the slowest targets are spread out over 64 or 128 physics frames.
Still, I don't think this is the problem here either, since this should spread them out more, not less... unless they all get piled up once ever 64 frames or something.

Post by **chuck_starchaser** » Sun Aug 05, 2007 6:22 am

I thought I heard they were randomized so they never piled up. Though, randomization would probably just randomize the pile-up's

I once offered Klauss an idea I came up with years ago, working on something similar. Essentially, having only powers of two time spreads, and having the power of two frequencies phase shifted. Say there were 4 update frequencies, for simplicity, f_fast, f_notsofast, f_slow and f_prettyslow events or updates, and have a full period of 16 physical frames that repeat: t00 to t15...

Code: Select all

t00
t01
t02
t03
t04
t05
t06
t07
t08
t09
t10
t11
t12
t13
t14
t15

t16
t17
....

First you fill all even numbered frames with f_fast.

Code: Select all

t00 f_fast
t01
t02 f_fast
t03
t04 f_fast
t05
t06 f_fast
t07
t08 f_fast
t09
t10 f_fast
t11
t12 f_fast
t13
t14 f_fast
t15

t16 f_fast
t17
....

Then you fill in every other odd number with f_notsofast.

Code: Select all

t00 f_fast
t01  f_notsofast
t02 f_fast
t03
t04 f_fast
t05  f_notsofast
t06 f_fast
t07
t08 f_fast
t09  f_notsofast
t10 f_fast
t11
t12 f_fast
t13  f_notsofast
t14 f_fast
t15

t16 f_fast
t17  f_notsofast
....

Then you fill every other vacant slot with f_slow.

Code: Select all

t00 f_fast
t01  f_notsofast
t02 f_fast
t03   f_slow
t04 f_fast
t05  f_notsofast
t06 f_fast
t07
t08 f_fast
t09  f_notsofast
t10 f_fast
t11   f_slow
t12 f_fast
t13  f_notsofast
t14 f_fast
t15

t16 f_fast
t17  f_notsofast
....

And so on as many octaves as you want to go.

Code: Select all

t00 f_fast
t01  f_notsofast
t02 f_fast
t03   f_slow
t04 f_fast
t05  f_notsofast
t06 f_fast
t07    f_prettyslow
t08 f_fast
t09  f_notsofast
t10 f_fast
t11   f_slow
t12 f_fast
t13  f_notsofast
t14 f_fast
t15        ....f_prettydamnedslow

t16 f_fast
t17  f_notsofast
....

This requires to set frequencies only at powers of two; but you're guaranteed no pileup's. Another good feature about it is the good transitions it makes when switching frequencies. Say you have a unit in the notsofast pool, and you want to speed it up:
Suppose it has just been updated at frame t05. It's previous frame had to be t01, which is 4 frames earlier, of course. Now you decide to speed it up to the fast pool. Just skip the next frame, t06, and slate it for the next f-fast frame after, which is t08. So it enters the new pool at t08 and now it gets updated every 2 frames. Notice that during the transition, it waited 3 frames (between t05 and t08), so it went like 4, 4, 4, 4, 3, 2, 2, 2, 2...; nice and smooth shift.

It also codes very efficiently, because the time table can be built as a 16 or 32 or 64... -entry switch( frame_number & mask ) statement. A switch statement of this nature compiles to a computed jump, which avoids polluting the branch prediction cache with inherently unpredictable conditional branches.

Post by **safemode** » Sun Aug 05, 2007 2:51 pm

First off, what determines a slow unit? Is it just processed less frequently than "fast" units? If it's got something to do with the time it takes to process a physics frame for it, how do we know how long that is going to take before hand to categorize it?

What i'm getting at is that all it takes is one function to take too long during a physics frame to hang the game. we have no way of pre-empting a physics frame so that we keep strict latency. And so far, nobody has profiled the game with a program capable of reporting back not only avg times in functions, but the max time in that function.

There is a function that is spiking ...or it's python, unless this slow unit/fast unit thing has something to do with the time it takes to process a physics frame...and they're getting too many in a row.

In any case, this is all off-topic.

Post by **chuck_starchaser** » Sun Aug 05, 2007 3:13 pm

Very true, safemode; sorry for the OT-ness; just that Ace mentioned the possibilities of pile-up's. And since you're asking, I'll answer what I meant, wile still OT: The physics updates, and apparently collisions too, are not computed at every frame for every unit, as that would be too much computation. The last time I looked at the code there was this "physics atom" thing, which determined the rhythm of the updates based on some heuristics. The times were continuously variable, though; (well, continuous integer counts of frames); and so there was the opportunity of, once in a while, too many units' scheduled next updates to coincide, and to "pile up", into a single frame; which is why, I believe, some randomization was added to the update times. But randomization doesn't guarantee that pile-up's won't occur. What I was suggesting above is a method for scheduling that avoids pile-up's altogether; at the cost of having power-of-two update times, rather than continuously variable update times.
As for how the time between updates is decided, I don't know; I wasn't dealing with that issue; that's already coded into the engine.
/OT

But, frankly, I don't believe the observed hiccups are due to pileups in the physics frames. At least what I've experienced was hiccups at the moments ships are spawned, which is what leads me to believe it's open-gl related: swapping textures from video memory to system memory to make room for the new ships' textures, or something like that... (I'm pretty sure no amount of video memory is enough with vegastrike, given that all units in a system compete for space in the video card. We've got typically about 10 megabytes of uncompressed textures per unit type; plus the planets and backgrounds.)