Pith. sign in

REVIEW 4 major objections 5 minor 17 references

Low Overhead Allocation Sampling in a Garbage Collected Virtual Machine

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 The paper shows that the check for whether an allocation should be sampled can be folded into the garbage collector's existing nursery-limit check, making per-allocation sampling free.

desk verdict Clever, honest systems paper with a real 'free check' for allocation sampling; evaluation needs more runs and explicit large-object handling, but the mechanism holds and it deserves peer review. read the letter →

arxiv 2506.16883 v1 pith:YGK422YT submitted 2025-06-20 cs.PL

Christoph Jung , C.F. Bolz-Tereick This is my paper · ORCID
classification cs.PL
keywords allocationsamplingprofilergarbagecollectionnurserybump-pointerPyprofilingoverheadobjectlifetime
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 sets out to show that statistical allocation profiling need not slow down every allocation. Its central trick is to fold the question 'should this allocation be sampled?' into the bump-pointer check the garbage collector already performs to decide whether the nursery is full, so the fast path of allocation is identical with and without sampling. The authors implement this in the PyPy virtual machine, capture the allocation call stack, object type, and survival to the next minor collection, and measure the overhead. They report a maximum time overhead of 25% for a 4 MB sampling period, with the overhead tunable through the period.

What carries the argument

The load-bearing object is a second pointer, the sample point, placed at $\mathit{sample\_point} = \mathit{nursery\_free} + \mathit{sample\_n\_bytes}$ at startup, together with the invariant that the number of bytes until the next sample equals $\mathit{sample\_point} - \mathit{nursery\_free}$. Its role is to make the nursery-limit comparison do double duty: the nursery limit is set to the minimum of the sample point and the real nursery top, so the existing allocation fast-path check fires both when the nursery is exhausted and when a sample is due, leaving the fast path unchanged. The paper notes that the pseudocode is somewhat simplified and that the real implementation must also handle objects larger than the sampling period, which need to be sampled more than once.

What would settle it

On a workload whose total allocation is known, run the profiler and compare the number of samples against total allocated bytes divided by the sampling period; a mismatch, especially when objects larger than the sampling period are allocated, would show that the invariant or the multi-sample case is not implemented as claimed.

Watch

Extended reading notes

Core claim

Allocation sampling can be made statistically accurate at the garbage-collector level with no per-allocation cost by reusing the nursery full check. The implementation introduces a sample point inside the nursery and keeps the invariant $\mathit{sample\_point} - \mathit{nursery\_free} = \mathit{sample\_n\_bytes} - \mathit{allocated}$, so the number of bytes until the next sample is exactly the gap between the current nursery pointer and the sample point. Setting the nursery limit to the lower of the sample point and the real nursery top means the existing overflow check fires both when a sample is due and when the nursery is truly full; the collector distinguishes the two cases, records a stack sample when needed, advances the sample point, and then either resumes allocation or performs a minor collection. For sampling periods larger than the nursery, the sample point lies outside the nursery and is adjusted by the change in the nursery free pointer at each minor collection; for large objects allocated outside the nursery, the sample point is moved left by the object size. The paper reports a measured maximum time overhead of 25% at a 4 MB sampling period, with slightly better overhead than time-based sampling when normalized to 1000 samples per second.

Load-bearing premise

Everything rests on the invariant that the gap between the nursery pointer and the sample point exactly tracks the bytes still to be allocated before a sample, and that this invariant survives minor collections, out-of-nursery allocations, and sampling periods larger than the nursery; the pseudocode leaves objects larger than the sampling period to the real implementation.

Editorial extensions

If this is right

  • At a 4 MB sampling period, enabling allocation sampling costs at most 25% extra time on the measured benchmarks, and lower overheads are available by raising the period.
  • The allocation fast path is the same with and without sampling, so sampling can remain enabled and only the slow path pays for stack walking and bookkeeping.
  • Each sample records the call stack, the object type, and whether the object died before or survived the next minor collection, giving a picture of allocation sites and object lifetimes.
  • Because samples are taken at GC events rather than at source or bytecode level, the profile reflects allocations that actually happen after JIT escape analysis, avoiding the distortion of instrumenting every allocation site.
  • Combining allocation sampling with time sampling gives a dual view of where time is spent and where memory is allocated, and the Guile profiler's approach is the special case where the sampling period equals the nursery size.

