search

toruseo / UXsim

Vehicular traffic flow simulator in road network, written in pure Python
https://toruseo.jp/UXsim/docs/
MIT License
120 stars 56 forks source link

Further speedups (`route_search_all`, `transfer` and `route_next_link_choice`) #94

Open EwoutH opened 1 month ago

EwoutH commented 1 month ago

Amazing speedups already have been achieved in route_search_all (https://github.com/toruseo/UXsim/issues/53 / https://github.com/toruseo/UXsim/pull/79) and homogeneous_DUO_update (https://github.com/toruseo/UXsim/issues/84 / https://github.com/toruseo/UXsim/pull/89), which both are now included in UXsim 1.4.0. For large scale networks, this results in over an order of magnitude speedup, in my own testing about ~40x.

This allows for completely new types of simulation and research experiments. Looking forward, further optimization could pave the way for states of small country simulations, simulations over multiple days or huge numbers of simulations for deep uncertainty analysis / hyperparameter optimization. These are the current performance bottlenecks:

image

Which means the following functions currently take up the most of the runtime:

Similar to earlier efforts, using fitting data structures, vectorization and lazy computation could have the most potential for speedups.

One thing to consider is that we need to watch out for Premature Optimization. I feel we already got the low-hanging fruit with the previous two speedups, maybe it's useful to first develop and stabilize UXsim further before squeezing further performance out of it.

toruseo commented 1 month ago

Thanks for testing again!

In my benchmark, the latter 2 are came from the random module of numpy. I think this will be very tough. For the route_search_all, these lines could be vectorized, but it is just a single for-loop. https://github.com/toruseo/UXsim/blob/71f5699287482c5cd6c26bd3b7fcfe5e1e3517da/uxsim/uxsim.py#L1290-L1302

My priority on these issues is not high. Please let me know if you find a solution!

EwoutH commented 1 month ago

At some point we could also consider things like cython, numba or PyO3.

toruseo commented 1 month ago

I want to keep UXsim's simplicity, generality, and tractability high. After all, if one really need speed, C is the best solution. The use of these frameworks may indeed cause "Premature Optimization". Of course, it will be okay if there are very simple solutions.

EwoutH commented 1 month ago

This is absolutely not urgent, just an issue to keep track of some things :)

I think the main next step is to get more people involved in UXsim. Building models, giving feedback, reporting bugs.

Maybe we could write some universities.