8 Years of Optimizing Apache Otava: How disconnected open source developers took an algorithm from n3 to constant time

Henrik Ingo

REVIEW 4 major objections 5 minor 6 references

8 Years of Optimizing Apache Otava: How disconnected open source developers took an algorithm from n3 to constant time

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Appending a data point now recomputes change points in constant time

desk verdict A useful historical review with a plausible incremental extension, but the paper's own benchmark table appears to contradict the headline constant-time claim. read the letter →

arxiv 2505.06758 v1 pith:EUQKQQPG submitted 2025-05-10 cs.PF

Henrik Ingo This is my paper · ORCID

classification cs.PF

keywords changepointdetectione-divisiveincrementalalgorithmconstanttimeperformanceoptimizationbenchmarkingcontinuousintegrationMonteCarlosignificancetest

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper recounts eight years of performance work on an open-source implementation of the e-divisive change point detection algorithm and adds a new incremental mode. Its central claim is that when a new data point is appended to a series, only the last window of W points needs to be recomputed, so the common update runs in constant time O($W^{2}$). Together with earlier optimizations, this yields a claimed speedup of 18,000 to 300,000 over the original by-the-book implementation. The authors also supply complexity analyses that earlier papers missed, most notably the effect of Monte Carlo permutation testing, and they report benchmarks on a 365-point series.

What carries the argument

The load-bearing mechanism is the windowed e-divisive algorithm: the series is split into overlapping or adjacent windows of size W, and the pairwise distance matrix is computed only within each window, giving O(TW) instead of O($T^{3}$). The new incremental update exploits the locality of this windowing: appending a point requires recomputation of only the final 1-2 windows, so the update cost is O($W^{2}$), a constant because W is fixed. The earlier switch from Monte Carlo significance testing to Student's t-test also matters, since it removed the O(m $T^{2}$) cost of running m permutations of the whole series.

What would settle it

Take a long series with a weak change point near position T-W, then append a single large outlier that sharply increases the estimated variance in the final window. If recomputing incrementally changes the significance or location of the earlier change point compared with a full recompute, the window-independence assumption fails.

Watch

Extended reading notes

Core claim

On the authors' own terms, the discovery is that e-divisive change point detection can be made incremental. Because the Hunter-style modification splits the series into windows of fixed width W, appending a single point only changes windows at the very end; windows more than W points away are unaffected. Recomputing the last one or two windows costs O($W^{2}$), and since W is a constant, this is O(1) with respect to series length T. The paper reports that this incremental version is 4x to 50x faster than the previous fastest version, and that the full sequence of optimizations represents a speedup of roughly four to five orders of magnitude over the original implementation.

Load-bearing premise

The paper's constant-time claim rests on the assertion that a newly appended point cannot change the change point decisions in any window that begins more than W points before the end of the series; that assertion is stated, not proven.

Editorial extensions

If this is right

Incremental updates make it feasible to recompute change points on every data append or page view, without background jobs, for series up to at least the tested length.
For monitoring dashboards, the cost of adding a new observation no longer grows with the history length, enabling real-time regression alerts.
The complexity analysis clarifies that the Monte Carlo significance test, not the pairwise distance matrix, was the original bottleneck, guiding future optimization effort.
The windowing plus incremental approach may transfer to other change point detection methods that use local test statistics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The constant-time result is conditional on the authors' window-independence assumption; if statistical significance depends on global variance or if change points are allowed to propagate across window boundaries, the O(1) bound may not hold for adversarial series.
A natural extension would be to derive formal error bounds for the incremental mode versus a full recomputation, since the paper provides benchmarks but no proof that detection quality is unaffected.
The same incremental idea could be applied to multivariate e-divisive detection, where the window statistics would be covariance matrices rather than scalars.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The genuinely new piece here is the incremental O(W^2) update for appending a point, and that is also where the paper's trouble sits: the benchmark table does not support the constant-time story. That is the first thing you should know.

To give credit where it is due, the paper does a few things well. The historical review of eight years of optimizations to what is now Apache Otava is readable and honest about the messiness of open source. The complexity corrections to prior work are real: adding the Monte Carlo permutation count m to the O() notation for the original e-divisive implementation fixes an actual omission, and supplying a complexity analysis for the Hunter modifications is useful. The incremental idea itself is a natural extension of Hunter's windowing scheme, and the derivation is not circular; it follows from the code's structure rather than being fit to any result. The author also clearly identifies his own role and the self-citation concern, which is mild.

Now the soft spots, in proportion. The aggregate 18,000-300,000 speedup is assembled from benchmarks on different hardware and published in different papers, so it is a historical claim rather than a controlled measurement. That is a minor issue if treated as history. The larger issue is Table 2. The incremental row grows from 5.5 ms at p=0.001 (6 change points) to 157 ms at p=0.1 (31 change points), a 28x increase. If only the last one or two windows of size W are recomputed, the runtime should be roughly flat across those columns—the number of change points in the whole series should not matter. At p=0.1 the incremental pass is only 1.17x faster than the full Student+W pass, which is not what an O(W^2) tail update should look like. Either the incremental implementation is redoing more than the last window, or the window-independence assumption is breaking down when change points are dense, or the benchmark methodology is measuring something unintended. The paper neither explains this nor acknowledges it. The window-independence assumption itself is asserted, not proved; the benchmark data suggests it deserves scrutiny. Also missing are error bars; reporting medians without variance is thin, especially when the claim is about constant time.

Who is this for? Performance engineers working with change point detection in CI or web UIs will find the history and the complexity corrections useful, and the incremental update is worth trying. But the benchmark needs major revision before the constant-time claim is credible. My recommendation: send it to peer review—the incremental extension deserves referee time—but expect heavy revision, and the reviewer should push hard on Table 2.

Referee Report

4 major / 5 minor

Summary. This paper reviews eight years of performance optimizations applied to the E-Divisive change point detection implementation now known as Apache Otava (incubating), attributing the improvements to a loosely connected group of open source contributors. It contributes a complexity analysis of earlier optimizations, adds the Monte Carlo permutation count m to the O() notation for the naive implementation, and introduces a new incremental optimization: when a single data point is appended to the end of a time series, the paper claims that only the last one or two windows need to be recomputed, reducing the cost of the common append operation to O(W^2) (in practice O(1) since the window size W is constant). The paper presents benchmark results on a 365-point TigerBeetle dataset comparing Native (C), Student+W, and Incremental modes, and claims a cumulative speedup of 18,000 to 300,000 over the original 'by the book' implementation.

Significance. If the O(1) incremental claim were rigorously established, this would be a practically valuable result for real-time change point detection in continuous performance engineering, and the paper provides a useful historical narrative of how open source contributors progressively improved a statistical algorithm. The paper makes a concrete, falsifiable performance claim, which is commendable, and the historical complexity analysis in Section 4 is a useful correction to earlier papers that omitted the Monte Carlo cost. However, the manuscript currently lacks a formal proof of the central window-independence assumption, and the paper's own benchmark data appear to contradict the constant-time claim. The cumulative speedup headline is also not reproducible from the measurements reported here because it aggregates results from different papers, different hardware, and different implementations.

major comments (4)

