The International Simutrans Forum

 

Author Topic: [Patch] Faster Route Calculation for Centralised Search  (Read 2408 times)

0 Members and 1 Guest are viewing this topic.

knightly

  • Guest
[Patch] Faster Route Calculation for Centralised Search
« on: November 05, 2009, 10:03:55 PM »
James,


I have made some changes to the centralised search code, and search speed is much faster. The commits have been uploaded to Github already, please check them out when you have time.

Here are the results on my PC :

Save Game    Before (ms)    After (ms)
Colin r26822503327
Colin v5.1252105
Colin v4.3625127
Yoshi71771928
198220537
Wipi5322

Note : Colin's 3 games are different games, not just saved/played in different versions of Simutrans.

Edit :
Forgot to mention that, as usual, the time recorded includes the time incurred in rebuilding all connexions (similar to destinations in Standard) and recalculating all paths.


Knightly
« Last Edit: November 05, 2009, 10:08:46 PM by Knightly »

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] Faster Route Calculation for Centralised Search
« Reply #1 on: November 05, 2009, 10:35:30 PM »
Knightly,

thank you very much for your efforts - very much appreciated! As you will see, I have uploaded a proto-version of 7.0 onto Github. I am hoping to release this week-end, but may be delayed, because I am moving. Do you think that you could have a look into fixing the mess that I made trying to merge the latest trunk changes with the distributed pathing system?

Also, I notice that the network code (albeit not yet complete, I understand) is now merged with the trunk (although not yet with 7.0). When we last spoke, you were unsure of whether the centralised system would work with the network mode - could you look into that when you have time? For the release of 7.0, I will not synchronise with any trunk version later than the latest stable release version, but for versions > 7.0, I should like to be able to synchronise with the latest nightlies again, so it would be most helpful for this to be looked into. Thank you very much. I shall have a look at integrating your impressive looking changes now.

Offline jamespetts gb

  • Simutrans-Extended project coordinator
  • Moderator
  • *
  • Posts: 18745
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: [Patch] Faster Route Calculation for Centralised Search
« Reply #2 on: November 08, 2009, 10:21:03 AM »
Knightly,

I have just found that your patch causes a Linux compile error with GCC:

Code: [Select]
In file included from gui/colors.cc:13:
gui/../path_explorer.h:290: error: integer constant is too large for 'long' type


Offline sanna

  • *
  • Posts: 234
Re: [Patch] Faster Route Calculation for Centralised Search
« Reply #3 on: November 11, 2009, 08:34:02 PM »
Knightly,
I have just found that your patch causes a Linux compile error with GCC:
Code: [Select]
In file included from gui/colors.cc:13:
gui/../path_explorer.h:290: error: integer constant is too large for 'long' type

As jamesspetts pointed out make fails on path_explorer.h:290
Code: [Select]
static const uint64 maximum_limit_64bit = 0xFFFFFFFFFFFFFFFF; with error message path_explorer.h:290: error: integer constant is too large for ‘long’ type

I tested the "obvious" thing and added ULL (0xFFFFFFFFFFFFFFFFULL) to the hexadecimal and it seems to work (for a clean make at least); though I am pretty sure that needs to be conditional on os, right? Not all compilers support LL iirc. Furthermore I am not sure if that should really be ULL and not just LL (0xFFFFFFFFFFFFFFFFLL). With "work" I mean I can compile, start game, build a minimal busline and have passangers transported; further than that I have not tested - so I do not know if the path explorer works as intended..

System: Debian/squeeze, gcc (Debian 4.3.4-5) 4.3.4, i386

knightly

  • Guest
Re: [Patch] Faster Route Calculation for Centralised Search
« Reply #4 on: November 11, 2009, 08:43:10 PM »
Hi Sanna :)

I tested the "obvious" thing and added ULL (0xFFFFFFFFFFFFFFFFULL) to the hexadecimal and it seems to work (for a clean make at least); though I am pretty sure that needs to be conditional on os, right? Not all compilers support LL iirc. Furthermore I am not sure if that should really be ULL and not just LL (0xFFFFFFFFFFFFFFFFLL).

Actually I have uploaded a fix at my Github branch, which uses defined constants from limits.h. Using limits.h will hopefully avoid compiler-specific suffixes for "unsigned long long" variables. It has to be ULL because it is intended to be Unsigned.

P.S. I have tested the centralised search again after the release of v7.0, but found that search speed is for some unknown reason (unknown here means that it's not related to centralised search's code) slower than what I got when I improved the centralised search code based on v6.8 in the first place.

Knightly
« Last Edit: November 11, 2009, 08:49:44 PM by Knightly »

Offline sanna

  • *
  • Posts: 234
Re: [Patch] Faster Route Calculation for Centralised Search
« Reply #5 on: November 11, 2009, 08:49:45 PM »
Actually I have uploaded a fix at my Github branch, which uses defined constants from limits.h. Using limits.h will hopefully avoid compiler-specific suffixes for "unsigned long long" variables.
Good to hear!
It has to be ULL because it is intended to be Unsigned.
That was my "guess" which is why I used ULL, but then I am no expert on such suffixes...