[lworld] RFR: Prototype inline cursors for List
Roger.Riggs at oracle.com
Thu Mar 26 18:14:54 UTC 2020
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 ConcurrentModification.
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 instead.
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.
> If everything goes right, it should be has efficient as doing a for loop on the array.
Yep, that's the idea.
The cost avoidance of not doing allocation is hard to measure.
In some previous experiements, the extra data that had to be moved around
wiped out the savings by not having an identity object.
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.
> ----- 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