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

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

X3 Complex tree?

Post by jlehtone » Thu, 7. Jun 18, 20:14

Recently (say, within last two years) someone on the forum made a claim that method of connecting stations to a complex does affect performance afterwards.

Method A:
* Connect two stations (and form a Hub)
* Connect station to the Hub
* Connect station to the Hub

Method B:
* Connect two stations (and form a Hub)
* Connect two stations to form a temporary Hub (X)
* Connect X to the Hub

The claim was that while both look like four stations linked to a Hub, the B is lighter. The difference presumably shows up when you scale to serious multi-station complexes.


The Search-Fu is not with me today. :oops:


I would speculate that the Hub has a list of members. Method A simply appends stations to the list.

Method B, in order to be different, would actually retain the temporary Hubs as (invisible) nodes on a tree data structure. In the example B the main Hub would have three members on list: two Stations and a hub-node. The hub-node has the other two member stations.


Whatever the true implementation, the main question is:

If the hypothesis about efficiency is true, then how to optimally connect N stations?
(10 << N)
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

Alan Phipps
Moderator (English)
Moderator (English)
Posts: 30367
Joined: Fri, 16. Apr 04, 19:21
x4

Post by Alan Phipps » Thu, 7. Jun 18, 20:28

I would suggest a search for posts and threads by glenmcd, such as this one.
A dog has a master; a cat has domestic staff.

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

Post by jlehtone » Thu, 7. Jun 18, 23:12

Thank you. :goner:
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

RainerPrem
Posts: 3560
Joined: Wed, 18. Jan 06, 07:39
x4

Re: X3 Complex tree?

Post by RainerPrem » Fri, 8. Jun 18, 06:01

jlehtone wrote: If the hypothesis about efficiency is true, then how to optimally connect N stations?
(10 << N)
Hi,

less than ten stations? I don't think you'll see a difference with a decent graphics card. Try a hundred stations instead.

cu
Rainer

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

Re: X3 Complex tree?

Post by Timsup2nothin » Fri, 8. Jun 18, 11:16

RainerPrem wrote:
jlehtone wrote: If the hypothesis about efficiency is true, then how to optimally connect N stations?
(10 << N)
Hi,

less than ten stations? I don't think you'll see a difference with a decent graphics card. Try a hundred stations instead.

cu
Rainer
That's actually "for N much greater than ten."
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!!!

RainerPrem
Posts: 3560
Joined: Wed, 18. Jan 06, 07:39
x4

Re: X3 Complex tree?

Post by RainerPrem » Sat, 9. Jun 18, 06:48

Timsup2nothin wrote:
RainerPrem wrote:
jlehtone wrote: If the hypothesis about efficiency is true, then how to optimally connect N stations?
(10 << N)
Hi,

less than ten stations? I don't think you'll see a difference with a decent graphics card. Try a hundred stations instead.

cu
Rainer
That's actually "for N much greater than ten."
Ah, sorry, I misread that.

cu
Rainer

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

Post by jlehtone » Sun, 10. Jun 18, 18:04

@Rainer: Graphics is not the issue. glenmcd shows that effects on CPU are felt OOS.

I did draw a tree (32 elliptic stations, hubs as boxes, final Hub is "H"):
https://imgur.com/hoVFl08
Each hub is created by connecting two stations. Then they are merged according to glenmcd's scheme:

Code: Select all

  H -> 1
  2 -> 3
  4 -> 5
  6 -> 7
  8 -> 9
 10 -> 11
 12 -> 13
 14 -> 15

  H -> 2
  4 -> 6
  8 -> 10
 12 -> 14

  H -> 4
  8 -> 12

  H -> 8
The assumption is that a Hub has a list of children and that on connecting hubs the vanishing one becomes child of the remaining one.

Given these, the tree does look like it could be more balanced, doesn't it?
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

RainerPrem
Posts: 3560
Joined: Wed, 18. Jan 06, 07:39
x4

Post by RainerPrem » Mon, 11. Jun 18, 06:30

jlehtone wrote:@Rainer: Graphics is not the issue. glenmcd shows that effects on CPU are felt OOS.

