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

Timsup2nothin
Posts: 3177
Joined: Thu, 22. Jan 09, 18:49

Post by Timsup2nothin » Wed, 13. Jun 18, 02:29

euclid wrote:Not sure if this is relevant but ....

.... the performance issue with huge complexes are due to the rendering of the connections. I'm using a mod that makes all connections "invisible" and have no FPS drop at all. A nice side effect is that no trader or defender gets stuck in the pipes ;-)

Cheers Euclid
That's part of (and the bulk of) the problem in sector. Graphics rendering.

The other problem is that every station in the universe has to be shoved through a production analysis cycle every however often. The "natural" universe has some limitations on just how many stations that will be, but of course the player can build as many as they want. So that production analysis can take longer and longer and longer. Actual data processing.

Then you throw in the complex, which not only requires a calculation to manage each station's production, but also requires some sort of processing of the interaction with the connecting hub (and the connecting hub, and the connecting hub, and the connecting hub, until it finally reaches the 'real' hub). Also data processing.

If you pile enough stations into existence crunching through it all will start to take time.
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!!!

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

Post by glenmcd » Wed, 13. Jun 18, 02:30

thanks for the tip Euclid and yes I've been using the invisible tubes mod since the early days (downloaded it somewhere between 2006 and 2012). It isn't at all relevant to this discussion, as we are looking at CPU processing causing delays during gate passing times, which doesn't involve anything graphic at all. But the same effect can and does hurt framerate. If you read my original article on the workaround (see link above), this will become clear. Specifically, the time to pass a gate between two empty sectors won't extend to minutes, hours or even days from less than a second, due to graphic items in other sectors.

That said, I agree that the vanilla compatible tubeless mod should be used by all!

User avatar
TTD
Posts: 10913
Joined: Sun, 6. Jul 08, 10:29
xr

Post by TTD » Wed, 13. Jun 18, 09:57

interesting reading...
tubless isthe way I went evenyually, especially after I got a station complex so big I could not enter the sector !


When I build complexes I usually gtoup types together, ie 4x fact A , 4x facriry B etc.

w would place them in a grid, wg 16 stations would be a grid of 4x4
Then I would find the point furthest from the grid that qould connect them all

if each station was a dot., joining lines would create a pyramid.
if more stations were needed I would brild a gtind of pyramids and form alarger pyrimid shaped complex.


the other method I have used is placing them in line,ie
a,b,c,d,e etc
then selecing a, finding the furthest point of connection for a along the line and conencting.
thus the distance from hub to a would be firther than hub to b, and so on.
this would be the first hub.
I would the find the furpoint fo that hub to connect along the rest of the line.


doing so would evenuall lead to a long string og factories with a single hub at the end

not sure which gave best performance, the second ,if placed along the edges of the sector map , looked neat and did not obstruct passage. the second, if place behind the gate seemed to be less of a problem ,time wise, to enter the sector.

Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 20544
Joined: Mon, 15. Nov 04, 00:26
x4

Post by Cycrow » Wed, 13. Jun 18, 10:45

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

Timsup2nothin
Posts: 3177
Joined: Thu, 22. Jan 09, 18:49

Post by Timsup2nothin » Wed, 13. Jun 18, 23:49

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.
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: 301
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: 3177
Joined: Thu, 22. Jan 09, 18: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: 3340
Joined: Mon, 7. Mar 05, 15:55
x3ap

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: 3177
Joined: Thu, 22. Jan 09, 18: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: 20544
Joined: Mon, 15. Nov 04, 00: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: 4036
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: 3177
Joined: Thu, 22. Jan 09, 18: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: 301
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: 20544
Joined: Mon, 15. Nov 04, 00: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: 17143
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.

Post Reply

Return to “X Trilogy Universe”