JDK-8170977 : SparseArrayData should not grow its underlying dense array data
  • Type: Bug
  • Component: core-libs
  • Sub-Component: jdk.nashorn
  • Affected Version: 9
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2016-12-09
  • Updated: 2017-11-29
  • Resolved: 2016-12-22
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 8 JDK 9
8u152Fixed 9 b151Fixed
Description
A report on nashorn-dev shows that our current way of populating the underlying dense array when setting elements in a SparseArrayData instance can lead to huge performance problems:

http://mail.openjdk.java.net/pipermail/nashorn-dev/2016-December/006713.html

When running the code with the data provided later in the thread, the following line causes the function's execution speed to drop by more than 100 x:

     response[summoner.id] = summoner;

The reason is that summoner.id is a numeric id that is sometimes smaller than the current max length for dense arrays (1024 x 1024), causing allocation of large dense arrays when the index is set.

The solution seems to be to never grow the underlying dense array in a sparse array data, even if the index is considered suitable for dense arrays. Another solution would be only grow the dense array if the growth is sequential, i.e. we're setting the element at index underlying.length(). However, this leads to complications as we need to check existing elements in the sparse map for that index, so I think the first approach is the better and simpler solution.

An initial implementation of the first approach shows that performance increases more than 100 x for the test script, from ~ 130000 ms for 1000 concurrent iterations to less than 1000 ms.