Reading between the lines

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

  • A possible generalization: any generational collector with a bump-pointer nursery and a limit check could carry a sample point, so the zero-cost-per-allocation property plausibly extends beyond this particular virtual machine.
  • If the invariant is maintained, the sample count on a test workload should equal total allocated bytes divided by the sampling period; testing that equality under randomized sampling periods and object sizes would directly probe the edge cases the pseudocode leaves out.
  • The recorded type-and-survival data could feed automatic pretenuring heuristics or lifetime-based allocation advice, a direction the paper mentions only as prior work.
  • Since large objects are sampled by moving the sample point left, an object larger than the sampling period should produce multiple samples; verifying that behavior would be a concrete test of the implementation's completeness.
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.

Referee Report

4 major / 5 minor

Summary. The paper presents a sampling allocation profiler integrated into PyPy's generational GC. The main idea is to set the nursery limit to a sample_point so that the existing fast-path comparison nursery_free > nursery_limit also decides whether an allocation sample should be taken; when the limit is reached, collect_and_reserve distinguishes a real minor-collection trigger from a sampling trigger. Large-object allocations are sampled by moving sample_point left and checking against nursery_free. The profiler records call stacks, RPython-level object types, and whether the sampled object survived a minor collection, and a converter exports the data to the Firefox Profiler UI. Evaluation on four benchmarks with five runs each reports overhead as a function of sampling period, with a maximum of 25% at a 4 MB sampling period, and a case study in the PyPy JIT demonstrates an allocation optimization.

Significance. If the implementation matches the claims, this is a practically valuable contribution: it shows how allocation-site sampling can be folded nearly for free into the existing bump-pointer check in a generational collector, and it enriches profiles with type and survival information that are useful for managed-language performance work. The work is open source, uses a fuzzer for correctness testing, and honestly labels the evaluation as preliminary. The overhead is measured directly against un-profiled execution, and there are no fitted parameters, so the central empirical claim is not circular. The main risks are that the simplified pseudocode hides exactly the edge cases on which the correctness invariant depends, and the empirical basis for the headline overhead number is thin.

major comments (4)
  1. [§3.2–3.4, Figs. 8 and 11, footnotes 10–11] The paper's central claim that the sampling check is free depends on the invariant sample_point - nursery_free = sample_n_bytes - allocated being preserved on every allocation path. The pseudocode in Figs. 8 and 11 is explicitly simplified and does not handle an allocation larger than the sampling period, which needs to be sampled more than once; the real code is not shown, and the fuzzer section does not report whether this boundary case was exercised. As written, the paper leaves a gap between the stated invariant and a verifiable implementation. Please include the actual code paths (or a precise specification) for oversize allocations and for sample points outside the nursery, together with fuzzer statistics covering these cases.
  2. [§3.2 and Fig. 4] The fast-path check is `gc.nursery_free > gc.nursery_limit`, so an allocation that makes the cumulative allocated bytes exactly equal to `sample_n_bytes` is not sampled; the sample is deferred to the next allocation. This is a real off-by-one issue when object sizes divide the sampling period, and it systematically misattributes the sample away from the object containing the boundary byte. The paper should state whether this is intentional and, if so, justify that it does not bias the profile; otherwise the comparison should be `>=`.
  3. [§5.1, Fig. 13] The headline overhead claim ('maximum time overhead of 25%' at a 4 MB sampling period) is based on five runs of each of four benchmarks, with no error bars, no per-run distribution shown, and no statement of which benchmark produced the maximum. Because overhead measurements in JITted virtual machines are noisy, this is not enough statistical support for a quantitative headline claim. Please report medians and spreads, or per-run values, and state whether 'maximum' means the worst observed run across all benchmarks.
  4. [§3.3] The case `sample_n_bytes > nursery_size` is described only in prose and Figure 10; there is no pseudocode for adjusting `sample_point` across minor collections or for deciding when to take a sample when `nursery_limit != sample_point`. Since the paper explicitly supports sampling periods larger than the nursery, this path must be specified precisely and tested, otherwise the correctness of the 'free check' claim for long periods cannot be assessed.
minor comments (5)
  1. [Abstract and §5.1] The abstract states the 25% maximum without the qualification 'preliminary evaluation' that appears in §5.1; please qualify the headline claim in the abstract as well.
  2. [§5.1] The phrase 'high sampling period (high period = low value for sample_n_bytes)' is inconsistent: a high sampling period should mean a large value of `sample_n_bytes`. Please correct the wording.
  3. [§5.1, Fig. 16] The formula for normalized overhead is ambiguous as written; use `1 + (overhead - 1) * 1000 / num_samples` with explicit parentheses, and note that this assumes the per-sample overhead is independent of the sampling rate.
  4. [Figure 1 caption] The caption contains the duplicated phrase 'show 7 show' and several other grammatical issues; please clean it up.
  5. [Figure 7 and §3.2] Figure 7 draws multiple sample points, while the text states that only one `sample_point` exists at any time; please clarify that the figure is a conceptual illustration rather than a literal snapshot.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the free-check claim is an implementation construction verified by fuzzing, and the overhead numbers are direct measurements without fitted parameters.

full rationale

The paper's central claim is that the sampling check can be folded into the existing nursery bump-pointer limit check, leaving the allocation fast path unchanged. This is presented as an engineering construction, not as a derived prediction: sample_point is initialized as nursery_free + sample_n_bytes, nursery_limit is set to min(sample_point, nursery_top), and the invariant sample_point - nursery_free = sample_n_bytes - allocated follows by arithmetic and is maintained by the shown code. The figure 4 fast path is identical with and without sampling, so the 'free check' claim is a property of the implemented mechanism rather than a conclusion derived from its own output. The overhead evaluation compares runtime with sampling to runtime without sampling on the same benchmarks; there are no fitted parameters, no subset of data used to predict another subset, and no self-citation is load-bearing. The references to the authors' earlier JIT work are background on escape analysis and PyPy's tracing JIT, not justifications of the sampling result. Correctness is checked by a randomized fuzzer against independently computed expected sample triggers. The noted simplifications for objects larger than the sampling period are robustness concerns, not circularity. No step in the paper reduces to its own inputs by definition or by self-citation.

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

The paper introduces no new abstract entities; sample_point is an implementation artefact (a pointer in the nursery) rather than a new physical or mathematical object. The central claim depends mainly on the standard GC design and the representativeness of the benchmarks.

assumptions (3)
  • domain assumption PyPy's GC uses a single contiguous nursery with bump-pointer allocation, so the nursery limit check is a single comparison.
    Section 2.2 and Figures 2-4 describe this standard GC design; the entire sampling mechanism depends on this layout.
  • domain assumption The branch on nursery overflow is predictable and cheap, so reusing it for sampling does not slow the fast path.
    Section 3.1 claims the fast path is unchanged; this assumes the added branch is not costly, which is plausible but not measured in isolation.
  • domain assumption The benchmark suite (four programs) is representative of allocation-heavy workloads.
    Section 5.1 explicitly says the evaluation is 'preliminary, with a limited benchmark set', so the 25% maximum overhead figure is conditional on this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Low Overhead Allocation Sampling in a Garbage Collected Virtual Machine." pith.science (2026). https://pith.science/paper/YGK422YT

@misc{pith2026250616883,
  author       = {Pith},
  title        = {Pith review of: Low Overhead Allocation Sampling in a Garbage Collected Virtual Machine},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YGK422YT}},
  note         = {Machine review of arXiv:2506.16883}
}
read the original abstract

Compared to the more commonly used time-based profiling, allocation profiling provides an alternate view of the execution of allocation heavy dynamically typed languages. However, profiling every single allocation in a program is very inefficient. We present a sampling allocation profiler that is deeply integrated into the garbage collector of PyPy, a Python virtual machine. This integration ensures tunable low overhead for the allocation profiler, which we measure and quantify. Enabling allocation sampling profiling with a sampling period of 4 MB leads to a maximum time overhead of 25% in our benchmarks, over un-profiled regular execution.

Figures

Figures reproduced from arXiv: 2506.16883 by the authors.

Figure 1
Figure 1. Firefox Profiler Call Tree View showing VMProf data. The three Memory tracks 1 show different kinds of memory statistics. There are two tracks with stack samples, both allocation samples 2 and time-based samples 3 . The thin black vertical marks 4 above the allocation sample track are the points where minor collections happen, the wider rectangles are (incremental) major collections. In the lower half, the call-tree… view at source ↗
Figure 2
Figure 2. Nursery allocation, fast path taken larger than the nursery and is collected less frequently and incrementally, using a mark-and-sweep approach. 2.2 Bump-Pointer Allocation in the Nursery The nursery is a small continuous memory area (typically a few megabytes in size) that utilizes two pointers to keep track of the start and end of the free space available for allocation in it. They are called nursery_free and nurs… view at source ↗
Figure 4
Figure 4. Pseudo-code for allocation function of PyPy’s GC 1 def collect_and_reserve(size): 2 gc.minor_collection() 3 result = gc.nursery_free 4 gc.nursery_free += size 5 return result [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figures from the paper (11 more)
Figure 5
Figure 5. Figure 5: Pseudo-code for collect_and_reserve 2.4 VMProf VMProf8 is a statistical time-based profiler for PyPy. VMProf samples the call stack of the running Python code a user￾configured number of times per second. By adjusting this number, the overhead of profiling can be modif…
Figure 7
Figure 7. Figure 7: Nursery with Sample Points that allocation is an extremely common operation in PyPy and given that it is currently very fast, we wanted to avoid that. PyPy’s GC manages to achieve a peak allocation rate of about 11 GB/s on the benchmark machine (see Section 5.1). To im…
Figure 6
Figure 6. Figure 6: Pseudo-code for an inefficient way to implement allocation sampling stand out the most; functions with shorter run time less so. VMProf was developed by PyPy developers for profiling PyPy, as ‘normal’ CPython profilers don’t work well with PyPy, or have a lot of overhe…
Figure 9
Figure 9. Figure 9: Sample Point outside of Nursery Nursery Free full Nursery Limit & Sampling Point free Actual Nursery Moved left, by the amount of previously occupied memory [PITH_FULL_IMAGE:figures/full_fig_p005_9.png]
Figure 10
Figure 10. Figure 10: Sample Point moved left after Minor GC sample_point is outside the nursery and is therefore not used as nursery_limit. To track when the next sample should happen, we need to make sure our bytes_until_sample invariant from Sec￾tion 3.2 is maintained. Since a minor col…
Figure 12
Figure 12. Figure 12: Object with Header and Padding To be able to map type IDs of RPython types from numbers to something human-readable, we also dump a mapping of RPython type IDs to their respective names into the profile so that a UI tool like the vmprof-firefox-converter may use that …
Figure 13
Figure 13. Figure 13: Allocation Sampling Period vs. Overhead [PITH_FULL_IMAGE:figures/full_fig_p008_13.png]
Figure 14
Figure 14. Figure 14: Time Sampling Period vs. Overhead Additionally, the average sampling rate in samples per second, overhead, and the overhead normalized to 1000 sam￾ples per second, for 32KB allocation sampling are shown in [PITH_FULL_IMAGE:figures/full_fig_p008_14.png]
Figure 15
Figure 15. Figure 15: Benchmark Memory statistics without Sampling Name Samples/s Overhead Norm. Overhead microbenchmark 52658 3.51 1.05 gcbench 41081 3.88 1.07 pypy_translate_step 8987 1.97 1.11 interpreter_pystone 8483 1.99 1.12 [PITH_FULL_IMAGE:figures/full_fig_p009_15.png]
Figure 16
Figure 16. Figure 16: 32KB Allocation Sampling statistics [PITH_FULL_IMAGE:figures/full_fig_p009_16.png]
Figure 17
Figure 17. Figure 17: Firefox Profiler: Call Tree View We profiled some SymPy19 functions with allocation sam￾pling [PITH_FULL_IMAGE:figures/full_fig_p009_17.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 11 canonical work pages

  1. [1]

    Matsakis

    Davide Ancona, Massimo Ancona, Antonio Cuni, and Nicholas D. Matsakis. 2007. RPython: a step towards reconciling dynamically and statically typed OO languages. InProceedings of the 2007 Symposium on Dynamic Languages (Montreal, Quebec, Canada)(DLS ’07). Association for Computing Machinery, New York, NY, USA, 53–64. doi:10.1145/ 1297081.1297091

    arXiv 2007

  2. [2]

    backtrace labs. 2020. Poireau GitHub. https://github.com/backtrace- labs/poireau

    work page 2020

  3. [3]

    bloomberg. 2022. memray GitHub. https://github.com/bloomberg/ memray 24https://github.com/Cskorpion/microbenchmark 25https://github.com/pypy/pypy/blob/main/rpython/translator/goal/ gcbench.py

    work page 2022

  4. [4]

    Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Michael Leuschel, Samuele Pedroni, and Armin Rigo. 2011. Allocation re- moval by partial evaluation in a tracing JIT. In Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manip- ulation (Austin, Texas, USA)(PEPM ’11). Association for Computing Machinery, New York, NY, USA,...

    arXiv 2011

  5. [5]

    Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, and Armin Rigo. 2009. Tracing the meta-level: PyPy’s tracing JIT compiler. In Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems (Genova, Italy)(ICOOOLPS ’09). Association for Computing Machinery, New York, NY, USA, 18–...

    arXiv 2009

  6. [6]

    Carl Friedrich Bolz-Tereick, Luke Panayi, Ferdia McKeogh, Tom Spink, and Martin Berger. 2025. Pydrofoil: accelerating Sail-based instruction set simulators. arXiv:arXiv:2503.04389 To appear in ECOOP 2025

    work page Pith review arXiv 2025

  7. [7]

    Humphrey Burchell, Octave Larose, and Stefan Marr. 2024. Towards Realistic Results for Instrumentation-Based Profilers for JIT-Compiled Systems. In Proceedings of the 21st ACM SIGPLAN International Con- ference on Managed Programming Languages and Runtimes (Vienna, Austria) (MPLR 2024). Association for Computing Machinery, New York, NY, USA, 82–89. doi: 1...

    work page arXiv 2024

  8. [8]

    Timothy L. Harris. 2000. Dynamic adaptive pre-tenuring. In Pro- ceedings of the 2nd International Symposium on Memory Management (Minneapolis, Minnesota, USA)(ISMM ’00). Association for Computing Machinery, New York, NY, USA, 127–136. doi:10.1145/362422.362476

    work page arXiv 2000

Show all 17 references
  1. [9]

    Richard Jones, Antony Hosking, and Eliot Moss. 2023. The Garbage Collection Handbook: The Art of Automatic Memory Management (2nd edition ed.). Chapman & Hall/CRC, Boca Raton

    2023

  2. [10]

    Blackburn, and Kathryn S

    Maria Jump, Stephen M. Blackburn, and Kathryn S. McKinley. 2004. Dynamic object sampling for pretenuring. In Proceedings of the 4th International Symposium on Memory Management (Vancouver, BC, Canada) (ISMM ’04). Association for Computing Machinery, New York, NY, USA, 152–162....

    2004

  3. [11]

    MacIver and Alastair F

    David R. MacIver and Alastair F. Donaldson. 2020. Test-Case Reduction via Test-Case Generation: Insights from the Hypothesis Reducer. In 34th European Conference on Object-Oriented Programming (ECOOP

    2020

  4. [12]

    MacIver, Zac Hatfield-Dodds, and many other contributors

    David R. MacIver, Zac Hatfield-Dodds, and many other contributors

  5. [13]

    Armin Rigo and Samuele Pedroni. 2006. PyPy’s approach to virtual machine construction. In DLS. ACM, Portland, Oregon, USA. doi: 10. 1145/1176617.1176753

    2006

  6. [14]

    Itamar Turner-Trauring. 2024. Sciagraph homepage. https://www. sciagraph.com/docs/reference/limitations/

    2024

  7. [15]

    Paul R. Wilson. 1992. Uniprocessor Garbage Collection Techniques. In Proceedings of the International Workshop on Memory Management . Springer-Verlag, 1–42. http://portal.acm.org/citation.cfm?id=664824

    1992

  8. [2019]

    Hypothesis: A new approach to property-based testing. (Nov. 2019). doi:10.21105/joss.01891

    2019 doi

  9. [2020]

    166), Robert Hirschfeld and Tobias Pape (Eds.)

    (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 166), Robert Hirschfeld and Tobias Pape (Eds.). Schloss Dagstuhl – Leibniz- Zentrum für Informatik, Dagstuhl, Germany, 13:1–13:27. doi: 10.4230/ LIPIcs.ECOOP.2020.13

Pith tools

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