[pgrouting-dev] Non-scheduled Routing algorithm

[Stephen Woodbridge]

On 6/13/2011 9:16 PM, Anton Patrushev wrote:
> Hi Kishore,
>
> I agree with Steve - mapping text vertex labels to integers makes more sense.
> Same for Pl/pgSQL performance - I think it is OK to have it done like
> this. The problems with Pl/pgSQL is its language limitation which
> limits us in programming techniques, but it is OK as long as you can
> solve your problem with what you have.

Yeah, this is a good point, you are fairly limited in the ability to 
create rich structures unless you can present them as records. So 
building trees, and pointers to objects can be done, but it is not easy 
and this is where you might run into performance problems.

Since you have already implemented your prototype in pgsql, then it 
obviously has what you need. It will be interesting to see how it 
preforms when given a real world example.

-Steve

> Anton.
>
> On 6/14/11, Stephen Woodbridge<woodbri at swoodbridge.com>  wrote:
>> On 6/13/2011 1:28 PM, Kishore Kumar wrote:
>>> Hi,
>>>
>>> I am facing the following issues in the prototype code[1]:
>>>
>>> 1. As I am internally calling Dijkstra function and the Dijkstra
>>> implementation assumes that vertex id and edge id are integers but
>>> according to GTFS, stop id and route id can be text also. This can be
>>> solved by:
>>>    a. Generating a new table that maps Auto-generated integers to Stop
>>> Ids(Map<Integer,Text>)
>>>    b. Modifying Dijkstra implementation to accept vertex id of type text
>>
>> I think I would do a. above. The reason is text id's are really for
>> people and and integer id's computers like. And it is likely that doing
>> b., you would need to remap the text labels to integer anyway for
>> performance reasons.
>>
>>> 2. Since the non-scheduling algorithm is not directly doing any lower
>>> level calculations, I implemented the prototype using PL/pgSQL
>>> language. Is rewriting the same logic in c is required and does it
>>> provide any significant performance boost? According to a post in
>>> pgsql-performance list[2], "I wouldn't expect the queries called by
>>> the pl/pgsql function to be much faster if called through SPI from C
>>> instead.". Hence, my current thought is to give real-life data as
>>> input and check for performance problems and if performance is bad,
>>> write the code in c.
>>
>> I do not have direct test experience to back this up, but assuming pgsql
>> as a language is implemented similar to Perl or python the standard is
>> to compile the source to bytecode and then run a bytecode interpreter.
>> This gives very good perfomance when 90% of the time is spend in library
>> functions that really are compiled C/C++ and called from the
>> interpreter. Where you start to run into performance problems is when
>> you have a lot of code or a lot of looping and evaluating expressions.
>> That said, the rule for optimizing code is to measure first and then
>> remove the worse bottle neck, and then repeat until you are happy with
>> the results. So I see no problem with a prototype in pgsql, and later it
>> or part of it can be rewritten to C if there are performance issues.
>>
>> Hope this helps,
>>     -Steve
>>
>>> Thanks&   Regards,
>>> J Kishore kumar.
>>>
>>> [1] -
>>> https://github.com/pgRouting/pgrouting/blob/gsoc-multimodal/extra/transit/sql/nonscheduled.sql
>>> [2] -
>>> http://archives.postgresql.org/pgsql-performance/2010-05/msg00199.php
>>>
>>> On Sun, Jun 12, 2011 at 1:30 PM, Anton Patrushev
>>> <anton.patrushev at georepublic.de>   wrote:
>>>> Hi Kishore,
>>>>
>>>> Ah, now I got it. Well, here in Russia some bus routes also don't have
>>>> fixed schedule and are regulated by number of buses/trips. Thus I
>>>> think the idea makes sense.
>>>>
>>>> Anton.
>>>> _______________________________________________
>>>> 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
>>
>> _______________________________________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>>
>
>