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. --
