X3 Complex tree?

General discussions about the games by Egosoft including X-BTF, XT, X², X³: Reunion, X³: Terran Conflict and X³: Albion Prelude.

Moderator: Moderators for English X Forum

SirNukes
Posts: 546
Joined: Sat, 31. Mar 07, 23:44
x4

Post by SirNukes » Thu, 14. Jun 18, 00:59

I took a poke at some of those benchmarks, and its amazing how bad things can get.

256 factories, connected in the bad style: 17 second gate time.
2x256 factories, joined together: 85 second gate time (400% increase for 100% more factories).

Destroying the complex hub made no change to the load times. Destroying the hub and all factories also made little difference (maybe knock off a second). Even alt-f4ing out of the game hit the massive delay, to the point I was hard killing the game from the task manager to save time.


I don't like any of the theories on underlying causes so far. Having to go 500 hops in a graph should be nothing on its own, unless you are programming your computer with punch cards and powering it with a bank of potatoes. Plus, a poorly constructed complex tree should stop being a problem once the complex is destroyed, presumably.

But, none of my other ideas on the problem have panned out yet, so who knows. Something must be going really skrewy in the code. The assembly I have looked at suggests child complexes get destructed and their factory lists joined into the parent complex, so that checks out at least.
Last edited by SirNukes on Thu, 14. Jun 18, 21:14, edited 2 times in total.

Timsup2nothin
Posts: 4690
Joined: Thu, 22. Jan 09, 17:49

Post by Timsup2nothin » Thu, 14. Jun 18, 04:02

I pride myself on being able to come up with a hypothesis for anything, usually plausible but I'll go with outlandish if plausible is out of reach. And I have to admit, I got nothin' for this load time doesn't recover even if the thing is destroyed part.
Trapper Tim's Guide to CLS 2

On Her Majesty's Secret Service-Dead is Dead, and he is DEAD

Not a DiD, so I guess it's a DiDn't, the story of my first try at AP
Part One, in progress

HEY! AP!! That's new!!!

zazie
Posts: 3702
Joined: Mon, 7. Mar 05, 14:55
x4

Post by zazie » Thu, 14. Jun 18, 10:00

Have not tested it by myself, but would the lags of a destroyed complex not 'disappear' after the "cool-down time" of the debris (iirc equal or little shorter than 2 IG-days)?

Timsup2nothin
Posts: 4690
Joined: Thu, 22. Jan 09, 17:49

Post by Timsup2nothin » Thu, 14. Jun 18, 10:26

zazie wrote:Have not tested it by myself, but would the lags of a destroyed complex not 'disappear' after the "cool-down time" of the debris (iirc equal or little shorter than 2 IG-days)?
Brilliant. I hadn't considered that the debris is still there.
Trapper Tim's Guide to CLS 2

On Her Majesty's Secret Service-Dead is Dead, and he is DEAD

Not a DiD, so I guess it's a DiDn't, the story of my first try at AP
Part One, in progress

HEY! AP!! That's new!!!

Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 22201
Joined: Sun, 14. Nov 04, 23:26
x4

Post by Cycrow » Thu, 14. Jun 18, 11:08

Timsup2nothin wrote:
Cycrow wrote:The order and layout of stations in a complex shouldn't effect production of wares, only the connection tubs.

when in a complex, stations produce the same as separate stations. They just share their storage space with a complex hub.

So the complex hub acts as a global storage for all the connected stations.

All stations in the complex have a direct link to the hub
the complex hub doesn't actually do any processing itself
It isn't about complex hubs 'processing' anything. It's about the processor time involved in updating a station's inventory. I won't claim to be familiar with the code, but there has to be some sort of routine like:

Check production in progress, allowing a quick exit if it is and the cycle isn't finished.

If it is at the end of cycle update product inventory
...which will take as many loops as there are connectors 'between' the station and the ultimate hub where the inventory is stored.

If production isn't in progress, or just ended, then it has to go through an inventory check for each resource and for product available space, and again that's going to involve looping as it checks each hub along the way to the one that actually counts.


