[Bug v3.7] Off-by-One in IF Condition of calculate

Topic: [Bug v3.7] Off-by-One in IF Condition of calculate_paths() (Read 3241 times) previous topic - next topic

[Bug v3.7] Off-by-One in IF Condition of calculate_paths()

May 12, 2009, 02:21:34 pm

James, in haltestelle::calculate_paths(), there is this conditional statement :

Quote

   if(paths_timestamp[category] < welt->get_base_pathing_counter() - welt->get_einstellungen()->get_max_rerouting_interval_months()
|| welt->get_base_pathing_counter() >= (65535 - welt->get_einstellungen()->get_max_rerouting_interval_months()))
   {
      // List is stale. Recalculate.
      // If this is false, then this is only being called to finish
      // calculating paths that have not yet been calculated.
      if(!open_list.empty())
      {
         open_list.clear();
         delete[] path_nodes;
      }

      // Reset the timestamp.
      paths_timestamp[category] = welt->get_base_pathing_counter();
   }

In the 1st component of the IF condition, we should use <= instead of just <. For example, ****uming max_rerouting_interval_months is 2, if paths_timestamp[c] is 7 and base_pathing_counter is 10, then the expression is true (7 < 10 - 2) and the IF body is executed, resetting paths_timestamp[c] to 10. It has to wait for 3 months, i.e. when base_pathing_counter = 13, before this condition will become true again (10 < 13 - 2). But according to your definition in simuconf.tab, all paths should become stale every other month.

Note : This problem happens with all similar checks between paths_timestamp[c]/connexions_timestamps[c], so please look around and make all necessary changes.

Related questions :

(1) It seems to me that both paths_timestamp(c) and connexions_timestamp(c) check against the same expression in calculate_paths() :
timestamp < base_pathing_counter - max_rerouting_interval_months
So, actually, paths and connexions become stale after the same interval? That is, both become stale every other month? This seems to be different from what is described in your simuconf.tab.

(2) Regarding this part of code from rebuild_connexions() :

Code: [Select]

	connexions_timestamp[category] = welt->get_base_pathing_counter();
	if(connexions_timestamp[category] == 0 || reschedule[category])
	{
		// Spread the load of rebuilding this with pathing - advance by half the interval.
		connexions_timestamp[category] += (welt->get_einstellungen()->get_max_rerouting_interval_months() / 2);
	}

I am not quite sure why you have to add 1 (= max_rerouting_interval_months / 2) to connexions_timestamp[c] even after it is set to the value of base_pathing_counter? Wouldn't that further postpone the time for next rebuild to 3 months later? Could you please explain your intention here? Many thanks in advance!

Re: [Bug v3.7] Off-by-One in IF Condition of calculate_paths()

Reply #1 – May 12, 2009, 09:20:57 pm

Knightly,

thank you - well spotted again. These changes will be in 3.8.

Regarding the second point: the intention is for there to be an offset in the connexions and paths timestamps so that paths and connexions are recalculated at different times, to spread processor load. For example:

connexion path    counter rebuild path rebuild connexion
1 0 0 NO    NO
2 1 1 NO    YES
3 2 2    YES    NO
4 3 3    NO YES

Have I made a mistake in implementing that intention...?

Re: [Bug v3.7] Off-by-One in IF Condition of calculate_paths()

Reply #2 – May 13, 2009, 07:30:50 am

James,

It seems to me that the code does not exhibit the same behaviour as you have described.

****uming max_rerouting_interval_months = 2, each time rebuild_connexions() is called, connexions_timestamp[c] is set either to the value of base_pathing_counter (in case where reschedule[c] is false) or to base_pathing_counter + 1 (in case where reschedule[c] is true). Thus, rebuilding of connexions will happen after 2 or 3 months, depending on reschedule[c]. I fail to see why path reconstruction will be done 3 months later instead of the default 2 months.

Incidentally, for this part of code in calculate_paths() :

Code: [Select]


	if(paths_timestamp[category] <= welt->get_base_pathing_counter() - welt->get_einstellungen()->get_max_rerouting_interval_months() || welt->get_base_pathing_counter() >= (65535 - welt->get_einstellungen()->get_max_rerouting_interval_months()))
	{
		// List is stale. Recalculate.
		// If this is false, then this is only being called to finish 
		// calculating paths that have not yet been calculated.
		if(!open_list.empty())
		{
			open_list.clear();
			delete[] path_nodes;
		}

		// Reset the timestamp.
		paths_timestamp[category] = welt->get_base_pathing_counter();
	}

Probably you may want to add reschedule[category] to the IF condition. The reason is that, when reschedule[c] is true, the paths become immediately stale and are deleted in get_path_to(), so all paths will be recalculated. In that case, paths_timestamp[c] should also be set to the value of base_pathing_counter, so that path reconstruction will not happen again shortly. I suppose this is the behaviour you expect, right?

Lastly, one more minor suggestion. I can see that the IF conditions for paths_timestamp[c] and connexions_timestamp[c] contain the same expressions : welt->get_base_pathing_counter() and welt->get_einstellungen()->get_max_rerouting_interval_months(). Maybe you can add a local variable to save the 2 values before the IF conditions, to shorten such lenghy IF conditions?

Re: [Bug v3.7] Off-by-One in IF Condition of calculate_paths()

Reply #3 – May 24, 2009, 05:12:35 am

James,

Sorry for reviving this relatively old thread, but I haven't received your views on the first point in my previous post. You may ignore the 2nd point regarding the check for reschedule[c], as that will be reset in rebuild_connexions() anyway.

Re: [Bug v3.7] Off-by-One in IF Condition of calculate_paths()

Reply #4 – May 24, 2009, 11:18:58 am

Knightly,

ahh, I forgot about this one. Are you referring to the timing for re-calculating connexions? If it doesn't work as I intend, then obviously, it ought to be fixed :-)