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: 17092
Joined: Sat, 23. Apr 05, 21:42

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: 18151
Joined: Fri, 16. Apr 04, 19:21

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: 17092
Joined: Sat, 23. Apr 05, 21:42

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: 1489
Joined: Wed, 18. Jan 06, 08:39

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: 3159
Joined: Thu, 22. Jan 09, 18: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: 1489
Joined: Wed, 18. Jan 06, 08:39

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: 17092
Joined: Sat, 23. Apr 05, 21:42

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: 1489
Joined: Wed, 18. Jan 06, 08:39

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: 17092
Joined: Sat, 23. Apr 05, 21:42

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: 18151
Joined: Fri, 16. Apr 04, 19:21

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: 902
Joined: Sat, 16. Oct 10, 11:07

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: 17092
Joined: Sat, 23. Apr 05, 21:42

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: 3159
Joined: Thu, 22. Jan 09, 18: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: 902
Joined: Sat, 16. Oct 10, 11:07

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: 10117
Joined: Sun, 15. Feb 04, 21:12

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

Post Reply

Return to “X Trilogy Universe”