[lworld] RFR: Prototype inline cursors for List

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Roger Riggs" <Roger.Riggs at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "valhalla-dev" <valhalla-dev at openjdk.java.net>
> Envoyé: Jeudi 26 Mars 2020 21:14:43
> Objet: Re: [lworld] RFR: Prototype inline cursors for List

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

Or document that you may seen null when you iterate using a Cursor.

Another possible more heavy lifting isto  change the implementation of ArrayList to have all removes + add at the beginning (add(int, E)) to create a new array.
(having a flag that say if at least one iterator was spawn may alleviate a little bit the pain).
But i think it defeats the diminish the appeal of ArrayList as being the go to, general purpose list.

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

the problem is that reading modCount is what's make the implementation slow, i.e. as slow as the iterator when EA works.

Rémi 

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