Skip to main content ↑ ↓
Topic: Changes to routing of goods (Read 16269 times) previous topic - next topic

Changes to routing of goods

I'm currently alter the routing of goods. Now I have a first (not playable in general) beta version. The following should work:
- Changes to schedules of lines / convoys
- Changes of convoys of a line
- Changes of a lineless convoy

The following will not work (but may work after reloading a game):
- Building or removing a tile of a halt
- Using the stop moving tool

Currently there is no benefit to the computing time, but this will come in future ;)

Please test this patch and tell me wether changes to lines / convoys are proccesed right for you.

Edit: The patch is against r2159, I didn't test it with newer versions since there was many bugs in them.

Re: Changes to routing of goods

Reply #1 –
Perhaps would be good idea to request a spezial nightly to wernieman. This way you can reach to more people, that usually ignore this kind of issues because they don't know how to deal with a patch. I mean, it seems an important change, so I guess you'll need a lot of feedback for usual players.

Re: Changes to routing of goods

Reply #2 –
May I ask - what are the changes?
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Re: Changes to routing of goods

Reply #3 –
What exactly changes? Only some internal representation, or do you change aspects of system visible to player?

Offtopic: Ugh, I feel the slow regression of my English towards Germlish (or Engman?) too. It is so much easier to say "it not work". Basic English rules! Ein spezial Nightly, bitte!

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

Re: Changes to routing of goods

Reply #4 –
There is a problem with the patch.  In cl**** convoi_t, there is a method named get_name, but everywhere it is called as gib_name and compiling errors are produced.

Otherwise, it compiled ok, but I cannot see any effects.  Are there any visible effects?

Re: Changes to routing of goods

Reply #5 –
Quote
Are there any visible effects?

Hopefully not :) I think he is working on an improvement of the routing of goods including some caching. The purpose is to speed up routing calculation.
Parsley, sage, rosemary, and maggikraut.

Re: Changes to routing of goods

Reply #6 –
Quote from: isidoro – on
There is a problem with the patch.  In cl**** convoi_t, there is a method named get_name, but everywhere it is called as gib_name and compiling errors are produced.
Mmh. If you patch the version r2159 it should work (I translated gib_name and replaced it everywhere with the english get_name).


In previous version if you changed something, that perhaps vary the routing of goods, karte_t::set_schedule_counter() was called and all stations recalced their calculation and all goods was rerouted. Even if you only opened the schedule of a convoy (and changed nothing), this happens.

Now if you change something, the routines karte_t::fpl_changed() and karte_t::catg_changed are called and they can decide what to do (this is not implemented yet). So if you change, e.g., a coal line, the p****engers aren't rerouted anymore.


You might test the following: Playing around with changing convoys and lines. You should see the changes immediately at the detail window of the stations (lines and convoys belonging to this station and the connected stations). If something goes wrong, try to reproduce it and post in the forum, what you've done (all bugs should be reproducible).

Re: Changes to routing of goods

Reply #7 –
I could make a spezial run of the nightlys BUT .....

Pleae make it for the new Version (217x) ....

Is this an offizial Projket, so if there a change that it will end in the Trunk?
I hope you understand my English

Re: Changes to routing of goods

Reply #8 –
Quote from: wernieman – on
I could make a spezial run of the nightlys BUT .....

Pleae make it for the new Version (217x) ....
Mmh. I didn't adopt the changes of the past r2159 versions since they contain some (many?) bugs. Can you patch it to r2159? Otherwise I have to spend some time to merge all changes, but I didn't feel like doing so unless there is a bugless revision.

Quote
Is this an offizial Projket, so if there a change that it will end in the Trunk?
Yes. Prissi wanted to create a branch, but he hasn't the rights on the svn-server to give me writing access.

Edit:
I've done a quick (and dirty?) patch against r2170. But I haven't had a deeper look on the changes and, so there is no warranty ;)

Re: Changes to routing of goods

Reply #9 –
At the moment I have no time for a spezial run .... so you have time to Saturday .. ;o)
I hope you understand my English

Re: Changes to routing of goods

Reply #10 –
A new beta version of my patch. It still against version 2171. Altering stations doesn't work yet.

