[lworld] RFR: Prototype inline cursors for List
forax at univ-mlv.fr
forax at univ-mlv.fr
Thu Mar 26 20:57:33 UTC 2020
----- 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.
> 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
>>> 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
>>> 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
>>> 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
>>> 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
>> BTW, i believe your implementation has a bug, the index can overflow in
> 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
>> 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
More information about the valhalla-dev