[pgrouting-dev] memory usage in bulk routing

[Stephen Woodbridge]

On 5/10/2013 1:37 PM, Alec Gosse wrote:
> Steve,
>
> I'm using a large number of routes to compute the likelihood that a
> vehicle (bicycle) observed at one edge would use other edges on the
> same trip as means of spatial extrapolation for limited vehicle count
> data. I wondered about the overhead of creating the graph.  Building
> a single graph definitely sounds preferable for my application. I'm
> using A* since shooting star seems to be missing from the dev
> install, but I would prefer to route from edge to edge rather than
> using vertices.

You should probably use TRSP as you can pass it an edge and a percentage 
along that edge. TRSP is the replacement for shooting star which is 
getting dropped because it has serious issues and nobody that 
understands the code.

> My goal is to write a table of edges traversed, in order, from an
> input table of start and destination edges. I believe that this is
> your second suggested use case. I'm game to code this with some
> guidance on where to start. Ideally, the function would build a graph
> and then do the routing on multiple threads reading the one graph. I
> know how to use openMP for this part, but am I correct that pgRouting
> is using boost threads?

Currently, I don't think any of our code explicitly takes advantage of 
threads, but I could be wrong. If you wanted to solve multiple problems 
on a single graph using threads, you would have to design that into any 
code you built. For example most solvers mark up the graph as they solve 
it, so this would be problematic for threads. Each thread would need to 
maintain its own private mirror of the graph to mark up.

But if 80% of the cost is building the graph, (I don't know what the 
cost is) then cutting that down is the easy win. If you make the 20% 2x 
as fast it is not a big saving if you can not eliminate the 80%.

-Steve

> Best, Alec
>
>
> On May 10, 2013, at 1:20 PM, Stephen Woodbridge
> <woodbri at swoodbridge.com> wrote:
>
>> On 5/10/2013 12:34 PM, Alec Gosse wrote:
>>> Hello, and please let me know if this off topic for this list.
>>>
>>> My application processes a large number of routes (~500k) in a
>>> batch. Each routing task is independent, however even processing
>>> ~100 requires multiple GB of ram on a graph of 50k edges. Memory
>>> usage grows continually as the query is running rather than
>>> leveling out as I would expect, which makes me think that each
>>> routing task is holding onto its memory until they all finish. I
>>> tried breaking the query into small chunks within a plpgsql loop,
>>> but to no benefit.
>>>
>>> Is this an accurate assessment, and or, is there a feasible way
>>> to route many trips in bulk from a table of start and end
>>> points?
>>
>> Alec,
>>
>> What routing algorithm (function) are you using? This sounds like
>> there might be a memory leak. The other possibility is that this is
>> all getting done in a single transaction and I have run into issues
>> because of this. For example, I had a process that I wrapped into a
>> stored procedure to iterate through a table, run a query and update
>> a table and that soaked up huge amounts of memory, but when I
>> rewrote it in perl as a client side script that did a query of a
>> table and then issued a new queries for each table row it did not
>> use a lot of memory. My understanding is that everything done in a
>> stored procedure is done implicitly in a transaction. So the perl
>> script was done in a transaction.
>>
>> If you are interested in coding some C/C++, one idea that I had is
>> to create a function that takes a list of locations, builds a
>> single graph then computes the distances for all pair combinations
>> in the list. Another variant of this would be to pass it a list of
>> location pairs, and it could return a tout for each pair.
>>
>> A large part of the cost is in building the graph, so if you can do
>> it once and reuse it, then you get a huge benefit. I have not had
>> time of funding to build something like this but it would be a
>> great feautre to add to pgrouting. What is your use case for?
>>
>> -Steve _______________________________________________
>> pgrouting-dev mailing list pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
> _______________________________________________ pgrouting-dev mailing
> list pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>