But now for each halt the number of the connected component is saved. You can see this in the halt detail frame (it's the number behind the category names). It means that all halts that are connected, have the same number and vice versa. So in later games, if p****engers can travel between all halts, all halts should have a "1" behind "p****engers". (The number behind the halts in this frame is the internal ID and not important for players. It's still there for debugging). Now you can check this number for to station and if it isn't the same, you have not look for a route.

Todo: Correct handling when altering stations, include a caching system for goods routes.

Re: Changes to routing of goods

Reply #11 –
New version of my patch. Now adding and removing stations works fine. Also the connected components for each category are computed (all stops with the same number are connected). You can see them in the halt detail window behing the category names (1). Behind the station names the ID of this halt is displayed, but usually of no interest - only displayed for debugging (2). Also a list of convoys serving this stop is displayed (3). The routing of goods also benefit of the computed connected components and so it's currently not limited by max_transfers and max_hops. (There is only a debugging information, if a good needs more than 1500 hops or more than 7 transfers).

Currently making a stop public is not working. The next goal is implementing a caching system.

Re: Changes to routing of goods

Reply #12 –
I have profiled the latest version of my patch and even with the unlimited BFS in haltestelle_t::suche_route the computation time of this routine decreased. You will find the profiles appended.

In my opinion, there is even more space for optimisation (by defining haltestelle_t::warenziele by a ordered_vector_tpl and by dropping the single linked list in suche_route, you can just use the indexes of the array 'nodes').

Re: Changes to routing of goods

Reply #13 –
Well, please test everybody.

I think I would like include it after 101. Currently I just want to release a new stable without new features, preferably this year.

I agree that sorted array will be helpful. However, public stops will be a key point for multiplayer and thus absolutely neccessary (apart from oil rigs and fish_swarms ... )

EDIT: Could not test it, since aparently files are missing.

Re: Changes to routing of goods

Reply #14 –
I did some profiling with the first version (first post) of your patch (which did compile after a little tweaking). However the results were not too good:

original
Code: [Select]
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  8.88      7.20     7.20   426385     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  6.50     12.47     5.27     5429     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.48     16.10     3.63     4086     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.68     19.08     2.98 474423161     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  3.37     21.81     2.73  2122536     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.27     23.65     1.84 473705611     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.26     25.48     1.83 666030882     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.25     27.30     1.82 606091288     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  2.11     29.01     1.71 537855165     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.95     30.59     1.58   501263     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  1.74     32.00     1.41 91931538     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.70     33.38     1.38 453983945     0.00     0.00  warenziel_t::gib_zielhalt() const

patched
Code: [Select]
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  8.61      8.01     8.01     4924     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  8.32     15.75     7.74   423708     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.61     20.97     5.22     5779     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.44     25.10     4.13 1499424232     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  3.62     28.47     3.37  2516619     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.83     31.09     2.63 532592865     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.52     33.44     2.34 469943829     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.50     35.77     2.33 1507417495     0.00     0.00  vector_tpl<route_t::ANode*>::get_count() const
  2.33     37.94     2.17 533897825     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.18     39.97     2.03 788778056     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.02     41.84     1.88   595308     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  1.73     43.45     1.61 512908572     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.61     44.95     1.50 577198113     0.00     0.00  warenziel_t::gib_zielhalt() const

suche_route() *increased* from 8.18s (since first run for 81s vs 93s of the second) to 15.75s, i.e. simply doubled.

Better in your profilng (forget about percentages, you need to look at the seconds). Because the first profiling run for 695s vs 659s for the second the second values need to be multiplied by 1,055. Thus we have 247s versus 230s, a gain of 7%.

Attached the diff I updated from the first post, without ordered_vector_tpl.h

EDIT: Using this file the newer patch also compiles until simhalt.cc complains about a lot linehandles_vec etc missing. I would like to do more profiling, but first I need to be able to compile at all.

Re: Changes to routing of goods

Reply #15 –
Quote from: prissi – on
However, public stops will be a key point for multiplayer and thus absolutely neccessary (apart from oil rigs and fish_swarms ... )
Only the function haltestelle_t::make_public_and_join doesn't work correctly yet, but I will fix it, too. Building or altering public stops works fine.

Quote
EDIT: Could not test it, since aparently files are missing.
I had forgot to do 'svn add tpl/ordered_vector_tpl.h'. The new patch file is appended.

Re: Changes to routing of goods

