RFR: 8319797: Recursive lightweight locking: Runtime implementation [v3]

[Axel Boldt-Christmas]

On Mon, 13 Nov 2023 22:25:43 GMT, David Holmes <dholmes at openjdk.org> wrote:

>> Not sure I understand. 
>> 
>> The change here is that [for every object A, there exists no other object B such that A == B] is changed to [for every contiguous run of object A, there exists no other object B outside that run such that A == B]. Both of these checks are `O(n^2)` in the worst case, and the second is is `O(n)` in the best case. 
>> 
>> I think you have describe the algorithm you envision. Or maybe you want to change what property we are asserting.
>
> I thought the issue was that without recursion support we must never find an A and B such that A == B. But with recursion support we can allow A == B if they are adjacent in the lock-stock. So that is what the check is performing, but apparently in two loops, where I was suggesting it can perhaps be done in a single loop.

The recursive locking is more strict. There can only be one consecutive range of the same objects. (e.g. `AABCC` is allowed while `AABAA` is not.)

The outer loop finds (the two for loop constructs which works on the index `i`) iterates over each range of consecutive objects which are the same. (Picks out the object at the range start index bumps the index until the object is different, finding the range end index). 
And the inner loop (the for loop construct which works on the index `j`) asserts that no other entry is the same as the object in the this range. (Only walks higher indexes as the lower entries have already been checked in previous iterations).

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/16606#discussion_r1392074056