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



MEDALMEDALMEDAL

Joined: 23 Apr 2005
Posts: 17013 on topic
Location: GalNet BBS
Thank you for registering your game
PostPosted: Thu, 7. Jun 18, 20:14    Post subject: X3 Complex tree? Reply with quote Print

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. Embarassed


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.
Back to top
View user's profile Send private message
Alan Phipps
Moderator (English)
Moderator (English)

MEDALMEDALMEDAL

Joined: 16 Apr 2004
Posts: 17678 on topic
Location: Stonehenge, UK
Thank you for registering your game
PostPosted: Thu, 7. Jun 18, 20:28    Post subject: Reply with quote Print

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



MEDALMEDALMEDAL

Joined: 23 Apr 2005
Posts: 17013 on topic
Location: GalNet BBS
Thank you for registering your game
PostPosted: Thu, 7. Jun 18, 23:12    Post subject: Reply with quote Print

Thank you. Goner


_________________
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
RainerPrem



MEDALMEDALMEDAL

Joined: 18 Jan 2006
Posts: 1382 on topic

Thank you for registering your game
PostPosted: Fri, 8. Jun 18, 06:01    Post subject: Re: X3 Complex tree? Reply with quote Print

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

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





Joined: 22 Jan 2009



PostPosted: Fri, 8. Jun 18, 11:16    Post subject: Re: X3 Complex tree? Reply with quote Print

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



MEDALMEDALMEDAL

Joined: 18 Jan 2006
Posts: 1382 on topic

Thank you for registering your game
PostPosted: Sat, 9. Jun 18, 06:48    Post subject: Re: X3 Complex tree? Reply with quote Print

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

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



MEDALMEDALMEDAL

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

@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:
  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.
Back to top
View user's profile Send private message
RainerPrem



MEDALMEDALMEDAL

Joined: 18 Jan 2006
Posts: 1382 on topic

Thank you for registering your game
PostPosted: Mon, 11. Jun 18, 06:30    Post subject: Reply with quote Print

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:
  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

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



MEDALMEDALMEDAL

Joined: 23 Apr 2005
Posts: 17013 on topic
Location: GalNet BBS
Thank you for registering your game
PostPosted: Mon, 11. Jun 18, 16:49    Post subject: Reply with quote Print

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.
Back to top
View user's profile Send private message
Alan Phipps
Moderator (English)
Moderator (English)

MEDALMEDALMEDAL

Joined: 16 Apr 2004
Posts: 17678 on topic
Location: Stonehenge, UK
Thank you for registering your game
PostPosted: Mon, 11. Jun 18, 17:02    Post subject: Reply with quote Print

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





Joined: 16 Oct 2010
Posts: 899 on topic
Location: Australia
Thank you for registering your game
PostPosted: Tue, 12. Jun 18, 03:39    Post subject: Reply with quote Print

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.

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



MEDALMEDALMEDAL

Joined: 23 Apr 2005
Posts: 17013 on topic
Location: GalNet BBS
Thank you for registering your game
PostPosted: Tue, 12. Jun 18, 19:47    Post subject: Reply with quote Print

glenmcd wrote:
Building the wrong way and then destroying the complex does not undo the CPU overhead, strangely enough.

Surprised 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:
  H - 3
 /|\
0 1 2


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


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


Case D (NEW; one intermediate hub, balanced):
Code:
    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.
Back to top
View user's profile Send private message
Timsup2nothin





Joined: 22 Jan 2009



PostPosted: Tue, 12. Jun 18, 21:00    Post subject: Reply with quote Print

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





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

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.

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



Joined: 15 Feb 2004
Posts: 8976 on topic
Location: Gower, South Wales
Thank you for registering your game
PostPosted: Wed, 13. Jun 18, 02:04    Post subject: Reply with quote Print

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


_________________
"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
Back to top
View user's profile Send private message Send e-mail MSN Messenger
Display posts from previous:   
Post new topic Reply to topic Goto page 1, 2  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 Wed, 20. Jun 18, 17:20

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.13646 seconds, sql queries = 29