Reply #16 –
I pimped up suche_route a little bit and we could save more computation time:
Code: [Select]
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 20.05    115.09   115.09  9811597     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  6.29    151.20    36.11 18595080     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  5.36    181.95    30.75    26597     0.00     0.01  karte_t::sync_step(long, bool, bool)
  5.31    212.43    30.48  1541292     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  3.34    231.60    19.17    15726     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.13    249.58    17.99 3363327223     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.62    264.60    15.02 2707242458     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
(The profiling runs for 566s.)

Furthermore, suche_route is mostly called by fabrik_t::verteile_waren, so we can save most of the computation time by cache the computed routes, since the factories always compute the same routes.
Code: [Select]
                2.95    5.40  149312/1541292     haltestelle_t::liefere_an(ware_t) [35]
                3.26    5.97  165086/1541292     stadt_t::step_p****agiere() [44]
               24.26   44.38 1226894/1541292     fabrik_t::verteile_waren(unsigned int) [21]
[20]    15.0   30.48   55.75 1541292         haltestelle_t::suche_route(ware_t&, koord*) [20]

Re: Changes to routing of goods

Reply #17 –
Well, then you game is strange. Suche Route is mostly called by p****engers, since those are generated at each house and thus are in most need for routes. On the Yoshi map I got those results (fast forward of course to minimize the drawing routine impact).

old
Code: [Select]
Flat profile: 273,1s

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  8.56     23.38    23.38  1543988     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  7.03     42.57    19.20    19446     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.09     53.73    11.16    16896     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.61     63.59     9.86 1627932145     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  3.59     73.39     9.79  7410328     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.70     80.77     7.38 1645137923     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.61     87.89     7.12 1869557202     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.27     94.08     6.19 2283757513     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.27    100.27     6.19  1844555     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  2.03    105.81     5.54 1969576809     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.82    110.78     4.97 1579570006     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.69    115.40     4.62 1573122411     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.67    119.97     4.57  2086585     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.65    124.47     4.51 139871352     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.56    128.75     4.27 172556166     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.48    132.79     4.05 159421305     0.00     0.00  grund_t::gib_weg(waytype_t) const
  1.40    136.62     3.82 193489934     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.34    140.26     3.65 257230441     0.00     0.00  grund_t::gib_hoehe() const
  1.33    143.91     3.64 252401163     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.32    147.51     3.61  1767738     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.25    150.92     3.40 33304443     0.00     0.00  convoi_t::sync_step(long)
  1.23    154.28     3.36 19378495     0.00     0.00  convoi_t::calc_acceleration(long)
  1.21    157.59     3.31 1643920274     0.00     0.00  einstellungen_t::gib_max_hops() const
  1.06    160.49     2.90 288219829     0.00     0.00  operator==(koord const&, koord const&)
  1.03    163.31     2.82 535491703     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.01    166.07     2.77 175221723     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.01    168.82     2.75 528360531     0.00     0.00  koord::koord(short, short)

Code: [Select]
Flat profile: 313,9s

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 10.73     33.68    33.68  1464040     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.98     52.47    18.79    19133     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.14     65.44    12.98 2998938572     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  3.48     76.38    10.93 2026980459     0.00     0.00  slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::next()
  3.36     86.92    10.55    17313     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.24     97.11    10.18 1954750234     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  3.22    107.21    10.10  2540750     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  3.00    116.63     9.43  7854335     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.62    124.84     8.21 1913186777     0.00     0.00  slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::get_current() const
  2.29    132.02     7.18 2247617788     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.92    138.04     6.02  1760986     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.80    143.69     5.65  2079604     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.77    149.26     5.57 1759681819     0.00     0.00  vector_tpl<route_t::ANode*>::get_count() const
  1.70    154.60     5.34 1744446382     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.32    158.75     4.15 168335459     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.25    162.67     3.92 127352346     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.18    166.37     3.70 155429540     0.00     0.00  grund_t::gib_weg(waytype_t) const
  1.15    169.99     3.62 223482675     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.15    173.60     3.61 191779879     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.10    177.06     3.46 243438617     0.00     0.00  grund_t::gib_hoehe() const
  1.08    180.45     3.39 32273673     0.00     0.00  convoi_t::sync_step(long)

Both games were run exactly the same time (from April to first July, the old accidently even until 3rd July)

