Extremely high memory usage when generating fast graph

[scd31]

I am facing extremely high memory usage when generating a fast graph(>25GB)

I have 873k nodes and 900k edges. My code looks like this:

	let mut input_graph = InputGraph::new();
	for e in edges {
		input_graph.add_edge(e.start_node, e.end_node, e.weight);
	}
	println!("Freezing graph...");
	input_graph.freeze();
	println!("Calculating optimized graph...");
	let fast_graph = fast_paths::prepare(&input_graph);
	println!("Done.\r\nSaving graph...\t");
	fast_paths::save_to_disk(&fast_graph, format!("{}.ff", filename).as_ref());
	println!("Done.");

It starts swallowing memory at let fast_graph = fast_paths::prepare(&input_graph);. I tried creating a new params with a ratio of 0.01 and 10.0, which didn't seem to help. (I'm not entirely sure what this value does, which is why I tried a small and large value)

I looked through the benchmark code but it doesn't look like I'm doing anything fundamentally different.

[scd31]

My bad. I did some more digging and I was accidentally inserting some weights near the upper limit of a u64. Once I fixed that, memory usage dropped significantly.

[easbar]

Glad you figured out your issue already. Can you give some insights what kind of graph you are working with and how long fast_paths::prepare and the path calculations are taking on such a large graph?

[scd31]

Sure. Here is my code: https://git.scd31.com/stephen/rustic-roads

I am using openstreetmap as my input. I've been experimenting with New Brunswick and Canada as my inputs.

I'll try to get some better benchmarks on the weekend. I can provide rough path calculations though. These numbers are the time it took to create a path calculator, and run it between one source point, and 20 thousand randomly distributed destination points.

New Brunswick - ~1.5 seconds

Canada - ~22 seconds

[easbar]

Ah interesting and thanks for the pointer to your routing engine, this is quite interesting indeed.

[Abdillah]

Hello, my case is somewhat similar to this. I build a graph out of Madinah city, SA openstreet map data.
Thus, my nodes start from billions. Although only add some edges, it gives a startling memory to allocate: 171.189.697.536 bytes, roughly 171 terabyte.

Can you point out on which part the allocation happened and why, @easbar? Maybe user will be able to workaround or add some usage specification to this library.

Add edge 1734994920 <-(241)-> 1734994839
Add edge 1734994839 <-(111)-> 1734994884
Add edge 1734994884 <-(101)-> 1734994880
Add edge 1734994880 <-(48)-> 1734994862
Add edge 1734994862 <-(48)-> 1734994912
Add edge 1734994912 <-(224)-> 1734994920
Add edge 4554720216 <-(23)-> 4708357879
Add edge 4708357879 <-(214)-> 4708357878
Add edge 7132904063 <-(216)-> 7132904062
Add edge 7132904062 <-(80)-> 7132904061
Add edge 7132904061 <-(110)-> 7132904060
Add edge 7132904060 <-(7)-> 7132904059
Add edge 7132904059 <-(22)-> 7132904058
Add edge 7132904058 <-(1)-> 7132904057
Add edge 7132904057 <-(96)-> 7132904056
Add edge 7132904056 <-(12)-> 7132904055
Add edge 4698696476 <-(202)-> 4698696477
Add edge 4713385027 <-(233)-> 4713385024
Add edge 4713385024 <-(213)-> 4713385028
Add edge 4713385028 <-(143)-> 4713385029
Add edge 4713385029 <-(103)-> 4713384989
Add edge 3492621093 <-(253)-> 3492621193
Add edge 3492621193 <-(140)-> 3492621293
Add edge 3492621293 <-(127)-> 3492621194
Add edge 3492621194 <-(75)-> 3492621093
Add edge 4205112598 <-(72)-> 4205112610
Add edge 4205112610 <-(177)-> 4205112612
Add edge 4205112612 <-(108)-> 4205112624
Add edge 4205112624 <-(122)-> 4205112632
Add edge 4205112632 <-(164)-> 4205112647
Add edge 4205112647 <-(190)-> 4205112654
Add edge 4205112654 <-(89)-> 4205112789
Add edge 4205112789 <-(242)-> 4205112797
Add edge 799620746 <-(123)-> 799614756
Add edge 4136109877 <-(109)-> 4136109839
Add edge 4136109839 <-(69)-> 4136109813
Add edge 4136109813 <-(94)-> 4136109799
Add edge 4707990505 <-(93)-> 4708060392
Add edge 4708060392 <-(253)-> 4708060393
There are 11 edges added, 7132904064 num nodes
Construct Intersection catalog..
Return StreetNetwork
Prepare.
memory allocation of 171189697536 bytes failed

[Abdillah]

I kind of understand better about the strange allocation now, CMIIW.

First, the number of nodes is calculated based on the highest node added e.g. 1, 2, 3, 999 will make number of nodes 999. Then comes this vector allocation which allocate memory based on the number of nodes squared.

So, for everyone on this issue, you can create ordered node catalog and add the index to the graph instead of the sparse number.

[dabreegster]

https://github.com/a-b-street/abstreet/blob/master/map_model/src/pathfind/node_map.rs has some simple mappings and helper functions for working with fast_paths. The NodeMap is very straightforward and sounds like the ordered node catalog approach you took.

If I ever get more time, I'll clean up this module and upstream it in this crate, since likely everybody needs to solve this sort of problem.

[Abdillah]

Thank you for pointing out, but I ended up using general purpose bidir_map.
And nice project, btw.