Page 1 of 2

Posted: Wed, 13. Jun 18, 02:29
by Timsup2nothin
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.

Posted: Wed, 13. Jun 18, 02:30
by glenmcd
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!

Posted: Wed, 13. Jun 18, 09:57
by TTD
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.

Posted: Wed, 13. Jun 18, 10:45
by Cycrow
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

Posted: Wed, 13. Jun 18, 23:49
by Timsup2nothin
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.

Posted: Thu, 14. Jun 18, 00:59
by SirNukes
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.

Posted: Thu, 14. Jun 18, 04:02
by Timsup2nothin
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.

Posted: Thu, 14. Jun 18, 10:00
by zazie
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)?

Posted: Thu, 14. Jun 18, 10:26
by Timsup2nothin
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.

Posted: Thu, 14. Jun 18, 11:08
by Cycrow
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

Posted: Thu, 14. Jun 18, 14:17
by ubuntufreakdragon
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

Posted: Thu, 14. Jun 18, 20:51
by Timsup2nothin
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.

Posted: Thu, 14. Jun 18, 21:13
by SirNukes
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.

Posted: Thu, 14. Jun 18, 22:17
by Cycrow
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.

Posted: Sun, 17. Jun 18, 15:43
by jlehtone
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?

Posted: Sat, 23. Jun 18, 01:43
by SirNukes
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.

Posted: Sat, 23. Jun 18, 03:38
by glenmcd
Nice work :)

Posted: Sat, 23. Jun 18, 11:05
by Cycrow
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

Posted: Sat, 23. Jun 18, 12:08
by jlehtone
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?

Posted: Sat, 23. Jun 18, 12:16
by glenmcd
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.