On 4/11/25 6:19 PM, Archie Cobbs wrote:
Sorry if that wasn't clear - I didn't mean power-of-two exponential
growth, I meant all segments were literally fixed size, like 256 or
something (or maybe this value would be provided to the constructor).
This keeps the access to individual elements constant time.
You can have power-of-two exponentially growing segments and still
access individual elements by index in constant time (although you don't
need this if you are just doing the ByteArrayOutputStream implementation).
For example, let the array of segments:
byte[][] segments;
start with 0th segment of length 1 byte, then 2, 4, 8, 16, ...
To access the i-th byte you would do:
byte getByte(int i) {
int segmentIndex = 31 - Integer.numberOfLeadingZeros(i + 1);
int byteIndex = i + 1 - (1 << segmentIndex);
return segments[segmentIndex][byteIndex];
}
This can be adapted to situations where the 0th segment starts not with
1 byte length but with any 2^N length. For example, 8:
byte getByte(int i) {
int segmentIndex = 31 - Integer.numberOfTrailingZeros(8) -
Integer.numberOfLeadingZeros(i + 8);
int byteIndex = i + 8 - (8 << segmentIndex);
return segments[segmentIndex][byteIndex];
}
What I'm trying to say is that constant segment length might not be the
best choice if you consider the range of possible ByteArray (BAOS) final
lengths. If you choose too small, the number of segments will be too
large, so you end up with multiple resizing(s) of the array of segments
then - the problem you are trying to solve would still be there,
although divided by the segment size. If you choose to big, the up-front
allocation overhead for small ByteArray(s) (BAOSes) would be too large.
With power-of-two exponentially growing segments you get an allocation
overhead below 2x the needed final length and no redundant copying
(apart from final copy to the result if you need such result as byte[]).
Regards, Peter
