On 10/4/20 12:47 am, Thomas Jones-Low wrote:
> On 4/9/2020 2:38 AM, Alex Goodwin wrote:
>>
>>
>> Thomas,
>>
>> So the hash and equality speedups I did for traveller-pyroute didn't
>> really change that?
>>
>> On reflection, I suppose only reducing run time by 40-odd percent
>> wouldn't do overly much.
>>
>> What sort of speedup would be needed to make the "submit custom gubbins
>> and rerun for charted space" approach work?  Roughly a thousandfold?
>>
>> I got the impression (from reading GT:FT and traveller-pyroute numerous
>> times) that the algorithm was inherently serial - for those of us
>> alongside me in the cheap seats, I believe that it really couldn't be
>> divided up and farmed out to multiple CPU cores to speed it up.
>>
>     The work you did was a great help. For a single sector the time to
> generate the map and data is under 60 seconds, which is probably
> enough for a web interface. But the whole of charted space is still
> running ~24 hours, so yes a thousand fold performance.
>
>     The python code is single-threaded. Python's ability to
> multi-thread compute bound tasks is so limited it may as well be
> non-existent. To get the parallelism it would need to be re-written in
> language more suited to it like Rust or Go. Which I may consider at
> some point because these are the new hot languages.
>
>     The other challenge, or what I consider a challenge, is adding a
> web interface. The option of pasting in your own sector or selecting
> one from the Traveller Map and having it process it. At that point I'm
> looking at wanting to have the whole process in JavaScript and doing
> the work on the user's machine.
I'm still not sure exactly _how_ you would divvy up route generation in
a way that would give the same result as the current version.  The best
I can come up with would be splitting up the route generation for each
separate BTN level (ie, 24, then 23, and on to 22, etc).

However, I think it's premature to worry about porting until the
algorithmic gubbins have been wrung out, as, IIRC, the time taken in
route-finding quickly dominates overall runtime.  Thus, to get that
1000x speedup, either drastically speed up route-finding, or stop the
music and go home.

In plainer language, the time taken to _find_ all the trade routes
rapidly exceeds 95% (or higher) of the total time taken (map generation,
loading files, setting up, etc) - especially at larger scales, so it's
pointless to worry about speeding up anything _but_ route finding.  My
previous efforts sped things up by 0.2 orders of magnitude, but as
Thomas has said, we need another 3.

** NON MATHEMATICAL READERS DEGAUSS NOW FOR ADDED REALISM **

My suggestion to speed up the algorithmic side of things is
implementing/stealing/using a _bidirectional_ version of the current
pathfinding choice, A*.

For example, consider trying to find a trade route from Zhdant to Glea -
eyeballing travellermap, that's at least 330 pc - so at least 83 jumps
(at J-4), neglecting any early cutoffs.

Assuming that each node being visited expands out to 1.2 nodes on
average, that results in ~ 22.4 million node expansions.  Two
half-length (42 jump - good number, that) expansions, starting at each
end and meeting somewhere roughly in the middle, is ~ 25,400 node
expansions in total - roughly 880x less work.

At each node expanding out to 1.1 nodes on average, those numbers become
~30k expansions in the one-way case and ~1200 expansions in the
bidirectional case - still a 25x reduction in work.

These longer, gnarlier routes currently make up a big chunk of route
finding time (by contrast, crossing a sector spinward-trailing under the
same assumptions results in 21 one-way node expansions for 1.2 case, 14
one-way node expansions for 1.1 case, assuming I haven't stuffed up the
calculation), and they're exactly the ones that will receive the biggest
speedups from bidirectional route finding.

--