suche_route took longer for your routine. The 40s time the patched version took longer is mostly due to
quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&) (from 6s to 13s)
slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::next() (from 0 to 11s)
slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::get_current() const (from 0 to 8s)
haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*) (from 3s to 6s)
(+29s in those routines)
Savings are in Warenziel:
slist_iterator_tpl<warenziel_t>::next() (from 7s to 0)
warenziel_t::gib_zielhalt() const (from 5s to 0)
(-12 s in those)

Memory consumption was 58MB vs 56MB for the game.

-----------------

Because it take most time to find a unsuccessful route, I suggested caching those. This will help factories as well as towns.

Re: Changes to routing of goods

Reply #18 –
Sorry for replying to my own post. I added caching (albeit only tested very little) and it decreased suche_route by 2s without adding much memory consumption (the rounded up number was the same as the original one)

Code: [Select]
Flat profile: 249s

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  8.67     21.60    21.60   759924     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  7.19     39.51    17.91    18519     0.00     0.00  karte_t::sync_step(long, bool, bool)
  3.55     48.35     8.85  6655817     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.02     55.88     7.53 1447526301     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.60     62.35     6.47  1736486     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  2.45     68.45     6.10 1453509307     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.44     74.55     6.09    12593     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  2.34     80.38     5.83 2061981421     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.15     85.73     5.36 1653320164     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.86     90.36     4.63  2057731     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.61     94.39     4.02 190425555     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.59     98.34     3.96 1398455382     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.55    102.21     3.86 1422473709     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.55    106.07     3.86 160332364     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.53    109.88     3.81 137278390     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.50    113.63     3.75 32804916     0.00     0.00  convoi_t::sync_step(long)
  1.50    117.36     3.74 147710954     0.00     0.00  grund_t::gib_weg(waytype_t) const
  1.46    121.00     3.63 365246258     0.00     0.00  koord3d::gib_2d() const
  1.46    124.63     3.63 246026370     0.00     0.00  grund_t::gib_hoehe() const
  1.42    128.18     3.55 19141964     0.00     0.00  convoi_t::calc_acceleration(long)
  1.36    131.56     3.38  1731227     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.36    134.94     3.38 244734182     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.28    138.14     3.20 1089259185     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.20    141.12     2.98 173005008     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.15    143.98     2.86 526342006     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.13    146.80     2.82 504766068     0.00     0.00  koord::koord(short, short)
  1.13    149.61     2.81 265894999     0.00     0.00  operator==(koord const&, koord const&)
  1.04    152.20     2.59 32762628     0.00     0.00  convoi_t::step()

The finde_route is probably due to stucked citycars ... maybe I should do those games without those.

Attached the patch (very little tested). It should not affect the number of sucessful routed goods nor change the delivery system in any other way.

Re: Changes to routing of goods

Reply #19 –
Quote from: prissi – on
Well, then you game is strange. Suche Route is mostly called by p****engers, since those are generated at each house and thus are in most need for routes. On the Yoshi map I got those results (fast forward of course to minimize the drawing routine impact).
I also used the game of Yoshi, that you have send me. Can you post the call graph of your profiling for suche_route?

Quote
suche_route took longer for your routine. The 40s time the patched version took longer is mostly due to
quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&) (from 6s to 13s)
slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::next() (from 0 to 11s)
slist_iterator_tpl<quickstone_tpl<haltestelle_t> >::get_current() const (from 0 to 8s)
haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*) (from 3s to 6s)
(+29s in those routines)
Savings are in Warenziel:
slist_iterator_tpl<warenziel_t>::next() (from 7s to 0)
warenziel_t::gib_zielhalt() const (from 5s to 0)
(-12 s in those)
You've missed 'slist_iterator_tpl<warenziel_t>::get_current() const'. 5s more saved with my patch  :P

I think the increased times are also caused by the fact that my patch neglect max_hops and max_transfers. I also can't explain the increased time of haltestelle_t::hole_ab. I didn't touch it.

Quote
Because it take most time to find a unsuccessful route, I suggested caching those. This will help factories as well as towns.
This is already implemented by haltestelle_t::con_comp. There is a connection between halt_a and halt_b for catg_index, if halt_a->con_comp[catg_index] == halt_b->con_comp[catg_index] and if halt_a->con_comp[catg_index] != 0.

