Skip to main content ↑ ↓
Topic: [patch] Stop Counting in rebuild_destinations() (Read 5710 times) previous topic - next topic

[patch] Stop Counting in rebuild_destinations()

This small patch (against r2844 and relative to the trunk folder) fixes 2 problems :

1) When self halt is encountered again, counting of stops should start over.

2) Waypoints (i.e. when get_halt() returns a null halt) should not be counted

Re: [patch] Stop Counting in rebuild_destinations()

Reply #1 –
Good. I'm just reading the same place. :)

@prissi
BTW, GCC can't compile r2844.
If you need a error log, there is in nightly site.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #2 –
1st: Can somebody explain me the definition of
Code: [Select]
		inline bool operator == (const warenzielsorter_t &k) const {
			return halt==k.halt  &&  stops<=k.stops  &&  catg_index==k.catg_index;
		}
In line 1091 "!warenziele_by_stops.is_contained(wzs)" is true also, if the connection is already there, but the existent is longer. But then, one don't need to increase "non_identical_schedules".

2nd: And imho, it would be better in line 1160-1174 to sort the warenziele_by_stops by the stops variable rather than do this double loop.

3rd: Wouldn't it be better to do the stuff for the lines before the single convoys? Then lines would be preferred since they usually have the higher throughput.

4th: I would also prefer not to double the code in lines 1051-1104 and 1128-1154.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #3 –
In reverse order:

@gerw
Any sorting routing would do essentially the same than this loop. There is no gain only looks prettier.

Doing Lines before makes sense, this is just the historical order.

Avoid doublind could be done before by a function hat_gehalten, although this would require a global cl**** then.

I was aware that shorter lines may add non_identical_schedules. But on the other hand this routine is very time critical. Therefore I omitted this extra check if there is a longer match.

@z9999
MSVC++ eats it, so I will look furhter then.

@Knightly:
Well spotted, thank you.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #4 –
Prissi,

You are most welcome :)

But I think Gerw is right about the non_identical_schedules :

Quote
                     for(  uint8 ctg=0;  ctg<add_catg_index.get_count();  ctg ++  ) {
                        if(
                           (add_catg_index[ctg]==0  &&  halt->get_pax_enabled())  ||
                           (add_catg_index[ctg]==1  &&  halt->get_post_enabled())  ||
                           (add_catg_index[ctg]>=2  &&  halt->get_ware_enabled())
                        ) {
                           do {
                              warenzielsorter_t wzs( halt, j, add_catg_index[ctg] );
                              // might be a new halt to add
                              if(  !warenziele_by_stops.is_contained(wzs)  ) {
                                 warenziele_by_stops.append(wzs);
                                 if(  non_identical_schedules[add_catg_index[ctg]] < 255  ) {
                                    // added additional stops => might be transfer stop
                                    non_identical_schedules[add_catg_index[ctg]]++;
                                 }
                              }
                           } while(  add_catg_index[ctg++]>=2  &&  ctg<add_catg_index.get_count()  );
                        }
                     }

In the above code, non_identical_schedules[catg] is incremented whenever a suitable schedule entry is added to warenziel_by_stops. However, non_identical_schedules[catg] should only be incremented once per schedule for each involved category, no matter how many schedule entries have been added to warenziel_by_stops. (Of course, if no entry is added for that schedule, non_identical_schedules[catg] should not be incremented.)

Knightly

Re: [patch] Stop Counting in rebuild_destinations()

Reply #5 –
Quote
   // now add them to warenziele ...
   for(  uint8  stops=0;  stops<255;  stops++  ) {

I may be wrong but I think last appended stop will win when searching route, doesn't it ?

Re: [patch] Stop Counting in rebuild_destinations()

Reply #6 –
suche_route removes the bottommost entry. Thus, if I did not made a mistake it shoudl be found first, because it was added to the stack first. At least this was my intention. And gerw/Knightly, I see you point and you are absolutely right. Sorry for that.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #7 –
Thank you for explaining it.
It is working like that. :)

Re: [patch] Stop Counting in rebuild_destinations()

Reply #8 –
Quote from: prissi – on
Any sorting routing would do essentially the same than this loop. There is no gain only looks prettier.
Shouldn't it be faster to sort it first (or keep it sorted all the time)? Or you make one basket for every value of warenzielsorter_t::stops?

Quote
I was aware that shorter lines may add non_identical_schedules. But on the other hand this routine is very time critical. Therefore I omitted this extra check if there is a longer match.
Yep. But I think, I was also wrong - only Knightly was right ;)

