The International Simutrans Forum

 

Author Topic: poor game flow in large maps  (Read 24562 times)

0 Members and 1 Guest are viewing this topic.

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #70 on: September 28, 2009, 05:34:04 PM »
Interesting. I tested only reroute_goods().
Most interesting thing is London_C.sve with max_hops 8000.
It's really the same as max_hops 2000.

2nd savegame (3 players, 6671 convois, 1193 halts)
 standard 9799 ms
 Knightly 3885 ms

3rd savegame (9 player, 870 convois, 952 halts)
 standard 677 ms
 Knightly 221 ms

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 8000
 standard 37259 ms
 Knightly 4548 ms
max_hops 2000
 standard 5517 ms
 Knightly 4534 ms

fuzion_051's The World 3.sve (2791 convois, 839 halts)
 standard 7979 ms
 Knightly 4476 ms

knightly

  • Guest
Re: poor game flow in large maps
« Reply #71 on: September 28, 2009, 06:07:23 PM »
Z9999 :

Thank you very much for testing. :)

Most interesting thing is London_C.sve with max_hops 8000.
It's really the same as max_hops 2000.

As I have mentioned above, only origin halt, transfer halts and destination halt will be added to the HNode array. Thus, the number of HNodes used in a single search is largely reduced. Judging from your figures :

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 8000
 standard 37259 ms
 Knightly 4548 ms
max_hops 2000
 standard 5517 ms
 Knightly 4534 ms

I think all or most route searches managed to complete within the 2000 max_hops limit. Probably the proportion of transfer halts is rather low.

Knightly

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #72 on: September 28, 2009, 06:17:08 PM »
Additional information. The percentage of transported passengers.

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 2000
 standard 9%
 Knightly 83%

 :award:

knightly

  • Guest
Re: poor game flow in large maps
« Reply #73 on: September 28, 2009, 06:59:26 PM »
I think the size of the HNode array can be reduced (by half?) to compensate for the additional memory consumed by the service_counters.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #74 on: September 29, 2009, 09:46:31 AM »
Here is my latest STD SVE you can see the improvement that has been made also please notice thatthe game has gone from 470mil in the red to 10mil in the black.

Thanks to gwer/Prissi/Knightly and everyone else who contributed to making this game playable. If I didn't mention your name I'm sorry, but I do know who you are, Fred, er, Joe, No its Vil something or was it Z9***.

Anyway Thanks

http://simutrans-germany.com/files/upload/Colin's Standard 2682.sve

knightly

  • Guest
Re: poor game flow in large maps
« Reply #75 on: September 29, 2009, 03:05:37 PM »
I have attached an updated patch, also against r2682 and relative to the trunk folder. It includes 2 bugfixes and reduces the size of HNode array by half.

Offline Colin

  • Devotees (Inactive)
  • *
  • Posts: 663
  • Certa Cito
Re: poor game flow in large maps
« Reply #76 on: October 02, 2009, 11:12:42 AM »
Knightly kindly sent me a copy of the GDI version of his patch and I'm here to tell you, the flow of my game improved beyond all expectations. The traffic (all modes) flows smoothly, there is no jerkiness of movement and no pauses at Auto Save.

As I pointed out to Knightly, GDI version has never worked with larger maps on my computer. I've always used SDL.  With his patch I can now use GDI.

Anyone who has downloaded my latest SVE should try it with this patch.

Thanks Knightly.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #77 on: October 04, 2009, 07:09:56 PM »
Only the service counter is not included, since to me it seems like the warenziel-list does essentially the same.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #78 on: October 04, 2009, 07:42:32 PM »
Prissi,

Only the service counter is not included, since to me it seems like the warenziel-list does essentially the same.
Sorry, but I don't think so.

A halt X served by a single pax line which has a schedule containing, say, 8 halts, will end up having 7 halts in warenziele[0] for pax. That fulfils your criteria :
I.e. only adding when reachable_halt->get_warenziele[ware_catg_index].get_count() > 1 ? Since hat gehalten just adds to warenziele anyway.
but X is definitely *not* a transfer halt. A transfer halt is where ware packets can switch lines/convoys. If you think that I am wrong on this, please state the reasons.