I can see some ways to code shortcuts from station to main hub that would eliminate the looping, but based on observed performance that wasn't done. When the complex connector concept was being coded the idea was most likely that people would connect a farm to a food fab, or some such, and that would be pretty much that. The people doing the coding probably, at the time, never thought about how the looping would add up in these gigantic complexes.
Not sure what you mean by looping an inventory check. But there is no difference between how a single factory and a complex handles its storage and production.

The number of "connections" between a factory and a complex is always 1

User avatar
ubuntufreakdragon
Posts: 5189
Joined: Thu, 23. Jun 11, 14:57
x4

Post by ubuntufreakdragon » Thu, 14. Jun 18, 14:17

I really want to know how this looks at the code level, however to approach a binary tree as close as posible you need 2^n-1 mini complexes an name 1lvl0 2lvl1 (2^k)lvlk and always merge 2lvlk in one lvl(k-1) hub

Code: Select all

                0
          1   L L   1
      2 L L 2   2 L L 2
     L L    L LL L    L L
My X3 Mods

XRebirth, things left to patch:
In General; On Firing NPC's; In De Vries; Out Of Zone; And the Antiwishlist

Timsup2nothin
Posts: 4690
Joined: Thu, 22. Jan 09, 17:49

Post by Timsup2nothin » Thu, 14. Jun 18, 20:51

Cycrow wrote: Not sure what you mean by looping an inventory check. But there is no difference between how a single factory and a complex handles its storage and production.

The number of "connections" between a factory and a complex is always 1
That's certainly how I would have it coded, but in an effort to explain the observed geometric way that lag builds up differently depending on how the connections are made the only thing I've seen that makes sense is that it isn't. It responds as if the factory is marked as being connected to whatever hub it was originally connected to, and that hub is then marked as being connected to whatever hub it got connected to, etc, up until you reach the most recently placed hub.
Trapper Tim's Guide to CLS 2

On Her Majesty's Secret Service-Dead is Dead, and he is DEAD

Not a DiD, so I guess it's a DiDn't, the story of my first try at AP
Part One, in progress

HEY! AP!! That's new!!!

SirNukes
Posts: 546
Joined: Sat, 31. Mar 07, 23:44
x4

Post by SirNukes » Thu, 14. Jun 18, 21:13

Wrecks are very lightweight objects, and shouldn't have anything to do with massive sector loading/unloading lag anyway. Plus the kill method I used doesn't leave wrecks.

After spending a bunch of time sifting through the KC, here are a few observations:

1) As Cycrow said, factories link to their hub directly, and hubs have a flat list of their factories, so production tasks and ware lists and such wouldn't care about how the complex was built.

2) During complex setup, the CreateConnections function handles most of the crunch to initialize the new complex with the joined factories. In this, there is a call to SA_CreateFactoryConnections which returns information used for tubes. The call passes (complex id, factory list) as args. Since that is a call to code outside the KC, it is a bit of a black box to me.

3) Depending on how the complex is built, each complex the player places will have a varying number of contained factories. In terms of total complexes built times the factories per complex, the build approaches scale as: O(N*log2(N)) for the balanced binary tree style of building, and O(N^2) for the imbalanced binary tree. So for 256 factories, that will always be 255 complex nodes, but averages ~8 factories per node for the balanced tree or ~128 factories per node for an imbalanced tree.

4) Complex destruction doesn't seem to have any similar SA call, like SA_DestroyFactoryConnections.


So, a theory on what could be happening:

A) Every call to SA_CreateFactoryConnections make a permanent record of the complex and its factories, but only picking out a few properties of interest (eg. just the id values) such that it doesn't need to care if the original objects get destroyed.

B) These records are used to build a graph (using a bunch of subset checks on factory lists) which will control how tubing is assigned.

C) Records of prior complexes are never destroyed. This makes some sense, since a complex gets destroyed whenever it is connected to a higher level complex, but the record is kept for tubing consistency.

