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

[EwoutH]

Amazing speedups already have been achieved in route_search_all (#53 / #79) and homogeneous_DUO_update (#84 / #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:

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

• route_search_all
• transfer
• route_next_link_choice

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]

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.

UXsim/uxsim/uxsim.py

Lines 1290 to 1302 in 71f5699

	for link in s.W.LINKS:
	i = link.start_node.id
	j = link.end_node.id
	if s.W.ADJ_MAT[i,j]:
	new_link_tt = link.traveltime_instant[-1]*s.W.rng.uniform(1, 1+noise) + link.route_choice_penalty
	n = adj_mat_link_count[i,j]
	s.adj_mat_time[i,j] = s.adj_mat_time[i,j]*n/(n+1) + new_link_tt/(n+1) # if there are multiple links between the same nodes, average the travel time
	# s.adj_mat_time[i,j] = new_link_tt #if there is only one link between the nodes, this line is fine, but for generality we use the above line
	adj_mat_link_count[i,j] += 1
	if link.capacity_in == 0: #if the inflow is profibited, travel time is assumed to be infinite
	s.adj_mat_time[i,j] = np.inf
	else:
	s.adj_mat_time[i,j] = np.inf

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

[EwoutH]

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

[toruseo]

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]

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.

[EwoutH]

Then there are two functions that would benefit a lot from a speedup: The Node transfer and the Vehicle route_next_link_choice. Both take up 15% to 20% of simulation time in a large-scale simulation.

Edit: I already stated that in the post above. In that case, this just confirms that these remain a bottleneck in large scale simulations.

[toruseo]

Closing. See #143 (comment) for the reason. Feel free to re-open.

[EwoutH]

Thanks for you continued work on this. I think this issue deserves to stay open, since these remain major bottlenecks in simulation speed.

[toruseo]

Okay, please feel free to share any specific ideas you come up with