conveyal / analysis-backend

Server component of Conveyal Analysis
http://conveyal.com/analysis
MIT License
23 stars 12 forks source link

Exception when creating exact times timetable #168

Closed abyrd closed 6 years ago

abyrd commented 6 years ago

This problem is detailed in conveyal/r5#290 but the problem is in Analysis backend code. Timetables with "exact times" enabled cause an exception on the backend unless the time range when the timetable is active is an exact multiple of the headway.

The problem is in the iteration termination condition at https://github.com/conveyal/analysis-backend/blob/dev/src/main/java/com/conveyal/taui/models/AbstractTimetable.java#L57

The integer division determining the number of departures always truncates toward zero, so the length of the departures array is too small by one except in the special case where the active time range of the timetable is exactly divisible by the headway, in which case the array is the right length.

We may want to make the array length one longer and make the termination condition equivalent to (departure <= endTime) rather than (departure < endTime) to avoid problems with zero-with time windows intended to create single departures. That is to say, we could make the end time inclusive rather than exclusive.

A short term workaround is to always use time ranges that are an exact multiple of the headway, e.g. if headway is 30 minutes and the timetable begins at 08:23 then it may end at 22:23, but not 22:22 or 22:24.

Generally when trying to fill an array of a predefined length, the termination condition of the loop should be expressed in terms of the array index to avoid such problems. Superficially it looks less efficient to multiply rather than add at every iteration, but a) this is not at all in a critical path, b) that's a micro-optimization on a loop of at most a few dozen iterations, and c) any modern compiler (including JVM JIT) is going to auto-optimize this anyway and loop termination based on an array index is a better hint to both the compiler and future readers.