JDK-8352891 Performance improvements to ByteArrayOutputStream

[Engebretson, John]

  Thank you Archie and Chen!
  Chen - I’m prototyping the generic allocator you describe and it’s extremely effective for Objects – but I’m hamstrung by trying to use generics on primitive byte.  I’m not aware of a way to work around that, and changing the array from byte[] to Byte[] would be a terrible idea, so I think we’re looking at two different allocators.  The template suggested by Archie may help implement that, but ultimately it’ll be multiple classes.
  Archie – your suggestion generally matches the implementation on the PR, except that the implementation is flexible on the segment size and each instance “self-tunes” based on inputs.  There are a few hard-coded scaling constants that we could consider tweaking, but my perf tests so far show they’re reasonable in the general case.  Self-managing eliminates guesswork about N and, most importantly, eliminates duplicative copying/allocation after the byte has been recorded.  The benchmark tests a handful of hard-coded sizes and can easily be expanded to handle more, at the expense of longer runtimes.
  I’ll update the PR later today with these new suggestions alongside the current, so we can clearly evaluate pros and cons.
  Thanks!
     John

At the risk of repeating my previous comment<https://mail.openjdk.org/pipermail/core-libs-dev/2025-March/141871.html>, I agree with Chen.

That is to say, there is a separate, more fundamental unsolved problem lurking underneath this discussion, and the two problem "layers" are perhaps better addressed separately.

Once the lower layer problem is properly framed and resolved, it becomes reusable, and wrapping it to solve various higher-layer problems is easy.

An internal class would be a reasonable and conservative way to start. There could even be a suite of such classes, built from templates a la X-Buffer.java.template.

These could be used all over the place (e.g., refactor StringBuilder). For example, I wonder how much the performance of e.g. ArrayList could be improved in scenarios where you are building (or removing elements from) large lists?

Just thinking out loud (apologies)... Define a "segmented array allocator" as an in-memory byte[] array builder that "chunks" the data into individual segments of size at most N.

We can think of the current ByteArrayOutputStream as such a thing with N = 2³² that is, there's only ever one "chunk".

The assertion is that N = 2³² is not the most efficient value. And obviously neither is N = 1.

So somewhere in the middle there is an optimal value for N, which presumably could be discovered via experimentation. It may be different for different architectures.

Another parameter would be: What is the size M ≤ N of a new chunk? E.g. you could start with M = 16 and then the chunk grows exponentially until it reaches N, at which point you start a new chunk. The optimal value for M could also be performance tested (it may already have been).

Of course, for performance optimization we'd need some distribution of array sizes that models "typical" use, etc.

-Archie

On Wed, Apr 9, 2025 at 6:19 PM Chen Liang <liangchenblue at gmail.com<mailto:liangchenblue at gmail.com>> wrote:
Hi John Engebretson,
I still wonder if we can make the byte array allocator a utility to the JDK, at least an internal one. I find that besides replacing BAOS uses, it can also optimize users like InputStream.readNBytes, BufWriterImpl of classfile, and maybe many more usages. Such an internal addition may be accepted to the JDK immediately because it has no compatibility impact and does not need to undergo CSR review.

Chen Liang


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20250410/b05f6c72/attachment-0001.htm>