I suspect this is not a pak64-specific issue...
Meanwhile, have you compared the performance of the GDI executable vs. SDL?
Can you post your savegame?Ok posted to http://simutrans-germany.com/files As Colin's Standard 2611.sve
There was a brief period of reduced responsiveness immediately after loading, but soon afterwards the game ran smoothly. When I tried to add a halt or adjust certain convoy's schedule, responsiveness was reduced again shortly afterwards for quite some time.I've noticed the same, while trying Colin's game. So it's the rerouting of goods, which makes the game laggy...
So, probably the reduced responsiveness is caused by the re-routing of all existing ware packets in one single world step after set_schedule_counter() is triggered by actions like halt construction/deletion or schedule changes.
I have just tried Colin's save game.
There was a brief period of reduced responsiveness immediately after loading, but soon afterwards the game ran smoothly. When I tried to add a halt or adjust certain convoy's schedule, responsiveness was reduced again shortly afterwards for quite some time.
I've noticed the same, while trying Colin's game. So it's the rerouting of goods, which makes the game laggy...
Reduced by quite a lot and when building a game, because one is continually adding halts or new schedules, it happens with repeated monotony. Every few game days actually, and not counting Auto Save which I've extended to every 3 months. Brave little Aussie fellow that I am. ;D ;D ;D
Gerw, is it possible to spread the load of re-routing ware packets across a few steps?It's currently spread across 32 steps, see spieler_t::step. But maybe this number should depend on the time, the rerouting needs.
It's currently spread across 32 steps, see spieler_t::step. But maybe this number should depend on the time, the rerouting needs.
Thanks a lot for pointing out. :) It is quite incredible that after spreading re-routing across 32 steps, the game is still so unresponsive.But one can think of a worst case, where all the 'expensive' stations (with many waiting goods) are rerouted in one step...
I could set the station coverage back to 2 but surely that would lead to an increase in Trams/Tram lines/Stations, creating even more route finding?Directly, it will only increase routing calculation effort to a smaller extent, because of the larger number of stations ("hops"). But usually, you will have more different lines, more interconnection points and more transfers, and that makes a big difference.
It makes a loss of over 41 thousand (not in travel costs) when the passengers leave. It returns home with over 300 passengers and makes a profit of over 22k when the passengers leave. Have I got a setting in wrong in the config.tab or is this another bug?(I assume that you don't refer to ST-experimental.)
As I wrote, my suggestions (if they matter at all) will not help (much) in the case of the passenger/mail network.
Directly, it will only increase routing calculation effort to a smaller extent, because of the larger number of stations ("hops"). But usually, you will have more different lines, more interconnection points and more transfers, and that makes a big difference.
Do you mean that if I make multiple smaller Tram networks in my cities instead of one large network it would improve the flow of the game?More different lines means more schedules and transfers to check, so goods routing calculation will need more CPU time. From this aspect, a larger station coverage can support in reducing calculation effort.
As your savegame doesn't contain an extremely large network, there may be a performance bug. Additionally, Z9999 may be right when he said that ST has become "too heavy".
Regarding the obscure revenue: It's unrelated to the program performance problems, so could you please open a new topic for that, also providing the savegame with the train? After that, I will move my own replies and any remaining related text there.
The station coverage is not important.
The problem in your savegame are not the size of the map but the shear amount of waiting persons. You have several stations with more than 300000 people waiting. Updating such a monster will of course take some time.
I will look into the code to make it smoother, although no promises ...
Hi Colin :)
According to the source code update history, Prissi's changes for speeding up re-routing have already been incorporated. So, does it improve the responsiveness of your game?
Knightly
No, if anything it's getting worse. I'm sorry to say.
void spieler_t::step()
{
if( halt_list.get_count()>0 ) {
uint32 it = halt_iterator_start;
slist_iterator_tpl <halthandle_t> iter( halt_list );
while( it>0 && iter.next() ) {
it--;
}
if( it>0 ) {
halt_iterator_start = 0;
}
else {
uint32 units_handled = 0;
while( units_handled<8192 ) {
if( !iter.next() ) {
halt_iterator_start = 0;
break;
}
halt_iterator_start ++;
// iterator until 8192 passengers were handled
units_handled += iter.get_current()->sum_all_waiting_goods();
iter.get_current()->step();
}
INT_CHECK("simplay 156");
}
}
}
I strongly suspect that you fell victim to a display bug: the sum of passengers of the packages displayed is never 300k, not even close. I guess lots of destinations with letter >B are missing.
bool haltestelle_t::step()
(...)
else if(reroute_counter!=welt->get_schedule_counter()) {
// all new connection updated => recalc routes
if( !reroute_goods() ) {
andbool haltestelle_t::reroute_goods()
{
// reroute only on demand
reroute_counter = welt->get_schedule_counter();
(...)
// break after a certain number of reroute actions
if( ++packets==255 ) {
return false;
}
Doing in one step caused the lag that we are trying to get rid ofBut if you do all searches within one BFS run, it will take only a little bit more time than the BFS run for the packet with the most transfers. So it won't be more laggy than the current nightly and the rerouting would be done much faster.
Not sure, what "BSF"
but rerouting all goods of one of the large stations took more than 100msIt tooks only 100ms if you reroute each good for itself. If you take one "big" run, where you search the graph for all possible ways, you can calculate all new routes at once.
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.
Thanks Gwer, and many thanks to Knightly who has tried his hardest to guide this addle brained gamer through my trials and tribulations.
Although 500 steps mean two minutes.
if(waren[last_catg_index] && waren[last_catg_index]->get_count()>0) {We can reroute as a batch a number of packets, determined by the smaller of (1) units_remaining and (2) (warray->get_count() - last_ware_index).
vector_tpl<ware_t> * warray = waren[last_catg_index];
while( last_ware_index<warray->get_count() ) {
if( suche_route( (*warray)[last_ware_index], NULL, false )==NO_ROUTE ) {
// remove invalid destinations
warray->remove_at(last_ware_index);
}
else {
last_ware_index++;
}
// break after a certain number of reroute actions
if( --units_remaining==0 ) {
return false;
}
}
// now we are finisched with this array
// => reset last_ware_index for the next categorie
}
I did some testing with this and yoshis game and I think I reasonable balanced it.
As for Gerw's suggestion to combine multiple searches for each individual packet into a single search, I think he is right that such combined search can reduce search time significantly, by eliminating the need to rebuild search trees from scratch for each individual packet. However, I think search time cannot be reduced to such a short time as entailed by the single longest individual search, because each examined halt needs to be compared against a list of outstanding ware packets' destination halts to see if there is a match. With a large game like Colin's, some halts may have over 900 pax packets, so even a combined search have to take quite some time to finish, still causing unresponsiveness problem.If you sort the destinations of the 900 packets, you can use binary search and you will need at most log(900) = 10 comparisons each step (Maybe a hash table is even better?). Further, you can kick out the packets, for which the route is already found. Imho, it takes maybe the time of routing 5 packets (with long route).
Can anyone tell me why my uploads always have a Red 'File Delete' where the uploaders name usually goes?
If you sort the destinations of the 900 packets, you can use binary search and you will need at most log(900) = 10 comparisons each step (Maybe a hash table is even better?). Further, you can kick out the packets, for which the route is already found. Imho, it takes maybe the time of routing 5 packets (with long route).
I see. Look forward to your patch then :)I don't feel like patching now. I've got not much time this (and the next 2) weeks and I will wait until prissi has finished his work. Otherwise, I have to rewrite my patch thousand times... Moving the rerouting to haltestelle_t is a good idea, but I don't like the idea of splitting, since Imho my suggestion is more elegant.
Usually the RESCHEDULING takes more time, since one has to loop over a lot of convois and lines.Maybe the lineless convoys and lines should also be cached at the stations?
Therefore building a search tree most likely will take longer than the actual rescheduling; also most stations have also in colins game very few people waiting.You don't need to build a search tree. You could take the code from suche_route, but in every step you test if the halt is the destination of any packet waiting there.
also most stations have also in colins game very few people waiting.
Before applying the patch : **** Colin Rebuilding destinations takes : 174 Rerouting goods takes : 43746 Complete refresh takes : 43920 **** Yoshi Rebuilding destinations takes : 5063 Rerouting goods takes : 2039 Complete refresh takes : 7102 **** 1982 Rebuilding destinations takes : 40 Rerouting goods takes : 332 Complete refresh takes : 372 **** Wipi Rebuilding destinations takes : 8 Rerouting goods takes : 67 Complete refresh takes : 75 **** Ferndale Rebuilding destinations takes : 3 Rerouting goods takes : 20 Complete refresh takes : 23 | After applying the patch : **** Colin Rebuilding destinations takes : 170 Rerouting goods takes : 4172 Complete refresh takes : 4342 **** Yoshi Rebuilding destinations takes : 5114 Rerouting goods takes : 684 Complete refresh takes : 5798 **** 1982 Rebuilding destinations takes : 34 Rerouting goods takes : 145 Complete refresh takes : 179 **** Wipi Rebuilding destinations takes : 7 Rerouting goods takes : 24 Complete refresh takes : 31 **** Ferndale Rebuilding destinations takes : 2 Rerouting goods takes : 3 Complete refresh takes : 5 |
/* Need to clean up?I think it is not necessary to reset the markers, as suche_route() only checks the inequality between the current marker and a halt's marker.
* Otherwise we just incease the mark => less time for cleanups
*/
if( current_mark == 0xFFFFFFFFu ) {
slist_iterator_tpl<halthandle_t > halt_iter (alle_haltestellen);
while( halt_iter.next() ) {
halt_iter.get_current()->marke = 0;
}
current_mark = 0;
}
Most interesting thing is London_C.sve with max_hops 8000.
It's really the same as max_hops 2000.
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
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.
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.
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.
reachable_halt->get_warenziele[ware_catg_index].get_count() > 1I 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.
But your patch, if I have two convois with the same schedule, then it will be too larger than 1 ...
Additional information. The percentage of transported passengers.
regbombay1's London_C.sve (4297 convois, 8577 halts)
max_hops 2000
standard 9%
Knightly 83%
Can I use your patch for any fork version of simutrans, if this was denied ?
It will be incorporated. I will probably just get this a more descriptive name (like number_of_non_unique_schedules or so ... )
The counter of warenziele is large after addition.
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.
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
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
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 |
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.
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.
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.