[lworld] RFR: Prototype inline cursors for List
Roger.Riggs at oracle.com
Thu Mar 26 20:14:43 UTC 2020
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
>> 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 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
> 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
> 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
More information about the valhalla-dev