ezgliding / goigc / 86

86%

master: 68%

push

travis-ci

Add caching of distance values in brute force

Add a cache for point to point distances in brute force Optimize(). This
is the result of a previous pprof analysis where it is clear most of the
time is spent calculating distance (and cos, sin, atan):
go tool pprof -top -cum cpu.pprof
15.62s of 16.70s total (93.53%)
Dropped 140 nodes (cum <= 0.08s)
      flat  flat%   sum%        cum   cum%
         0     0%     0%     16.42s 98.32%  runtime.goexit
         0     0%     0%     15.16s 90.78%  testing.tRunner
         0     0%     0%     14.60s 87.43%
github.com/ezgliding/goigc.(*bruteForceOptimizer).Optimize
     0.42s  2.51%  2.51%     14.60s 87.43%
github.com/ezgliding/goigc.(*bruteForceOptimizer).optimize1
         0     0%  2.51%     14.60s 87.43%
github.com/ezgliding/goigc.TestBruteForceOptimize.func1
     0.53s  3.17%  5.69%     11.10s 66.47%
github.com/ezgliding/goigc.(*Task).Distance
     0.40s  2.40%  8.08%     10.33s 61.86%
github.com/ezgliding/goigc.(*Point).Distance
     1.98s 11.86% 19.94%      9.93s 59.46%
github.com/ezgliding/goigc/vendor/github.com/golang/geo/s2.LatLng.Distance
     0.70s  4.19% 24.13%      3.10s 18.56%  math.atan2
     0.23s  1.38% 25.51%      2.65s 15.87%  runtime.newobject
     2.48s 14.85% 40.36%      2.48s 14.85%  math.sin
     0.93s  5.57% 45.93%      2.43s 14.55%  runtime.mallocgc
     0.41s  2.46% 48.38%      2.40s 14.37%  math.atan
     1.99s 11.92% 60.30%      1.99s 11.92%  math.satan
     1.94s 11.62% 71.92%      1.94s 11.62%  math.cos

Compute the distances inside the loop so we can reuse the values in the
cache, instead of using a Task struct.

Results show a significant improvement (was ~15s):
go test -bench=BenchmarkBruteForceOptimize -run=x -cpuprofile=cpu.pprof
BenchmarkBruteForceOptimize/optimize-short-flight-1/1-4         	       1	5175162399 ns/op
PASS
ok  	github.com/ezgliding/goigc	5.181s

20 of 20 new or added lines in 1 file covered. (100.0%)

389 of 452 relevant lines covered (86.06%)

1065613.38 hits per line