The concept of transfer halt is the *gist* of my patch, and distorting it will largely diminish the usefulness of this patch. My centralised search in ST EXP also focuses on transfer halts, and it works fine for a long time without any problem, and has significantly reduced search time. I can't see why you have to insist on removing the service counters (which is actually the core of my patch), unless it really takes up a lot of space or processing time per se.

However, the addition of service counters only consumes a little bit more of memory. 1000 halts with 16 ware categories will only use an additional (16 categories  + 4 byte pointer) x 1000 halts = ~20KB. And the additional processing time for clearing and incrementing the service counters is relatively small, according to my test results. You may perform profiling to be accurate.

Knightly
« Last Edit: October 04, 2009, 07:48:44 PM by Knightly »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #79 on: October 04, 2009, 09:44:19 PM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ... Or did I mistake it completely? But it would be still an improvement for any case without this.

I will look at it again.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #80 on: October 05, 2009, 05:16:51 AM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ... Or did I mistake it completely? But it would be still an improvement for any case without this.

You are right, but only if both convoys are lineless convoys. I think most players will group 2 lineless convoys with identical schedules into a single line for easier management, so this is not much of a problem in general.

You can solve this problem by modifying hat_gehalten() to return a boolean value which indicates whether any halt has been added to warenziele in this function call, and increment the service_counter[catg] in rebuild_destinations() only if that return value is true. But I doubt if the additional processing time justifies the gain in general.

BTW, do you mind performing profiling on my patch? I am interested to know how much faster suche_route() is, and how much slower rebuild_destinations() is, after the modifications. Many thanks in advance! :)

Edit 1 :

To make sure that you understand the difference between using service_counter[catg] and your suggested check :
reachable_halt->get_warenziele[ware_catg_index].get_count() > 1
I have attached a simple diagram (1st attachment) to illustrate it. Assuming only pax are involved. The letters are the names of the halts, and the numbers in bracket refer to the number of halts in warenziele[0]. The blue circle is served by Line P (A>B>C>D>E), and the green circle by Line Q (E>F>G>H>I). In this setup, only Halt E is a transfer halt.

With my patch, only Halt E will be identified as a transfer halt, since there are 2 lines (P & Q) serving it (i.e. service_counter[0] > 1). Searching route from A to H will only add origin halt A, transfer halt E and destination halt H to the HNode array.

But with your suggestion, all halts satisfy your criteria (i.e. warenziele[0] > 1), thus any intermediate non-transfer halts may also be added to HNode unnecessarily during the search. In this particular case, nodes are added for A, B, C, D, E, F, G, H during the search from A to H, wasting processing time -- the waste is not just on adding the nodes, but also on additional processing time involved in processing that node afterwards.

As you can see, my original code and your suggestion are very different, and your suggestion will largely reduce the effectiveness of my patch in reducing search time. Service_counter[catg] is the cornerstone of my patch, and it is necessary to make my patch work as intended. So, unless you can find a better way to determine transfer halt, please do not remove service_counter from my patch.

As a sidenote, during my development of ST EXP's centralised search, I realised that most games usually have only 50% or less of its halts as transfer halts (of course, there are exceptions, depending on player's strategies). That is the reason why focusing on transfer halts in suche_route() can significantly reduce search time.

Edit 2 :

Just in case you are not sure why we don't need to add non-transfer halts to the HNode array, please take a look at the 2nd attached image. In this diagram, there is only 1 single line serving halts A to E.

When searching for the route from A to E, A as the origin halt will first be added to the HNode array. Then, A's reachable halts (namely, B, C, D and E) are checked, one by one : with B, it is checked against the destination halt to see if we have found the destination, but no, this is not the destination; next, check if it is a transfer halt, but no, so no more processing is needed.

Rationale : if B is a non-transfer halt, there is only a single line/lineless convoy serving it; if current node A has B as its reachable halt, then A must also be served by the same line/lineless convoy, which in turn means that B's reachable halts are included in A's reachable halt's list (except A of course) and will be checked while processing A's reachable halts. Thus, there is no need to add B to HNode array, and no need to check B's reachable halts.
« Last Edit: October 05, 2009, 07:30:15 AM by Knightly »

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #81 on: October 05, 2009, 12:45:13 PM »
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ...

