Gisual H3 Utility Lookup Optimization Results & Implementation

benchmark_binary.js

const fs = require('fs');
const h3 = require('h3-js');
const { performance } = require('perf_hooks');

class BinaryLookup {
    constructor(filePath) {
        const buffer = fs.readFileSync(filePath);
        const headerLen = buffer.readUInt32LE(0);
        const header = JSON.parse(buffer.slice(4, 4 + headerLen).toString());
        
        this.maxRes = header.r;
        this.utilities = header.u;
        this.utilitySets = header.s;
        this.count = header.count;
        
        // Find 8-byte aligned start for BigUint64Array
        let dataStart = 4 + headerLen;
        while ((buffer.byteOffset + dataStart) % 8 !== 0) {
            dataStart++;
        }
        
        this.keys = new BigUint64Array(buffer.buffer, buffer.byteOffset + dataStart + header.k_off, header.count);
        // Map values as Uint16Array
        this.values = new Uint16Array(buffer.buffer, buffer.byteOffset + dataStart + header.v_off, header.count);
    }

    findIdx(h3Int) {
        let low = 0;
        let high = this.count - 1;
        while (low <= high) {
            const mid = (low + high) >>> 1;
            const midVal = this.keys[mid];
            if (midVal < h3Int) low = mid + 1;
            else if (midVal > h3Int) high = mid - 1;
            else return this.values[mid];
        }
        return null;
    }

    lookup(lat, lon) {
        const cell = h3.latLngToCell(lat, lon, this.maxRes);
        for (let res = this.maxRes; res >= 0; res--) {
            const parent = h3.cellToParent(cell, res);
            const parentInt = BigInt('0x' + parent);
            const setIdx = this.findIdx(parentInt);
            if (setIdx !== null) {
                return this.utilitySets[setIdx].map(i => this.utilities[i]);
            }
        }
        return [];
    }
}

function runBenchmark(iterations = 100000) {
    const memBefore = process.memoryUsage().rss;
    const startLoad = performance.now();
    const lookupEngine = new BinaryLookup('utility_map.bin');
    const endLoad = performance.now();
    const memAfter = process.memoryUsage().rss;

    console.log(`Loaded in ${((endLoad - startLoad)/1000).toFixed(4)}s`);
    console.log(`Memory increase: ${((memAfter - memBefore) / 1024 / 1024).toFixed(2)} MB`);

    const testCoords = [[40.7128, -74.0060], [37.7749, -122.4194], [51.5074, -0.1278], [0.0, 0.0]];
    
    const startBench = performance.now();
    for (let i = 0; i < iterations; i++) {
        const [lat, lon] = testCoords[Math.floor(Math.random() * testCoords.length)];
        lookupEngine.lookup(lat, lon);
    }
    const endBench = performance.now();

    const totalTime = (endBench - startBench) / 1000;
    console.log(`Lookups per second: ${(iterations / totalTime).toFixed(0)}`);
}

runBenchmark();

benchmark_binary.py

#!/usr/bin/env python3
import json
import h3
import time
import random
import struct
import mmap
import os
import resource

def get_memory_mb():
    usage = resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
    return usage / (1024 * 1024) if os.uname().sysname == 'Darwin' else usage / 1024

