nw:turtles-on-path-to much slower and more resource hungry than old network:link-path-turtles

[chardinator]

Used nw-ext-beta 0.02 and NetLogo 5.04

Replicating patches and neighbors*8 with turtles and links to use pathfinding in an 80 * 80 lattice. Times given are averages to find a random path over 100 paths using profiler extension.

13ms: network:link-path-turtles (average over 100 random paths)
23 seconds: nw:turtles-on-path-to for the first path found after snapshot
49ms: nw:turtles-on-path-to average over 100 paths after initial path was found

network:link-path-turtles can find paths in lattices over 600 * 600 before a Java heap overflow in creating over 5 million turtles and links.
finds a path in a 500 * 500 lattice in 2 seconds.

nw:turtles-on-path-to previously froze on a 100 * 100 lattice (with Netlogo 5.03), but now handles 150 *150 before freezing, albeit taking over 5 minutes to find the first path.

[nicolaspayette]

Thanks for reporting. I'm investigating the issue, but I'm not sure yet what is going on. Would you mind sharing your test code? I can probably replicate something similar, but it would help to have the same test case.

[SethTisue]

curious about this one

[nicolaspayette]

The time to build the snapshot is significant, but that should be helped by having set-context (#76) and querying the link manager directly (I'm currently working on that). Not having a copy will also help with memory.

I did some profiling, but could not find any other obvious bottlenecks.

The main issue, I think, is that for some graphs, BFS (used in the old extension) may simply perform better.

Different implementations of Dijkstra's algorithm may have different time complexities. I'm currently using Jung's implementation, which claims to be O(|E| log |V|). BFS is O(|E| + |V|), so it seems like a superior choice when it's possible to use it (it only works with unweighted graphs.)

Is that all there is to it? I'm not entirely sure. I'll see how much set-context helps, and then I'll experiment with swapping BFS in when appropriate.

@qiemem also suggests implementing A* (#81) and I am all for it, but neither Jung nor JGraphT provides it, so we'd have to bring in another lib or implement it ourselves.

[nicolaspayette]

Here is a profiling test for this:

extensions [ network nw profiler ]

to test
  ca
  nw:generate-lattice-2d turtles links 80 80 false
  profiler:start         ;; start profiling
  repeat 100 [
    nw-turtles-on-path-to
    network-link-path-turtles
  ]
  profiler:stop          ;; stop profiling
  print profiler:report  ;; view the results
  profiler:reset         ;; clear the data  
end

to nw-turtles-on-path-to
  ask one-of turtles [
    let p nw:turtles-on-path-to one-of other turtles
  ]
end

to network-link-path-turtles
  ask one-of turtles [
    let p network:link-path-turtles (one-of other turtles) links
  ]
end

As of 10641a0, for an 80 × 80 lattice, on my laptop, we get:

Name                               Calls Incl T(ms) Excl T(ms) Excl/calls
NW-TURTLES-ON-PATH-TO                100   1280.378   1280.378     12.804
NETWORK-LINK-PATH-TURTLES            100    836.209    836.209      8.362

And for 500 × 500 (i.e., 250000 turtles and 499000 links):

Name                               Calls Incl T(ms) Excl T(ms) Excl/calls
NW-TURTLES-ON-PATH-TO                100  66657.399  66657.399    666.574
NETWORK-LINK-PATH-TURTLES            100  64820.986  64820.986    648.210

The remaining discrepancy might be explainable by the randomization introduced for #82, or maybe just by the general overhead of set-context (allowing you to work with any combination of links and turtles instead of just a specific link breed). Further optimizations might still be possible, but I'm closing this issue for now.