ezgliding / goigc
86%
master: 68%

LAST BUILD BRANCH: binder
DEFAULT BRANCH: master
Repo Added
Files 11
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

LAST BUILD ON BRANCH pprofdist
branch: pprofdist
CHANGE BRANCH
x

84

Pull #2186

travis-ci

rochaporto 
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
Pull Request #2186:

390 of 453 relevant lines covered (86.09%)

1063261.04 hits per line

Relevant lines Covered
453 RELEVANT LINES 390 COVERED LINES
1063261.04 HITS PER LINE
Source Files on pprofdist
Coverage ∆ File Lines Relevant Covered Missed Hits/Line

Recent builds

Builds Branch Commit Type Ran Committer Via Coverage
84 pprofdist 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... Pull #2186 rochaporto travis-ci pending completion  
86 pprofdist 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... push rochaporto travis-ci pending completion  
83 pprofdist 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... push rochaporto travis-ci pending completion  
80 pprofdist Reuse Task.Turnpoints for each loop In addition to reuse the Task object, do not create a new Turnpoint struct on each loop. Instead create an initial one with the expected size (number of turn points) and set the values directly on the existing ... push rochaporto travis-ci pending completion  
74 pprofdist Reuse Task.Turnpoints for each loop In addition to reuse the Task object, do not create a new Turnpoint struct on each loop. Instead create an initial one with the expected size (number of turn points) and set the values directly on the existing ... push rochaporto travis-ci pending completion  
73 pprofdist Reuse Task object on every loop in bf optimizer The inner loop of the brute force optimizer is critical, and we were recreating a new Task before every Distance() call. Update the internal fields instead and call Distance() on the same object fo... push rochaporto travis-ci pending completion  
69 pprofdist Improve Task.Distance by not allocating new slices pprof analysis showed the following results: 0.95s 2.13% 3.01% 30.22s 67.86% github.com/ezgliding/goigc.(*Task).Distance 2.54s 5.70% 8.71% 16.31s 36.63% runtime.growslice ... push rochaporto travis-ci pending completion  
68 pprofdist Improve Task.Distance by not allocating new slices pprof analysis showed the following results: 0.95s 2.13% 3.01% 30.22s 67.86% github.com/ezgliding/goigc.(*Task).Distance 2.54s 5.70% 8.71% 16.31s 36.63% runtime.growslice ... push rochaporto travis-ci pending completion  
63 pprofdist Improve Task.Distance by not allocating new slices pprof analysis showed the following results: 0.95s 2.13% 3.01% 30.22s 67.86% github.com/ezgliding/goigc.(*Task).Distance 2.54s 5.70% 8.71% 16.31s 36.63% runtime.growslice ... push rochaporto travis-ci pending completion  
61 pprofdist Improve Task.Distance by not allocating new slices pprof analysis showed the following results: 0.95s 2.13% 3.01% 30.22s 67.86% github.com/ezgliding/goigc.(*Task).Distance 2.54s 5.70% 8.71% 16.31s 36.63% runtime.growslice ... push rochaporto travis-ci pending completion  
See All Builds (154)