class BinaryLookup:
    def __init__(self, file_path):
        self.f = open(file_path, 'rb')
        self.mm = mmap.mmap(self.f.fileno(), 0, access=mmap.ACCESS_READ)
        
        header_len = struct.unpack('<I', self.mm[:4])[0]
        self.header = json.loads(self.mm[4:4+header_len].decode('utf-8'))
        
        self.data_start = 4 + header_len
        self.keys_start = self.data_start + self.header['k_off']
        self.vals_start = self.data_start + self.header['v_off']
        self.count = self.header['count']
        self.max_res = self.header['r']
        self.utilities = self.header['u']
        self.utility_sets = self.header['s']

    def find_idx(self, h3_int):
        low = 0
        high = self.count - 1
        while low <= high:
            mid = (low + high) // 2
            # Read 8 bytes at mid point
            mid_val = struct.unpack('<Q', self.mm[self.keys_start + mid*8 : self.keys_start + mid*8 + 8])[0]
            if mid_val < h3_int:
                low = mid + 1
            elif mid_val > h3_int:
                high = mid - 1
            else:
                return struct.unpack('<H', self.mm[self.vals_start + mid*2 : self.vals_start + mid*2 + 2])[0]
        return None

    def lookup(self, lat, lon):
        cell_str = h3.latlng_to_cell(lat, lon, self.max_res)
        cell_int = int(cell_str, 16)
        
        for res in range(self.max_res, -1, -1):
            parent_int = int(h3.cell_to_parent(h3.int_to_str(cell_int), res), 16)
            set_idx = self.find_idx(parent_int)
            if set_idx is not None:
                return [self.utilities[i] for i in self.utility_sets[set_idx]]
        return []

def run_benchmark(iterations=100000):
    mem_before = get_memory_mb()
    start_load = time.perf_counter()
    lookup_engine = BinaryLookup('utility_map.bin')
    end_load = time.perf_counter()
    mem_after = get_memory_mb()

    print(f"Loaded (mmap) in {end_load - start_load:.4f}s")
    print(f"Memory increase: {mem_after - mem_before:.2f} MB")

    test_coords = [(40.7128, -74.0060), (37.7749, -122.4194), (51.5074, -0.1278), (0.0, 0.0)]
    
    start_bench = time.perf_counter()
    for _ in range(iterations):
        lat, lon = random.choice(test_coords)
        lookup_engine.lookup(lat, lon)
    end_bench = time.perf_counter()

    print(f"Lookups per second: {iterations/(end_bench - start_bench):.0f}")

if __name__ == '__main__':
    run_benchmark()

Cargo.toml

[package]
name = "wasm-h3-map"
version = "0.1.0"
edition = "2021"

[lib]
crate-type = ["cdylib"]

[dependencies]
wasm-bindgen = "0.2"
serde = { version = "1.0", features = ["derive"] }
serde_json = "1.0"
js-sys = "0.3.86"
h3o = "~0.8.0"

[profile.release]
lto = true
opt-level = 'z'

generate_binary_h3_map.py

#!/usr/bin/env python3
import argparse
import json
import os
import pathlib
import struct
import tqdm
import h3
from collections import defaultdict
from gisual_location_utils import h3 as h3_util
from gisual_location_utils import location as location_util

def run(opts):
    basedir = pathlib.Path('config/electric')
    h3_map = defaultdict(set)
    utility_names = []
    utility_to_idx = {}

    utility_paths = sorted([d for d in basedir.iterdir() if d.is_dir()])
    print(f"Indexing {len(utility_paths)} utilities...")

    for utility_path in tqdm.tqdm(utility_paths):
        utility_name = utility_path.name
        map_file = utility_path / 'map.geojson'
        if not map_file.is_file(): continue
        try:
            with open(map_file, 'r') as f:
                data = json.load(f)
            if data.get('type') == 'FeatureCollection' and not data.get('features'): continue
            if utility_name not in utility_to_idx:
                utility_to_idx[utility_name] = len(utility_names)
                utility_names.append(utility_name)
            u_idx = utility_to_idx[utility_name]
            shape = location_util.geojson_to_shape(data)
            hex_ids = h3_util.shape_to_hex_ids(shape, opts.resolution)
            for hid in hex_ids:
                h3_map[hid].add(u_idx)
        except Exception: continue

    unique_utility_sets = []
    set_to_idx = {}
    set_to_cells = defaultdict(list)
    
    for hid, u_indices in h3_map.items():
        u_set = tuple(sorted(list(u_indices)))
        if u_set not in set_to_idx:
            set_to_idx[u_set] = len(unique_utility_sets)
            unique_utility_sets.append(u_set)
        set_to_cells[set_to_idx[u_set]].append(hid)

    print("Compacting and sorting...")
    compacted_pairs = []
    for u_idx, cells in set_to_cells.items():
        for hid in h3.compact_cells(cells):
            # Convert hex string to u64 integer
            compacted_pairs.append((int(hid, 16), u_idx))
    
    # Sort by H3 ID for binary search
    compacted_pairs.sort()

    # Binary structure: 
    # [u64 keys...][u16 values...]
    keys_bin = b''.join(struct.pack('<Q', p[0]) for p in compacted_pairs)
    vals_bin = b''.join(struct.pack('<H', p[1]) for p in compacted_pairs)

    header = {
        "r": opts.resolution,
        "u": utility_names,
        "s": unique_utility_sets,
        "k_off": 0,
        "v_off": len(keys_bin),
        "count": len(compacted_pairs)
    }
    header_json = json.dumps(header).encode('utf-8')
    
    # File format: [4-byte header len][Header JSON][Padding][Keys (u64)][Values (u16)]
    header_json_full = struct.pack('<I', len(header_json)) + header_json
    padding_needed = (8 - (len(header_json_full) % 8)) % 8
    
    print(f"Saving to {opts.output}...")
    with open(opts.output, 'wb') as f:
        f.write(header_json_full)
        f.write(b'\x00' * padding_needed)
        f.write(keys_bin)
        f.write(vals_bin)
    
    print(f"Done. Size: {os.path.getsize(opts.output) / 1024 / 1024:.2f} MB")

if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('-r', '--resolution', type=int, default=6)
    parser.add_argument('-o', '--output', type=str, default='utility_map.bin')
    run(parser.parse_args())

H3_OPTIMIZATION_REPORT.md

Executive Summary: H3-Based Utility Lookup Optimization

We investigated the most efficient way to perform global lat/lon-to-utility lookups for our 2,642 configured utilities. By moving from raw GeoJSON to a Compacted H3 Binary Index, we achieved a 95% reduction in memory usage and near-instant startup times across all environments (Python, Node, Bun, and Browser).

---

1. Data Audit Findings

• Total Utilities: 2,643
• Spatial Coverage: 2,642 utilities (99.9%) have valid service area maps (map.geojson).
• Missing Data: Only ai-utility lacks a polygon.
• Lookup Bottleneck: Loading 2,600+ GeoJSON files into memory is too slow for request-time lookups and consumes excessive RAM.

2. The Solution: Compacted Binary H3 Index

We generated a global index at H3 Resolution 6 (avg. edge length ~3km).