D) The graph analysis algorithm has terrible performance when dealing with the O(N^2) complexity scaling on records (when a complex was built a certain way). This somewhat makes sense; a simple subset check (is every factory in record A also in record B) can scale as O(N^2). Comparing the balanced and imbalanced style of building complexes for 256 factories, imbalanced would be ~256 times more compute intensive to do a subset check.

E) The graph building function is rerun whenever the player loads the game, changes sector, or leaves the game, perhaps due to a bit of lazy coding to ensure the graph is always ready when a new complex is placed (since that is when the complex will store tubing information).

It would probably take someone with source code access to look into this any further.

Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 22201
Joined: Sun, 14. Nov 04, 23:26
x4

Post by Cycrow » Thu, 14. Jun 18, 22:17

for SA_CreateFactoryConnections,
this creates the sector objects for each of the connection tubes.

these are then freed when the sector is deactivated, or the complex is destroyed.

the connections only existing in the activate sector, this is why a large complex can cause longer load times when jumping to, or from the sector. As the all the tubes have to be created/freed

theres no SA_DestroyFactoryConnections as the connections can be destroyed in the same way as any other sector objects.

jlehtone
Posts: 21801
Joined: Sat, 23. Apr 05, 21:42
x4

Post by jlehtone » Sun, 17. Jun 18, 15:43

Destroyed Complex should not require status updates.
Data that is not cruched, should not consume CPU cycles.

If data is flat lists, what then produces the ingame observable discrepancies?
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

SirNukes
Posts: 546
Joined: Sat, 31. Mar 07, 23:44
x4

Post by SirNukes » Sat, 23. Jun 18, 01:43

Based on the slowdown happening everywhere, not just when heading to/from the complex sector, I took another look through the sector change KC code. The calls to SA_CleanUpObjects and SA_FreeAllBodies take no arguments, implying they look at all sectors in the universe and could be the culprits. So, I tried commenting each of them out and redid the benchmark. SA_FreeAllBodies made no difference, but as for SA_CleanUpObjects ...

256 factory complex, traversing between two empty sectors:
Baseline: 14 seconds
Removing SA_CleanUpObjects: <0.5 seconds.

256x2 factory complex for verification:
Baseline: 75 seconds
Removing SA_CleanUpObjects: <0.5 seconds.

So, there's the culprit. Something is seriously wrong inside SA_CleanUpObjects when dealing with a history of past complexes.

glenmcd
Posts: 920
Joined: Sat, 16. Oct 10, 11:07
x3tc

Post by glenmcd » Sat, 23. Jun 18, 03:38

Nice work :)

Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 22201
Joined: Sun, 14. Nov 04, 23:26
x4

Post by Cycrow » Sat, 23. Jun 18, 11:05

SirNukes wrote: The calls to SA_CleanUpObjects and SA_FreeAllBodies take no arguments, implying they look at all sectors in the universe and could be the culprits.
These commands are part of the sector engine, and they clean up the sector objects when changing sectors, which are only in the active sector, so its only working on a single sector each time.

sector objects and models, etc, only exist in the active sector

jlehtone
Posts: 21801
Joined: Sat, 23. Apr 05, 21:42
x4

Post by jlehtone » Sat, 23. Jun 18, 12:08

It is good that there are those, who can see deeper than the rest of us. Thank you.

I can only formulate questions. :oops:
SirNukes wrote:traversing between two empty sectors
How did these become empty?

IF SA_CleanUpObjects works only on the objects that are in the (empty) sector that you do leave,
THEN it would be affected only by objects that are there (or were, but have not been properly purged)


What are the baseline (with and without SA_CleanUpObjects) when no (other) sector has a Complex (yet)? In fact, is there a difference on moving between "vanilla empty" sectors and moving between "made empty" sectors?


Logically, there are three events:
A. Clean up current sector (3D) on departure
B. Populate new current sector (with 3D)
C. Update all the OOS

