A fast, offline reverse geocoder
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
actix
cmd
hyper
iron
reverse-geocoder
shio
.gitignore
.travis.yml
Cargo.lock
Cargo.toml
README.md
cities.csv

README.md

Build Status

Rust Reverse Geocoder

A fast, offline reverse geocoder in Rust, inspired by one written in Python. Given a latitude and longitude, this program returns the geographically closest city (using the data from the included cities.csv file).

This program is implemented as a library, an Actix REST API, an Iron REST API, and as a command-line utility, thanks to Cargo workspaces.

(Previously implemented on Shio and Hyper HTTP libraries. Needs work to run on those libraries again.)

Usage

Command line search

Example usage:

> cargo run -p rrgeo-cmd --release 40 -73
71 ms to load cities.csv
3 ms to build the KdTree
(40.72788, -73.09761): West Sayville New York Suffolk County US

Web Server

Example usage:

cargo run -p rrgeo-actix --release
cargo run -p rrgeo-iron --release

Navigate to the local web server.

Benchmarks

The core library (measured with criterion):

Benchmarking search: Warming up for 3.0000 s5 ms to build the KdTree
search                  time:   [1.1530 ms 1.1639 ms 1.1748 ms]                    
                        change: [-2.6577% -1.4078% -0.0250%] (p = 0.04 < 0.05)
                        Change within noise threshold.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

Served over Actix Web:

> wrk --latency http://localhost:3000/\?lat\=40\&long\=\-73
Running 10s test @ http://localhost:3000/?lat=40&long=-73
  2 threads and 10 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     2.47ms    0.87ms  13.01ms   74.17%
    Req/Sec     2.02k    39.42     2.07k    79.50%
  Latency Distribution
     50%    1.96ms
     75%    3.86ms
     90%    3.93ms
     99%    4.06ms
  40170 requests in 10.00s, 8.58MB read
Requests/sec:   4015.31
Transfer/sec:      0.86MB


Served over Iron:

> wrk --latency http://localhost:3000/\?lat\=40\&long\=\-73
Running 10s test @ http://localhost:3000/?lat=40&long=-73
  2 threads and 10 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     2.55ms    1.15ms  25.73ms   76.03%
    Req/Sec     1.99k   110.23     2.20k    82.50%
  Latency Distribution
     50%    1.96ms
     75%    3.35ms
     90%    3.92ms
     99%    5.95ms
  39563 requests in 10.01s, 8.23MB read
Requests/sec:   3954.05
Transfer/sec:    841.78KB

Performance

Below we have comparisons between the Rust, Python and Node.js versions.

Rust Node
Load CSV 61ms 1221ms
Build KdTree 4ms 805ms
Search 1.1ms 0.5ms

Most of the performance differences appear to be in time taken to load the CSV file and create the k-d tree, but not searching the tree. Searching time resembles algorithmic complexity of k-d tree. Python version is partly implemented in C++ meaning it is not a purely Python implementation. (It might be interesting to see how a pure Python version performs.) The Node.js version is pure JavaScript, as in, not using C add-ons.

Rust --release build

     Running `target/release/web`
PT0.062677465S seconds to load cities.csv
PT0.003835230S seconds to build the KdTree
PT0.068904911S seconds to search
PT0.002596743S seconds to search
PT0.002887542S seconds to search

Rust --debug build

     Running `target/debug/web`
PT1.198010357S seconds to load cities.csv
PT0.124435778S seconds to build the KdTree
PT1.401588031S seconds to search
PT0.077837996S seconds to search
PT0.078178297S seconds to search

Python mode 1 (single threaded K-D tree)

➜  reverse-geocoder git:(master) ✗ time python mode1.py
Loading formatted geocoded file...
[{'name': 'Saint Louis Park', 'cc': 'US', 'lon': '-93.34801', 'admin1': 'Minnesota', 'admin2': 'Hennepin County', 'lat': '44.9483'}]

python mode1.py  1.60s user 0.22s system 98% cpu 1.847 total

Python mode 2 (multi threaded K-D tree)

➜  reverse-geocoder git:(master) ✗ time python mode2.py
Loading formatted geocoded file...
[{'name': 'Saint Louis Park', 'cc': 'US', 'lon': '-93.34801', 'admin1': 'Minnesota', 'admin2': 'Hennepin County', 'lat': '44.9483'}]

python mode2.py  2.82s user 0.34s system 142% cpu 2.221 total

nreverse (Node.js version)

load modules: 12.619ms
load cities.csv: 1221.833ms
create kdtree: 805.310ms
search tree: 0.758ms
search tree: 0.086ms
search tree: 0.198ms
search tree: 0.104ms
search tree: 0.031ms
total_heap_size 114mb
total_heap_size_executable 5mb
total_physical_size 112mb
total_available_size 1325mb
used_heap_size 83mb
heap_size_limit 1432mb
malloced_memory 0mb
peak_malloced_memory 4mb
does_zap_garbage 0mb

License

Licensed under either of

at your option.