Even so, nothing worse than current bahavior.

In current simutrans, search priority of hub station is very low, and passengers can't reach their destination. That causes poor game flow, if player set high max_hops.

Additional information. The percentage of transported passengers.

regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 2000
 standard 9%
 Knightly 83%

In current simutrans, I can't play regbombay1's London_C.sve withmax_hops 8000 because of Re: poor game flow. But max_hops 2000 is not fun, bevause only 9% of passengers can travel.

@Knightly
Can I use your patch for any fork version of simutrans, if this was denied ?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #82 on: October 05, 2009, 02:20:19 PM »
It will be incorporated. I will probably just get this a more descriptive name (like number_of_non_unique_schedules or so ... )

knightly

  • Guest
Re: poor game flow in large maps
« Reply #83 on: October 05, 2009, 03:03:11 PM »
@ Z9999

Can I use your patch for any fork version of simutrans, if this was denied ?

Sure, no problem :D Please take the liberty to use it anywhere you like.


@ Prissi

It will be incorporated. I will probably just get this a more descriptive name (like number_of_non_unique_schedules or so ... )

You mean "service_counter"? Actually I am not sure how it should be named. "service_counter" is the best I can think of, meaning "serviced by how many lines/lineless convoys", but I admit that it is not ideal ... If you can think of a better yet concise description, please feel free to change it. ;)

Offline z9999

  • Devotees (Inactive)
  • *
  • Posts: 848
Re: poor game flow in large maps
« Reply #84 on: October 05, 2009, 08:07:45 PM »
@Knightly
 Thank you.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #85 on: October 06, 2009, 05:51:39 PM »
Prissi,

A suggestion regarding connections_searched in rebuild_destinations() : instead of incrementing this variable by 1 per line/lineless convoy, we can increment it by fpl->get_count(). I propose this because players seem to vary a lot as to the size of their schedules : some prefer to have 7-8 halts per schedule, but others may prefer >30 halts. Longer schedules take longer to process, thus by using fpl->get_count(), you can better control the pace of rebuilding destinations. Of course, your formula for decrementing units_remaining in haltestelle_t::step() needs to be changed accordingly.

Knightly

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #86 on: October 06, 2009, 06:02:08 PM »
That is a valid suggestion. ALso it came to my mind, that it is very easy to check, whether a schedule added something to a connection or not, i.e. whether there are more than one identical schedule: The counter of warenziele is large after addition. WIll go to implement that and your patch tonight I think.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #87 on: October 06, 2009, 06:10:58 PM »
The counter of warenziele is large after addition.

Good idea. A simple check like this should do.

For games like Yoshi's with numerous lineless convoys, I agree with Gerw that the only way to reduce the time involved in rebuilding destinations is to register them at the halts like registering the lines. Do you think it is feasible?

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #88 on: October 06, 2009, 06:32:11 PM »
Yoshis game is from an 87 version several years ago where line management was more clumsy ... and it does not contains so much lineless convois. I think this could be deferred, but if you want to have a go at it. Certainly it may give advantage; but then convois need to handle changes from and to lines even more carefully.

EDIT:
I did profiling, but the differences are small; moreover, most improvement seems from less calls to halthandle_t::is_bound() and halthandle_t(). But as z9999 said, I think most people actually finding a route is more important.
« Last Edit: October 06, 2009, 06:53:03 PM by prissi »

knightly

  • Guest
Re: poor game flow in large maps
« Reply #89 on: October 06, 2009, 07:43:40 PM »
I did profiling, but the differences are small; moreover, most improvement seems from less calls to halthandle_t::is_bound() and halthandle_t(). But as z9999 said, I think most people actually finding a route is more important.

Do you mind posting the profiling results? Many thanks.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #90 on: October 06, 2009, 07:49:58 PM »
Well, they are about 12MB, and the change is not seen easily. But here you go, everything up to 0.5% contribution, no calling stack:

