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

JIT can speculate (as we've seen a spectacular example of recently) and
recompile. This alone makes PMD's task intractable.

Alex

On Thu, 22 Jul 2021, 15:39 Nathan Reynolds, <[email protected]> wrote:

> 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