Re: [patch] Stop Counting in rebuild_destinations()

Reply #9 –
Make the bags by stops would make the test for already existing connections with lower stops count a little longer. SO I did not do this.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #10 –
Quote from: prissi – on
Make the bags by stops would make the test for already existing connections with lower stops count a little longer. SO I did not do this.
But if you have the bags, and you want to search for a warenziel_sorter_t with a small "stop", you have to look only in the bags with small numbers (< stop). I would guess, it could be a little bit faster.
 

Re: [patch] Stop Counting in rebuild_destinations()

Reply #12 –
Some code doubling is better, since the gathering of the goods of lineless convoi take some time. This is especially true, if then the owner is wrong or the convoi does not stops at the own stop. Based on your patch, this would be my suggestion.

(And the iterator require preincrement, although for vectors this is not enforced by the code. Also I dislike *xyz->operator[](inxed) compared to (*xyz)[index]. Is there a reason which using the long code?)

Re: [patch] Stop Counting in rebuild_destinations()

Reply #13 –
Quote from: prissi – on
Some code doubling is better, since the gathering of the goods of lineless convoi take some time. This is especially true, if then the owner is wrong or the convoi does not stops at the own stop. Based on your patch, this would be my suggestion.
Argh, I don't like to view a diff of patches ;)

Ok, my notes:
 - I would like to use an uint32 to index the convoys rather than this iterator beast - at least for me it is a beast...
 - The convoys could cache the catg_index-vector. This would take a little bit memory, but saves comp. time.
 - If the stations also have a list of lineless convoys, we could save even more comp. time (I've done this successfully some time ago). Also players would benefit from this, if this list is displayed at the stations details.


Can you commit your suggestion, so we have a common basis for the next suggestions? (The patches would become smaller and easier to read).

Quote
(And the iterator require preincrement, although for vectors this is not enforced by the code. Also I dislike *xyz->operator[](inxed) compared to (*xyz)[index]. Is there a reason which using the long code?)
No, it's only personal preference - I don't like the (*xyz)[idx] ;)

Re: [patch] Stop Counting in rebuild_destinations()

Reply #14 –
Quote from: gerw – on
- The convoys could cache the catg_index-vector. This would take a little bit memory, but saves comp. time.

I support this. Actually I did the same for EXP.

Quote from: gerw – on
- If the stations also have a list of lineless convoys, we could save even more comp. time (I've done this successfully some time ago). Also players would benefit from this, if this list is displayed at the stations details.

I think this should be done too, especially when Gerw has successfully done so before.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #15 –
Quote from: Knightly – on
I support this. Actually I did the same for EXP.
I thought of a variable simconvoi_t::add_catg_index_is_dirty and every time a vehicle changes, this is set to false. If now get_add_catg_index is called and it is dirty, it is recalculated. With this you have almost none overhead (and then you won't need doubled code ;) ).

Re: [patch] Stop Counting in rebuild_destinations()

Reply #16 –
The convoi has routines like add_vehicle and remove_vehicle, which could take care of the catg_index. Maybe then it would be clever to sort them also, since the are not called that often ... (and it would also save lines some h****les).

About keeping lists of linesless convois: I am not completely agains it. But then one needs to go the complete way, i.e. the stops should have an own schedule counter (and a global rerouting counter), thus only affected stops need to update their schedule (and when updating is finished, then global rerouting is needed). This could save even more time, when many player simulataniously change their stops (which will happen if I ever finish all the network code).

Re: [patch] Stop Counting in rebuild_destinations()

Reply #17 –
Ok. But we should do it step-by-step. Here's a roadmap:

1. simconvoi_t::get_catg_index (maybe sorted).
Or what about a bit-field: vector_tpl<bool> enabled_catg_index(length: max_index_catg); enabled_catg_index[ i ] == true <=> catg_index i can be transported by convoy => Then the same for lines

2. stations keeping track of their lineless convoys

2.5. Optimize rebuild_destinations

3. local schedule_counter, global reroute counter.

3.5. Optimize reroute_goods


If it is ok, I will do this in the next weeks (months, years, centuries,...) ;)

Re: [patch] Stop Counting in rebuild_destinations()

Reply #18 –
I would add that maybe that waiting a little longer between steps might be even good to iron out first the bugs before going next stage.

Re: [patch] Stop Counting in rebuild_destinations()

Reply #19 –
This is quite core code, but it's good that there are so many ideas for improvements, and also so many improvements already made in the past time. I'm happy to see this in the hands of so skilled people. Thank you for improving Simutrans :)