Code: [Select]
Flat profile: (improved system)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
  9.29     19.95    19.95    16647     0.00     0.00  karte_t::sync_step(long, bool, bool)
  5.83     32.47    12.52  1529605     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*, bool)
  5.00     43.20    10.73  5044991     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.82     51.41     8.21  1869586     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, schedule_t const*, spieler_t const*)
  2.97     57.80     6.39 1460434544     0.00     0.00  vector_tpl<ware_t>::get_count() const
  2.15     62.42     4.62  2094715     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  2.12     66.97     4.55 940084741     0.00     0.00  vector_tpl<ware_t>::operator[](unsigned int)
  2.03     71.34     4.37 696776484     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  1.87     75.35     4.01 192406260     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.82     79.27     3.92 130461686     0.00     0.00  planquadrat_t::get_boden_in_hoehe(short) const
  1.75     83.02     3.75 549425413     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.69     86.66     3.64 32334462     0.00     0.00  convoi_t::sync_step(long)
  1.67     90.25     3.59 233174821     0.00     0.00  grund_t::get_hoehe() const
  1.67     93.83     3.58 574663478     0.00     0.00  quickstone_tpl<haltestelle_t>::operator==(quickstone_tpl<haltestelle_t> const&) const
  1.65     97.38     3.55 152483261     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.64    100.91     3.53 937711102     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.54    104.22     3.31 240439540     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.52    107.49     3.27 18540007     0.00     0.00  convoi_t::calc_acceleration(long)
  1.48    110.66     3.17 139927198     0.00     0.00  grund_t::get_weg(waytype_t) const
  1.43    113.73     3.07 176234657     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.33    116.59     2.86 487695305     0.00     0.00  koord::koord(short, short)
  1.20    119.17     2.58 249793805     0.00     0.00  operator==(koord const&, koord const&)
  1.20    121.75     2.58 62523573     0.00     0.00  vehikel_t::get_gesamtgewicht() const
  1.19    124.30     2.55 54759565     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const
  1.09    126.64     2.34 359156267     0.00     0.00  koord3d::get_2d() const
  1.04    128.87     2.23 32300103     0.00     0.00  convoi_t::step()
  0.95    130.91     2.04 67751873     0.00     0.00  grund_t::get_vmove(koord) const
  0.94    132.93     2.02 82602392     0.00     0.00  ding_t::is_moving() const
  0.90    134.86     1.94 16125608     0.00     0.00  dingliste_t::remove(ding_t const*)
  0.83    136.65     1.79 648278617     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::operator[](unsigned int) const
  0.75    138.27     1.62 89449878     0.00     0.00  fussgaenger_t::sync_step(long)
  0.69    139.76     1.49 665227174     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::get_count() const
  0.60    141.04     1.28 28862148     0.00     0.00  stadtauto_t::sync_step(long)
  0.55    142.23     1.19 174167252     0.00     0.00  hashtable_iterator_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::next()
  0.54    143.40     1.17 240375956     0.00     0.00  karte_t::lookup(koord) const
  0.54    144.55     1.15 143737674     0.00     0.00  obj_besch_t::get_child(int) const
  0.53    145.69     1.14   133776     0.00     0.00  route_t::intern_calc_route(karte_t*, koord3d, koord3d, fahrer_t*, unsigned int, unsigned int)
  0.52    146.80     1.11 13741184     0.00     0.00  haltestelle_t::get_ware_summe(ware_besch_t const*) const


