JDK-8352891 Performance improvements to ByteArrayOutputStream

[Archie Cobbs]

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> 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
>
> On Wed, Apr 9, 2025 at 11:35 AM Engebretson, John <jengebr at amazon.com>
> wrote:
>
>> I think there is agreement that ByteArrayOutputStream.unsynchronized(int
>> cap) (or some such method) would be useful. It would not require using a
>> contiguous byte[] as the backing array so there is scope to experiment with
>> implementations that don't need to resize like the base BAOS does.
>>
>> Extending BOAS means the size is limited to an int. To go beyond would be
>> a different API and there is lots of scope to do experiments. I think too
>> early to create a CSR for MOS, assuming this is what you mean.
>>
>>   Thank you Alan!  PR [1] is updated with the factory method as
>> suggested; MOS is a package-private subclass of BAOS and the Javadoc in
>> BAOS makes no promises about the implementation returned.  I allowed MOS to
>> grow beyond 2GB and throw an intelligent error if it cannot service a
>> particular call (toByteArray, size, etc.).  Performance is unchanged.
>> Feedback appreciated.
>>
>>   Thanks!  😊
>>
>>      John
>>
>>
>>
>> [1] https://github.com/openjdk/jdk/pull/24232
>>
>>
>>
>

-- 
Archie L. Cobbs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20250409/a0ae4531/attachment.htm>