Problem
During filter sync, check_compact_filters_for_elements matches the union of every monitored script against every filter. BIP158 keys each filter's SipHashes off the block hash, so per filter the whole query set must be re-hashed and re-sorted — per-filter cost is O(M·hash + M log M) with M = monitored script count, and nothing is cacheable across filters.
For CoinJoin wallets M grows monotonically through the scan: every mixing round pays to a fresh single-use address, so a wallet's used-address count is roughly denominations × rounds, and the gap window slides past each one (recovery gap 100/pool on top). A heavy test wallet (~6,600 txs, thousands of CoinJoin outputs) starts a fresh mainnet recovery at a few hundred monitored scripts and ends at several thousand — so late-scan filters cost several times more than early ones, concentrated exactly in the wallet's dense activity region.
Profiling an in-app mainnet recovery (iOS sim, dev-ios profile, 2.32M filters from checkpoint 200k, integration build of #943 + #946 + #947) shows the filters phase is matching-bound, not block-bound. Share of on-CPU samples, consistent at mid-scan and in the dense tail (~88%):
- ~23% SipHash (NEON) of query items
- ~12% re-sorting hashed queries
- ~9% bip158 match/decode glue
- ~32% rayon dispatch overhead (see "related" below)
- wallet/block processing: <2%
Proposed optimization: prune dead single-use addresses from the forward query set
CoinJoin addresses are single-use by design — reuse would link mixing rounds. Once an address's outputs are all spent below the current scan height, in practice nothing ever pays it again. The matcher could drop such spent-and-empty addresses from the forward-scan query set as the scan front advances, keeping M roughly O(active UTXOs + gap lookahead) instead of O(total historical addresses).
For mixing-heavy wallets this bounds the dominant per-filter cost term in the dense region (potentially a several-fold reduction of M late in the scan).
Safety: the theoretical "someone paid an old CoinJoin address after it was emptied" case is exactly what the existing batch-coverage / rescan machinery (filters/manager.rs, cf. #933) is built to absorb — a conservative variant could apply the pruning only to CoinJoin-account scripts, whose single-use property is protocol-driven rather than conventional.
Related observations from the same profile (separate follow-ups?)
- ~32% of on-CPU time is rayon work-distribution overhead, suggesting per-filter task granularity is too fine at small
M; chunking filters per task would amortize dispatch + the per-task catch_unwind.
- The per-filter query re-sort (~12%) may be avoidable depending on merge strategy against the naturally ordered decoded GCS values.
Happy to share the full sample(1) captures and run logs (same wallet/runs discussed in the sync-speed thread).
Problem
During filter sync,
check_compact_filters_for_elementsmatches the union of every monitored script against every filter. BIP158 keys each filter's SipHashes off the block hash, so per filter the whole query set must be re-hashed and re-sorted — per-filter cost isO(M·hash + M log M)withM= monitored script count, and nothing is cacheable across filters.For CoinJoin wallets
Mgrows monotonically through the scan: every mixing round pays to a fresh single-use address, so a wallet's used-address count is roughlydenominations × rounds, and the gap window slides past each one (recovery gap 100/pool on top). A heavy test wallet (~6,600 txs, thousands of CoinJoin outputs) starts a fresh mainnet recovery at a few hundred monitored scripts and ends at several thousand — so late-scan filters cost several times more than early ones, concentrated exactly in the wallet's dense activity region.Profiling an in-app mainnet recovery (iOS sim,
dev-iosprofile, 2.32M filters from checkpoint 200k, integration build of #943 + #946 + #947) shows the filters phase is matching-bound, not block-bound. Share of on-CPU samples, consistent at mid-scan and in the dense tail (~88%):Proposed optimization: prune dead single-use addresses from the forward query set
CoinJoin addresses are single-use by design — reuse would link mixing rounds. Once an address's outputs are all spent below the current scan height, in practice nothing ever pays it again. The matcher could drop such spent-and-empty addresses from the forward-scan query set as the scan front advances, keeping
MroughlyO(active UTXOs + gap lookahead)instead ofO(total historical addresses).For mixing-heavy wallets this bounds the dominant per-filter cost term in the dense region (potentially a several-fold reduction of
Mlate in the scan).Safety: the theoretical "someone paid an old CoinJoin address after it was emptied" case is exactly what the existing batch-coverage / rescan machinery (
filters/manager.rs, cf. #933) is built to absorb — a conservative variant could apply the pruning only to CoinJoin-account scripts, whose single-use property is protocol-driven rather than conventional.Related observations from the same profile (separate follow-ups?)
M; chunking filters per task would amortize dispatch + the per-taskcatch_unwind.Happy to share the full
sample(1)captures and run logs (same wallet/runs discussed in the sync-speed thread).