Code: [Select]
Flat profile: (previous system)

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
  9.45     21.54    21.54  1483245     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*, bool)
  8.50     40.93    19.39    17067     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.95     52.22    11.29  5431731     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  4.43     62.31    10.10 1645188374     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.85     68.81     6.50 1898991967     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.03     73.44     4.63 1596670257     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::operator[](unsigned int) const
  1.89     77.77     4.32  2050348     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.89     82.06     4.30 963837657     0.00     0.00  vector_tpl<ware_t>::get_count() const
  1.89     86.36     4.30 132048612     0.00     0.00  planquadrat_t::get_boden_in_hoehe(short) const
  1.82     90.52     4.16  1817492     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, schedule_t const*, spieler_t const*)
  1.71     94.41     3.89 188892750     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.69     98.27     3.86 155337440     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.66    102.06     3.79 1666172006     0.00     0.00  vector_tpl<quickstone_tpl<haltestelle_t> >::get_count() const
  1.65    105.82     3.76 237458275     0.00     0.00  grund_t::get_hoehe() const
  1.55    109.36     3.54 32458683     0.00     0.00  convoi_t::sync_step(long)
  1.51    112.80     3.44 246075434     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.51    116.24     3.44 141813284     0.00     0.00  grund_t::get_weg(waytype_t) const
  1.50    119.65     3.41 528617071     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.48    123.02     3.37 172490871     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.46    126.36     3.34 18589421     0.00     0.00  convoi_t::calc_acceleration(long)
  1.32    129.37     3.01 496337298     0.00     0.00  koord::koord(short, short)
  1.16    132.01     2.65 32234028     0.00     0.00  convoi_t::step()
  1.13    134.58     2.57 54660352     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const
  1.10    137.08     2.50 367527603     0.00     0.00  koord3d::get_2d() const
  1.07    139.52     2.44 68549744     0.00     0.00  grund_t::get_vmove(koord) const
  1.04    141.90     2.38 252639444     0.00     0.00  operator==(koord const&, koord const&)
  0.98    144.13     2.23 577424393     0.00     0.00  vector_tpl<ware_t>::operator[](unsigned int)
  0.97    146.35     2.22 62518948     0.00     0.00  vehikel_t::get_gesamtgewicht() const
  0.94    148.49     2.14 83061006     0.00     0.00  ding_t::is_moving() const
  0.78    150.27     1.78 291959379     0.00     0.00  quickstone_tpl<haltestelle_t>::operator==(quickstone_tpl<haltestelle_t> const&) const
  0.78    152.04     1.77 85600845     0.00     0.00  fussgaenger_t::sync_step(long)
  0.78    153.81     1.77 15981170     0.00     0.00  dingliste_t::remove(ding_t const*)
  0.70    155.40     1.59 69182787     0.00     0.00  haltestelle_t::get_warenziele(unsigned char) const
  0.62    156.81     1.41 28987517     0.00     0.00  stadtauto_t::sync_step(long)
  0.60    158.18     1.37 246011854     0.00     0.00  karte_t::lookup(koord) const

Indeed, suche_route is much faster, it is no longer the most time consuming subroutine any more. I think the next release will be a big step towards playing larger maps or better perfomance on netbooks.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #91 on: October 07, 2009, 11:31:03 AM »
I have written another patch to speed up suche_route() a bit when checking those already-processed halts. Although we now only check transfer halts, transfer halts also have reachable halts which have already been processed. Originally, halthandle boundness is checked before checking marke, meaning that 2 checks are required. But the boundness check is actually unnecessary for these already-processed halt entries.

This patch moves marke out of haltestelle_t, and consolidates them into a static array. In this way, we can check the marker first, and skip the boundness check if this halt has already been processed before.

For small games, the effect of this patch is not noticeable; but for large games like Colin's and Yoshi's, there is a noticeable reduction in search time. In general, this patch will have a greater effect on games with a higher proportion of transfer halts.

The static array consumes 262KB of memory, which is the amount of memory saved by reducing the size of the HNode array by half in the previous patch.

Here are some testing results :


Before applying the patch :

**** Colin - Finished ****
Rebuilding destinations takes :  112 ms
Rerouting goods takes :  7487 ms
Complete refresh takes :  7599 ms

**** Yoshi ****
Rebuilding destinations takes :  4963 ms
Rerouting goods takes :  616 ms
Complete refresh takes :  5579 ms

**** 1982 ****
Rebuilding destinations takes :  40 ms
Rerouting goods takes :  149 ms
Complete refresh takes :  189 ms

**** Wipi ****
Rebuilding destinations takes :  9 ms
Rerouting goods takes :  19 ms
Complete refresh takes :  28 ms

**** Ferndale ****
Rebuilding destinations takes :  2 ms
Rerouting goods takes :  5 ms
Complete refresh takes :  7 ms

       
After applying the patch :

**** Colin - Finished ****
Rebuilding destinations takes :  115 ms
Rerouting goods takes :  6855 ms
Complete refresh takes :  6970 ms

**** Yoshi ****
Rebuilding destinations takes :  4945 ms
Rerouting goods takes :  528 ms
Complete refresh takes :  5473 ms

**** 1982 ****
Rebuilding destinations takes :  40 ms
Rerouting goods takes :  147 ms
Complete refresh takes :  187 ms

