Speed up look up
ringsaturn opened this issue · 1 comments
ringsaturn commented
The original geometry package support RTree/QuadTree index options for polygon, which is missed in the Rust package.
Original index useful links:
- https://medium.com/@tidwall/faster-geospatial-queries-in-tile38-f771e2f6b1bd
- tidwall/tile38@6257ddb
- tidwall/geojson#23
Package tzf-rs and tzfpy’s performance should increase a lot when preindex missed:
- p99: 10 times faster with RTree
- mean: about 5 times faster with RTree
But, tzf-rs will require more memory.
Excerpt from tidwall/geojson
=== RUN TestBigArizona
az/none 1582 points created in 106.201µs using 27344 bytes
az/none/in 100,000 ops over 4 threads in 399ms, 250,372/sec, 3994 ns/op
az/none/on 100,000 ops over 4 threads in 197ms, 508,399/sec, 1966 ns/op
az/none/out 100,000 ops over 4 threads in 403ms, 247,900/sec, 4033 ns/op
az/none/rnd 100,000 ops over 4 threads in 434ms, 230,199/sec, 4344 ns/op
az/quad 1582 points created in 336.003µs using 32232 bytes
az/quad/in 100,000 ops over 4 threads in 38ms, 2,615,503/sec, 382 ns/op
az/quad/on 100,000 ops over 4 threads in 17ms, 5,775,986/sec, 173 ns/op
az/quad/out 100,000 ops over 4 threads in 30ms, 3,289,053/sec, 304 ns/op
az/quad/rnd 100,000 ops over 4 threads in 46ms, 2,196,806/sec, 455 ns/op
az/rtre 1582 points created in 874.808µs using 39656 bytes
az/rtre/in 100,000 ops over 4 threads in 25ms, 4,021,162/sec, 248 ns/op
az/rtre/on 100,000 ops over 4 threads in 8ms, 12,413,302/sec, 80 ns/op
az/rtre/out 100,000 ops over 4 threads in 24ms, 4,147,342/sec, 241 ns/op
az/rtre/rnd 100,000 ops over 4 threads in 32ms, 3,130,243/sec, 319 ns/op
--- PASS: TestBigArizona (1.69s)
=== RUN TestBigTexas
tx/none 12478 points created in 276.703µs using 204880 bytes
tx/none/in 100,000 ops over 4 threads in 4655ms, 21,484/sec, 46545 ns/op
tx/none/on 100,000 ops over 4 threads in 2098ms, 47,672/sec, 20976 ns/op
tx/none/out 100,000 ops over 4 threads in 4550ms, 21,977/sec, 45501 ns/op
tx/none/rnd 100,000 ops over 4 threads in 4758ms, 21,019/sec, 47575 ns/op
tx/quad 12478 points created in 3.578431ms using 245864 bytes
tx/quad/in 100,000 ops over 4 threads in 116ms, 863,551/sec, 1158 ns/op
tx/quad/on 100,000 ops over 4 threads in 131ms, 760,742/sec, 1314 ns/op
tx/quad/out 100,000 ops over 4 threads in 113ms, 886,719/sec, 1127 ns/op
tx/quad/rnd 100,000 ops over 4 threads in 115ms, 869,634/sec, 1149 ns/op
tx/rtre 12478 points created in 8.743577ms using 295016 bytes
tx/rtre/in 100,000 ops over 4 threads in 60ms, 1,662,062/sec, 601 ns/op
tx/rtre/on 100,000 ops over 4 threads in 71ms, 1,405,447/sec, 711 ns/op
tx/rtre/out 100,000 ops over 4 threads in 58ms, 1,720,619/sec, 581 ns/op
tx/rtre/rnd 100,000 ops over 4 threads in 61ms, 1,631,339/sec, 612 ns/op
--- PASS: TestBigTexas (16.82s)
Benchmark from tzf(Go)
RTree: &geometry.IndexOptions{Kind: geometry.RTree, MinPoints: 64}
goos: darwin
goarch: amd64
pkg: github.com/ringsaturn/tzf
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkGetTimezoneName_Random_WorldCities-16 162284 7123 ns/op 8000 ns/p50 10000 ns/p90 14000 ns/p99 8 B/op 0 allocs/op
PASS
ok github.com/ringsaturn/tzf 9.069s
QuadTree: &geometry.IndexOptions{Kind: geometry.QuadTree, MinPoints: 64}
goos: darwin
goarch: amd64
pkg: github.com/ringsaturn/tzf
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkGetTimezoneName_Random_WorldCities-16 142278 8236 ns/op 8000 ns/p50 12000 ns/p90 19000 ns/p99 8 B/op 0 allocs/op
PASS
ok github.com/ringsaturn/tzf 5.801s
None: &geometry.IndexOptions{Kind: geometry.None, MinPoints: 64}
goos: darwin
goarch: amd64
pkg: github.com/ringsaturn/tzf
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkGetTimezoneName_Random_WorldCities-16 27058 43488 ns/op 30000 ns/p50 99000 ns/p90 193000 ns/p99 8 B/op 0 allocs/op
PASS
ok github.com/ringsaturn/tzf 5.068s
ringsaturn commented
Wait #6 finish.