[Section 6, Table 2] Table 2 directly contradicts the central O(1) claim. The Incremental row grows from 5.5 ms at p=0.001 (6 change points) to 157 ms at p=0.1 (31 change points), a 28x increase, even though the algorithm is said to recompute only the last window. At p=0.1 the Incremental time is 157 ms versus 184 ms for Student+W, only a 1.17x improvement, which is not what a constant-time incremental update should look like. The paper needs to either explain why the incremental runtime depends strongly on the number of change points or revise the claim; as written, the data suggest that the incremental pass re-evaluates more than the last one or two windows.
[Section 6] The load-bearing assumption 'the newly appended last point cannot have any effects on the points that are earlier than the last W points' is asserted but not proven. Since the e-divisive algorithm recursively splits the series at change points and the Hunter variant uses a weak-change-point merge step, it is not self-evident that appending a point cannot affect earlier windows or the global list of change points. A formal statement of the incremental algorithm and a proof of window independence (or a precise set of conditions under which it holds) are needed to support the O(W^2) complexity claim.
[Table 2 and Section 6] The text states that 'the incremental Otava version is between 4x and 50x faster than the Native C version', but Table 2 reports an Incremental relative time of 0.41 at p=0.1, which is only a 2.4x speedup. This is inconsistent with the stated 4x lower bound. The relative values in the table are also labeled 'Relative improvement' while the numbers appear to be fractions of the Native (C) time; the label and the claimed range need to be reconciled.
[Abstract and Sections 6-7] The headline cumulative speedup of 18,000 to 300,000 is not reproducible from this paper. It combines speedups reported in earlier papers (Daly et al. 2020, Fleming et al. 2023) that were measured on different hardware, with different datasets, and without a common baseline, and the present paper only measures three of the seven versions on a single dataset. A rigorous cumulative speedup claim requires an apples-to-apples benchmark that runs all versions in the same environment, or at least a clearly stated renormalization procedure; neither is provided.

minor comments (5)

[Abstract, Section 1.1] There are several typos that should be corrected, including 'continuosly' in the abstract and 'comopanies' in Section 1.1; a full proofreading pass is recommended.
[Table 2] The row label 'Relative improvement' is ambiguous because the values are fractions of the Native (C) time rather than percentage improvements; consider renaming to 'Relative time (fraction of Native C)' or making the direction explicit.
[Table 2] The paper reports only medians from 100 runs without confidence intervals or dispersion measures; given the large differences across columns, reporting standard deviation or an error range would strengthen the empirical claims.
[Section 6] The role of the weak-change-point merge() step in the incremental mode is not explained; the paper should clarify whether the incremental recomputation re-runs the merge globally, since that could be a source of the dependence on change point density observed in Table 2.
[Table 1] The relative speed ranges in Table 1 (e.g., '0.03 - 0.32') are given without specifying the configuration or dataset used to produce the endpoints, making the ranges difficult to interpret or reproduce.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation in the O(W^2) claim; minor self-citation in the aggregate speedup figure is not load-bearing.

full rationale

The central new claim is that appending one point requires recomputing only the last 1-2 windows, giving O(W^2)=O(1) for fixed W. This is an algorithmic-structural argument, not a fit: no parameter is estimated from data in Section 6, and the benchmark in Table 2 is an empirical measurement of the implementation rather than a forced consequence of the claim. The cumulative 18k-300k speedup multiplies the present benchmark's 4x-50x against 'Native C' by an 8500x figure from [Daly et al. 2020] and [Fleming et al. 2023], both coauthored by the present author. That is self-citation, but it is an aggregate historical benchmark claim, not the load-bearing premise of the O(1) derivation; the O(W^2) result stands independently of the speedup multiplier. No equation in the paper reduces to a previously fitted value, and no uniqueness theorem or ansatz is imported from the authors' prior work. The assertion that a new point cannot affect points earlier than the last W points is an unproved locality assumption; if wrong it is a correctness risk, not a circularity.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

No new particle, force, dimension, or other postulated entity is introduced; the paper only modifies an existing algorithm. The central O(1) claim rests on the window-independence assumption, the treatment of W as a fixed constant, and the validity of the inherited Student's t-test. The aggregate speedup additionally relies on comparability of benchmarks from different papers and hardware.

free parameters (3)

Window size W = Typically 50; the paper also mentions 30
The O(1) claim depends on W being a fixed constant independent of series length T. The incremental complexity is O(W^2), which is constant only if W is not allowed to grow.
Significance threshold p = User-set values 0.001, 0.01, 0.1, 0.2 in the benchmark
The p-value determines how many change points are found and therefore affects the runtime ratios; the speedup range is observed across these user choices.
Monte Carlo permutation count m = 100 in practical implementations; paper suggests 1000-10000 for robustness
m is added to the O() notation for the original algorithm and is a parameter of the significance test, not of the new incremental optimization.

