This week's book giveaways are in the Jython/Python and Object-Oriented programming forums.
We're giving away four copies each of Machine Learning for Business: Using Amazon SageMaker and Jupyter and Object Design Style Guide and have the authors on-line!
See this thread and this one for details.
Win a copy of Machine Learning for Business: Using Amazon SageMaker and JupyterE this week in the Jython/Python forum
or Object Design Style Guide in the Object-Oriented programming forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Paul Clapham
  • Jeanne Boyarsky
  • Knute Snortum
Sheriffs:
  • Liutauras Vilda
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Joe Ess
  • salvin francis
  • fred rosenberger

Can JIT Optimization break valid code

 
Sheriff
Posts: 9671
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Howdy Ranchers,

I was recently told by a colleague that JVM optimizes for loops which use int counter and if the condition contains an object which can change, my code might break. Let's take at an example piece of code:
[Edit] FYI I've written this code just as an example, I just wanted to show code in which the loop condition has a list which is changing. The OOM is expected behaviour just for this example.
[Edit: The condition was wrong in the above code so I fixed it after Campbell pointed out the issue. When I posted this initially the loop looked like this: for(int i = 1; i < strList.size(); i++)
Since this piece of code keeps adding an item to the List, it fails with OOM error every time I run it.
As per my colleague, JVM/JIT can optimize/cache the call to strList.size() and under certain circumstances (when memory is low and a few other things) the loop might exit after few iterations as the value of i may be more than the cached value of strList.size().

I'm not able to find anything which proves this claim right or wrong. As per me if this code exits without OOM, it is a bug in JVM. The List is local variable, not shared between threads, and JVM/JIT should be smart enough to know that it cannot cache the value of strList.size().

What are your thoughts on this?
 
Marshal
Posts: 67464
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Don't know, but if that does happen it is, as you say, both a bug and a failure to comply with the semantics of the JLS. I suspect your colleague is mistaken.

Since you are altering the continuation condition along with the execution of the loop, I think you have designed yourself a loop whose behaviour is not well defined. I think that is your problem; it is behaving like an infinite loop until you get your OutOfMemoryError.
 
Campbell Ritchie
Marshal
Posts: 67464
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Only I tried it on JShell, and before I ran it, I thought, “That isn't going to run at all.” And lo and behold, the loop duly runs 0×!

Campbell's JShell wrote:jshell> List<String> strList = new ArrayList<>(); strList.add("x0"); for(int i = 1; i < strList.size(); i++) { strList.add("x" + i); } <br /> strList ==> []
$4 ==> true

jshell> strList
strList ==> [x0]

Maybe you meant to start your for loop with ...i = 0;
 
Saloon Keeper
Posts: 21603
147
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You should never code with the expectation of an OOM other than to avoid one. Certainly you should not expect an OOM to be totally predictable, since it's the result of the sum total of everything running in the JVM plus the JVM's memory settings.

An Out of Memory Exception is generally NOT considered a mark of "valid code". It's more of an admission that you don't have things under control, and it's really not something to trap and recover from, since the overhead of the recovery process can itself trigger further OOMs. So OOM is almost universally instantly fatal.

There are several forms of loop optimization, but I think the one you're referring to is "loop unrolling". Since an increment/decrement and test take up a small, but finite amount of overhead, for small loops it's more efficient to simply replicate the loop body code and eliminate those parts. Note that in order to do that you have to be able to predict at compile time (or at least before execution) just how many iterations would be required, since you're generating a fixed block of code. Also, there's a limit on the count, since the amount of code generated is going to be "n" times the code in the loop body. For small loop bodies and small iteration counts (less than 10 or 20), the percentage of extra code versus true iteration is small, but as things get bigger, that advantage is offset by extra memory usage.
 
Ankit Garg
Sheriff
Posts: 9671
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Guys for your replies.

Cambell, sorry I missed to put the = in the condition, I've fixed it now to make it <=. I originally wrote the loop starting at 0, then I realized then it would put two "x0" values in the List, so my OCD kicked-in and I changed the loop to start from 1

I just wrote this code as an example to keep it simple, my actual code in question was doing a BFS by popping/pushing in the same list/queue which I was iterating on. I don't write actual production code expecting OOM

[Edit] For clarity, my actual code where we had the discussion at work looked something like this (maybe I should've put this code in the original post in the first place):
[/Edit]
I event tried to find something in the JSL, it is stated in the JLS that the expression is evaluated without any details of any possible optimization.

As much as I know about memory model, when only a single thread is involved, any caching of values cannot break documented behavior. If multiple threads are involved obviously things get much more complicated.

My problem with my colleagues explanation is, by his logic any loop can become infinite if the expression value is cached. For example this code can be an infinite loop if the return value of isEmpty call is cached:
 
Tim Holloway
Saloon Keeper
Posts: 21603
147
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ankit Garg wrote:
As much as I know about memory model, when only a single thread is involved, any caching of values cannot break documented behavior. If multiple threads are involved obviously things get much more complicated.



And you should never assume that a JVM is only running one thread. In some, I think, the garbage collector has its own thread, and other internal housekeeping threads are also possible. I would venture to suspect that even in a totally single-threaded environment, the memory management system's use of internal unused block links would be subject to random variation, thus putting some "fuzz" into the memory subsystem.

Ankit Garg wrote:
My problem with my colleagues explanation is, by his logic any loop can become infinite if the expression value is cached. For example this code can be an infinite loop if the return value of isEmpty call is cached:



The expression value cannot be cached unless the compiler can definitely determine that the code is 100% idempotent. Just because you unroll a loop doesn't mean that you can ignore side-effects. Also, recall that I said that loops can only be unrolled if the compiler can determine that a fixed number of iterations will always be made. Once you add additional loop termination conditions, unrolling is no longer really viable - the whole point of loop unrolling is that you can delete the increment/decrement and test, and keeping the test even if you could avoid the increment would not save nearly as much. Indeed, on some machines, the test is more overhead than the incrementing.
 
Ankit Garg
Sheriff
Posts: 9671
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Tim. When I said single thread I meant my code itself is not starting any thread and the data is not shared between my application threads.

The expression value cannot be cached unless the compiler can definitely determine that the code is 100% idempotent


EXACTLY my point, the compiler/JVM should not cache the value returned by the method call unless it is 100% sure the value can be cached (thus the method call can be skipped) without changing the behaviour of the code. Any instruction reordering or optimization should not break expected behaviour. But apparently these optimizations and caching done by the JVM are not documented very well so I'm trying to find proof/documentation of it (if any).
 
Saloon Keeper
Posts: 11188
244
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Any such optimizations would be documented in the VM Spec, not the JLS. Even then, the specs only describe what an implementation MUST do, not what an implementation MAY do, so you won't know about optimizations a specific vendor has made unless their implementation is open source.

It doesn't matter that much though. Compiler/JIT optimizations should be completely invisible to a single-threaded application. Your colleague is mistaken when they say that your code might break. It was already broken, and Campbell has pointed out the reason.
 
Tim Holloway
Saloon Keeper
Posts: 21603
147
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're not likely to. Compiler optimizations are almost entirely at the discretion of the compiler implementer, not part of the language definition. By definition, an "optimization" that does not exactly replicate the functionality (though not necessarily the timing and memory usage) of the code it replaces is a defective optimization (a/k/a bug) and not a true implementation of the language itself.

Also note that in many compilers, the aggressiveness of the optimizer and the techniques it will employ can be fine-tuned, as for example the "desktop" and "server" optimization levels on the Sun JVM.

But remember that trying to think ahead of the compiler is premature optimization. And if you try and optimise instruction sequences manually, you're actually likely to short-circuit optimization options that the compiler can take advantage of. It's best to write straightforward code and trust the compiler. And only AFTER a performance problem is seen should you start worrying about instruction-level optimization. Which leads to the 2 most fundamental rules of optimization:

1. The bottleneck is never where you "know" it's going to be (trust me, I've spent years observing this!)

2. Picking a more appropriate algorithm will speed things up much more than instruction twiddling 99.9997% of the time. As I frequently mention, I once optimized a process by using a "less efficient" sort algorithm because it performed optimally for the data it would work with whereas the "more efficient" sorts would all see that data as worst-case.
 
Ranch Hand
Posts: 118
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Only I tried it on JShell, and before I ran it, I thought, “That isn't going to run at all.” And lo and behold, the loop duly runs 0×!

Campbell's JShell wrote:jshell> List<String> strList = new ArrayList<>(); strList.add("x0"); for(int i = 1; i < strList.size(); i++) { strList.add("x" + i); } <br /> strList ==> []
$4 ==> true

jshell> strList
strList ==> [x0]

Maybe you meant to start your for loop with ...i = 0;


You got the condition wrong - look again closely - in the top post OP had: "i <= list.size()" - as one item is added before the list has a size of 1 - when i is init to 1 it matches the condition: 1 is smaller than or equal to 1 - hence the train runs off ...
 
Ankit Garg
Sheriff
Posts: 9671
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kristina Hansen wrote:You got the condition wrong - look again closely - in the top post OP had: "i <= list.size()" - as one item is added before the list has a size of 1 - when i is init to 1 it matches the condition: 1 is smaller than or equal to 1 - hence the train runs off ...


Hi Kristina, I actually fixed the condition after Campbell pointed out the issue. Apologies for the confusion. As I mentioned in my reply, my OCD caused the issue as after I wrote the code in my IDE and pasted it here, I edited the code

Stephan wrote:It doesn't matter that much though. Compiler/JIT optimizations should be completely invisible to a single-threaded application.


Tim wrote:By definition, an "optimization" that does not exactly replicate the functionality (though not necessarily the timing and memory usage) of the code it replaces is a defective optimization (a/k/a bug) and not a true implementation of the language itself.


Thanks Stephan & Tim. This is my understanding as well. I'm trying to find something similar mentioned in VM spec or some other official documentation to use as a "proof"
 
Tim Holloway
Saloon Keeper
Posts: 21603
147
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're not likely to find my definition of optimization in the official Java docs. It's more of an axiom in general compiler design. and thus implied rather than explicitly stated.

While some of my older mainframe language manuals did stress that optimization was likely to affect resource usage - back then optimization was more likely to be an extra-cost option than the rule - these days I think we more or less take it for granted.
 
Campbell Ritchie
Marshal
Posts: 67464
257
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Kristina Hansen wrote:. . . You got the condition wrong  . . .

Damn!
I even used drag'n'drop to pass the code to JShell, so I wouldn't notice such an error.
 
Ankit Garg
Sheriff
Posts: 9671
42
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all for the insights, appreciate the responses. Now I know my code was right (not the example code which throws OOM, the BFS one )

Campbell Ritchie wrote:I even used drag'n'drop to pass the code to JShell, so I wouldn't notice such an error.


That was me editing the post, sorry about that.
 
Create symphonies in seed and soil. For this tiny ad:
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps
https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!