The A and B should not be affected by what is OOS both before and after transition.


Tangent: I've crashed (at the Gate to other ship) when I did jump from sector to the same sector. I presume that the usual "clean up and repopulate" is not performed in that special case. How about the "update factory status"? Does such in-sector jump invoke the C-event?


Polymorphism. NPC Complex is quite different from player Complex. Does same function iterate over all stations for production and stock status, or do player properties have separate function from NPC?
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

glenmcd
Posts: 920
Joined: Sat, 16. Oct 10, 11:07
x3tc

Post by glenmcd » Sat, 23. Jun 18, 12:16

jlehtone wrote:
SirNukes wrote:traversing between two empty sectors
How did these become empty?
If this refers to my original benchmarking for the balance binary tree complex workaround, I used a script to destruct every object in the two sectors.

SirNukes
Posts: 546
Joined: Sat, 31. Mar 07, 23:44
x4

Post by SirNukes » Sat, 23. Jun 18, 21:35

I am indeed using Glen's wonderful saves. The SA_CleanUpObject removal is in my customization tool (a little buried since not for general use), so between the two anyone should be able to verify the measurements I gave.

For reference, here is a summary of my current notes on the key code section in the KC when changing sectors:
  • Do prep work to stop the player ship, stop jumping, close monitors, turn off seta, etc.
  • Call player.LeaveSector, with some light work like rehiding cargo of other sector ships.
  • Call CLIENT.LeaveSector, which will then call Sector.Deactivate, which in turn calls Deactivate on the various sector ships and stations and such. These Deactivate functions are going around calling SA_FreeObject, presumably on the 3d sector object. For instance, complexes will loop over their list of tube information and call SA_FreeObject on the ones with 3d objects (stored in an internal array along with general information recorded from SA_CreateFactoryConnections, which was called at complex creation).
  • Call SA_CleanUpObjects, adding the silly delay.
  • Call SA_FreeAllBodies, adding no noticeable delay.
  • Call CLIENT.EnterSector; basically the reverse of LeaveSector, this goes around calling flavors of Activate functions. For complexes, it is ActivateConnections, which loops over the recorded list of tube information calling stuff like SA_AllocObject (and storing the result for later deactivation), SA_StartObjectInSpace, SA_SetFactoryConnectionParent.
  • Call Player.EnterSector, which deals with stuff like flagging a sector as visited, updating player statistics, etc.
  • Call PLAYER.WarpEnterSector followed by general setup stuff (place the player, turn on monitors, etc.).
So, a couple observations:

My earlier thought that SA_CreateFactoryConnections created tubes feels incorrect, I am now thinking it just returns the necessary info for tube creation (subtype and placement; maintype is always 20), though I haven't picked it all apart yet.

3d object creation/removal appears to be somewhat handled in the KC, which leaves me wondering what would actually happen if I played for a bit with SA_CleanUpObjects disabled. Maybe I'll try that later today.

SirNukes
Posts: 546
Joined: Sat, 31. Mar 07, 23:44
x4

Post by SirNukes » Sun, 24. Jun 18, 02:49

I spent about an hour with SA_CleanUpObjects removed on my XRM save, puttering around some sectors, doing some fighting, then doing a fast tour of a bunch of sectors. Everything played out normally.

In case stale objects were building up, I watched the X3 memory usage and checked the save game size. Memory usage was stable, growing up to ~3.5 GB and then cleaning out old data to go back to ~1.8 GB, growing again with more sectors visited and objects loaded. This is the same behavior as normal. Save game size at the end was similar to (slightly smaller than) when started.

Another test used the 256-factory complex save, this time popping through the gate to the complex sector repeatedly to see if there might be some object buildup. Memory usage was stable, suggesting no buildup.

So, right now, the only obvious effect SA_CleanUpObjects appears to have is adding sector exit delay for games with big complexes. Interestingly, this function is not in the X2 KC documentation, so that game appears to have made do without it.

Post Reply

Return to “X Trilogy Universe”