[lworld] RFR: Prototype inline cursors for List

Remi Forax forax at univ-mlv.fr
Thu Mar 26 17:48:37 UTC 2020


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.
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.

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.

If everything goes right, it should be has efficient as doing a for loop on the array.

regards,
Rémi

----- 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 mailing list