assumptions (3)

domain assumption Appending a new point affects only the last 1-2 windows; earlier change points remain valid.
This is the assumption that makes the O(1) claim hold. Section 6 asserts it without proof, and it could fail under overlapping windows or global significance testing.
domain assumption Student's t-test on each window provides a valid significance test for change points.
Inherited from [Fleming et al. 2023]; no statistical justification is given in this paper.
domain assumption Historical speedup ratios from different papers and hardware can be multiplied to produce the aggregate 18k-300k speedup.
The paper combines previous benchmarks with new ones, but comparability across experimental setups is not experimentally established.

how reviews work

0 comments

Cite this review

Pith. "Pith review of 8 Years of Optimizing Apache Otava: How disconnected open source developers took an algorithm from n3 to constant time." pith.science (2026). https://pith.science/paper/EUQKQQPG

@misc{pith2026250506758,
  author       = {Pith},
  title        = {Pith review of: 8 Years of Optimizing Apache Otava: How disconnected open source developers took an algorithm from n3 to constant time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EUQKQQPG}},
  note         = {Machine review of arXiv:2505.06758}
}

read the original abstract

As the project now known as Apache Otava (incubating) makes it first release, we look back over the past 8 years that the codebase was developed by a rather uncoordinated, loosely connected group of performance engineers at MongoDB, Datastax, Confluent, Nyrkio and others. Ever since the first publication (Daly 2020), developers of the code base now known as Apache Otava (incubating), have continuosly improved its performance. Even when a contributor's primary motivation was to add functionality, it seems like they couldn't help themselves but to also make some performance optimizations while at it. When developing the Nyrkio web service to provide change detection for performance testing, we have observed that Otava had become fast enough that it was almost feasible to compute change points synchronously, as the user is browsing test results in a web browser. Inspired by this, we have developed and contributed a new optimization for the common case where new data points are appended to the end of the series. This is now the 7th generation of performance optimizations in Otava. These improvements have been done over the past 8 years of development, by disconnected individuals at different employees. Taken together, the historical optimizations and those published in this paper, represent a 18 000 to 300 000 speedup over the original by the book implementation of (Matteson and James 2014). In the language of computational complexity, an evolution from O (n3) to O (1) (constant time). The ability to compute and recompute change points in real-time unlocks new opportunities in the user experience.

Figures

Figures reproduced from arXiv: 2505.06758 by the authors.

