Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Massive Speed Up #3

Merged
merged 3 commits into from
Nov 9, 2023
Merged

Conversation

kevinkreiser
Copy link
Contributor

@kevinkreiser kevinkreiser commented Jun 24, 2023

Lookups in just_gtfs are done on std::vectors with std::find. This is slow if you do a lot of looking up things by id which, many workflows could forseeably do.

These same lookups also make copies of the structs they look up, presumably so they can signal that they have not found a certain thing by its id using std::optional (which cannot hold a const reference).

This pr changes that by:

  1. sorting any feed that is loaded by the id used to look them up (and tie breakers after that)
  2. this allows the look ups to be done in O(log n) time instead of O(n) with 0 added space (O(1) look up could be had but comes at the cost of a bunch of memory)
  3. for those functions which return a range we now return an iterator range
  4. for those functions which optionally sorted the output we now give no choice, output is always sorted
  5. sorting does take some time but its is tiny
  6. we no longer make copies of things we look up instead returning a const reference
  7. for things we do not find, we replace the "not found" semantic with a default constructed static struct of the relevant type. this struct can be checked for validity using gtfs::valid which makes use of the equality operator to check for equality with a default constructed object

these changes made huge improvements in performance cutting the time to process even a small feed from 6 minutes down to 80 seconds, about an 80% reduction.

see valhalla/valhalla#4167 for more info

@nilsnolde
Copy link
Collaborator

We're about to merge valhalla/valhalla#4167 @mesozoic-drones . We're also fine running on our fork, or even shift development to that fork, or just PR'ing here. Let us know what your preference is.

Copy link
Owner

@mesozoic-drones mesozoic-drones left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you, it's a major improvement!

@mesozoic-drones mesozoic-drones merged commit f6ef4ff into mesozoic-drones:master Nov 9, 2023
@mesozoic-drones mesozoic-drones mentioned this pull request Nov 9, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants