Re: Are there real use cases with the Java access modes?

JIT has to decide if the loop condition can be hoisted.  JIT halts the
hoisting optimization even on the world "full of nontrivial things"... and
if not the JIT team gets a bug to fix.  Hence, I suspect JIT is
conservative on how deep it tries to examine to figure out if the condition
can be hoisted.  I suspect that when JIT does not know what the destination
is (e.g. Runnable.run()), then it halts.

So, the PMD rule needs to be at least as good as JIT at determining if the
variable can be hoisted.  This will prevent unintentional infinite loops at
run time.  If the PMD rule is better than JIT, then that is just a bonus
for the programmer.  I suspect the PMD rule can be better than JIT.  If I
understand correctly, JIT is limited to looking at what is inlined due to
runtime constraints.  PMD can has the time to go much deeper.  Also, if the
loop calls Runnable.run(), then PMD can look at all classes that implement
Runnable.  Yes, this will mean false negatives, but as long as it is better
than JIT who cares.

If the PMD rule cannot be as good as JIT, then the PMD rule will catch most
unintentional infinite loops and has a few false negatives for the
nontrivial things.  This is much better than no PMD rule.  However, for
those that use Graal, the PMD rule can be just as good as Graal since Graal
produces a single executable (i.e. a closed system).

On Thu, Jul 22, 2021 at 7:38 AM Alex Otenko <[email protected]>
wrote:

> I think the problem is still the halting problem. You only have the text
> of the program, and you need to decide not only that quit=true exists, but
> that it is reachable from the loop body.
>
> There are trivial cases where you can do this, but the world is full of
> nontrivial things. Say, createRandom...NP sets quit=true. Now what? Say, a
> subclass overrides createRandom...NP. Now what? Say, you call someone that
> has reference to this, and calls createRandom...NP. Now what? Is it the
> same instance or not?
>
> Etc, etc, etc
>
> The bottom line is: often there is no simple answer to a complex problem,
> and infinitely often there is no answer.
>
> Alex
>
>
> On Thu, 22 Jul 2021, 13:46 Nathan Reynolds via Concurrency-interest, <
> [email protected]> wrote:
>
>> It is not quite the halting problem.  The halting problem asks if the
>> computation ends.  The PMD rule asks if among the many branches inside the
>> loop's call tree if the exit variable is set.  It does not care if the
>> branch is never taken.
>>
>> Consider this code...
>>
>> private boolean quit;
>>
>> while (!quit)
>> {
>>    createRandomAlgorithmInPforNP();
>>
>>    if (doesAlgorithmWork())
>>    {
>>       quit = true;
>>    }
>> }
>>
>> The method createRandomAlgorithmInPforNP() creates a random algorithm
>> that runs in polynomial time and hopefully solves a NP problem.  The method
>> doesAlgorithmWork() tests the created algorithm to see if it works.  This
>> is an example of a halting problem.  We don't 100% know if an algorithm
>> will ever be found and hence if the loop will run forever.
>>
>> But, this does not matter for the PMD rule.  The PMD rule only cares that
>> there is a "quit = true" in the loop body (or in the call tree).  Why?  The
>> PMD rule is looking to see if "while (!quit)" can be hoisted out of the
>> loop thus creating an infinite loop.  It will execute the same logic that
>> JIT does to determine if "while (!quit)" can be hoisted.  We have working
>> code (i.e. JIT) that we can use to implement the PMD rule.
>>
>> On Thu, Jul 22, 2021 at 2:35 AM Andrew Haley via Concurrency-interest <
>> [email protected]> wrote:
>>
>>> On 7/21/21 4:50 PM, Nathan Reynolds via Concurrency-interest wrote:
>>>
>>> > Sounds like a job for a linter.  For easier cases, an easy PMD rule
>>> > will catch such a problem.  For harder cases, the PMD rule will need
>>> > to traverse the call tree to see if a thread executing the loop
>>> > could change the field.  If not, flag a problem to the programmer.
>>>
>>> I suspect that getting this right (no false positives or negatives) is
>>> equivalent to the halting problem, i.e. it's uncomputable. The best
>>> you can say is that if an expression used as the exit condition of a
>>> loop has a term hoisted from memory, the loop might not terminate.
>>>
>>> However, while linting for that provides some information to the naive
>>> programmer, it "solves" the problem of infinite loops but ignores
>>> silently returning false results.
>>>
>>> --
>>> Andrew Haley  (he/him)
>>> Java Platform Lead Engineer
>>> Red Hat UK Ltd. <https://www.redhat.com>
>>> https://keybase.io/andrewhaley
>>> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing list
>>> [email protected]
>>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> [email protected]
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>

_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest