docs(changelog): add the #1708 fragment

Co-Authored-By: Claude Fable 5.2 <[email protected]>

changelog.d/1708-flights-fleet-floor-lookups.md

@@ -0,0 +1,4 @@
+- Make a whole-globe view of Live Flights about three times faster on a slow
+  CPU. Aircraft at cruise altitude no longer ask for the ground under them on
+  every pass, and a ground floor read no longer formats numbers into text
+  (mazy1998, #1708).

docs/CURRENT-STATE.md

@@ -2949,7 +2949,13 @@ visits to one place share a key but does not bound how many distinct places a
 session visits, and the cache previously had no eviction, so a long session
 retained every coordinate it ever resolved. Eviction is least-recently-used:
 a consumer read, including a warm hit in a batch lookup, promotes its entry, so
-the cell being watched is not dropped for having been resolved early. The bound sits far above a city-scale session, so
+the cell being watched is not dropped for having been resolved early. A
+synchronous read (`cachedEllipsoidalGround`, `cachedRealEllipsoidalGround`)
+promotes its entry only once half the bound's worth of stores and promotions
+have passed since the entry was last newest, so an entry read at least that
+often is still never evicted while the per-frame floor reads no longer rewrite
+the cache; those reads find entries through a numeric key and format no
+strings. The bound sits far above a city-scale session, so
 normal use never evicts and issues no additional proxy requests. A batch's
 results are assembled from what that call resolved or found warm, so eviction
 during a large batch cannot report one of its points as unresolved. Re:Earth and

src/data/motionModel.js

@@ -311,6 +311,10 @@ export const COAST_FLOOR_LIFT_M = 1.5;
  */
 export function floorCoastedPosition(position, cachedGroundFloor) {
   if (typeof cachedGroundFloor !== 'function') return position;
+  // Most coasting contacts are at cruise, and this runs for each of them on
+  // every fleet pass. One above COAST_FLOOR_CEILING_M cannot be lifted by any
+  // ground, so it needs neither the geodetic conversion nor the floor read.
+  if (clearOfAllGround(position)) return position;
   const carto = Cesium.Cartographic.fromCartesian(
     position,
     Cesium.Ellipsoid.WGS84,
@@ -334,6 +338,36 @@ export function floorCoastedPosition(position, cachedGroundFloor) {
 
 const _coastCarto = new Cesium.Cartographic();
 
+/**
+ * @constant {number} No ground reaches this height above the ellipsoid:
+ * Everest's summit is about 8,821 m (8,849 m above a geoid that sits 28 m
+ * below the ellipsoid there).
+ */
+export const COAST_FLOOR_CEILING_M = 9000;
+const _oneOverRadiiSq = Cesium.Ellipsoid.WGS84.oneOverRadiiSquared;
+const COAST_CLEAR_SCALED_SQ =
+  (1 + COAST_FLOOR_CEILING_M / Cesium.Ellipsoid.WGS84.minimumRadius) ** 2;
+
+/**
+ * Whether a position is certainly more than COAST_FLOOR_CEILING_M above the
+ * ellipsoid, from three multiplications. Scale the axes so the ellipsoid is
+ * the unit sphere: a point h metres up its surface normal is then at most
+ * 1 + h / (polar radius) from the centre, so one further out than
+ * 1 + ceiling / (polar radius) is above the ceiling. At the equator this
+ * answers yes from about 30 m above the ceiling; at the poles, from the
+ * ceiling itself.
+ * @param {Cesium.Cartesian3} position
+ * @returns {boolean}
+ */
+function clearOfAllGround(position) {
+  return (
+    position.x * position.x * _oneOverRadiiSq.x +
+      position.y * position.y * _oneOverRadiiSq.y +
+      position.z * position.z * _oneOverRadiiSq.z >
+    COAST_CLEAR_SCALED_SQ
+  );
+}
+
 /**
  * Seconds to coast past the last report: the elapsed time, bounded by the
  * source's coast limit and STALE_COAST_MAX_SEC; none for a contact that

src/data/motionModel.test.mjs

@@ -10,6 +10,7 @@ import {
   liftRepeatedGroundFix, synthesizeForwardKinematicsFix,
   projectGroundArcLatLon, corridorPathLatLon,
   COURSE_TRACK_ONLY_MPS, COURSE_CHORD_ONLY_MPS, COURSE_MIN_DPS, TURN_MIN_SPEED_MPS,
+  floorCoastedPosition, COAST_FLOOR_CEILING_M, COAST_FLOOR_LIFT_M,
 } from './motionModel.js';
 
 const AUSTIN = { lat: 30.2672, lon: -97.7431, alt: 9000 };
@@ -341,3 +342,79 @@ test('corridorPathLatLon returns nothing without a display position', () => {
     extrapolating: true, displayLat: NaN, displayLon: -97.66, courseDeg: 0, speedMps: 10, lookaheadSec: 60,
   }), []);
 });
+
+/** floorCoastedPosition as it was before the cruise skip: always converts and reads. */
+function floorCoastedReference(position, groundAt) {
+  const carto = Cesium.Cartographic.fromCartesian(position);
+  if (!carto) return position;
+  const ground = groundAt(
+    Cesium.Math.toDegrees(carto.latitude),
+    Cesium.Math.toDegrees(carto.longitude),
+  );
+  if (!Number.isFinite(ground) || carto.height >= ground + COAST_FLOOR_LIFT_M)
+    return position;
+  return Cesium.Cartesian3.fromRadians(carto.longitude, carto.latitude, ground + COAST_FLOOR_LIFT_M);
+}
+
+test('a coasting contact above any terrain is not looked up against the ground', () => {
+  let reads = 0;
+  const ground = () => {
+    reads += 1;
+    return 8821; // Everest's summit, the highest floor there is
+  };
+  // Just over the ceiling and at cruise, from pole to equator.
+  for (let lat = -90; lat <= 90; lat += 7.5) {
+    for (const lon of [0, 86.925, -78.8, 179.9]) {
+      for (const height of [COAST_FLOOR_CEILING_M + 35, 10_000, 12_500, 40_000]) {
+        const position = Cesium.Cartesian3.fromDegrees(lon, lat, height);
+        const before = Cesium.Cartesian3.clone(position);
+        assert.equal(floorCoastedPosition(position, ground), position);
+        assert.ok(Cesium.Cartesian3.equals(position, before));
+      }
+    }
+  }
+  assert.equal(reads, 0);
+});
+
+test('below the ceiling a coast is floored exactly as before', () => {
+  // Terrain that rises under the coast, known in some places and not others.
+  const ground = (lat, lon) => (Math.floor(lat * 10 + lon) % 3 === 0 ? null : 1500 + ((lat * 7 + lon * 3) % 900));
+  let lifted = 0;
+  let checked = 0;
+  for (let lat = -89; lat <= 89; lat += 5.5) {
+    for (let lon = -180; lon < 180; lon += 17) {
+      for (const height of [-40, 0, 800, 1499, 1501.4, 2399, 2402, 5000, 8990, 9000, 9010, 11_000, 30_000]) {
+        const position = Cesium.Cartesian3.fromDegrees(lon, lat, height);
+        const expected = floorCoastedReference(Cesium.Cartesian3.clone(position), ground);
+        const actual = floorCoastedPosition(position, ground);
+        assert.ok(
+          Cesium.Cartesian3.equals(actual, expected),
+          `coast at ${lat}, ${lon}, ${height} m`,
+        );
+        checked += 1;
+        if (!Cesium.Cartesian3.equals(expected, Cesium.Cartesian3.fromDegrees(lon, lat, height))) lifted += 1;
+      }
+    }
+  }
+  assert.ok(lifted > 500, `${lifted} of ${checked} coasts were lifted onto the ground`);
+});
+
+test('nothing at or below the ceiling skips the ground', () => {
+  let reads = 0;
+  const ground = () => {
+    reads += 1;
+    return null;
+  };
+  let asked = 0;
+  for (let lat = -90; lat <= 90; lat += 2.5) {
+    for (const height of [-400, 0, 4000, 8821, COAST_FLOOR_CEILING_M - 1, COAST_FLOOR_CEILING_M]) {
+      floorCoastedPosition(Cesium.Cartesian3.fromDegrees(33, lat, height), ground);
+      asked += 1;
+    }
+  }
+  assert.equal(reads, asked);
+});
+
+test('the ceiling clears the highest ground with room to spare', () => {
+  assert.ok(COAST_FLOOR_CEILING_M > 8849 + 100);
+});

src/services/groundFloor.js

@@ -45,6 +45,39 @@ export function createGroundFloor({ terrain, signal }) {
     return { lat: Number(lat.toFixed(3)), lon: Number(lon.toFixed(3)) };
   }
 
+  /**
+   * One coordinate's coarse cell as an integer: `Number(deg.toFixed(3))` in
+   * thousandths of a degree, without the trip through a string. The floor is
+   * read for every aircraft on every fleet pass, and `coarseFloorCoord`'s two
+   * `toFixed` calls and the string keys built from them were most of the cost.
+   * `toFixed` rounds the exact decimal value; `deg * 1000` is within 1e-10 of
+   * it for |deg| < 1000, so the two can only round differently right at a
+   * half, and there the string decides.
+   * @param {number} deg
+   * @returns {number}
+   */
+  function coarseCellIndex(deg) {
+    const scaled = deg * 1000;
+    if (
+      !(Math.abs(deg) < 1000) ||
+      Math.abs(scaled - Math.floor(scaled) - 0.5) < 1e-6
+    )
+      return Math.round(Number(deg.toFixed(3)) * 1000);
+    return Math.round(scaled);
+  }
+
+  /**
+   * Key of a coarse cell in `_meshCells`: the two indices packed into one
+   * number, or the text form for a longitude too far out of range to pack.
+   * @param {number} latIndex @param {number} lonIndex
+   * @returns {number|string}
+   */
+  function meshCellKey(latIndex, lonIndex) {
+    return Math.abs(lonIndex) < 500_000 && Math.abs(latIndex) < 1e9
+      ? latIndex * 1_000_000 + lonIndex
+      : `${latIndex},${lonIndex}`;
+  }
+
   /**
    * Pure floor clamp.
    *  - finite alt + finite ground → max(alt, ground + lift)
@@ -424,8 +457,8 @@ export function createGroundFloor({ terrain, signal }) {
   // reported here by meshFloorSampler.js. Design principle (owner): NEVER
   // below the visible surface; slightly above is always fine. The DEM stays
   // the instant global prior/fallback and the sanity gate for samples.
-  /** @type {Map<string, Array<{lat: number, lon: number, h: number}>>}
-   *  coarse cell key -> rendered-surface readings (m, ellipsoidal), each kept
+  /** @type {Map<number|string, Array<{lat: number, lon: number, h: number}>>}
+   *  coarse cell key (`meshCellKey`) -> rendered-surface readings (m, ellipsoidal), each kept
    *  at the point it was probed. A read answers from the reading nearest the
    *  asked point, so a viaduct and the street beside it in one cell keep their
    *  own heights. */
@@ -468,8 +501,7 @@ export function createGroundFloor({ terrain, signal }) {
       !Number.isFinite(heightM)
     )
       return;
-    const c = coarseFloorCoord(lat, lon);
-    const key = `${c.lat},${c.lon}`;
+    const key = meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon));
     if (!_meshCells.has(key)) _meshCells.set(key, [{ lat, lon, h: heightM }]);
   }
 
@@ -497,7 +529,7 @@ export function createGroundFloor({ terrain, signal }) {
     const cell = coarseFloorCoord(lat, lon);
     const prior = cachedRealEllipsoidalGround(cell.lat, cell.lon);
     if (!meshFloorSampleWithinPrior(heightM, prior)) return false;
-    const key = `${cell.lat},${cell.lon}`;
+    const key = meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon));
     const readings = _meshCells.get(key);
     if (!readings) {
       _meshCells.set(key, [{ lat, lon, h: heightM }]);
@@ -538,8 +570,16 @@ export function createGroundFloor({ terrain, signal }) {
   function cachedMeshFloor(lat, lon) {
     if (!_meshPreferred) return null;
     if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
-    const c = coarseFloorCoord(lat, lon);
-    const readings = _meshCells.get(`${c.lat},${c.lon}`);
+    return meshFloorInCell(
+      lat,
+      lon,
+      meshCellKey(coarseCellIndex(lat), coarseCellIndex(lon)),
+    );
+  }
+
+  /** `cachedMeshFloor` for a caller that already has the point's cell key. */
+  function meshFloorInCell(lat, lon, key) {
+    const readings = _meshCells.get(key);
     if (!readings) return null;
     if (readings.length === 1) return readings[0].h;
     const k = Math.cos((lat * Math.PI) / 180) ** 2;
@@ -572,10 +612,14 @@ export function createGroundFloor({ terrain, signal }) {
    */
   function cachedGroundFloor(lat, lon) {
     if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
-    const mesh = cachedMeshFloor(lat, lon);
-    if (mesh != null) return mesh;
-    const c = coarseFloorCoord(lat, lon);
-    return cachedRealEllipsoidalGround(c.lat, c.lon);
+    // The cell is worked out once, as integers, for both reads.
+    const latIndex = coarseCellIndex(lat);
+    const lonIndex = coarseCellIndex(lon);
+    if (_meshPreferred) {
+      const mesh = meshFloorInCell(lat, lon, meshCellKey(latIndex, lonIndex));
+      if (mesh != null) return mesh;
+    }
+    return cachedRealEllipsoidalGround(latIndex / 1000, lonIndex / 1000);
   }
 
   /**

src/services/groundFloor.test.mjs

@@ -0,0 +1,176 @@
+import { test } from 'node:test';
+import assert from 'node:assert/strict';
+import { createGroundFloor } from './groundFloor.js';
+import { createTerrainHeights } from './terrainHeights.js';
+
+/** Counts Number.prototype.toFixed calls made while `run` executes. */
+function countToFixed(run) {
+  const original = Number.prototype.toFixed;
+  let calls = 0;
+  Number.prototype.toFixed = function (...args) {
+    calls += 1;
+    return original.apply(this, args);
+  };
+  try {
+    run();
+  } finally {
+    Number.prototype.toFixed = original;
+  }
+  return calls;
+}
+
+/**
+ * The floor read as it was before the cell became an integer: the coarse cell
+ * through `toFixed(3)`, mesh cells and DEM cells under string keys.
+ */
+function referenceFloor() {
+  const mesh = new Map();
+  const dem = new Map();
+  const coarse = (lat, lon) => ({
+    lat: Number(lat.toFixed(3)),
+    lon: Number(lon.toFixed(3)),
+  });
+  const demKey = (lat, lon) => `${lat.toFixed(5)},${lon.toFixed(5)}`;
+  return {
+    reportMesh(lat, lon, h) {
+      const c = coarse(lat, lon);
+      const key = `${c.lat},${c.lon}`;
+      if (!mesh.has(key)) mesh.set(key, [{ lat, lon, h }]);
+    },
+    storeDem(lat, lon, h) {
+      dem.set(demKey(lat, lon), h);
+    },
+    read(lat, lon, meshPreferred = true) {
+      if (!Number.isFinite(lat) || !Number.isFinite(lon)) return null;
+      const c = coarse(lat, lon);
+      const readings = meshPreferred ? mesh.get(`${c.lat},${c.lon}`) : null;
+      if (readings) return readings[0].h;
+      return dem.get(demKey(c.lat, c.lon)) ?? null;
+    },
+  };
+}
+
+/** A real terrain cache whose every resolved point takes the height asked for. */
+async function warmTerrain(points) {
+  const heights = new Map(points.map((p) => [`${p.lat},${p.lon}`, p.h]));
+  const terrain = createTerrainHeights({
+    source: {
+      async getHeights(chunk) {
+        return chunk.map((item) => ({
+          ellipsoid: heights.get(`${item.lat},${item.lon}`),
+        }));
+      },
+    },
+  });
+  await terrain.resolveEllipsoidalGround(
+    points.map(({ lat, lon }) => ({ lat, lon })),
+  );
+  return terrain;
+}
+
+/** Deterministic pseudo-random numbers in [0, 1). */
+function random(seed) {
+  let state = seed;
+  return () => {
+    state = (state * 1664525 + 1013904223) % 4294967296;
+    return state / 4294967296;
+  };
+}
+
+/** Coordinates that land on, and just either side of, a coarse-cell edge. */
+function edgeCoordinates() {
+  const out = [];
+  for (const base of [0, 0.0005, -0.0005, 12.3455, -12.3455, 89.9995, 179.9995])
+    for (const nudge of [0, 1e-13, -1e-13, 1e-9, -1e-9, 1e-7, -1e-7, 4e-4])
+      out.push(base + nudge);
+  // Thousandths whose doubles sit a hair either side of the half.
+  for (let k = -40; k <= 40; k += 1) out.push((k + 0.5) / 1000);
+  out.push(-0, 1.0005, 1.0015, 2.5, -2.5, 1e-7, -1e-7);
+  return out;
+}
+
+test('the floor read answers exactly as the string-keyed read did', async () => {
+  const next = random(20261113);
+  const cells = [];
+  for (let i = 0; i < 400; i += 1) {
+    cells.push({
+      lat: Number((next() * 170 - 85).toFixed(3)),
+      lon: Number((next() * 360 - 180).toFixed(3)),
+      h: Math.round(next() * 4000),
+    });
+  }
+  // Cells along the equator and the prime meridian, where a cell index is 0.
+  for (const edge of edgeCoordinates()) {
+    const lat = Number(edge.toFixed(3));
+    cells.push({ lat: Math.max(-89, Math.min(89, lat)), lon: 10, h: 77 });
+    cells.push({ lat: 10, lon: lat, h: 88 });
+  }
+  const reference = referenceFloor();
+  for (const c of cells) reference.storeDem(c.lat, c.lon, c.h);
+  const terrain = await warmTerrain(cells);
+  const groundFloor = createGroundFloor({ terrain });
+
+  // A rendered-surface reading in every seventh cell, taken off its centre.
+  cells.forEach((c, i) => {
+    if (i % 7) return;
+    const lat = c.lat + 0.0002;
+    const lon = c.lon - 0.0003;
+    reference.reportMesh(lat, lon, c.h + 3);
+    groundFloor.reportMeshFloorCell(lat, lon, c.h + 3);
+  });
+
+  const probes = [];
+  for (const c of cells) {
+    probes.push([c.lat, c.lon]);
+    probes.push([c.lat + (next() - 0.5) * 0.002, c.lon + (next() - 0.5) * 0.002]);
+  }
+  for (const a of edgeCoordinates())
+    for (const b of [10, 10.0004, -0, 0.0005, -0.0005]) {
+      probes.push([a, b]);
+      probes.push([b, a]);
+    }
+  probes.push([NaN, 1], [1, Infinity], [95, 400], [10, 720.1234]);
+
+  for (const meshPreferred of [true, false]) {
+    groundFloor.setMeshFloorPreferred(meshPreferred);
+    let hits = 0;
+    for (const [lat, lon] of probes) {
+      const expected = reference.read(lat, lon, meshPreferred);
+      assert.equal(
+        groundFloor.cachedGroundFloor(lat, lon),
+        expected,
+        `floor at ${lat}, ${lon} (mesh ${meshPreferred})`,
+      );
+      if (expected !== null) hits += 1;
+    }
+    assert.ok(hits > 400, `${hits} probes found a floor`);
+  }
+});
+
+test('reading a floor formats no numbers, hit or miss', async () => {
+  const cell = { lat: 51.47, lon: -0.454, h: 25 };
+  const terrain = await warmTerrain([cell]);
+  const groundFloor = createGroundFloor({ terrain });
+  groundFloor.reportMeshFloorCell(48.3537, 11.7861, 453);
+
+  const calls = countToFixed(() => {
+    // The DEM cell, a rendered-surface cell, and open ocean with neither.
+    assert.equal(groundFloor.cachedGroundFloor(51.4702, -0.4541), 25);
+    assert.equal(groundFloor.cachedGroundFloor(48.3538, 11.7862), 453);
+    for (let i = 0; i < 1000; i += 1)
+      assert.equal(groundFloor.cachedGroundFloor(30 + i * 0.011, -40.2), null);
+  });
+  // Before, each read made six toFixed calls (the cell twice, the DEM key).
+  assert.equal(calls, 0);
+});
+
+test('a reading reported at a point is found from anywhere in its cell', async () => {
+  const terrain = await warmTerrain([{ lat: 41.5, lon: -97.66, h: 120 }]);
+  const groundFloor = createGroundFloor({ terrain });
+  assert.equal(groundFloor.reportValidatedMeshFloorCell(41.5003, -97.6602, 129), true);
+  assert.equal(groundFloor.cachedMeshFloor(41.4996, -97.6598), 129);
+  assert.equal(groundFloor.cachedGroundFloor(41.4996, -97.6598), 129);
+  // The next cell over has no reading and no DEM entry.
+  assert.equal(groundFloor.cachedMeshFloor(41.5006, -97.6602), null);
+  assert.equal(groundFloor.cachedGroundFloor(41.5006, -97.6602), null);
+});

src/services/terrainHeights.js

@@ -86,6 +86,89 @@ export function createTerrainHeights({
    */
   const cache = new Map();
 
+  /**
+   * The same entries under a numeric key, for the synchronous reads. Those run
+   * for every aircraft on every fleet pass (about 94,000 a second with 7,500
+   * aircraft in view), nearly all of them misses, and building the string key
+   * (two `toFixed` calls and a concatenation) was most of what a read cost.
+   * Kept in step with `cache` by `cacheStore`, eviction and the abort handler.
+   * `at` is the value of `moves` when the entry last became the newest.
+   * @type {Map<number, {key: string, entry: object, at: number}>}
+   */
+  const cells = new Map();
+  /** Counts every move to the newest end of `cache`: stores and promotions. */
+  let moves = 0;
+  /**
+   * A read promotes its entry only once this many moves have passed since it
+   * was last the newest. An entry cannot reach the cold end in fewer than
+   * CACHE_MAX_ENTRIES - 1 moves, so one read at least this often is never
+   * evicted, without rewriting the Map on every read.
+   */
+  const PROMOTE_AFTER_MOVES = Math.floor(CACHE_MAX_ENTRIES / 2);
+
+  /**
+   * `value.toFixed(5)` as an integer count of 1e-5 steps, or null when the
+   * fast arithmetic cannot be trusted to match it. `toFixed` rounds the exact
+   * decimal value; `value * 1e5` is within 2e-8 of it for |value| < 1000, so
+   * the two can only round differently this close to a half. A negative value
+   * that rounds to zero is left to the string too: it formats as "-0.00000",
+   * a different key from "0.00000".
+   * @param {number} value
+   * @returns {number|null}
+   */
+  function fixed5Index(value) {
+    if (!(Math.abs(value) < 1000)) return null;
+    const scaled = value * 1e5;
+    if (Math.abs(scaled - Math.floor(scaled) - 0.5) < 1e-6) return null;
+    const index = Math.round(scaled);
+    return Object.is(index, -0) ? null : index;
+  }
+
+  /** Indices at or past this (500 degrees) do not pack into one integer. */
+  const CELL_INDEX_LIMIT = 5e7;
+
+  /**
+   * The numeric key for a coordinate: its two 5-decimal indices packed into
+   * one integer (below 2^53), or null when the coordinate has to go through
+   * its string key instead.
+   * @param {number} lat
+   * @param {number} lon
+   * @returns {number|null}
+   */
+  function cellKey(lat, lon) {
+    const latIndex = fixed5Index(lat);
+    const lonIndex = fixed5Index(lon);
+    if (
+      latIndex === null ||
+      lonIndex === null ||
+      Math.abs(latIndex) >= CELL_INDEX_LIMIT ||
+      Math.abs(lonIndex) >= CELL_INDEX_LIMIT
+    )
+      return null;
+    return latIndex * 1e8 + lonIndex;
+  }
+
+  /**
+   * The numeric key of a stored string key. The text is the rounded
+   * coordinate itself, so this is exact. Null for a key `cellKey` never
+   * produces; such a key is only ever read through its string.
+   * @param {string} key
+   * @returns {number|null}
+   */
+  function cellKeyOf(key) {
+    const comma = key.indexOf(',');
+    const latIndex = Math.round(Number(key.slice(0, comma)) * 1e5);
+    const lonIndex = Math.round(Number(key.slice(comma + 1)) * 1e5);
+    if (
+      !(Math.abs(latIndex) < CELL_INDEX_LIMIT) ||
+      !(Math.abs(lonIndex) < CELL_INDEX_LIMIT) ||
+      Object.is(latIndex, -0) ||
+      Object.is(lonIndex, -0)
+    )
+      return null;
+    return latIndex * 1e8 + lonIndex;
+  }
+
   /**
    * Store an entry and drop the coldest ones once past the cap. `Map` iterates
    * in insertion order, so deleting the first key evicts the least recently
@@ -101,10 +184,15 @@ export function createTerrainHeights({
   function cacheStore(key, entry) {
     cache.delete(key);
     cache.set(key, entry);
+    moves += 1;
+    const cell = cellKeyOf(key);
+    if (cell !== null) cells.set(cell, { key, entry, at: moves });
     while (cache.size > CACHE_MAX_ENTRIES) {
       const coldest = cache.keys().next().value;
       if (coldest === undefined) break;
       cache.delete(coldest);
+      const coldestCell = cellKeyOf(coldest);
+      if (coldestCell !== null) cells.delete(coldestCell);
     }
   }
 
@@ -119,9 +207,36 @@ export function createTerrainHeights({
     if (entry === undefined) return undefined;
     cache.delete(key);
     cache.set(key, entry);
+    moves += 1;
+    const cell = cellKeyOf(key);
+    const held = cell === null ? undefined : cells.get(cell);
+    if (held) held.at = moves;
     return entry;
   }
 
+  /**
+   * The synchronous read: the entry for a coordinate, or undefined on a miss.
+   * Same answer as `cacheTouch(cacheKey(lat, lon))`, without building the
+   * string, and promoting only an entry that has drifted towards the cold end
+   * (see PROMOTE_AFTER_MOVES).
+   * @param {number} lat
+   * @param {number} lon
+   * @returns {{ellipsoid: number, source: 'reearth'|'geoid-fallback', retryAt?: number}|undefined}
+   */
+  function cacheRead(lat, lon) {
+    const cell = cellKey(lat, lon);
+    if (cell === null) return cacheTouch(cacheKey(lat, lon));
+    const held = cells.get(cell);
+    if (held === undefined) return undefined;
+    if (moves - held.at > PROMOTE_AFTER_MOVES) {
+      cache.delete(held.key);
+      cache.set(held.key, held.entry);
+      moves += 1;
+      held.at = moves;
+    }
+    return held.entry;
+  }
+
   /**
    * Builds the rounded cache key shared between the in-memory cache and the
    * `points` string sent to the proxy (see file header, point 2).
@@ -142,7 +257,7 @@ export function createTerrainHeights({
    * @returns {number|null}
    */
   function cachedEllipsoidalGround(lat, lon) {
-    const entry = cacheTouch(cacheKey(lat, lon));
+    const entry = cacheRead(lat, lon);
     return entry ? entry.ellipsoid : null;
   }
 
@@ -159,7 +274,7 @@ export function createTerrainHeights({
    * @returns {number|null}
    */
   function cachedRealEllipsoidalGround(lat, lon) {
-    const entry = cacheTouch(cacheKey(lat, lon));
+    const entry = cacheRead(lat, lon);
     return entry && entry.source === 'reearth' ? entry.ellipsoid : null;
   }
 
@@ -370,7 +485,14 @@ export function createTerrainHeights({
     });
   }
 
-  signal?.addEventListener('abort', () => cache.clear(), { once: true });
+  signal?.addEventListener(
+    'abort',
+    () => {
+      cache.clear();
+      cells.clear();
+    },
+    { once: true },
+  );
   return {
     cachedEllipsoidalGround,
     cachedRealEllipsoidalGround,

src/services/terrainHeights.test.mjs

@@ -169,3 +169,151 @@ test('an out-of-range cache bound falls back to the default instead of disabling
     );
   }
 });
+
+/** Counts Number.prototype.toFixed calls made while `run` executes. */
+function countToFixed(run) {
+  const original = Number.prototype.toFixed;
+  let calls = 0;
+  Number.prototype.toFixed = function (...args) {
+    calls += 1;
+    return original.apply(this, args);
+  };
+  try {
+    run();
+  } finally {
+    Number.prototype.toFixed = original;
+  }
+  return calls;
+}
+
+test('a synchronous read finds exactly the entry its 5-decimal key names', async () => {
+  // Stored coordinates, and for each the reads that must and must not reach it.
+  // The expectation is the string key the cache has always used.
+  const stored = [
+    [0, 0.001],
+    [51.47, -0.454],
+    [-33.94611, 151.17722],
+    [0.00001, 0.00002],
+    [-0.00001, 0.00003],
+    [89.99999, 179.99999],
+    [-89.99999, -179.99999],
+    [12.345675, 98.765435],
+    [1e-7, 5],
+    [-1e-7, 6],
+    [7, -1e-7],
+    [200.5, 361.25],
+    [10, 500],
+    [10, 499.999999],
+  ];
+  const key = (lat, lon) => `${lat.toFixed(5)},${lon.toFixed(5)}`;
+  const heights = new Map(
+    stored.map(([lat, lon], i) => [key(lat, lon), 100 + i]),
+  );
+  const terrain = createTerrainHeights({
+    source: {
+      async getHeights(chunk) {
+        return chunk.map((item) => ({ ellipsoid: heights.get(item.key) }));
+      },
+    },
+  });
+  await terrain.resolveEllipsoidalGround(
+    stored.map(([lat, lon]) => ({ lat, lon })),
+  );
+
+  const probes = [];
+  const nudges = [
+    0, 1e-13, -1e-13, 1e-9, -1e-9, 4e-6, -4e-6, 4.9999e-6, 5e-6, -5e-6,
+    5.0001e-6, 1e-5, -1e-5,
+  ];
+  for (const [lat, lon] of stored)
+    for (const a of nudges)
+      for (const b of [0, 4e-6, -5e-6])
+        probes.push([lat + a, lon + b], [lat + b, lon + a]);
+  probes.push([0, 0], [-0, 0.001], [0, -0], [NaN, 1], [1, Infinity], [1e21, 2]);
+
+  let hits = 0;
+  for (const [lat, lon] of probes) {
+    const expected = heights.get(key(lat, lon)) ?? null;
+    assert.equal(
+      terrain.cachedEllipsoidalGround(lat, lon),
+      expected,
+      `plain read at ${lat}, ${lon}`,
+    );
+    assert.equal(
+      terrain.cachedRealEllipsoidalGround(lat, lon),
+      expected,
+      `real read at ${lat}, ${lon}`,
+    );
+    if (expected !== null) hits += 1;
+  }
+  assert.ok(
+    hits > 100 && hits < probes.length,
+    `${hits} of ${probes.length} reads hit`,
+  );
+});
+
+test('a synchronous read of an ordinary coordinate formats no numbers', async () => {
+  const terrain = createTerrainHeights({ source: stubSource() });
+  await terrain.resolveEllipsoidalGround([pointAt(1), pointAt(2)]);
+  const calls = countToFixed(() => {
+    assert.equal(
+      terrain.cachedRealEllipsoidalGround(0, lonAt(1)),
+      heightAt(lonAt(1)),
+    );
+    assert.equal(
+      terrain.cachedEllipsoidalGround(0, lonAt(2)),
+      heightAt(lonAt(2)),
+    );
+    // Misses are the common case: an aircraft over a cell nobody resolved.
+    for (let i = 10; i < 1010; i += 1)
+      assert.equal(terrain.cachedRealEllipsoidalGround(45.123, lonAt(i)), null);
+  });
+  // Before, every read built its key with two toFixed calls.
+  assert.equal(calls, 0);
+});
+
+test('an entry read again and again is not rewritten on each read, and still outlives the rest', async () => {
+  const terrain = createTerrainHeights({
+    source: stubSource(),
+    maxCacheEntries: 8,
+  });
+  for (let i = 0; i < 8; i += 1)
+    await terrain.resolveEllipsoidalGround([pointAt(i)]);
+
+  // Coordinate 0 is the coldest. Read it between stores, as a parked contact
+  // would; the seven newer ones are never read.
+  for (let i = 8; i < 15; i += 1) {
+    for (let read = 0; read < 50; read += 1)
+      assert.equal(
+        terrain.cachedEllipsoidalGround(0, lonAt(0)),
+        heightAt(lonAt(0)),
+      );
+    await terrain.resolveEllipsoidalGround([pointAt(i)]);
+  }
+  assert.equal(
+    terrain.cachedEllipsoidalGround(0, lonAt(0)),
+    heightAt(lonAt(0)),
+  );
+  for (let i = 1; i < 8; i += 1)
+    assert.equal(
+      terrain.cachedEllipsoidalGround(0, lonAt(i)),
+      null,
+      `unread coordinate ${i} was evicted`,
+    );
+});
+
+test('an evicted coordinate is gone from the synchronous read too', async () => {
+  const terrain = createTerrainHeights({
+    source: stubSource(),
+    maxCacheEntries: 2,
+  });
+  for (let i = 0; i < 5; i += 1)
+    await terrain.resolveEllipsoidalGround([pointAt(i)]);
+  for (let i = 0; i < 3; i += 1)
+    assert.equal(terrain.cachedRealEllipsoidalGround(0, lonAt(i)), null);
+  for (let i = 3; i < 5; i += 1)
+    assert.equal(
+      terrain.cachedRealEllipsoidalGround(0, lonAt(i)),
+      heightAt(lonAt(i)),
+    );
+});