I am wondering about these profiles. I feel like handling with some kind of magic :)

Can you test the new appended version of my patch? There I defined haltestelle_t::warenziele as an array of halthandle_vec and so we will save the calls of slist_iterator_tpl.

Re: Changes to routing of goods

Reply #20 –
I will try it again. I delete all citycar.*.pak from my pakfolder, since those are the most random elements here. And make sure, you are maxing out the fast forward (set it to 1000 or so).

Re: Changes to routing of goods

Reply #21 –
Ok, without citycars, game and pak load automatically, all messages autoclose.

old code:
minimized total 255,9s second 259,3s
memory between 39400kB and 41800kB
P****engers 33%
Post 21%

Code: [Select]
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 11.43     29.25    29.25  1502425     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.63     43.66    14.40    18463     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.46     55.08    11.42 1584337647     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  3.97     65.23    10.15    15162     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.29     73.66     8.43  6784023     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.13     81.66     8.00 1601035112     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.70     88.56     6.90 2223387965     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.35     94.56     6.00 1819776320     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.20    100.19     5.63  1680132     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  1.93    105.13     4.94 1769667949     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.84    109.83     4.70 1537297492     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.79    114.41     4.58 1531036154     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.49    118.22     3.82  1706583     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.42    121.86     3.64  1996273     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.35    125.33     3.46 32342391     0.00     0.00  convoi_t::sync_step(long)
  1.35    128.78     3.45 1599828592     0.00     0.00  einstellungen_t::gib_max_hops() const
  1.35    132.23     3.45 107987406     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.23    135.38     3.15 1603078938     0.00     0.00  karte_t::gib_einstellungen() const
  1.18    138.41     3.03 163004359     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.15    141.35     2.94 208523962     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.14    144.26     2.91 203551949     0.00     0.00  grund_t::gib_hoehe() const
  1.12    147.13     2.87 1783291686     0.00     0.00  vector_tpl<route_t::ANode*>::get_count() const
  1.12    149.99     2.86 19017002     0.00     0.00  convoi_t::calc_acceleration(long)
  1.07    152.71     2.73 145805716     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.02    155.32     2.61 112422439     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.00    157.88     2.56 54977847     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const

and second:
Code: [Select]
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 12.59     32.64    32.64  1489845     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.37     46.56    13.92    18326     0.00     0.00  karte_t::sync_step(long, bool, bool)
  4.16     57.35    10.79 1589167260     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  3.89     67.44    10.09    13715     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.29     75.97     8.53 1606343252     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.94     83.58     7.61  6650334     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.90     91.11     7.53 2229764815     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.33     97.15     6.04 1825290743     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.05    102.47     5.32  1646269     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  2.00    107.66     5.19 1542396091     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.84    112.43     4.77 1612835814     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.84    117.19     4.76 1536236002     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.70    121.59     4.40  2001100     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.61    125.76     4.17 1605136600     0.00     0.00  einstellungen_t::gib_max_hops() const
  1.51    129.67     3.91 107879945     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.40    133.29     3.62  1705248     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.37    136.85     3.56 19113064     0.00     0.00  convoi_t::calc_acceleration(long)
  1.35    140.36     3.51 1608378372     0.00     0.00  karte_t::gib_einstellungen() const
  1.22    143.54     3.17 32350320     0.00     0.00  convoi_t::sync_step(long)
  1.12    146.44     2.90 202627304     0.00     0.00  grund_t::gib_hoehe() const
  1.06    149.19     2.75 163018130     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.05    151.91     2.72 207872148     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const

your code:
total 267,2s
memory between 40500kB and 46500kB
P****engers 52%
Post 21%
Code: [Select]
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 16.64     44.46    44.46  1482615     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.87     60.14    15.68    18155     0.00     0.00  karte_t::sync_step(long, bool, bool)
  5.29     74.26    14.12 3165878648     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  3.51     83.63     9.37    13040     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.39     92.69     9.06 2460099998     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.55     99.50     6.80  6273195     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.35    105.78     6.28 2096927630     0.00     0.00  ordered_vector_tpl<quickstone_tpl<haltestelle_t>, unsigned short>::get_by_index(unsigned short) const
  2.29    111.89     6.11  1791235     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.95    117.10     5.21  1654897     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  1.67    121.55     4.45 1589204793     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.66    125.99     4.44  2069764     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.34    129.56     3.57 559439927     0.00     0.00  quickstone_tpl<haltestelle_t>::operator==(quickstone_tpl<haltestelle_t> const&) const
  1.29    133.00     3.44 100241111     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.26    136.37     3.38 32889492     0.00     0.00  convoi_t::sync_step(long)
  1.17    139.49     3.12 1008054273     0.00     0.00  vector_tpl<ware_t>::operator[](unsigned int)
  1.15    142.55     3.06 19154175     0.00     0.00  convoi_t::calc_acceleration(long)
  1.08    145.43     2.88 166307945     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.03    148.18     2.75 461906969     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.02    150.90     2.71 149366562     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)


