dotcloud/docker — pull request #6657 by unclejack (2014-06-24 22:27:43+00:00)
Title: refactor TruncIndex to use a trie & vendor deps

This replaces suffixarray with a go-patricia trie.

```
10 second test BEFORE:
PASS
BenchmarkTruncIndexAdd100 500 57708465 ns/op 6109651 B/op 1414 allocs/op
BenchmarkTruncIndexAdd250 50 414062258 ns/op 36072887 B/op 3797 allocs/op
BenchmarkTruncIndexAdd500 10 1766381236 ns/op 140041404 B/op 7940 allocs/op
BenchmarkTruncIndexGet100 100000 260940 ns/op 362320 B/op 450 allocs/op
BenchmarkTruncIndexGet250 10000 1127151 ns/op 2198736 B/op 1126 allocs/op
BenchmarkTruncIndexGet500 5000 3336467 ns/op 8734328 B/op 2252 allocs/op
BenchmarkTruncIndexNew100 10000 1259865 ns/op 170950 B/op 238 allocs/op
BenchmarkTruncIndexNew250 5000 3510118 ns/op 405243 B/op 553 allocs/op
BenchmarkTruncIndexNew500 2000 7792312 ns/op 820164 B/op 1074 allocs/op
ok docker/pkg/truncindex 186.085s

10 second test AFTER:
PASS
BenchmarkTruncIndexAdd100 100000 285569 ns/op 135162 B/op 2433 allocs/op
BenchmarkTruncIndexAdd250 20000 782660 ns/op 358482 B/op 6173 allocs/op
BenchmarkTruncIndexAdd500 10000 1666162 ns/op 719209 B/op 12413 allocs/op
BenchmarkTruncIndexGet100 200000 94354 ns/op 31506 B/op 737 allocs/op
BenchmarkTruncIndexGet250 100000 250821 ns/op 78868 B/op 1841 allocs/op
BenchmarkTruncIndexGet500 50000 524279 ns/op 155941 B/op 3684 allocs/op
BenchmarkTruncIndexNew100 100000 266988 ns/op 136154 B/op 2453 allocs/op
BenchmarkTruncIndexNew250 20000 746447 ns/op 361445 B/op 6205 allocs/op
BenchmarkTruncIndexNew500 10000 1587854 ns/op 714249 B/op 12394 allocs/op
ok docker/pkg/truncindex 219.076s
```