[lworld] RFR: Prototype inline cursors for List

[Remi Forax]

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

Hi Roger,

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

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
>> array.
> 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
  https://github.com/forax/valuetype-lworld/blob/master/src/main/java/fr.umlv.valuetype/fr/umlv/valuetype/xlist/XArrayList.java#L1130
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
  https://github.com/forax/valuetype-lworld/blob/master/src/test/java/fr.umlv.valuetype/fr/umlv/valuetype/perf/XArrayListCursorBenchMark.java#L21

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
> 

cheers,
Rémi

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