[lworld] RFR: Prototype inline cursors for List
forax at univ-mlv.fr
Thu Mar 26 19:38:22 UTC 2020
----- Mail original -----
> De: "Roger Riggs" <Roger.Riggs at oracle.com>
> À: "valhalla-dev" <valhalla-dev at openjdk.java.net>
> Envoyé: Jeudi 26 Mars 2020 19:14:54
> Objet: Re: [lworld] RFR: Prototype inline cursors for List
> Hi Remi,
> On 3/26/20 1:48 PM, Remi Forax wrote:
>> Hi Roger,
>> I think implementing remove() on a cursor is a bad idea, since we have
>> introduced Collection.removeIf() in 8 the main use case of remove() has
>> disappeared and it's still implemented by Iterator if someone really want it.
> Possibly, I was trying out what it takes for parity with Iterator.
>> In term of performance, it makes a huge difference because you can now implement
>> a snapshot at the beginning semantics, you don't have to be aware if the
>> XArrayList changes and you don't have to propagate back the structural change
>> done by remove(), so basically you can avoid the check for
> Yes simplifying the semantics would help, but that would not be an
> ArrayList but something else.
> Part of the exercise was to see where inline classes can subsitute for
> (assumed) more expensive identity classes.
>> With that, in the cursor, you can capture the array and the size when creating
>> it instead of capturing a reference to the enclosing class (XArrayList.this),
>> it should be a little more efficient.
>> I believe you can also remove the try/catch + rethrow and use Objects.checkIndex
> Unless the VM can eliminate the checks the implicit array range check
> should be cheaper/free.
> Or I misunderstand how try/catch is implemented by the vm.
yes, i hope the range check to be fully removed.
>> If everything goes right, it should be has efficient as doing a for loop on the
> Yep, that's the idea.
> The cost avoidance of not doing allocation is hard to measure.
especially when the escape analysis works
> In some previous experiements, the extra data that had to be moved around
> wiped out the savings by not having an identity object.
yes, when the cost of copy in a field or in an array is greater than the cost of dereferencing a pointer but here everything should be on the stack, so no trade-of.
> I've looked at the code with JMH and perfasm and
> I'll be looking more closely at the performance and any help is appreciated.
Here my implementation
BTW, i believe your implementation has a bug, the index can overflow in advance().
with mostly the same test, i use microseconds so the results are more readable and a 3 seconds duration to have more stable results
Cursors are now faster than iterators and a loop + get().
Benchmark (size) Mode Cnt Score Error Units
XArrayListCursorBenchMark.getViaArray 100000 avgt 5 345.798 ± 3.048 us/op
XArrayListCursorBenchMark.getViaCursorForLoop 100000 avgt 5 278.712 ± 2.501 us/op
XArrayListCursorBenchMark.getViaCursorWhileLoop 100000 avgt 5 278.281 ± 3.816 us/op
XArrayListCursorBenchMark.getViaIterator 100000 avgt 5 323.989 ± 4.374 us/op
XArrayListCursorBenchMark.getViaIteratorCurs 100000 avgt 5 312.738 ± 1.848 us/op
> Thanks, Roger
>> ----- Mail original -----
>>> De: "Roger Riggs" <rriggs at openjdk.java.net>
>>> À: "valhalla-dev" <valhalla-dev at openjdk.java.net>
>>> Envoyé: Jeudi 26 Mars 2020 18:14:10
>>> Objet: [lworld] RFR: Prototype inline cursors for List
>>> Implementation of Cursors and jmh tests comparing
>>> typical List traversal via direct index, iterator,
>>> inline cursor, and an iterator implemented on top of cursor.
>>> Sample results:
>>> (size) Mode Cnt Score Error Units
>>> XArrayListCursorTest.getViaArray 100000 avgt 5 507793.484
>>> 7086.038 ns/op
>>> XArrayListCursorTest.getViaCursorForLoop 100000 avgt 5 656461.958
>>> 52488.547 ns/op
>>> XArrayListCursorTest.getViaCursorWhileLoop 100000 avgt 5 641963.323
>>> 32219.409 ns/op
>>> XArrayListCursorTest.getViaIterator 100000 avgt 5 558863.817
>>> 23539.256 ns/op
>>> XArrayListCursorTest.getViaIteratorCurs 100000 avgt 5 733161.466
>>> 33721.881 ns/op
>>> Commit messages:
>>> - Prototype inline cursors for List
>>> Changes: https://git.openjdk.java.net/valhalla/pull/5/files
>>> Webrev: https://webrevs.openjdk.java.net/valhalla/5/webrev.00
>>> Stats: 2139 lines in 3 files changed: 2139 ins; 0 del; 0 mod
>>> Patch: https://git.openjdk.java.net/valhalla/pull/5.diff
>>> Fetch: git fetch https://git.openjdk.java.net/valhalla pull/5/head:pull/5
> >> PR: https://git.openjdk.java.net/valhalla/pull/5
More information about the valhalla-dev