I did draw a tree (32 elliptic stations, hubs as boxes, final Hub is "H"):
https://imgur.com/hoVFl08
Each hub is created by connecting two stations. Then they are merged according to glenmcd's scheme:

Code: Select all

  H -> 1
  2 -> 3
  4 -> 5
  6 -> 7
  8 -> 9
 10 -> 11
 12 -> 13
 14 -> 15

  H -> 2
  4 -> 6
  8 -> 10
 12 -> 14

  H -> 4
  8 -> 12

  H -> 8
The assumption is that a Hub has a list of children and that on connecting hubs the vanishing one becomes child of the remaining one.

Given these, the tree does look like it could be more balanced, doesn't it?
The tree is completely correct. You see it, when you use binary numbers instead of decimal ones.

First step: connect all "*1" stations to those with the same number ending with "0" 11010 => 11011 All "*1" stations disappear.

Second step: connect all "*10" stations to "*00" 11000 => 11010

Third step "*100" to "*000" and so on.

cu
Rainer

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

Post by jlehtone » Mon, 11. Jun 18, 16:49

My issue is not with the numbers, but with the picture:
https://imgur.com/hoVFl08
  • That is not a binary tree
  • That is not balanced
That tree is based on these rules:
  • Node on tree has a list of children.
  • Connecting two stations creates a Hub with two children.
  • Connecting a station to Hub adds one more child to the list of the Hub.
  • Connecting two Hubs converts one into child of the other.
Side-effect: every hub node on the tree has at least 2 station leafs.

A binary tree would construct differently:
  • Connecting two stations creates a Hub with two children. A binary tree.
  • Connecting a station to Hub converts the Hub into internal tree node, adds new Root Hub, and adds the former hub and the station as childs. Remains binary tree. Properties of old Hub (e.g. location) are copied to the new Root Hub.
  • Connecting two Hubs adds a new Root Hub and makes both previous hubs children of the new Hub. Properties of the first old Hub (e.g. location) are copied to the new Root Hub.
Side-effects:
A hub node might not have any stations as direct children.
On certain Complex sizes all Stations are equidistant from the Hub.


glenmcd does assume binary tree, although some of his analysis does not match the binary tree model that I did describe above. What did I miss?
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

Alan Phipps
Moderator (English)
Moderator (English)
Posts: 30367
Joined: Fri, 16. Apr 04, 19:21
x4

Post by Alan Phipps » Mon, 11. Jun 18, 17:02

Our friend glenmcd is still a self-professed forum lurker although not so active on it now. Why not give him a PM and bring his attention to this thread?
A dog has a master; a cat has domestic staff.

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

Post by glenmcd » Tue, 12. Jun 18, 03:39

If you are building a complex with a station count that is an exact power of 2, build it in a balanced binary tree structure for least CPU load IS, least CPU load OOS, and least CPU load when changing sectors.

When you must have one complex and you have a station count that is not an exact power of 2, remove the stations on the lowest level and leave above as is. It matters not which stations you remove from this structure, as long as they are removed from the lowest level. Keep it binary, so always 0 to 2 children never more.

Having one complex with 128 stations, is roughly twice the CPU performance overhead compared to two 64 station complexes, if using the binary tree method in both cases. If you use the old connection method, the 128 station complex is around 4 billion (2^(64/2)) times more lCPU overhead for IS framerate, OOS framerate and sector change times when compared to two 64 station complexes built the old way. The exact numbers are not critical, the fact that one is highly exponential growth and the other isn't, is critical for large complexes (>~50 stations).

The difficulty comes when adding stations to an existing complex. I try to always build complexes with an exact power of 2 number of stations, joining them to others of same size only when I have the money to build the second. This means having multiple complexes while you are generating income to buy more stations. Place the hubs close together and this isn't such a big deal for transporting wares. In the worst case, you'll have a station count one less than an even power of 2, so for a 63 station setup you'll have 7 complex hubs and one station by itself. It's easy to assume that more complex hubs produces more CPU overhead, but because of how complex connection kits were coded, the opposite is true.

Doing it this way, EVERY complex you make is a balanced binary tree throughout all of your game. Building the wrong way and then destroying the complex does not undo the CPU overhead, strangely enough.

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

