Re: RFR: 8231640: (prop) Canonical property storage [v13]
> The commit in this PR implements the proposal for enhancement that was > discussed in the core-libs-dev mailing list recently[1], for > https://bugs.openjdk.java.net/browse/JDK-8231640 > > At a high level - the `store()` APIs in `Properties` have been modified to > now look for the `SOURCE_DATE_EPOCH` environment variable[2]. If that env > variable is set, then instead of writing out the current date time as a date > comment, the `store()` APIs instead will use the value set for this env > variable to parse it to a `Date` and write out the string form of such a > date. The implementation here uses the `d MMM HH:mm:ss 'GMT'` date > format and `Locale.ROOT` to format and write out such a date. This should > provide reproducibility whenever the `SOURCE_DATE_EPOCH` is set. Furthermore, > intentionally, no changes in the date format of the "current date" have been > done. > > These modified `store()` APIs work in the presence of the `SecurityManager` > too. The caller is expected to have a read permission on the > `SOURCE_DATE_EPOCH` environment variable. If the caller doesn't have that > permission, then the implementation of these `store()` APIs will write out > the "current date" and will ignore any value that has been set for the > `SOURCE_DATE_EPOCH` env variable. This should allow for backward > compatibility of existing applications, where, when they run under a > `SecurityManager` and perhaps with an existing restrictive policy file, the > presence of `SOURCE_DATE_EPOCH` shouldn't impact their calls to the `store()` > APIs. > > The modified `store()` APIs will also ignore any value for > `SOURCE_DATE_EPOCH` that cannot be parsed to an `long` value. In such cases, > the `store()` APIs will write out the "current date" and ignore the value set > for this environment variable. No exceptions will be thrown for such invalid > values. This is an additional backward compatibility precaution to prevent > any rogue value for `SOURCE_DATE_EPOCH` from breaking applications. > > An additional change in the implementation of these `store()` APIs and > unrelated to the date comment, is that these APIs will now write out the > property keys in a deterministic order. The keys will be written out in the > natural ordering as specified by `java.lang.String#compareTo()` API. > > The combination of the ordering of the property keys when written out and the > usage of `SOURCE_DATE_EPOCH` environment value to determine the date comment > should together allow for reproducibility of the output generated by these > `store()` APIs. > > New jtreg test classes have been introduced to verify these changes. The > primary focus of `PropertiesStoreTest` is the ordering aspects of the > property keys that are written out. On the other hand > `StoreReproducibilityTest` focuses on the reproducibility of the output > generated by these APIs. The `StoreReproducibilityTest` runs these tests > both in the presence and absence of `SecurityManager`. Plus, in the presence > of SecurityManager, it tests both the scenarios where the caller is granted > the requisite permission and in other case not granted that permission. > > These new tests and existing tests under `test/jdk/java/util/Properties/` > pass with these changes. > > [1] > https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-August/080758.html > [2] https://reproducible-builds.org/specs/source-date-epoch/ Jaikiran Pai has updated the pull request incrementally with one additional commit since the last revision: unused imports - Changes: - all: https://git.openjdk.java.net/jdk/pull/5372/files - new: https://git.openjdk.java.net/jdk/pull/5372/files/6447f9bb..92374664 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=5372=12 - incr: https://webrevs.openjdk.java.net/?repo=jdk=5372=11-12 Stats: 5 lines in 1 file changed: 0 ins; 5 del; 0 mod Patch: https://git.openjdk.java.net/jdk/pull/5372.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5372/head:pull/5372 PR: https://git.openjdk.java.net/jdk/pull/5372
Re: RFR: 8231640: (prop) Canonical property storage [v10]
Hello Roger,
I've now updated the PR to implement these suggested changes. I think at
this point all suggestions have been implemented and I don't think there
are any open questions.
If the latest PR looks fine, I think the next step will be a CSR creation.
-Jaikiran
On 13/09/21 7:13 pm, Roger Riggs wrote:
Hi Jaikiran,
"Editing" the value of the comment property, to remove or ignore
blanks for other special
characters makes the code more complex and adds a bunch of conditions.
Dropping
the comment if it doesn't have the allowed format is hard to track
down, because there's
no way to report it was dropped or why.
I would write the value of the comment property using the
writeComments method
so it is encoded the same as the other comment passed as an store
argument.
That will handle all special characters and multi-line comments. It is
simpler to specify
and has the same predictable output as other comments.
if the property is non-empty
On 9/12/21 10:29 AM, Jaikiran Pai wrote:
...
This was discussed elsewhere, but after writing that, I'm now
thinking that we **should** honor the property even if it is blank.
It would be useful to disable the timestamp simply by setting the
property to the empty string; this will simply result in an empty
comment line. This would simplify the code (and the spec) by
removing conditions related to String::isBlank.
OK. I don't see any obvious issues with interpreting
empty/whitespace-only value for the system property to translate to
an empty comment line. To be clear, an empty comment line that gets
written out in such cases is *always* going to be the "#" character
followed by a line separator right? Irrespective of what or how many
whitespace characters are present in the property value? Or do you
want those characters to be carried over into that comment line that
gets written out? The reason I ask this is because I think we should
always write just the "#" followed by the line separator character in
such cases, which effectively means we will still need the
String::isBlank check which would then look something like:
if (propVal.isBlank()) {
bw.write("#");
bw.newLine();
}
Side question: do we want to do any escaping or vetting of the
property value?
One of the reasons why we didn't want to use the date in epoch
seconds or a formatted date string was to avoid the complexities that
come with managing that property value. So a free-form property value
seemed more appropriate and I think a free-form value still seems
appropriate, but I think we should keep any vetting to minimal. More
details below.
If for example it contains embedded newlines, this could result in a
malformed property file. Or, if carefully constructed, it could
contain additional property values. I think this is an unintended
consequence of changing the property value from a numeric time value
to a free-form string. We may want to reconsider this.
The specification on the load(Reader reader) method of the
java.util.Properties class has this to say about comment lines (and
lines in general).
(snipped relevant content):
There are two kinds of line, natural lines and logical
lines.
A natural line is defined as a line of characters that is terminated
either
by a set of line terminator characters ({@code \n} or {@code \r} or
{@code \r\n}) or by the end of the stream. A natural line may be
either a blank line, a comment line, or hold all or some of a
key-element pair. A logical
line holds all the data of a key-element pair, which may be spread
out across several adjacent natural lines by escaping
the line terminator sequence with a backslash character
{@code \}. Note that a comment line cannot be extended
in this manner; every natural line that is a comment must have
its own comment indicator, as described below.
With that knowledge about comment lines, I think what we should do is
disallow system property values that contain any form of line
terminator characters (\n or \r or \r\n). If the system property
value is _not_ blank (as specified by String::isBlank) and contains
any of these line terminator characters, we should simply ignore it
and write out the current date as the date comment. That, IMO, should
prevent any of these sneaky/rogue value that can end up either
creating additional property key/values to be written out or causing
any malformed properties file. Plus, that would help us keep the
vetting to minimal without involving too much complexity.
src/java.base/share/classes/java/util/Properties.java line 855:
853: * the value of this system property represents a formatted
854: * date time value that can be parsed back into a {@link
Date} using an appropriate
855: * {@link DateTimeFormatter}
With the property behavior added to normative text above, I don't
think we need this note anymore. We might want to leave something
here about the convention of putting a
Re: RFR: 8231640: (prop) Canonical property storage [v12]
> The commit in this PR implements the proposal for enhancement that was > discussed in the core-libs-dev mailing list recently[1], for > https://bugs.openjdk.java.net/browse/JDK-8231640 > > At a high level - the `store()` APIs in `Properties` have been modified to > now look for the `SOURCE_DATE_EPOCH` environment variable[2]. If that env > variable is set, then instead of writing out the current date time as a date > comment, the `store()` APIs instead will use the value set for this env > variable to parse it to a `Date` and write out the string form of such a > date. The implementation here uses the `d MMM HH:mm:ss 'GMT'` date > format and `Locale.ROOT` to format and write out such a date. This should > provide reproducibility whenever the `SOURCE_DATE_EPOCH` is set. Furthermore, > intentionally, no changes in the date format of the "current date" have been > done. > > These modified `store()` APIs work in the presence of the `SecurityManager` > too. The caller is expected to have a read permission on the > `SOURCE_DATE_EPOCH` environment variable. If the caller doesn't have that > permission, then the implementation of these `store()` APIs will write out > the "current date" and will ignore any value that has been set for the > `SOURCE_DATE_EPOCH` env variable. This should allow for backward > compatibility of existing applications, where, when they run under a > `SecurityManager` and perhaps with an existing restrictive policy file, the > presence of `SOURCE_DATE_EPOCH` shouldn't impact their calls to the `store()` > APIs. > > The modified `store()` APIs will also ignore any value for > `SOURCE_DATE_EPOCH` that cannot be parsed to an `long` value. In such cases, > the `store()` APIs will write out the "current date" and ignore the value set > for this environment variable. No exceptions will be thrown for such invalid > values. This is an additional backward compatibility precaution to prevent > any rogue value for `SOURCE_DATE_EPOCH` from breaking applications. > > An additional change in the implementation of these `store()` APIs and > unrelated to the date comment, is that these APIs will now write out the > property keys in a deterministic order. The keys will be written out in the > natural ordering as specified by `java.lang.String#compareTo()` API. > > The combination of the ordering of the property keys when written out and the > usage of `SOURCE_DATE_EPOCH` environment value to determine the date comment > should together allow for reproducibility of the output generated by these > `store()` APIs. > > New jtreg test classes have been introduced to verify these changes. The > primary focus of `PropertiesStoreTest` is the ordering aspects of the > property keys that are written out. On the other hand > `StoreReproducibilityTest` focuses on the reproducibility of the output > generated by these APIs. The `StoreReproducibilityTest` runs these tests > both in the presence and absence of `SecurityManager`. Plus, in the presence > of SecurityManager, it tests both the scenarios where the caller is granted > the requisite permission and in other case not granted that permission. > > These new tests and existing tests under `test/jdk/java/util/Properties/` > pass with these changes. > > [1] > https://mail.openjdk.java.net/pipermail/core-libs-dev/2021-August/080758.html > [2] https://reproducible-builds.org/specs/source-date-epoch/ Jaikiran Pai has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 16 additional commits since the last revision: - Merge latest from master branch - Implement Roger's and the agreed upon decision to allow free-form text for the system property. Plus updates to test to match the expectations - Update javadoc based on Stuart's inputs - allow free-form text for java.util.Properties.storeDate system property - jcheck fix - trailing whitespace in test - Implement Roger's suggestions: - Rely on java.util.Properties.storeDate system property instead of SOURCE_DATE_EPOCH environment variable - No need for caching the parsed date - Update the javadoc to match new expectations - Update tests to match the new expectations - dummy commit to trigger GitHub actions job to try and reproduce an unexplained failure with the new tests that happened around 24 hours back, this time yesterday (rule out any time/date/timezone specific issues) - update javadoc to match latest changes - Implement Stuart's suggestion to use Collections instead of Arrays for ordering property keys - update the new tests to match the new date format expectations and also print out some log messages for better debuggability of the tests - ... and 6 more: https://git.openjdk.java.net/jdk/compare/dae096b0...6447f9bb - Changes: - all:
Re: RFR: 8258117: jar tool sets the time stamp of module-info.class entries to the current time
Hello Bernd, On 14/09/21 6:10 am, Bernd Eckenfels wrote: Is there support for repeatable builds planned? Using the source file might be acceptable, but the class file timestamp could be changing more likely for repeated builds? To clarify the description of my PR, this change uses the timestamp of the (compiled) module-info.class file that is being added/updated to the jar. -Jaikiran
Integrated: 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice
On Tue, 14 Sep 2021 00:15:31 GMT, David Holmes wrote: > Please review this trivial fix to add the missing comma. > > Thanks, > David This pull request has now been integrated. Changeset: c54a918a Author:David Holmes URL: https://git.openjdk.java.net/jdk/commit/c54a918a0e526403a395ad76c1dd0519be136ac7 Stats: 1 line in 1 file changed: 0 ins; 0 del; 1 mod 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice Reviewed-by: psandoz - PR: https://git.openjdk.java.net/jdk/pull/5504
Re: RFR: 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice
On Tue, 14 Sep 2021 00:15:31 GMT, David Holmes wrote: > Please review this trivial fix to add the missing comma. > > Thanks, > David Thanks Paul and Ian! - PR: https://git.openjdk.java.net/jdk/pull/5504
Re: RFR: 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice
On Tue, 14 Sep 2021 00:15:31 GMT, David Holmes wrote: > Please review this trivial fix to add the missing comma. > > Thanks, > David LGTM. Thanks @dholmes-ora - PR: https://git.openjdk.java.net/jdk/pull/5504
Re: RFR: 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice
On Tue, 14 Sep 2021 00:15:31 GMT, David Holmes wrote: > Please review this trivial fix to add the missing comma. > > Thanks, > David Marked as reviewed by psandoz (Reviewer). - PR: https://git.openjdk.java.net/jdk/pull/5504
RFR: 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice
Please review this trivial fix to add the missing comma. Thanks, David - Commit messages: - 8273691: Missing comma after 2021 in GraphemeTestAccessor.java copyright notice Changes: https://git.openjdk.java.net/jdk/pull/5504/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5504=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8273691 Stats: 1 line in 1 file changed: 0 ins; 0 del; 1 mod Patch: https://git.openjdk.java.net/jdk/pull/5504.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5504/head:pull/5504 PR: https://git.openjdk.java.net/jdk/pull/5504
Re: RFR: 8258117: jar tool sets the time stamp of module-info.class entries to the current time
Is there support for repeatable builds planned? Using the source file might be acceptable, but the class file timestamp could be changing more likely for repeated builds? -- http://bernd.eckenfels.net Von: core-libs-dev im Auftrag von Jaikiran Pai Gesendet: Monday, September 13, 2021 7:44:22 AM An: compiler-...@openjdk.java.net ; core-libs-dev@openjdk.java.net Betreff: RFR: 8258117: jar tool sets the time stamp of module-info.class entries to the current time The commit here is a potential fix for the issue noted in https://bugs.openjdk.java.net/browse/JDK-8258117. The change here repurposes an existing internal interface `ModuleInfoEntry` to keep track of the last modified timestamp of a `module-info.class` descriptor. This commit uses the timestamp of the `module-info.class` on the filesystem to set the time on the `JarEntry`. There are a couple of cases to consider here: 1. When creating a jar (using `--create`), we use the source `module-info.class` from the filesystem and then add extended info to it (attributes like packages, module version etc...). In such cases, this patch will use the lastmodified timestamp from the filesystem of `module-info.class` even though we might end up updating/extending/modifying (for example by adding a module version) its content while storing it as a `JarEntry`. 2. When updating a jar (using `--update`), this patch will use the lastmodified timestamp of `module-info.class` either from the filesystem or from the source jar's entry (depending on whether a new `module-info.class` is being passed to the command). Here too, it's possible that we might end up changing/modifying/extending the `module-info.class` (for example, changing the module version to a new version) that gets written into the updated jar file, but this patch _won't_ use `System.currentTimeMillis()` even in such cases. If we do have to track actual changes that might happen to `module-info.class` while extending its info (in `extendedInfoBytes()`) and then decide whether to use current system time as last modified time, then this will require a bigger change and also a discussion on what kind of extending of module-info.class content will require a change to the lastmodifiedtime of that entry. - Commit messages: - 8258117: jar tool sets the time stamp of module-info.class entries to the current time Changes: https://git.openjdk.java.net/jdk/pull/5486/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5486=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8258117 Stats: 317 lines in 2 files changed: 298 ins; 0 del; 19 mod Patch: https://git.openjdk.java.net/jdk/pull/5486.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5486/head:pull/5486 PR: https://git.openjdk.java.net/jdk/pull/5486
Integrated: 8273430: Suspicious duplicate condition in java.util.regex.Grapheme#isExcludedSpacingMark
On Wed, 8 Sep 2021 20:24:31 GMT, Ian Graves wrote: > The duplicate condition in this chain of expressions needs to be shrunk to > drop a couple of character that are not excluded spacing marks. This pull request has now been integrated. Changeset: 3d9dc8f8 Author:Ian Graves URL: https://git.openjdk.java.net/jdk/commit/3d9dc8f824abf597d9b28f456cfeb5af927221b8 Stats: 539 lines in 4 files changed: 147 ins; 388 del; 4 mod 8273430: Suspicious duplicate condition in java.util.regex.Grapheme#isExcludedSpacingMark Reviewed-by: naoto - PR: https://git.openjdk.java.net/jdk/pull/5425
Re: RFR: 8273681: Add Vector API vs Arrays.mismatch intrinsic benchmark
On Fri, 10 Sep 2021 08:32:02 GMT, Kartik Ohri wrote: > Hi all! > > Please review this PR to add a benchmark comparing the performance of > Arrays.mismatch intrinsic in the JDK with that of the Vector API. Kindly > refer to this [thread] on panama-dev regarding some initial discussion about > this benchmark. I have attached the [results] of the full benchmark run along > with the [assembly] output of a shorter run I had done while analysing the > results. The benchmarks were run against the latest build of panama-vector > available from builds.shipilev.net. > > Also, I have not added the copyright header to this file yet as I am an > individual contributor (OCA signed) and do not know what to put there. > > [thread]: > https://mail.openjdk.java.net/pipermail/panama-dev/2021-September/014839.html > [results]: https://github.com/openjdk/jdk/files/7142452/results.csv > [assembly]: https://github.com/openjdk/jdk/files/7142362/benchmarks.txt > > Regards, > Kartik Benchmark looks good (assuming license is added). test/micro/org/openjdk/bench/jdk/incubator/vector/ArrayMismatchBenchmark.java line 52: > 50: static final VectorSpecies LONG_SPECIES_PREFERRED = > LongVector.SPECIES_PREFERRED; > 51: > 52: static final Random random = new Random(); We could use the recently added `RandomGenerator` instead in the spirit of encouraging the use of new and preferred APIs: - remove the static field - replace `FLOAT_SPECIES` with `DOUBLE_SPECIES` - in `setup` create an instance `RandomGenerator rg = RandomGenerator.getDefault()` - remove `createRandomFloats` and use `rg.doubles(...).toArray()` - PR: https://git.openjdk.java.net/jdk/pull/5459
Re: RFR: 8273681: Add Vector API vs Arrays.mismatch intrinsic benchmark
On Fri, 10 Sep 2021 08:32:02 GMT, Kartik Ohri wrote: > Hi all! > > Please review this PR to add a benchmark comparing the performance of > Arrays.mismatch intrinsic in the JDK with that of the Vector API. Kindly > refer to this [thread] on panama-dev regarding some initial discussion about > this benchmark. I have attached the [results] of the full benchmark run along > with the [assembly] output of a shorter run I had done while analysing the > results. The benchmarks were run against the latest build of panama-vector > available from builds.shipilev.net. > > Also, I have not added the copyright header to this file yet as I am an > individual contributor (OCA signed) and do not know what to put there. > > [thread]: > https://mail.openjdk.java.net/pipermail/panama-dev/2021-September/014839.html > [results]: https://github.com/openjdk/jdk/files/7142452/results.csv > [assembly]: https://github.com/openjdk/jdk/files/7142362/benchmarks.txt > > Regards, > Kartik The simplest approach is to copy the license from here https://github.com/openjdk/jdk/blob/master/test/micro/org/openjdk/bench/jdk/incubator/vector/RotateBenchmark.java - PR: https://git.openjdk.java.net/jdk/pull/5459
Re: RFR: 8272515: JFR: Names should only be valid Java identifiers
On Wed, 8 Sep 2021 13:00:17 GMT, Erik Gahlin wrote:
> Hi,
>
> Could I have a review of change that prevents invalid Java identifiers or
> type names in JFR events. For rationale and compatibility issues see the CSR
> request. The only change to java.base is making
> jdk.modules.internal.Checks::isJavaIdentifier(String) public, so it can be
> reused by the jdk.jfr module.
>
> Testing: /jdk/jdk/jfr + tier1 + tier2
>
> Thanks
> Erik
src/java.base/share/classes/jdk/internal/module/Checks.java line 171:
> 169: * otherwise false.
> 170: */
> 171: public static boolean isJavaIdentifier(String str) {
I see Checks is already used by code in the jdk.jlink and jdk.jartool module so
probably okay if JFR uses it. At some point we need to get back to trimming
back the qualified exports to avoid too much back sliding into a ball of mud.
-
PR: https://git.openjdk.java.net/jdk/pull/5415
RFR: 8273681: Add Vector API vs Arrays.mismatch intrinsic benchmark
Hi all! Please review this PR to add a benchmark comparing the performance of Arrays.mismatch intrinsic in the JDK with that of the Vector API. Kindly refer to this [thread] on panama-dev regarding some initial discussion about this benchmark. I have attached the [results] of the full benchmark run along with the [assembly] output of a shorter run I had done while analysing the results. The benchmarks were run against the latest build of panama-vector available from builds.shipilev.net. Also, I have not added the copyright header to this file yet as I am an individual contributor (OCA signed) and do not know what to put there. [thread]: https://mail.openjdk.java.net/pipermail/panama-dev/2021-September/014839.html [results]: https://github.com/openjdk/jdk/files/7142452/results.csv [assembly]: https://github.com/openjdk/jdk/files/7142362/benchmarks.txt Regards, Kartik - Commit messages: - Add Vector API vs Arrays.mismatch intrinsic benchmark Changes: https://git.openjdk.java.net/jdk/pull/5459/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5459=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8273681 Stats: 213 lines in 1 file changed: 213 ins; 0 del; 0 mod Patch: https://git.openjdk.java.net/jdk/pull/5459.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5459/head:pull/5459 PR: https://git.openjdk.java.net/jdk/pull/5459
Integrated: 8273513: Make java.io.FilterInputStream specification more precise about overrides
On Wed, 8 Sep 2021 22:00:53 GMT, Brian Burkhalter wrote: > Modify the class level specification of `java.io.FilterInputStream` to be > more exact about `java.io.InputStream` methods that it overrides. This pull request has now been integrated. Changeset: 6cf5079d Author:Brian Burkhalter URL: https://git.openjdk.java.net/jdk/commit/6cf5079d8e789c82646a3e16b1763e2c7646d400 Stats: 54 lines in 1 file changed: 21 ins; 9 del; 24 mod 8273513: Make java.io.FilterInputStream specification more precise about overrides Reviewed-by: dfuchs, naoto - PR: https://git.openjdk.java.net/jdk/pull/5426
Integrated: 8273616: Fix trivial doc typos in the java.base module
On Fri, 10 Sep 2021 21:16:19 GMT, Pavel Rappo wrote: > 8273616: Fix trivial doc typos in the java.base module This pull request has now been integrated. Changeset: b4b12101 Author:Pavel Rappo URL: https://git.openjdk.java.net/jdk/commit/b4b121018d16e531f3a51ff75ae37fdc374d530b Stats: 55 lines in 34 files changed: 0 ins; 0 del; 55 mod 8273616: Fix trivial doc typos in the java.base module Reviewed-by: jrose, iris, lancea, dfuchs, rriggs - PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 17:50:11 GMT, Piotr Tarsa wrote: >> I made a JMH test on jdk16 to test count4 (xor) performance: >> https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor >> >> >> Benchmark (size) Mode Cnt Score Error Units >> ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 >> ns/op >> ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 >> ns/op >> ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op >> ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op >> >> Masked xor does not get optimized by c2 too. >> >> Using Unsafe is better, see: >> https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java >> >> If you want, I could make another radixsort() using on or off heap count >> buffers and Unsafe, as I did in Marlin to avoid bound checks... > > I think an uncontroversial and efficient solution would be to replace > > count4[(a[i] >>> 24) ^ 0x80]--; > > with > > count4[(a[i] >>> 24) & 0xFF]--; > > and after finishing counting, first half of `count4` should be swapped with > second half of `count4`. FYI I made another radixsortNew() using Unsafe to access to all count arrays: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/dbfbd731ffd798defc75528cc1db04063bdb4619/src/edu/sorting/DualPivotQuicksort202105.java#L795 But it is only 2% faster in radix-sort-benchmark (1M arrays): https://github.com/bourgesl/radix-sort-benchmark/blob/main/results/2021-ref/cmp-16-1M-full.log It looks not worth the extra complexity for few percents, I think. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 20 May 2021 08:03:03 GMT, Nils Eliasson wrote: >> I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: >> using Unsafe is only 2% faster, not worth the extra complexity for few >> percent. > > A small update of the XorINodes type calculation makes the bound check go > away. Testing now. That bounds check shouldn't be there, it's an obvious case and will be fixed: https://github.com/openjdk/jdk/pull/4136 - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 18 May 2021 19:58:35 GMT, iaroslavski wrote: >> https://bugs.openjdk.java.net/browse/JDK-8267332 > > I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: > using Unsafe is only 2% faster, not worth the extra complexity for few > percent. A small update of the XorINodes type calculation makes the bound check go away. Testing now. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 18 May 2021 18:06:21 GMT, Nils Eliasson wrote: >> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: >> >>> 670: count2[(a[i] >>> 8) & 0xFF]--; >>> 671: count3[(a[i] >>> 16) & 0xFF]--; >>> 672: count4[(a[i] >>> 24) ^ 0x80]--; >> >> It seems that C2 can't eliminate the bounds check here because of the `xor`, >> even though this can't possibly exceed 256. The three masked accesses above >> are all eliminated. Maybe someone could look in to improving that. > > https://bugs.openjdk.java.net/browse/JDK-8267332 I agree with Laurent (bourgesl), see his comment on May 15 regarding to xor: using Unsafe is only 2% faster, not worth the extra complexity for few percent. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > Sorting: > > - adopt radix sort for sequential and parallel sorts on int/long/float/double > arrays (almost random and length > 6K) > - fix tryMergeRuns() to better handle case when the last run is a single > element > - minor javadoc and comment changes > > Testing: > - add new data inputs in tests for sorting > - add min/max/infinity values to float/double testing > - add tests for radix sort src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: > 670: count2[(a[i] >>> 8) & 0xFF]--; > 671: count3[(a[i] >>> 16) & 0xFF]--; > 672: count4[(a[i] >>> 24) ^ 0x80]--; It seems that C2 can't eliminate the bounds check here because of the `xor`, even though this can't possibly exceed 256. The three masked accesses above are all eliminated. Maybe someone could look in to improving that. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 20 May 2021 21:21:26 GMT, Nils Eliasson wrote: >> A small update of the XorINodes type calculation makes the bound check go >> away. Testing now. > > That bounds check shouldn't be there, it's an obvious case and will be fixed: > https://github.com/openjdk/jdk/pull/4136 Thanks for fixing hotspot C2 (xor) so quickly ! - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Tue, 11 May 2021 14:37:21 GMT, Jörn Horstmann
wrote:
>> Sorting:
>>
>> - adopt radix sort for sequential and parallel sorts on
>> int/long/float/double arrays (almost random and length > 6K)
>> - fix tryMergeRuns() to better handle case when the last run is a single
>> element
>> - minor javadoc and comment changes
>>
>> Testing:
>> - add new data inputs in tests for sorting
>> - add min/max/infinity values to float/double testing
>> - add tests for radix sort
>
> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 669:
>
>> 667:
>> 668: for (int i = low; i < high; ++i) {
>> 669: count1[ a[i] & 0xFF]--;
>
> Not a reviewer, but having recently implemented a radixsort myself I'm
> wondering what is the logic or benefit of decrementing and counting backwards
> here?
>
> One thing I did differently, and I'm not fully sure is an optimization, is
> remembering the last bucket for each of the 4 counts. Checking whether the
> data is already sorted by that digit can then be done by checking
> `count[last_bucket] == size`, which avoids the first loop in `passLevel`.
> Again, not sure whether it is actually faster, maybe the two separate simple
> loops like here are better.
@jhorstmann In counting backwards we perform comparing with 0 in a loop,
Comparing with 0 may be faster than comparing with other value. In general,
backward or forward moving is your favor.
Keeping last_bucket and use check count[last_bucket] == size sounds good, but
we need to run benchmarking and compare. I think we will not see big difference
because the size of count array is too small, 256 only, whereas we scan whole
array with size at least 6K. The corner case when we can see max effect of
using last_bucket is array with all equal elements (4 count arrays will have
only one non-zero element). but such array will be caught by tryMerge method.
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 13:18:27 GMT, Laurent Bourgès wrote: >> I don't know Laurent, I find the handling of signed order over-complicated. >> Subtracting `Integer.MIN_VALUE` is really cheap... > > I made a JMH test on jdk16 to test count4 (xor) performance: > https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor > > > Benchmark (size) Mode Cnt Score Error Units > ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 ns/op > ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 ns/op > ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op > ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op > > Masked xor does not get optimized by c2 too. > > Using Unsafe is better, see: > https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java > > If you want, I could make another radixsort() using on or off heap count > buffers and Unsafe, as I did in Marlin to avoid bound checks... I think an uncontroversial and efficient solution would be to replace count4[(a[i] >>> 24) ^ 0x80]--; with count4[(a[i] >>> 24) & 0xFF]--; and after finishing counting, first half of `count4` should be swapped with second half of `count4`. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 20:47:48 GMT, Richard Startin wrote: >> Sorting: >> >> - adopt radix sort for sequential and parallel sorts on >> int/long/float/double arrays (almost random and length > 6K) >> - fix tryMergeRuns() to better handle case when the last run is a single >> element >> - minor javadoc and comment changes >> >> Testing: >> - add new data inputs in tests for sorting >> - add min/max/infinity values to float/double testing >> - add tests for radix sort > > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672: > >> 670: count2[(a[i] >>> 8) & 0xFF]--; >> 671: count3[(a[i] >>> 16) & 0xFF]--; >> 672: count4[(a[i] >>> 24) ^ 0x80]--; > > It seems that C2 can't eliminate the bounds check here because of the `xor`, > even though this can't possibly exceed 256. The three masked accesses above > are all eliminated. Maybe someone could look in to improving that. https://bugs.openjdk.java.net/browse/JDK-8267332 - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski
wrote:
> Sorting:
>
> - adopt radix sort for sequential and parallel sorts on int/long/float/double
> arrays (almost random and length > 6K)
> - fix tryMergeRuns() to better handle case when the last run is a single
> element
> - minor javadoc and comment changes
>
> Testing:
> - add new data inputs in tests for sorting
> - add min/max/infinity values to float/double testing
> - add tests for radix sort
src/java.base/share/classes/java/util/DualPivotQuicksort.java line 669:
> 667:
> 668: for (int i = low; i < high; ++i) {
> 669: count1[ a[i] & 0xFF]--;
Not a reviewer, but having recently implemented a radixsort myself I'm
wondering what is the logic or benefit of decrementing and counting backwards
here?
One thing I did differently, and I'm not fully sure is an optimization, is
remembering the last bucket for each of the 4 counts. Checking whether the data
is already sorted by that digit can then be done by checking
`count[last_bucket] == size`, which avoids the first loop in `passLevel`.
Again, not sure whether it is actually faster, maybe the two separate simple
loops like here are better.
-
PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 07:41:19 GMT, Richard Startin wrote: >> Great analysis on C2, richard. >> >> maybe (x ^ 0x80) &0xFF would help C2 to eliminate bound checks... > > I don't know Laurent, I find the handling of signed order over-complicated. > Subtracting `Integer.MIN_VALUE` is really cheap... I made a JMH test on jdk16 to test count4 (xor) performance: https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor Benchmark (size) Mode Cnt Score Error Units ArrayXorBenchmark.arrayAndOriginal 100 avgt 20 684561,951 ± 2177,120 ns/op ArrayXorBenchmark.arrayXorOriginal 100 avgt 20 777255,465 ± 1815,136 ns/op ArrayXorBenchmark.arrayXor_Masked 100 avgt 20 814163,377 ± 2665,436 ns/op ArrayXorBenchmark.arrayXor_Unsafe 100 avgt 20 707273,922 ± 2994,380 ns/op Masked xor does not get optimized by c2 too. Using Unsafe is better, see: https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java If you want, I could make another radixsort() using on or off heap count buffers and Unsafe, as I did in Marlin to avoid bound checks... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 09:53:37 GMT, Richard Startin
wrote:
>> Laurent, the date in this class is not the date of our last commit,
>> this date is the date when I have final idea regarding to Radix sort,
>> therefore, I prefer to keep 2020.06.14
>
> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I
> believe this work derives from an unsigned radix sort I implemented on
> 10/04/2021
> https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
> which has numerous structural similarities to this work:
> * Producing all four histograms in one pass
> * Skipping passes based on detecting the total in the histogram
> * Bailing out of the skip detection if a nonzero value not equal to the total
> is encountered
> * Manually unrolling the LSD radix sort loop in order to avoid array copies
>
> My implementation from 10th April is below for reference:
>
> public static void unrollOnePassHistogramsSkipLevels(int[] data) {
> int[] histogram1 = new int[257];
> int[] histogram2 = new int[257];
> int[] histogram3 = new int[257];
> int[] histogram4 = new int[257];
>
> for (int value : data) {
> ++histogram1[(value & 0xFF) + 1];
> ++histogram2[((value >>> 8) & 0xFF) + 1];
> ++histogram3[((value >>> 16) & 0xFF) + 1];
> ++histogram4[(value >>> 24) + 1];
> }
> boolean skipLevel1 = canSkipLevel(histogram1, data.length);
> boolean skipLevel2 = canSkipLevel(histogram2, data.length);
> boolean skipLevel3 = canSkipLevel(histogram3, data.length);
> boolean skipLevel4 = canSkipLevel(histogram4, data.length);
>
> if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
> return;
> }
> int[] copy = new int[data.length];
>
> int[] source = data;
> int[] dest = copy;
>
> if (!skipLevel1) {
> for (int i = 1; i < histogram1.length; ++i) {
> histogram1[i] += histogram1[i - 1];
> }
> for (int value : source) {
> dest[histogram1[value & 0xFF]++] = value;
> }
> if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel2) {
> for (int i = 1; i < histogram2.length; ++i) {
> histogram2[i] += histogram2[i - 1];
> }
> for (int value : source) {
> dest[histogram2[(value >>> 8) & 0xFF]++] = value;
> }
> if (!skipLevel3 || !skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel3) {
> for (int i = 1; i < histogram3.length; ++i) {
> histogram3[i] += histogram3[i - 1];
> }
> for (int value : data) {
> dest[histogram3[(value >>> 16) & 0xFF]++] = value;
> }
> if (!skipLevel4) {
> int[] tmp = dest;
> dest = source;
> source = tmp;
> }
> }
>
> if (!skipLevel4) {
> for (int i = 1; i < histogram4.length; ++i) {
> histogram4[i] += histogram4[i - 1];
> }
> for (int value : source) {
> dest[histogram4[value >>> 24]++] = value;
> }
> }
> if (dest != data) {
> System.arraycopy(dest, 0, data, 0, data.length);
> }
> }
>
> private static boolean canSkipLevel(int[] histogram, int dataSize) {
> for (int count : histogram) {
> if (count == dataSize) {
> return true;
> } else if (count > 0) {
> return false;
> }
> }
> return true;
> }
>
>
> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with
> me about doing so. On 25/04/2021 there was a new implementation of
> `DualPivotQuicksort` with a signed radix sort but the same structural
> similarities, and with the same method and variable names in places
> https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
>
>
> // TODO add javadoc
> private static void radixSort(Sorter sorter, int[] a, int low, int high) {
> int[] b;
> // LBO: prealloc (high - low) +1 element:
> if (sorter == null || (b = sorter.b) == null || b.length < (high -
> low)) {
> // System.out.println("alloc b: " + (high - low));
> b = new int[high - low];
> }
>
> int[] count1, count2, count3, count4;
> if (sorter != null) {
> sorter.resetRadixBuffers();
> count1 = sorter.count1;
> count2 = sorter.count2;
> count3 = sorter.count3;
> count4 = sorter.count4;
> } else {
> // System.out.println("alloc radix buffers(4x256)");
> count1 = new int[256];
> count2 = new int[256];
> count3 = new int[256];
>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 10:22:57 GMT, Laurent Bourgès wrote:
>> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I
>> believe this work derives from an unsigned radix sort I implemented on
>> 10/04/2021
>> https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
>> which has numerous structural similarities to this work:
>> * Producing all four histograms in one pass
>> * Skipping passes based on detecting the total in the histogram
>> * Bailing out of the skip detection if a nonzero value not equal to the
>> total is encountered
>> * Manually unrolling the LSD radix sort loop in order to avoid array copies
>>
>> My implementation from 10th April is below for reference:
>>
>> public static void unrollOnePassHistogramsSkipLevels(int[] data) {
>> int[] histogram1 = new int[257];
>> int[] histogram2 = new int[257];
>> int[] histogram3 = new int[257];
>> int[] histogram4 = new int[257];
>>
>> for (int value : data) {
>> ++histogram1[(value & 0xFF) + 1];
>> ++histogram2[((value >>> 8) & 0xFF) + 1];
>> ++histogram3[((value >>> 16) & 0xFF) + 1];
>> ++histogram4[(value >>> 24) + 1];
>> }
>> boolean skipLevel1 = canSkipLevel(histogram1, data.length);
>> boolean skipLevel2 = canSkipLevel(histogram2, data.length);
>> boolean skipLevel3 = canSkipLevel(histogram3, data.length);
>> boolean skipLevel4 = canSkipLevel(histogram4, data.length);
>>
>> if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
>> return;
>> }
>> int[] copy = new int[data.length];
>>
>> int[] source = data;
>> int[] dest = copy;
>>
>> if (!skipLevel1) {
>> for (int i = 1; i < histogram1.length; ++i) {
>> histogram1[i] += histogram1[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram1[value & 0xFF]++] = value;
>> }
>> if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel2) {
>> for (int i = 1; i < histogram2.length; ++i) {
>> histogram2[i] += histogram2[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram2[(value >>> 8) & 0xFF]++] = value;
>> }
>> if (!skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel3) {
>> for (int i = 1; i < histogram3.length; ++i) {
>> histogram3[i] += histogram3[i - 1];
>> }
>> for (int value : data) {
>> dest[histogram3[(value >>> 16) & 0xFF]++] = value;
>> }
>> if (!skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel4) {
>> for (int i = 1; i < histogram4.length; ++i) {
>> histogram4[i] += histogram4[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram4[value >>> 24]++] = value;
>> }
>> }
>> if (dest != data) {
>> System.arraycopy(dest, 0, data, 0, data.length);
>> }
>> }
>>
>> private static boolean canSkipLevel(int[] histogram, int dataSize) {
>> for (int count : histogram) {
>> if (count == dataSize) {
>> return true;
>> } else if (count > 0) {
>> return false;
>> }
>> }
>> return true;
>> }
>>
>>
>> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with
>> me about doing so. On 25/04/2021 there was a new implementation of
>> `DualPivotQuicksort` with a signed radix sort but the same structural
>> similarities, and with the same method and variable names in places
>> https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
>>
>>
>> // TODO add javadoc
>> private static void radixSort(Sorter sorter, int[] a, int low, int high)
>> {
>> int[] b;
>> // LBO: prealloc (high - low) +1 element:
>> if (sorter == null || (b = sorter.b) == null || b.length < (high -
>> low)) {
>> // System.out.println("alloc b: " + (high - low));
>> b = new int[high - low];
>> }
>>
>> int[] count1, count2, count3, count4;
>> if (sorter != null) {
>> sorter.resetRadixBuffers();
>> count1 = sorter.count1;
>> count2 = sorter.count2;
>> count3 = sorter.count3;
>> count4 = sorter.count4;
>> } else {
>> // System.out.println("alloc radix buffers(4x256)");
>> count1 = new int[256];
>> count2 = new int[256];
>> count3 = new int[256];
>> count4 = new int[256];
>> }
>>
>>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 21:44:38 GMT, Richard Startin wrote: >> For what it's worth, I benchmarked this implementation radix sort ([adapted >> here to fit in to my >> harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) >> against a [signed >> variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) >> of what I have claimed this work was derived from and the proposed >> implementation does not perform favourably on uniformly random data: >> >> >> >> Benchmark (bits) (padding) >> (scenario) (seed) (size) Mode Cnt Score Error Units >> RadixSortBenchmark.jdk17 7 >> UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op >> RadixSortBenchmark.jdk23 7 >> UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op >> RadixSortBenchmark.jdk30 7 >> UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 >> UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 >> UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 >> UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op >> >> >> >> I believe the root cause is a defect in the mechanism employed to skip >> passes as can be seen by the increased number of instructions and cycles >> here. In the proposed implementation, instructions is roughly constant as a >> function of bits. In the case where all passes must be performed (bits = >> 30), IPC is superior in `unrollOnePassHistogramsSkipLevelsSigned`. >> >> >> Benchmark >> (bits) (padding) (scenario) (seed) (size) Mode Cnt Score >> Error Units >> RadixSortBenchmark.jdk:cycles >> 17 7 UNIFORM 0 100 avgt 34976971.877 >>#/op >> RadixSortBenchmark.jdk:instructions >> 17 7 UNIFORM 0 100 avgt 70121142.003 >>#/op >> RadixSortBenchmark.jdk:cycles >> 23 7 UNIFORM 0 100 avgt 32369970.385 >>#/op >> RadixSortBenchmark.jdk:instructions >> 23 7 UNIFORM 0 100 avgt 70201664.963 >>#/op >> RadixSortBenchmark.jdk:cycles >> 30 7 UNIFORM 0 100 avgt 30789736.602 >>#/op >> RadixSortBenchmark.jdk:instructions >> 30 7 UNIFORM 0 100 avgt 70180942.122 >>#/op >> RadixSortBenchmark.jdk:IPC >> 30 7 UNIFORM 0 100 avgt 2.279 >> insns/clk >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 17 7 UNIFORM 0 100 avgt 26983994.479 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 17 7 UNIFORM 0 100 avgt 62065304.827 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 23 7 UNIFORM 0 100 avgt 26161703.124 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 23 7 UNIFORM 0 100 avgt 63102683.167 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles >> 30 7 UNIFORM 0 100 avgt 29780103.795 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions >> 30 7 UNIFORM 0 100 avgt 74437097.025 >>#/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned:IPC >> 30 7 UNIFORM 0 100 avgt 2.500 >> insns/clk >> >> >> >> The biggest difference in executed code appears to be that bounds checks are >> not eliminated in the first counting pass in the proposed implementation: >> >> >> [Hottest Region >>
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Fri, 14 May 2021 07:14:27 GMT, Laurent Bourgès wrote: >> So the issue of not skipping passes was my fault in the translation process, >> so not something to worry about, though after [fixing >> that](https://github.com/richardstartin/radix-sort-benchmark/commit/ccbee984c6a0e0f50c30de59e1a5e9fbcad89510) >> the original implementation still has the edge because of the bounds checks >> on the `xor` not getting eliminated. >> >> >> Benchmark (bits) (padding) >> (scenario) (seed) (size) Mode Cnt ScoreError Units >> RadixSortBenchmark.jdk17 7 >> UNIFORM 0 100 avgt5 10432.408 ± 87.024 us/op >> RadixSortBenchmark.jdk23 7 >> UNIFORM 0 100 avgt5 9465.990 ± 40.598 us/op >> RadixSortBenchmark.jdk30 7 >> UNIFORM 0 100 avgt5 11189.146 ± 50.972 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 >> UNIFORM 0 100 avgt5 9546.963 ± 41.698 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 >> UNIFORM 0 100 avgt5 9412.114 ± 43.081 us/op >> RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 >> UNIFORM 0 100 avgt5 10823.618 ± 64.311 us/op > > Great analysis on C2, richard. > > maybe (x ^ 0x80) &0xFF would help C2 to eliminate bound checks... I don't know Laurent, I find the handling of signed order over-complicated. Subtracting `Integer.MIN_VALUE` is really cheap... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 14:44:28 GMT, Richard Startin wrote: >> @iaroslavski I would prefer to discuss this in private than here, but my >> argument is that the name `skipByte` came from Laurent's code, and that >> Laurent's code was clearly derived from my own within a fork of my >> repository. I linked the commits where you changed `skipByte` to `passLevel` >> and Laurent changed my name `canSkipLevel` to `skipByte`. >> >> For me, this raises questions about the independence of your work from >> Laurent's, and Laurent's work is clearly derived from my own (and I don't >> think anyone is disputing the latter). I would be happy to sort this out in >> private. > > In private correspondence with Vladimir, it was explained that where > Vladimir's code and Laurent's code are identical, including typos > ([Vladimir's > code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), > [Laurent's > code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) > it is because Vladimir sent the code to Laurent, not the other way around, > therefore Vladimir's code does not derive from Laurent's, and it does not > derive from mine. I can only trust that this is the case, so please disregard > my claim that this is derivative work when reviewing this PR. For what it's worth, I benchmarked this implementation radix sort ([adapted here to fit in to my harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) against a [signed variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) of what I have claimed this work was derived from and the proposed implementation does not perform favourably on uniformly random data: Benchmark (bits) (padding) (scenario) (seed) (size) Mode Cnt Score Error Units RadixSortBenchmark.jdk17 7 UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op RadixSortBenchmark.jdk23 7 UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op RadixSortBenchmark.jdk30 7 UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op I believe the root cause is a defect in the mechanism employed to skip passes as can be seen by the increased number of instructions and cycles here. In the proposed implementation, instructions is roughly constant as a function of bits. In the case where all passes must be performed (bits = 30), IPC is superior in `unrollOnePassHistogramsSkipLevelsSigned`. Benchmark (bits) (padding) (scenario) (seed) (size) Mode Cnt Score Error Units RadixSortBenchmark.jdk:cycles 17 7 UNIFORM 0 100 avgt 34976971.877 #/op RadixSortBenchmark.jdk:instructions 17 7 UNIFORM 0 100 avgt 70121142.003 #/op RadixSortBenchmark.jdk:cycles 23 7 UNIFORM 0 100 avgt 32369970.385 #/op RadixSortBenchmark.jdk:instructions 23 7 UNIFORM 0 100 avgt 70201664.963 #/op RadixSortBenchmark.jdk:cycles 30 7 UNIFORM 0 100 avgt 30789736.602 #/op RadixSortBenchmark.jdk:instructions 30 7 UNIFORM 0 100 avgt 70180942.122 #/op RadixSortBenchmark.jdk:IPC 30 7 UNIFORM 0 100 avgt 2.279 insns/clk RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles 17 7 UNIFORM 0 100 avgt 26983994.479 #/op
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 20:23:16 GMT, Richard Startin wrote: >> In private correspondence with Vladimir, it was explained that where >> Vladimir's code and Laurent's code are identical, including typos >> ([Vladimir's >> code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), >> [Laurent's >> code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) >> it is because Vladimir sent the code to Laurent, not the other way around, >> therefore Vladimir's code does not derive from Laurent's, and it does not >> derive from mine. I can only trust that this is the case, so please >> disregard my claim that this is derivative work when reviewing this PR. > > For what it's worth, I benchmarked this implementation radix sort ([adapted > here to fit in to my > harness](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR681-R710782)) > against a [signed > variant](https://github.com/richardstartin/radix-sort-benchmark/commit/07169e8e8602152cfda859baa159db165bf5fcab#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR396-R478) > of what I have claimed this work was derived from and the proposed > implementation does not perform favourably on uniformly random data: > > > > Benchmark (bits) (padding) > (scenario) (seed) (size) Mode Cnt Score Error Units > RadixSortBenchmark.jdk17 7 > UNIFORM 0 100 avgt5 11301.950 ± 113.691 us/op > RadixSortBenchmark.jdk23 7 > UNIFORM 0 100 avgt5 11792.351 ± 60.757 us/op > RadixSortBenchmark.jdk30 7 > UNIFORM 0 100 avgt5 11184.616 ± 67.094 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 17 7 > UNIFORM 0 100 avgt5 9564.626 ± 69.497 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 23 7 > UNIFORM 0 100 avgt5 9432.085 ± 58.983 us/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned 30 7 > UNIFORM 0 100 avgt5 10772.975 ± 51.848 us/op > > > > I believe the root cause is a defect in the mechanism employed to skip passes > as can be seen by the increased number of instructions and cycles here. In > the proposed implementation, instructions is roughly constant as a function > of bits. In the case where all passes must be performed (bits = 30), IPC is > superior in `unrollOnePassHistogramsSkipLevelsSigned`. > > > Benchmark > (bits) (padding) (scenario) (seed) (size) Mode Cnt Score > Error Units > RadixSortBenchmark.jdk:cycles > 17 7 UNIFORM 0 100 avgt 34976971.877 > #/op > RadixSortBenchmark.jdk:instructions > 17 7 UNIFORM 0 100 avgt 70121142.003 > #/op > RadixSortBenchmark.jdk:cycles > 23 7 UNIFORM 0 100 avgt 32369970.385 > #/op > RadixSortBenchmark.jdk:instructions > 23 7 UNIFORM 0 100 avgt 70201664.963 > #/op > RadixSortBenchmark.jdk:cycles > 30 7 UNIFORM 0 100 avgt 30789736.602 > #/op > RadixSortBenchmark.jdk:instructions > 30 7 UNIFORM 0 100 avgt 70180942.122 > #/op > RadixSortBenchmark.jdk:IPC > 30 7 UNIFORM 0 100 avgt 2.279 > insns/clk > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles > 17 7 UNIFORM 0 100 avgt 26983994.479 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions > 17 7 UNIFORM 0 100 avgt 62065304.827 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:cycles > 23 7 UNIFORM 0 100 avgt 26161703.124 > #/op > RadixSortBenchmark.unrollOnePassSkipLevelsSigned:instructions > 23 7 UNIFORM 0 100 avgt 63102683.167
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 11:31:49 GMT, iaroslavski wrote: >> Perhaps we can resolve this issue in private - my email address is on my >> profile (or in the commits in `radix-sort-benchmark`)? > > @richardstartin And one more addon: my first version of Radix sort, see my > github https://github.com/iaroslavski/sorting/tree/master/radixsort uses > another name, like skipBytes, then renamed to passLevel. > So, the common part is "skip". And this method has different number of > parameters. I don't see any collision with your code. @iaroslavski I would prefer to discuss this in private than here, but my argument is that the name `skipByte` came from Laurent's code, and that Laurent's code was clearly derived from my own within a fork of my repository. I linked the commits where you changed `skipByte` to `passLevel` and Laurent changed my name `canSkipLevel` to `skipByte`. For me, this raises questions about the independence of your work from Laurent's, and Laurent's work is clearly derived from my own (and I don't think anyone is disputing the latter). I would be happy to sort this out in private. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 11:47:58 GMT, Richard Startin wrote: >> @richardstartin And one more addon: my first version of Radix sort, see my >> github https://github.com/iaroslavski/sorting/tree/master/radixsort uses >> another name, like skipBytes, then renamed to passLevel. >> So, the common part is "skip". And this method has different number of >> parameters. I don't see any collision with your code. > > @iaroslavski I would prefer to discuss this in private than here, but my > argument is that the name `skipByte` came from Laurent's code, and that > Laurent's code was clearly derived from my own within a fork of my > repository. I linked the commits where you changed `skipByte` to `passLevel` > and Laurent changed my name `canSkipLevel` to `skipByte`. > > For me, this raises questions about the independence of your work from > Laurent's, and Laurent's work is clearly derived from my own (and I don't > think anyone is disputing the latter). I would be happy to sort this out in > private. In private correspondence with Vladimir, it was explained that where Vladimir's code and Laurent's code are identical, including typos ([Vladimir's code](https://github.com/iaroslavski/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR672), [Laurent's code](https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719)) it is because Vladimir sent the code to Laurent, not the other way around, therefore Vladimir's code does not derive from Laurent's, and it does not derive from mine. I can only trust that this is the case, so please disregard my claim that this is derivative work when reviewing this PR. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Thu, 13 May 2021 10:53:48 GMT, Richard Startin wrote: >> You misunderstood my approach: >> - vladimir & tagir discussed radix sorts since previous work on DPQS in 2019 >> - I enjoyed reading your blog post testing the performance of your radix >> sort vs Arrays.sort() >> - I tested and forked your radix-sort-benchmark to reproduce your >> experiments on openjdk16 (dpqs 19.11) >> - Vladimir proposed his own radixsort() >> - I did port DPQS impls in my fork of your benchmark to make a global >> comparison: dpqs 11, 19, 21 vs yours + arrays.sort(): it helped comparing >> implementations and decide when radix sort wins depending on dataset >> presortness >> - I tried many variants on my github repositories, but Vladimir never merged >> any of my change as he is not a regular github user (clone, fork, merge). >> >> Our goal is not to underestimate your work (sort + benchmark) but Vladimir >> wrote his own code, me many experiments (tests, benchmarks) to obtain this >> original patch, written by Vladimir, with his radix sort implementation >> working on any int/long/float/double arrays, following the GPLv2 license. >> >> You gave me motivation to make Arrays.sort() faster and we worked hard to >> write, test and benchmark this patch to be ready for OpenJDK 17 > > Perhaps we can resolve this issue in private - my email address is on my > profile (or in the commits in `radix-sort-benchmark`)? @richardstartin The ideas to take 4 histograms at once or use check to skip digits are very simple and come not only from you, for example, see article from 2001, http://stereopsis.com/radix.html When Laurent and I discussed our Radix sort, your code was demonstrated. I wrote my implementation and at the first version I took the similar names (even not perfect for my cases) and later I renamed them to better values. You can see that from functional point of view your code and my code are different, they process skipped digits in different manner, No your code was copied. Date 2020.06.14 means the start of my activities on Radix sort, not final version. Let me know, if you have any questions @richardstartin And one more addon: my first version of Radix sort, see my github https://github.com/iaroslavski/sorting/tree/master/radixsort uses another name, like skipBytes, then renamed to passLevel. So, the common part is "skip". And this method has different number of parameters. I don't see any collision with your code. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 12:20:09 GMT, iaroslavski
wrote:
>> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47:
>>
>>> 45: * @author Doug Lea
>>> 46: *
>>> 47: * @version 2020.06.14
>>
>> Vladimir, I would update to 2021.05.06 (+your hash)
>
> Laurent, the date in this class is not the date of our last commit,
> this date is the date when I have final idea regarding to Radix sort,
> therefore, I prefer to keep 2020.06.14
Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I believe
this work derives from an unsigned radix sort I implemented on 10/04/2021
https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226
which has numerous structural similarities to this work:
* Producing all four histograms in one pass
* Skipping passes based on detecting the total in the histogram
* Bailing out of the skip detection if a nonzero value not equal to the total
is encountered
* Manually unrolling the LSD radix sort loop in order to avoid array copies
My implementation from 10th April is below for reference:
public static void unrollOnePassHistogramsSkipLevels(int[] data) {
int[] histogram1 = new int[257];
int[] histogram2 = new int[257];
int[] histogram3 = new int[257];
int[] histogram4 = new int[257];
for (int value : data) {
++histogram1[(value & 0xFF) + 1];
++histogram2[((value >>> 8) & 0xFF) + 1];
++histogram3[((value >>> 16) & 0xFF) + 1];
++histogram4[(value >>> 24) + 1];
}
boolean skipLevel1 = canSkipLevel(histogram1, data.length);
boolean skipLevel2 = canSkipLevel(histogram2, data.length);
boolean skipLevel3 = canSkipLevel(histogram3, data.length);
boolean skipLevel4 = canSkipLevel(histogram4, data.length);
if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
return;
}
int[] copy = new int[data.length];
int[] source = data;
int[] dest = copy;
if (!skipLevel1) {
for (int i = 1; i < histogram1.length; ++i) {
histogram1[i] += histogram1[i - 1];
}
for (int value : source) {
dest[histogram1[value & 0xFF]++] = value;
}
if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel2) {
for (int i = 1; i < histogram2.length; ++i) {
histogram2[i] += histogram2[i - 1];
}
for (int value : source) {
dest[histogram2[(value >>> 8) & 0xFF]++] = value;
}
if (!skipLevel3 || !skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel3) {
for (int i = 1; i < histogram3.length; ++i) {
histogram3[i] += histogram3[i - 1];
}
for (int value : data) {
dest[histogram3[(value >>> 16) & 0xFF]++] = value;
}
if (!skipLevel4) {
int[] tmp = dest;
dest = source;
source = tmp;
}
}
if (!skipLevel4) {
for (int i = 1; i < histogram4.length; ++i) {
histogram4[i] += histogram4[i - 1];
}
for (int value : source) {
dest[histogram4[value >>> 24]++] = value;
}
}
if (dest != data) {
System.arraycopy(dest, 0, data, 0, data.length);
}
}
private static boolean canSkipLevel(int[] histogram, int dataSize) {
for (int count : histogram) {
if (count == dataSize) {
return true;
} else if (count > 0) {
return false;
}
}
return true;
}
Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with me
about doing so. On 25/04/2021 there was a new implementation of
`DualPivotQuicksort` with a signed radix sort but the same structural
similarities, and with the same method and variable names in places
https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
// TODO add javadoc
private static void radixSort(Sorter sorter, int[] a, int low, int high) {
int[] b;
// LBO: prealloc (high - low) +1 element:
if (sorter == null || (b = sorter.b) == null || b.length < (high -
low)) {
// System.out.println("alloc b: " + (high - low));
b = new int[high - low];
}
int[] count1, count2, count3, count4;
if (sorter != null) {
sorter.resetRadixBuffers();
count1 = sorter.count1;
count2 = sorter.count2;
count3 = sorter.count3;
count4 = sorter.count4;
} else {
// System.out.println("alloc radix buffers(4x256)");
count1 = new int[256];
count2 = new int[256];
count3 = new int[256];
count4 = new int[256];
}
for (int i = low; i <
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 12:20:09 GMT, iaroslavski wrote: >> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: >> >>> 45: * @author Doug Lea >>> 46: * >>> 47: * @version 2020.06.14 >> >> Vladimir, I would update to 2021.05.06 (+your hash) > > Laurent, the date in this class is not the date of our last commit, > this date is the date when I have final idea regarding to Radix sort, > therefore, I prefer to keep 2020.06.14 as you want, but you should maybe indicate which version corresponds to your master code too. It would help tracking changes between forks (iarosalvskiy/sorting master) - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > Sorting: > > - adopt radix sort for sequential and parallel sorts on int/long/float/double > arrays (almost random and length > 6K) > - fix tryMergeRuns() to better handle case when the last run is a single > element > - minor javadoc and comment changes > > Testing: > - add new data inputs in tests for sorting > - add min/max/infinity values to float/double testing > - add tests for radix sort Still waiting OCA approval Yes, I ping again, will see what happens >Суббота, 24 июля 2021, 14:47 +03:00 от Laurent Bourgès ***@***.***>: > > >Still waiting for individual OCA approval >— >You are receiving this because you were mentioned. >Reply to this email directly, view it on GitHub , or unsubscribe . Still waiting OCA approval - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Wed, 12 May 2021 11:36:09 GMT, Laurent Bourgès wrote: >> Sorting: >> >> - adopt radix sort for sequential and parallel sorts on >> int/long/float/double arrays (almost random and length > 6K) >> - fix tryMergeRuns() to better handle case when the last run is a single >> element >> - minor javadoc and comment changes >> >> Testing: >> - add new data inputs in tests for sorting >> - add min/max/infinity values to float/double testing >> - add tests for radix sort > > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: > >> 45: * @author Doug Lea >> 46: * >> 47: * @version 2020.06.14 > > Vladimir, I would update to 2021.05.06 (+your hash) Laurent, the date in this class is not the date of our last commit, this date is the date when I have final idea regarding to Radix sort, therefore, I prefer to keep 2020.06.14 > src/java.base/share/classes/java/util/DualPivotQuicksort.java line 288: > >> 286: /* >> 287: * Invoke radix sort on large array. >> 288: */ > > I prefer testing (sorter == null) first as it is always true for sequential > sort and avoid testing bits > ... in this case It makes sense, I will update. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
On Sat, 8 May 2021 20:54:48 GMT, iaroslavski wrote: > Sorting: > > - adopt radix sort for sequential and parallel sorts on int/long/float/double > arrays (almost random and length > 6K) > - fix tryMergeRuns() to better handle case when the last run is a single > element > - minor javadoc and comment changes > > Testing: > - add new data inputs in tests for sorting > - add min/max/infinity values to float/double testing > - add tests for radix sort Congratulation, what an amazing job ! DPQS is now 50% faster in average but 2.5 times faster (rms) my favorite !! Finally OOME is now handled to let sort work under low-mem conditions ! I will work on more benchmarks for long/float/double types. Laurent Still waiting for individual OCA approval src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47: > 45: * @author Doug Lea > 46: * > 47: * @version 2020.06.14 Vladimir, I would update to 2021.05.06 (+your hash) src/java.base/share/classes/java/util/DualPivotQuicksort.java line 288: > 286: /* > 287: * Invoke radix sort on large array. > 288: */ I prefer testing (sorter == null) first as it is always true for sequential sort and avoid testing bits > ... in this case - PR: https://git.openjdk.java.net/jdk/pull/3938
RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
Sorting: - adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K) - fix tryMergeRuns() to better handle case when the last run is a single element - minor javadoc and comment changes Testing: - add new data inputs in tests for sorting - add min/max/infinity values to float/double testing - add tests for radix sort - Commit messages: - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) Changes: https://git.openjdk.java.net/jdk/pull/3938/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=3938=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8266431 Stats: 889 lines in 3 files changed: 718 ins; 46 del; 125 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
On Mon, 13 Sep 2021 11:06:15 GMT, Сергей Цыпанов
wrote:
> Currently the method is implemented like
>
> public List> parameterList() {
> return Collections.unmodifiableList(Arrays.asList(ptypes.clone()));
> }
>
> This seems to be excessive, as three objects are allocated here. Instead we
> can use `List.of(ptypes)` which doesn't allocate anything for empty array and
> for one of length 1 and 2 it allocates lightweight objects with 2 fields,
> still copying longer arrays. This is likely to be fruitful as most of methods
> have 0-2 parameters.
>
> Also there is a couple of cases when `MethodType.parameterLis()` is called to
> get its size, which is excessive either as we can use
> `MethodType.parameterCount()` instead.
Looks good to me.
-
Marked as reviewed by mchung (Reviewer).
PR: https://git.openjdk.java.net/jdk/pull/5489
Re: RFR: 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
On Mon, 13 Sep 2021 11:06:15 GMT, Сергей Цыпанов
wrote:
> Currently the method is implemented like
>
> public List> parameterList() {
> return Collections.unmodifiableList(Arrays.asList(ptypes.clone()));
> }
>
> This seems to be excessive, as three objects are allocated here. Instead we
> can use `List.of(ptypes)` which doesn't allocate anything for empty array and
> for one of length 1 and 2 it allocates lightweight objects with 2 fields,
> still copying longer arrays. This is likely to be fruitful as most of methods
> have 0-2 parameters.
>
> Also there is a couple of cases when `MethodType.parameterLis()` is called to
> get its size, which is excessive either as we can use
> `MethodType.parameterCount()` instead.
Looks good.
BTW it can be improved even further by caching the immutable List view of
parameters.
-
Marked as reviewed by vlivanov (Reviewer).
PR: https://git.openjdk.java.net/jdk/pull/5489
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
On Mon, 13 Sep 2021 11:22:27 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Use "ensure" instead of "insure" Marked as reviewed by jrose (Reviewer). - PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: 8266936: Add a finalization JFR event [v11]
> Greetings, > > Object.finalize() was deprecated in JDK9. There is an ongoing effort to > replace and mitigate Object.finalize() uses in the JDK libraries; please see > https://bugs.openjdk.java.net/browse/JDK-8253568 for more information. > > We also like to assist users in replacing and mitigating uses in non-JDK code. > > Hence, this changeset adds a periodic JFR event to help identify which > classes are overriding Object.finalize(). > > Thanks > Markus Markus Grönlund has updated the pull request incrementally with two additional commits since the last revision: - remove rehashing and rely on default grow_hint for table resize - mtStatistics - Changes: - all: https://git.openjdk.java.net/jdk/pull/4731/files - new: https://git.openjdk.java.net/jdk/pull/4731/files/fd86899f..62592daf Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=4731=10 - incr: https://webrevs.openjdk.java.net/?repo=jdk=4731=09-10 Stats: 258 lines in 6 files changed: 25 ins; 197 del; 36 mod Patch: https://git.openjdk.java.net/jdk/pull/4731.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/4731/head:pull/4731 PR: https://git.openjdk.java.net/jdk/pull/4731
Re: RFR: 8247980: Exclusive execution of java/util/stream tests slows down tier1
On Thu, 19 Aug 2021 15:15:31 GMT, Aleksey Shipilev wrote: > See the bug report for more details. I would appreciate if people with their > corporate testing systems would run this through their systems to avoid > surprises. (ping @RealCLanger, @iignatev). @ArnoZeller, have your runs identify any problems with these tests? I wonder if we want to integrate this PR, and see if we see any problems going forward. If we do, and those problems look environmental or intrinsic to the tests, we can revert the patch. Thoughts? - PR: https://git.openjdk.java.net/jdk/pull/5189
Re: RFR: 8271820: Implementation of JEP 416: Reimplement Core Reflection with Method Handle [v8]
On Wed, 1 Sep 2021 01:05:32 GMT, Mandy Chung wrote: >> This reimplements core reflection with method handles. >> >> For `Constructor::newInstance` and `Method::invoke`, the new implementation >> uses `MethodHandle`. For `Field` accessor, the new implementation uses >> `VarHandle`.For the first few invocations of one of these reflective >> methods on a specific reflective object we invoke the corresponding method >> handle directly. After that we spin a dynamic bytecode stub defined in a >> hidden class which loads the target `MethodHandle` or `VarHandle` from its >> class data as a dynamically computed constant. Loading the method handle >> from a constant allows JIT to inline the method-handle invocation in order >> to achieve good performance. >> >> The VM's native reflection methods are needed during early startup, before >> the method-handle mechanism is initialized. That happens soon after >> System::initPhase1 and before System::initPhase2, after which we switch to >> using method handles exclusively. >> >> The core reflection and method handle implementation are updated to handle >> chained caller-sensitive method calls [1] properly. A caller-sensitive >> method can define with a caller-sensitive adapter method that will take an >> additional caller class parameter and the adapter method will be annotated >> with `@CallerSensitiveAdapter` for better auditing. See the detailed >> description from [2]. >> >> Ran tier1-tier8 tests. >> >> [1] https://bugs.openjdk.java.net/browse/JDK-8013527 >> [2] >> https://bugs.openjdk.java.net/browse/JDK-8271820?focusedCommentId=14439430=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-14439430 > > Mandy Chung has updated the pull request incrementally with one additional > commit since the last revision: > > minor cleanup and more test case. Hi Peter, I haven't tried the approach of making the Method @stable reference to MethodAccessor instead of volatile. This reminds me of your experiment [1] which I lost track of. It'd be good if you can try that approach and compare the benchmark results. [1] https://bugs.openjdk.java.net/browse/JDK-6824466?focusedCommentId=14212580=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-14212580 - PR: https://git.openjdk.java.net/jdk/pull/5027
Re: RFR: 8273514: java/util/DoubleStreamSums/CompensatedSums.java failure [v3]
> Relaxing some assertion bounds to allow for small error values that still > show improvement over previous summation method. Ian Graves has updated the pull request incrementally with one additional commit since the last revision: Factoring out Math.pow for squares - Changes: - all: https://git.openjdk.java.net/jdk/pull/5430/files - new: https://git.openjdk.java.net/jdk/pull/5430/files/8f77f3d3..bcd5892d Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=5430=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk=5430=01-02 Stats: 13 lines in 1 file changed: 4 ins; 3 del; 6 mod Patch: https://git.openjdk.java.net/jdk/pull/5430.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5430/head:pull/5430 PR: https://git.openjdk.java.net/jdk/pull/5430
Re: RFR: 8273514: java/util/DoubleStreamSums/CompensatedSums.java failure [v2]
On Mon, 13 Sep 2021 00:08:20 GMT, Joe Darcy wrote:
>> Ian Graves has updated the pull request incrementally with one additional
>> commit since the last revision:
>>
>> Tweaking asserts
>
> test/jdk/java/util/DoubleStreamSums/CompensatedSums.java line 87:
>
>> 85: badParallelStreamError +=
>> Math.pow(computeFinalSum(DoubleStream.of(rand).parallel().collect(doubleSupplier,objDoubleConsumer,badCollectorConsumer))
>> - sum[0], 2);
>> 86:
>> 87:
>
> Above, if there are going to be multiple uese of Math.pow(arg, 2) in the
> test, I recommend defining a local private static square(double d) method for
> this test where square is
> double square(double arg) {return arg * arg;}
> The library method pow(arg, 2) does a check for the exponent being two and
> does a multiple instead.
Good call. Done.
-
PR: https://git.openjdk.java.net/jdk/pull/5430
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
On Mon, 13 Sep 2021 11:22:27 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Use "ensure" instead of "insure" Marked as reviewed by lancea (Reviewer). - PR: https://git.openjdk.java.net/jdk/pull/5475
Integrated: 8273259: Character.getName doesn't follow Unicode spec for ideographs
On Thu, 2 Sep 2021 19:26:12 GMT, Naoto Sato wrote: > Simple spec clarification. A CSR has also been drafted > (https://bugs.openjdk.java.net/browse/JDK-8273296). This pull request has now been integrated. Changeset: 4cfa230e Author:Naoto Sato URL: https://git.openjdk.java.net/jdk/commit/4cfa230e2daac118f21c7d8996d48a1a15d87a62 Stats: 21 lines in 1 file changed: 12 ins; 0 del; 9 mod 8273259: Character.getName doesn't follow Unicode spec for ideographs Reviewed-by: bpb, lancea, iris, darcy - PR: https://git.openjdk.java.net/jdk/pull/5354
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
On Mon, 13 Sep 2021 11:22:27 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Use "ensure" instead of "insure" Marked as reviewed by iris (Reviewer). - PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
On Mon, 13 Sep 2021 11:06:15 GMT, Сергей Цыпанов
wrote:
> Currently the method is implemented like
>
> public List> parameterList() {
> return Collections.unmodifiableList(Arrays.asList(ptypes.clone()));
> }
>
> This seems to be excessive, as three objects are allocated here. Instead we
> can use `List.of(ptypes)` which doesn't allocate anything for empty array and
> for one of length 1 and 2 it allocates lightweight objects with 2 fields,
> still copying longer arrays. This is likely to be fruitful as most of methods
> have 0-2 parameters.
>
> Also there is a couple of cases when `MethodType.parameterLis()` is called to
> get its size, which is excessive either as we can use
> `MethodType.parameterCount()` instead.
I'm also running a test job for this change. If that comes back green I'll
sponsor the PR after the 24 hour review period (in case anybody else wants to
comment).
-
PR: https://git.openjdk.java.net/jdk/pull/5489
Re: RFR: 8231640: (prop) Canonical property storage [v10]
Hi Jaikiran,
"Editing" the value of the comment property, to remove or ignore blanks
for other special
characters makes the code more complex and adds a bunch of conditions.
Dropping
the comment if it doesn't have the allowed format is hard to track down,
because there's
no way to report it was dropped or why.
I would write the value of the comment property using the writeComments
method
so it is encoded the same as the other comment passed as an store argument.
That will handle all special characters and multi-line comments. It is
simpler to specify
and has the same predictable output as other comments.
if the property is non-empty
On 9/12/21 10:29 AM, Jaikiran Pai wrote:
...
This was discussed elsewhere, but after writing that, I'm now
thinking that we **should** honor the property even if it is blank.
It would be useful to disable the timestamp simply by setting the
property to the empty string; this will simply result in an empty
comment line. This would simplify the code (and the spec) by removing
conditions related to String::isBlank.
OK. I don't see any obvious issues with interpreting
empty/whitespace-only value for the system property to translate to an
empty comment line. To be clear, an empty comment line that gets
written out in such cases is *always* going to be the "#" character
followed by a line separator right? Irrespective of what or how many
whitespace characters are present in the property value? Or do you
want those characters to be carried over into that comment line that
gets written out? The reason I ask this is because I think we should
always write just the "#" followed by the line separator character in
such cases, which effectively means we will still need the
String::isBlank check which would then look something like:
if (propVal.isBlank()) {
bw.write("#");
bw.newLine();
}
Side question: do we want to do any escaping or vetting of the
property value?
One of the reasons why we didn't want to use the date in epoch seconds
or a formatted date string was to avoid the complexities that come
with managing that property value. So a free-form property value
seemed more appropriate and I think a free-form value still seems
appropriate, but I think we should keep any vetting to minimal. More
details below.
If for example it contains embedded newlines, this could result in a
malformed property file. Or, if carefully constructed, it could
contain additional property values. I think this is an unintended
consequence of changing the property value from a numeric time value
to a free-form string. We may want to reconsider this.
The specification on the load(Reader reader) method of the
java.util.Properties class has this to say about comment lines (and
lines in general).
(snipped relevant content):
There are two kinds of line, natural lines and logical
lines.
A natural line is defined as a line of characters that is terminated
either
by a set of line terminator characters ({@code \n} or {@code \r} or
{@code \r\n}) or by the end of the stream. A natural line may be
either a blank line, a comment line, or hold all or some of a
key-element pair. A logical
line holds all the data of a key-element pair, which may be spread
out across several adjacent natural lines by escaping
the line terminator sequence with a backslash character
{@code \}. Note that a comment line cannot be extended
in this manner; every natural line that is a comment must have
its own comment indicator, as described below.
With that knowledge about comment lines, I think what we should do is
disallow system property values that contain any form of line
terminator characters (\n or \r or \r\n). If the system property value
is _not_ blank (as specified by String::isBlank) and contains any of
these line terminator characters, we should simply ignore it and write
out the current date as the date comment. That, IMO, should prevent
any of these sneaky/rogue value that can end up either creating
additional property key/values to be written out or causing any
malformed properties file. Plus, that would help us keep the vetting
to minimal without involving too much complexity.
src/java.base/share/classes/java/util/Properties.java line 855:
853: * the value of this system property represents a formatted
854: * date time value that can be parsed back into a {@link
Date} using an appropriate
855: * {@link DateTimeFormatter}
With the property behavior added to normative text above, I don't
think we need this note anymore. We might want to leave something
here about the convention of putting a timestamp here, and an
implicit(?) requirement that it be formatted properly.
The newly updated PR has updated this @implNote to remove some of the
previous text and yet retain some hints on what would be an "ideal"
value for the system property value. But I think we should perhaps
just get rid of this
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
On Mon, 13 Sep 2021 11:22:27 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Use "ensure" instead of "insure" Marked as reviewed by rriggs (Reviewer). - PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
On Mon, 13 Sep 2021 11:06:15 GMT, Сергей Цыпанов
wrote:
> Currently the method is implemented like
>
> public List> parameterList() {
> return Collections.unmodifiableList(Arrays.asList(ptypes.clone()));
> }
>
> This seems to be excessive, as three objects are allocated here. Instead we
> can use `List.of(ptypes)` which doesn't allocate anything for empty array and
> for one of length 1 and 2 it allocates lightweight objects with 2 fields,
> still copying longer arrays. This is likely to be fruitful as most of methods
> have 0-2 parameters.
>
> Also there is a couple of cases when `MethodType.parameterLis()` is called to
> get its size, which is excessive either as we can use
> `MethodType.parameterCount()` instead.
LGTM
-
Marked as reviewed by jvernee (Reviewer).
PR: https://git.openjdk.java.net/jdk/pull/5489
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
On Mon, 13 Sep 2021 11:22:27 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Use "ensure" instead of "insure" LGTM - Marked as reviewed by dfuchs (Reviewer). PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v2]
On Fri, 10 Sep 2021 23:20:11 GMT, Pavel Rappo wrote: >> 8273616: Fix trivial doc typos in the java.base module > > Pavel Rappo has updated the pull request incrementally with one additional > commit since the last revision: > > Revert two fixes Thanks to those who reviewed this PR. Since I posted it, I've found three more occurrences of _insure_ used in the sense of _ensure_: two in the `java.io.Object*Stream` area and one in the `java.util.Currency` class. I decided to fix those in this PR, which now needs to be (re)reviewed. Thanks! There are more occurrences of _insure_, which I didn't touch. Some of them are in java.sql, java.sql.rowset and java.desktop. In the latter, _insure_ even crept into method names. - PR: https://git.openjdk.java.net/jdk/pull/5475
Re: RFR: 8273616: Fix trivial doc typos in the java.base module [v3]
> 8273616: Fix trivial doc typos in the java.base module Pavel Rappo has updated the pull request incrementally with one additional commit since the last revision: Use "ensure" instead of "insure" - Changes: - all: https://git.openjdk.java.net/jdk/pull/5475/files - new: https://git.openjdk.java.net/jdk/pull/5475/files/9a9deee1..4b33fb94 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=5475=02 - incr: https://webrevs.openjdk.java.net/?repo=jdk=5475=01-02 Stats: 3 lines in 2 files changed: 0 ins; 0 del; 3 mod Patch: https://git.openjdk.java.net/jdk/pull/5475.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5475/head:pull/5475 PR: https://git.openjdk.java.net/jdk/pull/5475
RFR: 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
Currently the method is implemented like
public List> parameterList() {
return Collections.unmodifiableList(Arrays.asList(ptypes.clone()));
}
This seems to be excessive, as three objects are allocated here. Instead we can
use `List.of(ptypes)` which doesn't allocate anything for empty array and for
one of length 1 and 2 it allocates lightweight objects with 2 fields, still
copying longer arrays. This is likely to be fruitful as most of methods have
0-2 parameters.
Also there is a couple of cases when `MethodType.parameterLis()` is called to
get its size, which is excessive either as we can use
`MethodType.parameterCount()` instead.
-
Commit messages:
- 8273656: Improve java.lang.invoke.MethodType.parameterList() and its usage
Changes: https://git.openjdk.java.net/jdk/pull/5489/files
Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5489=00
Issue: https://bugs.openjdk.java.net/browse/JDK-8273656
Stats: 7 lines in 2 files changed: 0 ins; 0 del; 7 mod
Patch: https://git.openjdk.java.net/jdk/pull/5489.diff
Fetch: git fetch https://git.openjdk.java.net/jdk pull/5489/head:pull/5489
PR: https://git.openjdk.java.net/jdk/pull/5489
Re: RFR: 8266936: Add a finalization JFR event [v10]
On Wed, 8 Sep 2021 17:37:20 GMT, Coleen Phillimore wrote:
>> Markus Grönlund has updated the pull request incrementally with three
>> additional commits since the last revision:
>>
>> - localize
>> - cleanup
>> - FinalizerStatistics
>
> src/hotspot/share/services/classLoadingService.cpp line 80:
>
>> 78:
>> 79: size_t ClassLoadingService::compute_class_size(InstanceKlass* k) {
>> 80: // lifted from ClassStatistics.do_class(Klass* k)
>
> Can you remove this line? I think that function is gone now.
Thanks Coleen for taking a look at this.
It is used internally by notify_class_loaded() and notify_class_unloaded();
therefore I will change it to have internal linkage.
> src/hotspot/share/services/finalizerService.cpp line 44:
>
>> 42: _ik(ik),
>> 43: _objects_on_heap(0),
>> 44: _total_finalizers_run(0) {}
>
> Is this hashtable for every InstanceKlass that defines a finalizer? How many
> are there generally? Why couldn't this be a simple hashtable like
> ResourceHashtable (soon to be renamed) which you can write in only a few
> lines of code?
This hashtable holds a FinalizerEntry for every InstanceKlass that provides a
non-empty finalizer method and have allocated at least one object. How many
there are in general depends on the application. A ResourceHashtable does not
have the concurrency property required, as lookups and inserts will happen as
part of object allocation.
> src/hotspot/share/services/finalizerService.cpp line 114:
>
>> 112:
>> 113: static inline void added() {
>> 114: set_atomic(&_count);
>
> Why isn't Atomic::inc() good enough here? It's used everywhere else.
Our Atomic implementation does not support CAS of a 64-bit value on 32-bit
platforms (compiles but does not link).
> src/hotspot/share/services/finalizerService.cpp line 123:
>
>> 121: static inline uintx hash_function(const InstanceKlass* ik) {
>> 122: assert(ik != nullptr, "invariant");
>> 123: return primitive_hash(ik);
>
> If the hash function is primitive_hash, this hash is good enough to not need
> rehashing. The only reason for the rehashing for symbol and string table was
> that the char* had a dumb hash that was faster but could be hacked, so it
> needed to become a different hashcode. This doesn't need rehashing.
Thank you for pointing that out. I had assumed this to be a part of the
syntactic contract for using the ConcurrentHashTable. My wrong assumption was
because the SymbolTable (which I used as a model) seemed to pass a
"rehash_warning" bool to the accessor APIs (get, insert). However, looking more
closely at the signatures in ConcurrentHashTable, that bool is a "grow_hint",
not "rehash" specifically. Thanks again; I will remove the rehash support code.
> src/hotspot/share/services/finalizerService.cpp line 485:
>
>> 483: void FinalizerService::purge_unloaded() {
>> 484: assert_locked_or_safepoint(ClassLoaderDataGraph_lock);
>> 485: ClassLoaderDataGraph::classes_unloading_do(_unloading);
>
> Since you remove entries on unloading, I don't see any reason to have any
> concurrent cleanup.
> You do however need in the lookup code, some code that doesn't find the
> InstanceKlass if !ik->is_loader_alive()
"Since you remove entries on unloading, I don't see any reason to have any
concurrent cleanup."
Thank you, that is true. The only concurrent work required will be to grow the
table.
"You do however need in the lookup code, some code that doesn't find the
InstanceKlass if !ik->is_loader_alive()"
A precondition is that the code doing the lookup hold the
ClassLoaderDataGraph_lock or is at a safepoint. Is that still the case? Would
not purge_unloaded() take out the InstanceKlass from the table, as part of
unloading, before !ik->is_loader_alive() is published to the outside world?
-
PR: https://git.openjdk.java.net/jdk/pull/4731
RFR: 8272515: JFR: Names should only be valid Java identifiers
Hi, Could I have a review of change that prevents invalid Java identifiers or type names in JFR events. For rationale and compatibility issues see the CSR request. The only change to java.base is making jdk.modules.internal.Checks::isJavaIdentifier(String) public, so it can be reused by the jdk.jfr module. Testing: /jdk/jdk/jfr + tier1 + tier2 Thanks Erik - Commit messages: - Improve guard against invalid type - Remove unused imports - Initial Changes: https://git.openjdk.java.net/jdk/pull/5415/files Webrev: https://webrevs.openjdk.java.net/?repo=jdk=5415=00 Issue: https://bugs.openjdk.java.net/browse/JDK-8272515 Stats: 308 lines in 11 files changed: 259 ins; 23 del; 26 mod Patch: https://git.openjdk.java.net/jdk/pull/5415.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/5415/head:pull/5415 PR: https://git.openjdk.java.net/jdk/pull/5415
Re: RFR: 8271820: Implementation of JEP 416: Reimplement Core Reflection with Method Handle [v8]
On Wed, 1 Sep 2021 01:05:32 GMT, Mandy Chung wrote: >> This reimplements core reflection with method handles. >> >> For `Constructor::newInstance` and `Method::invoke`, the new implementation >> uses `MethodHandle`. For `Field` accessor, the new implementation uses >> `VarHandle`.For the first few invocations of one of these reflective >> methods on a specific reflective object we invoke the corresponding method >> handle directly. After that we spin a dynamic bytecode stub defined in a >> hidden class which loads the target `MethodHandle` or `VarHandle` from its >> class data as a dynamically computed constant. Loading the method handle >> from a constant allows JIT to inline the method-handle invocation in order >> to achieve good performance. >> >> The VM's native reflection methods are needed during early startup, before >> the method-handle mechanism is initialized. That happens soon after >> System::initPhase1 and before System::initPhase2, after which we switch to >> using method handles exclusively. >> >> The core reflection and method handle implementation are updated to handle >> chained caller-sensitive method calls [1] properly. A caller-sensitive >> method can define with a caller-sensitive adapter method that will take an >> additional caller class parameter and the adapter method will be annotated >> with `@CallerSensitiveAdapter` for better auditing. See the detailed >> description from [2]. >> >> Ran tier1-tier8 tests. >> >> [1] https://bugs.openjdk.java.net/browse/JDK-8013527 >> [2] >> https://bugs.openjdk.java.net/browse/JDK-8271820?focusedCommentId=14439430=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-14439430 > > Mandy Chung has updated the pull request incrementally with one additional > commit since the last revision: > > minor cleanup and more test case. Hi Mandy, I'm still looking at this great work and have a few questions that I want to ask upfront. I understand the need for hard-coded specialization as opposed to inserting more MH transformations. You want to squeeze the startup costs as much as possible. But what I would like to understand is the need for MHInvoker and generated implementations of that interface. I can see that by making the target MH a constant in such generated MHInvoker, JVM is able to optimize the MH invocation chain better when JIT kicks-in. So instead of holding the reference to a target MethodHandle in say DirectMethodHandleAccessor, you hold a reference to MHInvoker. You trade constant MH optimization for indirection to a non-constant MHInvoker instance (I see @Stable annotation there, but it would only be effective when the holder MethodAccessor instance was also constant which unfortunately isn't as it is held by a volatile field in Method so even if Method was constant, its MethodAccessor would not be). So my question is whether this trade pays off. I wonder what the performance would be if: - MHInvoker was eliminated - the DirectMethodHandleAccessor just used the target MH directly (via @Stable field) but still using hard-coded specializations - AdaptiveMethodHandleAccessor would not be needed then - the Method had @Stable reference to MethodAccessor instead of volatile (data races are used everywhere so why not for this field too?) I guess you already tried this approach and later added MHInvoker "middleman" to optimize the warmed-up performance. If not, I can try that variant and come up with benchmark results to compare... - PR: https://git.openjdk.java.net/jdk/pull/5027