**** Wipi ****
Rebuilding destinations takes :  8 ms
Rerouting goods takes :  18 ms
Complete refresh takes :  26 ms

**** Ferndale ****
Rebuilding destinations takes :  2 ms
Rerouting goods takes :  3 ms
Complete refresh takes :  5 ms


Note : Colin's save game is different from the one used previously.

Further testing is welcome.
« Last Edit: October 07, 2009, 11:35:33 AM by Knightly »

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #92 on: October 07, 2009, 07:08:27 PM »
This will certainly perform different on different processors, the longer the pipeline, the better.

I am quite torn on this; even in your old patch you used an unchecked array, which was marginally ok, since it was only accessed with an predefined counter. However, for a large project like simutrans, I would like to keep objects together. The mark of a station belongs imho to the station.

Of curse, that is only my view. But there were many more places liek the different tree types. The are accessed via a 9 bit variable. Nevertheless I put them into a vector, which will check boundness at every access, to catch a broken register or some other programm error before really bad things happen. Even if this costs same percent performance.

People tend to forget, what things belong together. Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

knightly

  • Guest
Re: poor game flow in large maps
« Reply #93 on: October 07, 2009, 08:44:38 PM »
Prissi,

This will certainly perform different on different processors, the longer the pipeline, the better.

Most probably you are right on this. Pipeline issue aside, this patch will avoid many unnecessary halthandle boundness checks. More specifically, each halt's handle will be checked for boundness for no more than once in a single suche_route() call.


I am quite torn on this; even in your old patch you used an unchecked array, which was marginally ok, since it was only accessed with an predefined counter.

If non_identical_schedules were to use vector, then I believe warenziele should also be a vector of vectors too, right? IMHO, if our code are written such that errors are already guarded against, why should we compel ourselves to use vectors to incur unnecessary overhead?


However, for a large project like simutrans, I would like to keep objects together. The mark of a station belongs imho to the station.

I think this is more a point of view than hard fact. Extension buildings are part of a station, no doubt. But for markers, I think its sole purpose is to serve suche_route(), but not inherently part of a halt by definition. It's only working data for suche_route().


People tend to forget, what things belong together. Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

I agree that things that go together should be grouped together in their respective classes. And I agree with the doctrines of OOP too. But sometimes we tend to assume that certain variables should belong to a certain class of objects; but if we think deeper, there may be no necessary connection between them.


As for the patch, I know in advance that you may not like the static array. Actually, if I do not need to initialise the array elements with zeros, I would have declared it as a static local array inside suche_route() like the HNode array, for I believe the markers are only working data of suche_route().


Edit :

I have made a small change to the patch (moving the init_markers() call out of an IF block in karte_t::init()). Updated patch attached.


Knightly
« Last Edit: October 08, 2009, 06:33:05 AM by Knightly »

Offline Spike

  • *
  • Posts: 1361
  • First Simutrans Developer and Graphics Artist
Re: poor game flow in large maps
« Reply #94 on: October 08, 2009, 09:23:01 AM »
Keeping things together with their data was imho the main idea of OOP. Maybe I have become to fundamentalistic in my views. But I am certainly open to challenge my optionions by arguments.

I agree that things that go together should be grouped together in their respective classes. And I agree with the doctrines of OOP too. But sometimes we tend to assume that certain variables should belong to a certain class of objects; but if we think deeper, there may be no necessary connection between them.

Trying to deliver arguments pro separate markers:

If the lifetime of data differs much, I think this is a sign that they are independent, and can/should be kept independently.

Stations have a lifetime of program runtime, the markers only for a search.

Also, if we think about threading, such marks must not be part of the station data, otherwise multi-threaded searches are not possible.

Offline prissi

  • Developer
  • Administrator
  • *
  • Posts: 9595
  • Languages: De,EN,JP
Re: poor game flow in large maps
« Reply #95 on: October 08, 2009, 07:36:28 PM »
Looking at the code, I feel like it would make sense to make the markers part of halthandle_t, i.e. derive a class from quckstone_tpl. That way also the initialisation would be automatically correct. Even more, the marked and mar test could be then part of the more intelligent halthandle too. But I would like to here you opinion.