[lworld] RFR: Prototype inline cursors for List

[Roger Riggs]

Hi Remi,

yes, with those modifications its faster, but its not a Cursor for ArrayList
since CME is possible and not checked.
That would be appropriate for CopyOnWriteArraylist for example.

We also have a chance to create new implementations of List, etc.

I do want to understand where the pitfalls are when attempting
to improve implementations by replacing with inline classes.

On 3/26/20 3:38 PM, Remi Forax wrote:
> ----- 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://urldefense.com/v3/__https://github.com/forax/valuetype-lworld/blob/master/src/main/java/fr.umlv.valuetype/fr/umlv/valuetype/xlist/XArrayList.java*L1130__;Iw!!GqivPVa7Brio!KDKclikzivMcFelPyi433ivEn2MsWszmcVnYc16HMeRowkPFjlf386atqiTjAFWU$
> BTW, i believe your implementation has a bug, the index can overflow in advance().
That was intentional, since anything >= size is out of range anyway
and it has to be checked in get().
It wasn't worth an extra check.
>
> 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://urldefense.com/v3/__https://github.com/forax/valuetype-lworld/blob/master/src/test/java/fr.umlv.valuetype/fr/umlv/valuetype/perf/XArrayListCursorBenchMark.java*L21__;Iw!!GqivPVa7Brio!KDKclikzivMcFelPyi433ivEn2MsWszmcVnYc16HMeRowkPFjlf386atqpU5B1iE$
>
> 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

Good.

Thanks, Roger