EnglishGermanFrenchRussianItalianSpanish
Log inRegister
 
X3 Complex tree?
Post new topic Reply to topic Goto page Previous  1, 2, 3  Next
View previous topic :: View next topic
Author Message
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Wed, 13. Jun 18, 02:29    Post subject: Reply with quote Print

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 Wink

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!!!
Back to top
View user's profile Send private message
glenmcd





Joined: 16 Oct 2010
Posts: 902 on topic
Location: Australia
Thank you for registering your game
PostPosted: Wed, 13. Jun 18, 02:30    Post subject: Reply with quote Print

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!

Back to top
View user's profile Send private message
TTD





Joined: 06 Jul 2008
Posts: 10911 on topic
Location: Wiltshire,UK
Thank you for registering your game
PostPosted: Wed, 13. Jun 18, 09:57    Post subject: Reply with quote Print

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.


_________________
Not My Sites...
TCplots-AP
Customize your start
XDownloads (a Mod Library)
Xadrian'sComplexCalc
REBIRTH HELP
Back to top
View user's profile Send private message Send e-mail
Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)



Joined: 15 Nov 2004
Posts: 20521 on topic
Location: London
Thank you for registering your game
PostPosted: Wed, 13. Jun 18, 10:45    Post subject: Reply with quote Print

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


_________________
My Scripts | MY X3TC Scripts | X3 Plugin Manager | Custom Gui
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Wed, 13. Jun 18, 23:49    Post subject: Reply with quote Print

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!!!
Back to top
View user's profile Send private message
SirNukes





Joined: 31 Mar 2007
Posts: 182 on topic

Thank you for registering your game
modified
PostPosted: Thu, 14. Jun 18, 00:59    Post subject: Reply with quote Print

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
Back to top
View user's profile Send private message
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Thu, 14. Jun 18, 04:02    Post subject: Reply with quote Print

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!!!
Back to top
View user's profile Send private message
zazie



MEDALMEDALMEDAL

Joined: 07 Mar 2005
Posts: 3311 on topic

Thank you for registering your game
PostPosted: Thu, 14. Jun 18, 10:00    Post subject: Reply with quote Print

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)?

Back to top
View user's profile Send private message
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Thu, 14. Jun 18, 10:26    Post subject: Reply with quote Print

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!!!
Back to top
View user's profile Send private message
Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)



Joined: 15 Nov 2004
Posts: 20521 on topic
Location: London
Thank you for registering your game
PostPosted: Thu, 14. Jun 18, 11:08    Post subject: Reply with quote Print

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


_________________
My Scripts | MY X3TC Scripts | X3 Plugin Manager | Custom Gui
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
ubuntufreakdragon



MEDALMEDALMEDAL

Joined: 23 Jun 2011
Posts: 3915 on topic
Location: Das Randland des Wahnsinns!
Thank you for registering your game
PostPosted: Thu, 14. Jun 18, 14:17    Post subject: Reply with quote Print

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:

                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
Back to top
View user's profile Send private message
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Thu, 14. Jun 18, 20:51    Post subject: Reply with quote Print

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!!!
Back to top
View user's profile Send private message
SirNukes





Joined: 31 Mar 2007
Posts: 182 on topic

Thank you for registering your game
PostPosted: Thu, 14. Jun 18, 21:13    Post subject: Reply with quote Print

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.

Back to top
View user's profile Send private message
Cycrow
Moderator (Script&Mod)
Moderator (Script&Mod)



Joined: 15 Nov 2004
Posts: 20521 on topic
Location: London
Thank you for registering your game
PostPosted: Thu, 14. Jun 18, 22:17    Post subject: Reply with quote Print

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.


_________________
My Scripts | MY X3TC Scripts | X3 Plugin Manager | Custom Gui
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
jlehtone



MEDALMEDALMEDAL

Joined: 23 Apr 2005
Posts: 17033 on topic
Location: GalNet BBS
Thank you for registering your game
PostPosted: Sun, 17. Jun 18, 15:43    Post subject: Reply with quote Print

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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic Reply to topic Goto page Previous  1, 2, 3  Next
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
Control Panel
Login Data
The time now is Sat, 18. Aug 18, 16:01

All times are GMT + 2 Hours

[ Disclaimer / Impressum ] | [ Privacy Policy / Datenschutz ]

Board Security

Copyright © EGOSOFT 1989-2018
Powered by phpBB © 2001, 2005 phpBB Group
Template created by Avatar & BurnIt!
Debug: page generation = 0.15166 seconds, sql queries = 29