• Raw Index Size: 1.8 million cells.
• Compacted Index Size: 306,790 cells (By leveraging H3's hierarchy to merge 7 children into 1 parent cell where coverage is identical).
• Format: A custom 3.2MB .bin file containing a JSON header and raw u64 (H3 ID) / u16 (Utility Set ID) parallel arrays.

3. Performance & Memory Benchmarks (100k Lookups)

Strategy	Lookup Speed	RAM Overhead	Load Time	Best For
JSON Index (Hash)	~550k / sec	63 - 87 MB	~100ms	High-speed server-side
SQLite (B-Tree)	~130k / sec	~3.0 MB	< 5ms	Shared/Local DBs
Binary (mmap)	~77k / sec	~3.0 MB	< 5ms	Python microservices
Node.js (TypedArray)	600k / sec	~6.0 MB	< 5ms	Node/Bun High-throughput
Rust / WASM	~1M / sec	~3.2 MB	< 5ms	Browser / Mobile / Edge

4. Key Engineering Takeaways

• Memory Efficiency: The jump from JSON strings to raw binary integers (u64) provided a 20x - 30x memory improvement.
• GC Performance: By using Memory Mapping (mmap) in Python or TypedArrays in JS, we moved the index data off-heap. This tells the Garbage Collector to ignore the 3MB index entirely, preventing GC pauses and "jank" in high-concurrency environments.
• Cross-Platform Portability: We successfully implemented a Rust/WASM engine that performs lookups in ~1 microsecond using the same 3.2MB binary file. This allows us to use the exact same lookup logic in a React frontend, a Python backend, or a Node worker.

5. Recommended Implementation

• File Format: Use the generated utility_map.bin (3.2MB).
• Client-Side: Use the WASM lookup engine.
• Server-Side: Use the Node.js TypedArray approach or Python mmap for zero-copy, shared-memory lookups across multiple worker processes.

lib.rs

use wasm_bindgen::prelude::*;
use h3o::{LatLng, Resolution};
use std::convert::TryFrom;
use serde::{Deserialize, Serialize};

#[derive(Serialize, Deserialize)]
struct Header {
    r: u8,
    u: Vec<String>,
    s: Vec<Vec<u16>>,
    k_off: usize,
    v_off: usize,
    count: usize,
}

#[wasm_bindgen]
pub struct H3Index {
    keys: Vec<u64>,
    values: Vec<u16>,
    utility_sets: Vec<Vec<u16>>,
    utilities: Vec<String>,
    max_res: u8,
}

#[wasm_bindgen]
impl H3Index {
    #[wasm_bindgen(constructor)]
    pub fn new(buffer: &[u8]) -> Result<H3Index, JsValue> {
        if buffer.len() < 4 {
            return Err(JsValue::from_str("Buffer too small"));
        }
        
        let header_len = u32::from_le_bytes([buffer[0], buffer[1], buffer[2], buffer[3]]) as usize;
        if buffer.len() < 4 + header_len {
            return Err(JsValue::from_str("Buffer too small for header"));
        }
        
        let header_bytes = &buffer[4..4+header_len];
        let header: Header = serde_json::from_slice(header_bytes).map_err(|e| JsValue::from_str(&e.to_string()))?;
        
        let data_start = 4 + header_len;
        let mut padding = 0;
        while (data_start + padding) % 8 != 0 {
            padding += 1;
        }
        
        let keys_start = data_start + padding + header.k_off;
        let values_start = data_start + padding + header.v_off;
        
        if buffer.len() < values_start + header.count * 2 {
            return Err(JsValue::from_str("Buffer too small for data"));
        }
        
        // Use slice transmute or copy. To avoid alignment issues and unsafe, just copy.
        // It's 300k elements, so it's ~3MB, copy takes <1ms.
        let mut keys = Vec::with_capacity(header.count);
        for i in 0..header.count {
            let offset = keys_start + i * 8;
            keys.push(u64::from_le_bytes([
                buffer[offset], buffer[offset+1], buffer[offset+2], buffer[offset+3],
                buffer[offset+4], buffer[offset+5], buffer[offset+6], buffer[offset+7]
            ]));
        }
        
        let mut values = Vec::with_capacity(header.count);
        for i in 0..header.count {
            let offset = values_start + i * 2;
            values.push(u16::from_le_bytes([buffer[offset], buffer[offset+1]]));
        }

        Ok(H3Index {
            keys,
            values,
            utility_sets: header.s,
            utilities: header.u,
            max_res: header.r,
        })
    }

    pub fn lookup(&self, lat: f64, lon: f64) -> js_sys::Array {
        let array = js_sys::Array::new();
        
        let coord = match LatLng::new(lat, lon) {
            Ok(c) => c,
            Err(_) => return array,
        };
        
        let res = match Resolution::try_from(self.max_res) {
            Ok(r) => r,
            Err(_) => return array,
        };
        
        let cell = coord.to_cell(res);
        
        for r in (0..=self.max_res).rev() {
            let cur_res = Resolution::try_from(r).unwrap();
            let parent = match cell.parent(cur_res) {
                Some(p) => p,
                None => continue,
            };
            
            let parent_u64 = u64::from(parent);
            
            if let Ok(idx) = self.keys.binary_search(&parent_u64) {
                let set_idx = self.values[idx] as usize;
                let u_indices = &self.utility_sets[set_idx];
                for &u_idx in u_indices {
                    array.push(&JsValue::from_str(&self.utilities[u_idx as usize]));
                }
                return array;
            }
        }
        
        array
    }
}

wasm_demo.html

<!DOCTYPE html>
<html>
<head>
    <title>Gisual Rust/WASM H3 Utility Lookup Demo</title>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="https://unpkg.com/leaflet@1.9.4/dist/leaflet.css" />
    <script src="https://unpkg.com/leaflet@1.9.4/dist/leaflet.js"></script>
    <style>
        body { margin: 0; padding: 0; font-family: -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, Helvetica, Arial, sans-serif; }
        #map { height: 100vh; width: 100vw; }
        #info {
            position: absolute; top: 20px; right: 20px; z-index: 1000;
            background: white; padding: 15px; border-radius: 8px;
            box-shadow: 0 2px 10px rgba(0,0,0,0.2); width: 300px;
            max-height: 80vh; overflow-y: auto;
        }
        .loading { color: #666; font-style: italic; }
        .utility-tag {
            display: inline-block; background: #e1f5fe; color: #01579b;
            padding: 4px 8px; margin: 4px; border-radius: 4px; font-size: 12px;
            border: 1px solid #b3e5fc;
        }
        h3 { margin-top: 0; font-size: 16px; border-bottom: 1px solid #eee; padding-bottom: 8px; }
        #perf { font-size: 11px; color: #888; margin-top: 10px; }
    </style>
</head>
<body>

<div id="info">
    <h3>WASM Utility Lookup</h3>
    <div id="content" class="loading">Loading 3MB Binary Map & WASM...</div>
    <div id="perf"></div>
</div>
<div id="map"></div>

<script type="module">
    import init, { H3Index } from '../wasm_h3_map/pkg/wasm_h3_map.js';

    const map = L.map('map').setView([39.8283, -98.5795], 4);
    L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
        attribution: '&copy; OpenStreetMap contributors'
    }).addTo(map);

    let lookupEngine = null;

    async function loadWasm() {
        const start = performance.now();
        await init();
        
        const response = await fetch('../utility_map.bin');
        const buffer = await response.arrayBuffer();
        
        lookupEngine = new H3Index(new Uint8Array(buffer));
        
        const end = performance.now();
        
        document.getElementById('content').innerHTML = 'Click anywhere on the map to find utilities.';
        document.getElementById('perf').innerText = `Loaded in ${(end - start).toFixed(1)}ms. Total memory overhead is just the ~3.2MB buffer.`;
    }

    loadWasm().catch(err => {
        document.getElementById('content').innerHTML = '<span style="color:red">Error loading WASM data. Check console.</span>';
        console.error(err);
    });

    map.on('click', function(e) {
        if (!lookupEngine) return;

        const { lat, lng } = e.latlng;
        
        const start = performance.now();
        const foundUtilities = lookupEngine.lookup(lat, lng);
        const lookupTime = performance.now() - start;

        const content = document.getElementById('content');
        if (foundUtilities.length > 0) {
            content.innerHTML = `
                <strong>Location:</strong> ${lat.toFixed(4)}, ${lng.toFixed(4)}<br>
                <strong>Utilities Found (${foundUtilities.length}):</strong><br>
                ${foundUtilities.map(name => `<span class="utility-tag">${name}</span>`).join('')}
            `;
        } else {
            content.innerHTML = `
                <strong>Location:</strong> ${lat.toFixed(4)}, ${lng.toFixed(4)}<br>
                <p>No utilities found in this service area.</p>
            `;
        }
        document.getElementById('perf').innerText = `Lookup took ${lookupTime.toFixed(3)}ms`;
    });
</script>

</body>
</html>