**Figure 2.** A short timeseries used for illustration purposes [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

**Figure 3.** Pairwise differences an optimal threshold for each test separately. In conclusion, a more sophisticated statistical method is needed. Immediately at the start, the e-divisive algorithm takes a different approach than most other algorithms we reviewed or thought of. Commonly the problem of validating results from a Continuous Benchmarking pipeline is seen as one where one or a few newest results are compared against … view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: The E-divisive algorithm, illustrated. (See [Matteson and James 2014] for actual math. [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]

**Figure 5.** Figure 5: 𝑞ˆ computed for each gap between points in the series scale differently with the number of change points 𝜅 found, and in practice we often find less than the 20 found in the benchmarks in [Fleming et al. 2023]. 4 Computational Complexity Analysis of the Historical Resu…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 3 canonical work pages

[3]

In Workshop on Testing Database Systems (DBTest’20) (2020)

Automated System Performance Testing at MongoDB. In Workshop on Testing Database Systems (DBTest’20) (2020). https: //doi.org/10.1145/3395032.3395323 3Note that even if we assign blame to the third person due to the customary writing style, it is the same third person as is authoring the present article. Nyrkiö whitepaper Angus Kroll

arXiv 2020
[2014]

A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data. J. Amer. Statist. Assoc. 109, 505 (2014), 334–345. http://www.jstor.org/stable/24247158 MongoDB. [n. d.]. Signal Processing Algorithms. https://github.com/mongodb/signal- processing-algorithms Accessed: 2021-10-13. Piotr Kołaczkowski. [n. d.]. Hunter – Hunts Performance Regr...

work page arXiv 2014
[2020]

In Proceedings of the 2020 ACM/SPEC International Conference on Performance Engineering(ICPE ’20) (2020)

The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System. In Proceedings of the 2020 ACM/SPEC International Conference on Performance Engineering(ICPE ’20) (2020). https://doi.org/10.1145/ 3358960.3375791 Matt Fleming, Piotr Kolaczkowski, Ishita Kumar, Shaunak Das, Sean McCarthy, Pushkala Pattabhira...

arXiv 2020
[2022]

Fixing Performance Regressions Before They Happen. ... (2022). https://netflixtechblog.com/fixing-performance-regressions-before-they- happen-eab2602b86fe blog. David S. Matteson and Nicholas A. James

work page 2022
[2023]

In Proceedings of the 2023 ACM/SPEC International Conference on Performance Engineering (Coimbra, Portugal) (ICPE ’23)

Hunter: Using Change Point De- tection to Hunt for Performance Regressions. In Proceedings of the 2023 ACM/SPEC International Conference on Performance Engineering (Coimbra, Portugal) (ICPE ’23). Association for Computing Machinery, New York, NY, USA, 199–206. https: //doi.org/10.1145/3578244.3583719 Henrik Ingo and David Daly

arXiv 2023
[2024]

In Kafka Summit Lon- don

Automating Speed: A proven approach to preventing performance regressions in Kafka Streams. In Kafka Summit Lon- don. https://www.confluent.io/events/kafka-summit-london-2024/automating- speed-a-proven-approach-to-preventing-performance-regressions-in/

work page 2024

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [3]

In Workshop on Testing Database Systems (DBTest’20) (2020)

Automated System Performance Testing at MongoDB. In Workshop on Testing Database Systems (DBTest’20) (2020). https: //doi.org/10.1145/3395032.3395323 3Note that even if we assign blame to the third person due to the customary writing style, it is the same third person as is authoring the present article. Nyrkiö whitepaper Angus Kroll

arXiv 2020

[2] [2014]

A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data. J. Amer. Statist. Assoc. 109, 505 (2014), 334–345. http://www.jstor.org/stable/24247158 MongoDB. [n. d.]. Signal Processing Algorithms. https://github.com/mongodb/signal- processing-algorithms Accessed: 2021-10-13. Piotr Kołaczkowski. [n. d.]. Hunter – Hunts Performance Regr...

work page arXiv 2014

[3] [2020]

In Proceedings of the 2020 ACM/SPEC International Conference on Performance Engineering(ICPE ’20) (2020)

The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System. In Proceedings of the 2020 ACM/SPEC International Conference on Performance Engineering(ICPE ’20) (2020). https://doi.org/10.1145/ 3358960.3375791 Matt Fleming, Piotr Kolaczkowski, Ishita Kumar, Shaunak Das, Sean McCarthy, Pushkala Pattabhira...

arXiv 2020

[4] [2022]

Fixing Performance Regressions Before They Happen. ... (2022). https://netflixtechblog.com/fixing-performance-regressions-before-they- happen-eab2602b86fe blog. David S. Matteson and Nicholas A. James

work page 2022

[5] [2023]

In Proceedings of the 2023 ACM/SPEC International Conference on Performance Engineering (Coimbra, Portugal) (ICPE ’23)

Hunter: Using Change Point De- tection to Hunt for Performance Regressions. In Proceedings of the 2023 ACM/SPEC International Conference on Performance Engineering (Coimbra, Portugal) (ICPE ’23). Association for Computing Machinery, New York, NY, USA, 199–206. https: //doi.org/10.1145/3578244.3583719 Henrik Ingo and David Daly

arXiv 2023

[6] [2024]

In Kafka Summit Lon- don

Automating Speed: A proven approach to preventing performance regressions in Kafka Streams. In Kafka Summit Lon- don. https://www.confluent.io/events/kafka-summit-london-2024/automating- speed-a-proven-approach-to-preventing-performance-regressions-in/

work page 2024