Post by jlehtone » Tue, 12. Jun 18, 19:47

glenmcd wrote:Building the wrong way and then destroying the complex does not undo the CPU overhead, strangely enough.
:o That is scary. Does it linger forever? No garbage collection? What if the stations destruct too and ruins finally vanish; will the game still compute something?


2^n Complexes are quite easy, except perhaps for Mines and SPP that have never exactly followed the "900 ECells per hour" standard.


Just to confirm, connecting four stations, here are two data structures (generic and binary tree) with two inputs (OLD and NEW):

Case A (OLD; one hub with a list):

Code: Select all

  H - 3
 /|\ 
0 1 2
Case B (OLD; one hub, but a tree):

Code: Select all

      H
     / \
    o   3
   / \ 
  o   2
 / \
0   1
Case C (NEW; one intermediate hub):

Code: Select all

  H - o - 3
 /|   | 
0 1   2
Case D (NEW; one intermediate hub, balanced):

Code: Select all

    H
   / \
  o   o
 / \ / \ 
0  1 2  3
In game all four would look exactly the same; one hub, four stations, and four tubes.

From player point of view the A and B are identical.
The difference is in the implementation.
In A every station is one link from the final Hub.
In B the average distance is 2.25 links, and there is a binary tree.

From player point of view the C and D are identical.
Again, the difference is in the implementation.
The C is not a binary tree and connecting two Complexes does not create a new hub node to the tree. The average distance is 1.5 links.
The D is a binary tree. The average (and every) distance is 2 links.

A and C are results of implementation that mimics what the player can easily observe during build: "I did drop a CCK and got a tube between this and that."

@glenmcd:
B and D are the implementation that best explains the observed effects on performance?
Goner Pancake Protector X
Insanity included at no extra charge.
There is no Box. I am the sand.

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

Post by Timsup2nothin » Tue, 12. Jun 18, 21:00

jlehtone wrote: B and D are the implementation that best explains the observed effects on performance?
I know you didn't ask me, but, yes. They explain it a lot better if you add four more stations.

In case D that means a structure exactly like the one you have, plus a CCK to connect them, and every station is then three from the hub, a 50% increase.

In case B that means doubling the length of the 'string' leaving two stations at seven steps and an average of 3.785 steps. That's a 72% increase in number of steps.
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: 920
Joined: Sat, 16. Oct 10, 11:07
x3tc

Post by glenmcd » Wed, 13. Jun 18, 01:46

I'm with Tim on that one. I don't know how the CCKs are coded, I can only go on observations. And I can't see how you could connect stations to have performance mimmick A or C. CCKs seem to support pooling the resources and products from two stations, but when you connect a third, somehow performance wise it gets connected in series rather than in parallel with the first two. So that would explain why a balanced binary tree gives better performance than trying to connect umteen stations to a single hub.

Simply counting the number of links from bottom to top of a balanced binary tree doesn't mimmic performance observations accurately either. Specifically, when you use a single CCK to connect two 64-factory complexes, you'd think that the performance would decrease by only around 10 percent, but in fact it reduces by more than 50 percent. And this is why now I suggest do use the balance binary tree method, but try to keep total complex size to some reasonable figure, such as 128 / 256 or maybe 512. 2048+ complexes can invite performance problems, if you are really picky about framerate and gate passing times.

User avatar
euclid
Moderator (Script&Mod)
Moderator (Script&Mod)
Posts: 13289
Joined: Sun, 15. Feb 04, 20:12
x4

Post by euclid » Wed, 13. Jun 18, 02:04

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
"In any special doctrine of nature there can be only as much proper science as there is mathematics therein.”
- Immanuel Kant (1724-1804), Metaphysical Foundations of the Science of Nature, 4:470, 1786

Timsup2nothin
Posts: 4690
Joined: Thu, 22. Jan 09, 17: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: 920
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: 11165
Joined: Sun, 6. Jul 08, 10:29
x4

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: 22201
Joined: Sun, 14. Nov 04, 23: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: 4690
Joined: Thu, 22. Jan 09, 17: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!!!

Post Reply

Return to “X Trilogy Universe”