my caching code:
total 241,8s
memory between 38200kB and 46000kB
P****engers 33%
Post 21%

Code: [Select]
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 13.31     32.19    32.19   751021     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  5.87     46.37    14.18    17744     0.00     0.00  karte_t::sync_step(long, bool, bool)
  3.21     54.13     7.77 1430432534     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.88     61.09     6.96  6001066     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  2.77     67.79     6.70 1436250716     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  2.70     74.31     6.52 2037970909     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.66     80.73     6.42    13082     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  2.09     85.80     5.06 1633681009     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  1.89     90.36     4.57  1984277     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.78     94.67     4.30  1490387     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  1.69     98.75     4.09 1405342181     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.60    102.62     3.87  1715025     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.53    106.31     3.69 107662601     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.51    109.96     3.65 1381915426     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.44    113.44     3.48 1438259138     0.00     0.00  karte_t::gib_einstellungen() const
  1.33    116.67     3.23 18980169     0.00     0.00  convoi_t::calc_acceleration(long)
  1.30    119.81     3.15 32281602     0.00     0.00  convoi_t::sync_step(long)
  1.27    122.87     3.06 434896895     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.24    125.87     3.00 204733482     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.20    128.77     2.90 1435409371     0.00     0.00  einstellungen_t::gib_max_hops() const
  1.20    131.66     2.89 1027928457     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.17    134.48     2.82 161567383     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.14    137.24     2.76 197284070     0.00     0.00  grund_t::gib_hoehe() const
  1.03    139.74     2.50 287359649     0.00     0.00  koord3d::gib_2d() const
  1.01    142.17     2.43 400544479     0.00     0.00  koord::koord(short, short)
  1.00    144.60     2.42 145222083     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)

Full logfiles are found here: http://www.simutrans-germany.com/files/upload/simutrans.zip

suche_route() is 44s versus 29s/33s which accounts nearly for the difference intotal time. Interestingly  vector_tpl<ware_t>::operator[](unsigned int) and vector_tpl<ware_t>::get_count() const (3.12s and 2.59s are in the top routines, while in the old code they are much further down 2.15s and 1.01s). Also memory consumption is of course worse 39,64 MB versus 42,48MB or 42MB for caching only. (The percentage most likely change due to the time for image drawing even though minimized.)

