Performance of pyvalhalla

[Hendriksn]

For my project, I need an open-source routing engine that can find the best route for up to 100 endpoints to a fixed start point. The engine should be able to process dynamic routing information (e.g., traffic data) as fast as possible. Since Valhalla seems to be a better choice compared to OSMR, I tested its performance to determine its suitability.

On my PC, I observed that the average response time performance is actually better when using it with Docker via HTTP. I am wondering if I made a mistake in my measurements. I created a Python script that extracts 100 endpoints from a coordinate.txt file and calls the PyValhalla library for each endpoint separately. I have attached the script for your reference:
measure_script.txt.

The results from PyValhalla were as follows:

• Total Response Time: 3.30 seconds
• Average Response Time: 0.16 seconds
• Throughput: 30.27 requests per second

However, when I tested the API with a self-hosted Docker image and processed the same set of coordinates (with the same values), I obtained the following results:

• Total Response Time: 1.137 seconds
• Average Response Time: 642.6 ms
• Throughput: 87.95 requests per second

I made a visual studio project for the api test. The files can be seen here: https://gist.github.com/Hendriksn/2e3ead62c5dcf3f9fcd65b2cea0a06af

The coordinates that are used for my performance test are from germany.
Start point: lat: 52.678092, lon: 11.112545
Endpoints can be seen here they are all for up to 100km away from the start point:
coordinates 0-100.txt

I ensured that the coordinates were processed in parallel in both testing environments. As a requirement, the routing engine should process this number of requests in less than two seconds. I wonder if something is wrong with my measurements. Could anyone provide insights or suggestions?

[baileyheading]

Hey, have you tried doing PyValhalla not in parallel? Launching processes in Python is very costly for such a short operation. Multithreading is better I find for this kind of thing but potentially just doing it sequentially will outperform the docker method anyway

[Hendriksn]

I tried running PyValhalla sequentially, but it's not any faster. You can find the script in the attachments. The results are actually pretty much the same and still not better than the API, which makes me wonder if I am doing something wrong.

Total Response Time: 3.24 seconds
Average Response Time: 0.03 seconds
Throughput: 30.82 Anfragen pro seconds

my_script.txt

[baileyheading]

it makes sense possibly that the overheads for attempting parallel could negate the benefits from it resulting in similar runtime. to get a benefit with parallel, you could break it up into perhaps two processes with 2 matrix routes (50 each in your case) each. if the parallel is actually working properly in the first place that could work perhaps.

[nilsnolde]

Apart from Python being pretty much unusable for parallelizing (threading won’t work here I believe, we don’t release the GIL in the C++ component), did you try a 1:many matrix? Do you really need all the 100 results or you just need e.g. the 10 most optimal ones? The latter would exorbitantly speed up matrix computation.

[Hendriksn]

I tried the matrix approach and got slightly better results:

Total Response Time: 2.02 seconds
Average Response Time: 0.02 seconds
Throughput: 49.49 Request per seconds

my_script.txt

I am working on a project that requires up to 100 endpoints, each located within 200km of a starting point. For each route, including up to three alternatives, the calculation should not exceed 2 seconds, even when processing dynamic routing information such as traffic data.
Given these requirements, do you think it is feasible to achieve this performance with pyvalhalla or Valhalla? Alternatively, would it be more practical to use OSMR, despite my preference for the Valhalla engine? I really appreciate your efforts in maintaining Valhalla!

[baileyheading]

Nils is the guru on this, but I've found Graph Hopper destroys Valhalla for this kind of routing (in terms of speed). I've struggled though with the settings for routing profiles and currently get different results from Valhalla (a bit of an issue I haven't solved yet). it's quite easy to setup the java server. You can also run it in python using a java bridge. As with pyvalhalla, if it's setup right it's simply faster than using the API server because you cutout the HTTP overheads.

Edit: You can then parallelise the java bridges with multiprocesssing if you're really looking to throw parallelism at the problem. It really depends if you're doing ad-hoc experiments versus making something to be stable on any system. firing up many processes can get a bit unstable in python

[baileyheading]

ah yes you're right about the threading, I forgot what I did previously. You can use multiprocessing but not for one route at a time. you'd need to put them into chunks of enough routes (enough to cover several seconds per process probably) to cover the overheads for setup and tear down of the processes. The matrix one just finds the times right? I would've expected finding routes would mean wanting to see the routes

[nilsnolde]

Matrix can return geometries since last year sometime, but not for pyvalhalla yet: valhalla/valhalla#4432. Upstream needs be to released:)

[baileyheading]

Matrix can return geometries since last year sometime, but not for pyvalhalla yet: valhalla/valhalla#4432. Upstream needs be to released:)

I build my own pyvalhalla copies (Mac ARM) so I've had this option for a while but didn't know

[Hendriksn]

I implemented your solution using chunks and saw significant speed improvements.

• Total Response Time: 1.51 seconds
• Average Response Time: 0.02 seconds
• Throughput: 66.24 requests per second

my_script.txt

Unfortunately, it is still slower than the API for my use case. When searching for the fastest route with the API (without alternatives), the results are as follows:

• Average Response Time: 415.62 ms
• Total Response Time: 0.723 seconds
• Throughput: 138.31 requests per second

I will also add the coordinates I used above for anyone interested in testing it.

[baileyheading]

interesting results! perhaps you considered this already but make sure the number of chunks is not bigger than the number of cpu cores you have (otherwise the processes will be uneven and you may end up waiting for a single process to complete by itself, and you'll have to repeat the overheads each time too). Also, bigger chunks (less cores) could get improved results because the overheads of so many processes can be substantial when the task is quite short. It suggests the parallelism is working at least!

[baileyheading]

@nilsnolde I've had a look at the matrix geometry. If I do a sources_to_targets expansion, can I also get the total times to reach a particular edge? I don't want to run it twice needlessly. In fact, does the matrix endpoint return the times for each segment? That way if you use it for routing you would be able to know how long to reach each segment in your navigation

edit: can either matrix or expansion matrix get the full picture? maybe there is a parameter I'm missing

[baileyheading]

I've just compared my current valhalla version and there have been some serious changes to costmatrix. I was noticing some bugs in it and yeh, things have been altered. I should be able to just count back through the previous edges I think to find the total duration to the expansion edges right?

in my current working version, the prev_edge_id is the same every time for matrix expansion

Edit: yep, that fixes some big bugs I was having