Skip to content

perf(status-history): compute day buckets in a single pass - #4098

Open
aithal007 wants to merge 1 commit into
fosrl:mainfrom
aithal007:perf/status-history-single-pass
Open

aithal007 wants to merge 1 commit into
fosrl:mainfrom
aithal007:perf/status-history-single-pass

Conversation

@aithal007

@aithal007 aithal007 commented Nov 12, 2026 •

Copy link
Copy Markdown

## Community Contribution License Agreement
By creating this pull request, I grant the project maintainers an unlimited,
perpetual license to use, modify, and redistribute these contributions under any terms they
choose, including both the AGPLv3 and the Fossorial Commercial license terms. I
represent that I have the right to grant this license for all contributed content.

AI Disclosure

An AI coding assistant helped write the rewrite, the tests and the benchmarks, and to fuzz the new implementation against the current one. The equivalence and benchmark numbers below come from running them locally.

Description

Replaces #3802 (rebased onto latest main; the old PR's red check was the repo's ESLint setup, not this change).

Summary

computeBuckets() in server/lib/statusHistory.ts builds one bucket per day for the status-history endpoints. For each day it rescanned the entire event list, and cloned it:

const dayEvents = events.filter(...)            // full scan
const lastBeforeDay = [...events]               // full clone of every event
    .filter((e) => e.timestamp < dayStartSec)   // full scan
    .at(-1);                                    // ...to read a single element

That's three full traversals and one full array allocation per day, with days going up to 365 (the schema's own max). The clone exists only to read its last element. A further pair of arrays was allocated per day to build allStatuses just to call .every() on it.

Separately, getBatchedStatusHistory() grouped events per entity with events.filter(...) and lastKnownEvents.find(...) inside a loop over entities, which is O(entities x events).

What changed

computeBuckets already sorts its input by (timestamp, id) (the same-second ordering fix for #3994), and the day windows advance monotonically, so a single forward cursor yields each day's slice and the carried-in status with no rescanning and no per-day clone. The allStatuses check became an in-place scan with an early exit, and the batched grouping became a single pass into Maps.

No behaviour change: this is only how the same result is computed. The same-second ordering regression test from #3994 is kept alongside the new tests.

Impact

This is synchronous work on the request path, so it's time the process can't serve anything else.

computeBuckets, single entity (median of 7 runs, against current main):

days events main this PR speedup
30 500 0.43 ms 0.12 ms 3.7x
90 2,000 4.42 ms 0.34 ms 13.2x
365 5,000 36.81 ms 1.31 ms 28.2x
365 20,000 237.76 ms 2.35 ms 101.3x

Batched grouping (300 events per entity, measured on the original base before the rebase; that grouping code is unchanged):

entities events before after speedup
10 3,000 0.29 ms 0.33 ms 0.9x
50 15,000 6.60 ms 0.20 ms 33.2x
200 60,000 108.86 ms 1.27 ms 85.4x
500 150,000 181.75 ms 2.86 ms 63.6x

The 10-entity grouping row is a wash: building the Maps costs about what the scan did at that size. The win starts around 50 entities. The computeBuckets improvement applies at every size.

Verification

Output equivalence: 20,000 generated workloads, zero differences against the current computeBuckets on main. The fuzz covers days (1-365), event counts (0-1000), shuffled and sorted input, many same-second and same-day-boundary timestamps, priorStatus, and tzOffsetMinutes (including -720 and +840), comparing full JSON.stringify output with the clock frozen so both versions see the same "now". (An earlier run without a frozen clock showed 2 of 6,000 differences, both the final window ending one second later because the wall clock ticked between the two calls.)

Tests (server/lib/statusHistory.test.ts) pin the properties the cursor must preserve, most importantly that a day inherits the status of the newest event from any earlier day, which is the part a naive cursor gets wrong.

How to test?

  1. npx tsx server/lib/statusHistory.test.ts: all assertions pass.
  2. npx tsc --noEmit: clean (SQLite and Postgres drivers).
  3. npm test: the new test file passes.

Separately, I've emailed a report to security@pangolin.net. Could someone from the team take a look when you get a chance?

computeBuckets() rescanned the whole event list once per day, and cloned it
once per day on top of that:

    const dayEvents = events.filter(...)            // full scan
    const lastBeforeDay = [...events]               // full clone
        .filter((e) => e.timestamp < dayStartSec)   // full scan
        .at(-1);                                    // ...to read one element

With days up to 365 (the schema's max) that is three full traversals and one
full array allocation per day. A further array pair was allocated per day to
build `allStatuses` just to run `.every()` over it.

The events are sorted by (timestamp, id) at the top of the function and the
day windows advance monotonically, so one forward cursor yields each day's
slice and the carried-in status without any rescanning. The `allStatuses`
check is done in place with an early exit.

getBatchedStatusHistory() separately grouped events with
`events.filter(...)` and `lastKnownEvents.find(...)` per entity, i.e.
O(entities x events). That is now a single grouping pass into Maps.

Measured against current main (median of 7 runs), computeBuckets for one
entity:

    days  events     main      now   speedup
      30     500   0.43ms   0.12ms      3.7x
      90    2000   4.42ms   0.34ms     13.2x
     365    5000  36.81ms   1.31ms     28.2x
     365   20000 237.76ms   2.35ms    101.3x

Output is unchanged: fuzzed against the current implementation over 20,000
generated workloads (shuffled and sorted input, same-second ties, timezone
offsets, prior status) with the clock frozen, with identical results.

The new tests sit alongside the existing same-second ordering test and cover
the properties the cursor has to preserve, notably that a day inherits the
status of the newest event from any earlier day.
Copilot AI balanced review requested due to automatic review settings November 12, 2026 17:39

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Copilot was unable to review this pull request because the user who requested the review has insufficient remaining quota. Try requesting a review at a lower effort level.

An organization owner can choose the repository organization as the billing source for reviews requested by members with a paid Copilot license. Learn about Copilot code review billing. Review the Copilot code review billing settings.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants