FastByteBuffer: tiered grow strategy to avoid O(n²) reallocation at the extremes

[num0001]

Summary

The current auto-resize policy in FastByteBuffer.ensureCapacity() causes excessive reallocations at both ends of the buffer-size spectrum. This issue proposes a tiered growth strategy, picking up the existing TODO at FastByteBuffer.java:182.

Current behaviour

// FastByteBuffer.java:183
final int addCapacity = Math.min(
        Math.max(DEFAULT_MIN_CAPACITY_INCREASE, newCapacity >> 3),
        DEFAULT_MAX_CAPACITY_INCREASE); // min 1 KiB, +12.5%, max 100 KiB

Effectively: addCapacity = clamp(newCapacity / 8, 1 KiB, 100 KiB).

Problems

1. Small buffers grow too slowly

Below ~8 KiB, newCapacity >> 3 is below the 1 KiB floor, so growth is fixed at +1 KiB regardless of buffer size. Growing from 1 KiB to 100 KiB takes ~99 reallocations + memcpys. ArrayList and StringBuilder both double in this regime to amortise allocation cost.

2. Large buffers grow too slowly

Above ~800 KiB, the +12.5% step gets clamped to the 100 KiB ceiling. A 10 MiB buffer that needs to roughly double requires ~100 reallocations — classic O(n²) cost on the hot serialisation path the README benchmarks rely on.

The midrange (~8 KiB – 800 KiB) at +12.5% works well and should be preserved.

Proposal

A three-tier policy matching the existing TODO comment ("increase fast for small arrays, +n% for medium, byte-by-byte for large"):

Regime	Range	Growth strategy	Rationale
Small	< 8 KiB	Double (addCapacity = newCapacity)	Avoid many tiny reallocations during ramp-up
Medium	8 KiB – 8 MiB	+12.5%, floored at 1 KiB	Unchanged from today; works well in practice
Large	≥ 8 MiB	Fixed slab (+1 MiB)	Avoid runaway memory waste on huge buffers

private static final int SMALL_THRESHOLD  = 1 << 13;   // 8 KiB
private static final int LARGE_THRESHOLD  = 1 << 23;   // 8 MiB
private static final int LARGE_ADD_CAPACITY = 1 << 20; // 1 MiB

final int addCapacity;
if (newCapacity < SMALL_THRESHOLD) {
    addCapacity = newCapacity; // double
} else if (newCapacity < LARGE_THRESHOLD) {
    addCapacity = Math.max(DEFAULT_MIN_CAPACITY_INCREASE, newCapacity >> 3); // +12.5%
} else {
    addCapacity = LARGE_ADD_CAPACITY; // fixed 1 MiB slab
}
forceCapacity(newCapacity + addCapacity, limit());

Expected impact

Scenario	Reallocations (current)	Reallocations (proposed)
1 KiB → 100 KiB	~99	~7
10 MiB → 20 MiB	~100	~10
64 KiB → 80 KiB (midrange)	2	2 (unchanged)

Memory overhead stays bounded: ≤ 1 MiB unused slab at large sizes, ≤ 2× allocation at small sizes (same as ArrayList).

Open questions for maintainers

1. Threshold values — are 8 KiB / 8 MiB acceptable defaults, or do you want them tuned to a known workload (e.g. typical MDP message sizes)?
2. Tunability — should the thresholds be exposed as constructor parameters / system properties, or hard-coded constants? I'd suggest keeping them private static final for now and revisiting only if a real use case needs override.
3. Large-tier policy — fixed 1 MiB slab vs. capped percentage? Fixed slab is simpler and bounds worst-case waste; percentage with a high cap (e.g. min(25%, 16 MiB)) would also work.

Proposed scope

• Modify ensureCapacity() in FastByteBuffer.java — ~15 LOC.
• Add tests covering each regime + data-preservation across grows in IoBufferTests.java. The existing testFastByteBufferResizing() uses Matchers.greaterThan and remains compatible.
• (Optional) JMH microbench measuring time-to-fill a 50 MiB buffer via 1 KiB writes, old vs. new.

No API change; IoBuffer.ensureCapacity() semantics are unchanged.

Happy to open a PR once thresholds are confirmed.

[RalphSteinhagen]

@num0001 really nice writeup and your timing is good (see below)

Thanks for picking up that TODO. Green light from me on a PR. 👍

I think the large-buffer case is the real win here: above ~800 KiB, the +100 KiB cap turns growth linear, which is the O(n²) cost worth killing. I feel the small end may be more modest than the table suggests -- +12.5% already kicks in above 8 KiB -- but doubling there is still a nice touch. Also, the boundaries align well with our own use-cases.

One quick thing to clarify: a flat +1 MiB large-tier slab is still additive, so a 100->200 MiB grow stays ~100 reallocs. I'd lean perhaps toward 'multiplicative but capped' (e.g. +50% capped at ~16 MiB) -- but curious what you think. The rest of your plan looks great; just please confirm testFastByteBufferResizing() still passes, since it leans on ByteArrayCache reuse.

N.B. Also — if you'd like to go deeper, the timing's good: we've got more comms/serialisation work and improvements coming on the Java side (GNU Radio 4 streaming, plus an OpenDigitizer discussion/improvements), and this buffer sits right underneath it. Happy to share where things are heading and the real message-size profiles that should drive these thresholds.

Either way, thanks for digging in!

[num0001]

Thanks for the quick read and the green light!

You're right on the small-tier point — once you cross 8 KiB the +12.5% already amortises well, so the 1 KiB → 100 KiB scenario in my table is the best case, not the typical one. Doubling under 8 KiB is more of a polish than a fix; I'll soften the framing in the PR description.

Good catch on the large-tier slab. A flat +1 MiB is still additive, so 100 → 200 MiB stays ~100 reallocs — exactly the thing we're trying to kill. I'll switch to your multiplicative-capped suggestion:

// Large tier
addCapacity = Math.min(newCapacity >> 1, LARGE_ADD_CAPACITY_MAX); // +50%, capped at 16 MiB

Revised impact:

| Scenario              | Current   | Proposed (+50% / 16 MiB cap) |
|-----------------------|-----------|------------------------------|
| 1 KiB → 100 KiB       | ~99       | ~7                           |
| 10 MiB → 20 MiB       | ~100      | ~2                           |
| 100 MiB → 200 MiB     | ~1000     | ~7                           |

Above ~32 MiB the cap starts to bite and growth becomes linear again, but with a 160× larger step than today (16 MiB vs. 100 KiB), so worst-case behaviour is bounded without runaway memory waste.

On the test: I'll verify testFastByteBufferResizing() end-to-end against the new policy locally before opening the PR — the ensureAdditionalCapacity(100) → capacity > 1124 assertion at the end leans on the ByteArrayCache returning a previously-grown array, which interacts non-trivially with the new growth steps. If the test needs an adjustment I'll flag it in the PR rather than silently tweaking the expected bound.

And yes — I'd very much like the deeper context. Real message-size profiles from GNU Radio 4 streaming / OpenDigitizer would be the right thing to drive the threshold constants, and I'd rather pick numbers that match the actual workload than guess from microbenches. Happy to take it to a discussion thread, gitter, or wherever suits you.

[RalphSteinhagen]

@num0001 Great! Looking forward to your PR.

If you are willing to share your use case, you could reach us at: https://matrix.to/#/#fair-acc_opencmw:gitter.im
Or PM me if you prefer.