Speed up look up

[ringsaturn]

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
• Questions on DefaultIndexOptions 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

benchmark

=== 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]

Wait #6 finish.