RFR: JDK-8318476: Add resource consumption note to BigInteger and BigDecimal

[Joseph D. Darcy]

Hi Hans,

Giving some additional context, we'll occasionally get bug reports that 
amount to an observation equivalent to the following:

"I have two Big{Foo} variables and in a loop I assign larger and larger 
values to them. As the values get large, bigFoo1.add(bigFoo2) runs much 
faster than bigFoo1.multiply(bigFoo2). This seems wrong."

With additional knowledge of the algorithmic complexities of add and 
multiply for large values, the above is not a surprising result and the 
intention of the note is to share some additional context with the 
reader so they are not surprised by this result either. Additionally, 
the note does describe what the JDK implementation has done for some 
time, switching between algorithms based in input size, etc.

The new text in both classes appears under an apiNote, which means the 
next text is informative without being normative. Therefore, the JDK is 
not obliged to behave in the described way, but is free to do so.

The current BigInteger implementation is not written to be hardened 
against timing side-channel measurements.

Thanks,

-Joe

On 10/23/2023 10:19 AM, Hans Boehm wrote:
> Since I think this is about asymptotic complexity, which is determined 
> by behavior on large inputs, is there a reason to talk about switching 
> to other algorithms on smaller inputs? We certainly don't want to get 
> into the habit of listing "easy case" optimizations everywhere.
>
> I'm unclear about the extent to which BigInteger is intended to 
> provide running times that depend only on the size of the inputs, or 
> whether they can vary with the actual bits in the input. Though hard 
> to state precisely, this does seem to matter to cryptographers. And it 
> sometimes seems to matter to others, since guarantees aimed at 
> cryptographers can slow down other code. Is it worth stating something 
> more in this area?
>
> On Sat, Oct 21, 2023 at 2:14 AM Alan Bateman <alanb at openjdk.org> wrote:
>
>     On Sat, 21 Oct 2023 00:56:21 GMT, Joe Darcy <darcy at openjdk.org> wrote:
>
>     > Add informative notes to BigInteger and BigDecimal about
>     possible running times, etc.
>
>     The wording looks okay to me and I expect it will appear as an API
>     note in BigInteger.
>
>     However, for BigDecimal I suspect the h2 headings (for the next
>     heading and the existing heading for IEEE 754 Decimal Arithmetic)
>     means they won't look like they are part of the API note, instead
>     they will look like new sections after the API note. Do you see
>     what I mean in the generated javadoc?
>
>     -------------
>
>     Marked as reviewed by alanb (Reviewer).
>
>     PR Review:
>     https://git.openjdk.org/jdk/pull/16298#pullrequestreview-1691219200
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20231023/6fee9c61/attachment-0001.htm>