In the moment it seems that your version consumes more memory is slower [and as a feature? has not a max_hop limit (which is essential with multiplayer. Otherwise with a single public interchange all poeple will find a rout over it, even though the exceed the maximum hops clearly.]

If it is of any consolation, also my caching is not very effective apparently and mainly east up memory, as was multithreading and a zillion (ok, less than ten) other attempts I did there. Even more, nothing seems broken (apart from p****engers finding a route that are too long in transit imho), so programmingwise you did a good job.

What I learned from this profiling session is that we need a new grafik driver without an interface to get reliable profiling. Also the impact of different random generator settings is really huge, thus even three mont are too short (but they took about 20min per run on my machine :()

Re: Changes to routing of goods

Reply #22 –
Some very minor optimisations with large impact. Those would apply also to the other code, imho.

The = operator for quickstone was unneeded and the handles for the search are references and the max_hops are constant before. The game was run the same time as before.

Code: [Select]
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 10.12     23.02    23.02  1491857     0.00     0.00  haltestelle_t::suche_route(ware_t&, koord*)
  6.42     37.63    14.61    17714     0.00     0.00  karte_t::sync_step(long, bool, bool)
  3.79     46.26     8.63    14042     0.00     0.00  route_t::find_route(karte_t*, koord3d, fahrer_t*, unsigned int, unsigned char, unsigned int)
  3.43     54.05     7.79 1601981873     0.00     0.00  slist_iterator_tpl<warenziel_t>::next()
  3.34     61.65     7.60  5976032     0.00     0.00  display_img_nc(short, short, short, unsigned short const*)
  3.23     68.99     7.34 1584873484     0.00     0.00  quickstone_tpl<haltestelle_t>::is_bound() const
  2.71     75.15     6.16 1953899287     0.00     0.00  quickstone_tpl<haltestelle_t>::quickstone_tpl(quickstone_tpl<haltestelle_t> const&)
  2.59     81.05     5.90 1820628738     0.00     0.00  quickstone_tpl<haltestelle_t>::operator->() const
  2.31     86.31     5.26  1490418     0.00     0.00  recode_img_src_target_color(short, unsigned short*, unsigned short*)
  2.23     91.38     5.07  1700855     0.00     0.00  haltestelle_t::hole_ab(ware_besch_t const*, unsigned int, fahrplan_t*)
  1.99     95.91     4.53 1601934882     0.00     0.00  vector_tpl<route_t::ANode*>::operator[](unsigned int)
  1.77     99.93     4.02 1538235056     0.00     0.00  slist_iterator_tpl<warenziel_t>::get_current() const
  1.59    103.54     3.61 1532025506     0.00     0.00  warenziel_t::gib_zielhalt() const
  1.58    107.14     3.60 107929129     0.00     0.00  planquadrat_t::gib_boden_in_hoehe(short) const
  1.56    110.69     3.55 32252529     0.00     0.00  convoi_t::sync_step(long)
  1.51    114.13     3.44  1985325     0.00     0.00  hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::put(sync_steppable*, sync_steppable*)
  1.48    117.51     3.38 19125885     0.00     0.00  convoi_t::calc_acceleration(long)
  1.47    120.85     3.34 161815100     0.00     0.00  ding_t::get_flag(ding_t::flag_values) const
  1.32    123.85     3.00 205999433     0.00     0.00  karte_t::ist_in_kartengrenzen(short, short) const
  1.23    126.64     2.79 110903172     0.00     0.00  dingliste_t::bei(unsigned char) const
  1.17    129.29     2.66 410915688     0.00     0.00  koord::koord(short, short)
  1.13    131.87     2.57 434182531     0.00     0.00  slist_iterator_tpl<hashtable_tpl<sync_steppable*, sync_steppable*, ptrhash_tpl<sync_steppable*> >::node_t>::next()
  1.13    134.44     2.57 110873373     0.00     0.00  grund_t::gib_weg(waytype_t) const
  1.13    137.00     2.56 145490772     0.00     0.00  vehikel_basis_t::fahre_basis(unsigned int)
  1.09    139.49     2.49 200955396     0.00     0.00  grund_t::gib_hoehe() const
  1.06    141.88     2.40 32247243     0.00     0.00  convoi_t::step()
  1.02    144.19     2.31 55111467     0.00     0.00  quickstone_tpl<simline_t>::is_bound() const

Re: Changes to routing of goods

Reply #23 –
Now I added also caching of found routes and some improvements inspired by prissi (references). This will consume more memory (in a huge test game 70 instead of 50 mb after 2 months) but save some computation time.

What does not work yet:
- make stop public
- if the connected factories of a stop change, existed goods may take a wrong route
- if the cache is deleted the memory isn't freed

Todo:
- clean up the code
- patch against newest revision

Re: Changes to routing of goods

Reply #24 –
A new patch for prissi. It's against r2227 and it doesn't include caching. I just translated my old patch, but I didn't had a deeper look. Since last updates doesn't touch routing matters, it should work.

Re: Changes to routing of goods

Reply #25 –
There is for instance and "halthandlevec" type(?) which is never defined anywhere.
 

Re: Changes to routing of goods

Reply #26 –
This is defined in ordered_vector_tpl:
Code: [Select]
typedef ordered_vector_tpl<uint8, uint8> catg_index_vec;
typedef ordered_vector_tpl<halthandle_t, uint16> halthandle_vec;
typedef ordered_vector_tpl<linehandle_t, uint16> linehandle_vec;
typedef ordered_vector_tpl<convoihandle_t, uint16> convoihandle_vec;