Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

How far can the JVM go removing dead code?  RSS feed

 
Avor Nadal
Ranch Hand
Posts: 156
Java Netbeans IDE Postgres Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello:

Yesterday I read the document "One VM, Many Languages" from John Rose and Brian Goetz. It was very clarifying. I saw an example in which a method was inlined first, and then the JVM removed a check of null of a variable because it was obvious that the variable in question could never be null. It was considered dead code.

So I was wondering who far can the JVM go to detect dead code in if-else and switch blocks. Does it only recognise null checks or can it also do comparisons with primitive types? And what about Strings?

For example:



If the JVM decided to inline the method doSomethingElse in doSomething, Could it detect that the value of type is constant and remove the switch block at all? What if this block were of type if-else instead of switch?



In the page #7 of the document, they mention a list of optimizations that the HotSpot JVM can do. Maybe one or two of them are the answers to my questions. However, I get lost with so many technical terms :/ .

Thank you!
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Avor Nadal wrote:So I was wondering who far can the JVM go to detect dead code in if-else and switch blocks. Does it only recognise null checks or can it also do comparisons with primitive types? And what about Strings?

Simply put: No idea. And without knowing the person/people who wrote the JVM, and how they were thinking, neither could anybody else.

If your question is: What could a JVM divine as "dead code"? The answer is: probably all of it (or close to).

The question then becomes one of common sense: Where does the time and complexity required to find a piece of dead code outweigh the value in finding it?

And the answer, I suspect, is "fairly early". I suspect there are a few simple checks that can find a large amount of rotting statements; but as you try to get "cleverer", the amount (or value) of what you find diminishes, and adds a lot of unnecessary complexity.

And in those situations, I've usually found the 80:20 rule a pretty good one to live by.

However, I'm not a JVM writer, so it's pure speculation.

Winston
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think Winston is pretty much spot on. I would add that HotSpot (or any other JVM) may at any given moment decide *not* to compile a particular method to native code, or *not* to unroll a loop, or *not* to inline a method, or *not* to perform any number of other optimizations that it can do in principle, because it thinks that would not be the best thing to do at that particular moment. All such decisions are liable to be revisited (and possibly reversed) during the JVM runtime due to the data the JVM gathers about code execution, and the analytics it performs on that data.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulf Dittmer wrote:All such decisions are liable to be revisited (and possibly reversed) during the JVM runtime due to the data the JVM gathers about code execution, and the analytics it performs on that data.

Ulf, this question is just for my own interest, and I don't want to usurp the thread:

It seems to me that the decision about "when is enough" is a recursive one, and on the same lines as the Heisenberg Principle; so I wonder if the "80:20" principle is some sort of general limit.

Sometimes, I really wish I was a mathematician instead of a mere programmer.

Winston
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't know that there is much uncertainty about it, or that the 80:20 rule applies. The JVM gathers statistics about which methods are called how often, and how long their execution takes. It also can make very reasonable estimates what overhead would be involved in compiling or inlining them, and how much faster a native or inlined method would execute. So its decisions on which optimizations make sense can be based on pretty hard numbers. Those include the available memory and the current CPU utilization, so, for example, if a JVM has plenty of memory and rarely taxes the CPU above 20%, it's probably a good guess that all optimizations will be done, as the resource overhead can easily be absorbed.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulf Dittmer wrote:The JVM gathers statistics about which methods are called how often, and how long their execution takes....

Oh right. I had no idea it was doing quite so much stuff in the background, TBH. Cheers for that.

Does that mean that it might change how it executes a class or method over time? Or is a class, once loaded, frozen?

Winston
 
Tim Cooke
Marshal
Posts: 3870
233
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The OP's example is pretty simple. It's clear to determine that the value of 'type' is always going to be "C" because it's hard coded just above the switch statement.

Where things get a little unpredictable, and this is related to Ulf's discussion on the gathering of statistics, is when the JVM can inline a variable read statement if it hasn't changed after x number of reads.

For example:
Say we are implementing a queue. The queue itself is an array, there's a producer thread putting stuff on the queue, and a consumer thread reading stuff from the queue. An array slot is empty if it contains null. On the consumer end, there's a thread that simply spins on the array reading the values looking for a non-null slot to read and remove from the queue. There's an infinite loop of 'array[index]' calls.

All sounds ok right? Wrong. Let's say the queue is quiet and the consumer spins reading null every time from the array slots. After x number of reads (10s or 100s of thousand) the compiler makes a decision that the read calls will never produce anything but null and will inline that code to just null. So now when the producer puts something on the queue, the consumer will never read it.

I learned this from Martin Thompson when he was teaching us how to write low latency lock free algorithms earlier this year.
 
Avor Nadal
Ranch Hand
Posts: 156
Java Netbeans IDE Postgres Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First, thank you all for your answers .

Winston Gutkowski wrote:The question then becomes one of common sense: Where does the time and complexity required to find a piece of dead code outweigh the value in finding it?


That's a very reasonable concern. Although it doesn't look like that, I want to clarify that I had it too, he he he. I agree that the optimization that I asked about in my previous message requires an analysis that is more complex than a simple null check. But I really wanted to know if this kind of optimization is at least considered by the JVM (if it's be able to do so), even although it's applied very sparsely. I understand that it's complicated to know that, because as you have mentioned, only someone who has designed HotSpot can know it. But I had the hope that this type of information had been leaked sometime, as others have ;) .

I've also have been thinking carefully about the 2 examples that I presented in my first message and I believe that a switch block could be optimized easier than an if-else block. Because the former has a very well known structure, whereas the latter can include any kind of comparison (not only equality). Even a switch with Strings it's easier, because the translation to bytecode is formed by a lookupswitch and a tableswitch (again, well known structures). However, as you mentioned, the JVM would need to decide it it's worth it.
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm fairly certain that the JVM would not make optimizations on a sub-method level at runtime. If "doSomethingElse" is not called with any parameter but "C", then the javac compiler could in theory optimize some of the code away. I don't know if it does; but you can check by examining the generated bytecode if you're really interested. See http://www.javaranch.com/journal/200607/ThreadsAndJavap.html for an introduction to using javap for this.
 
Avor Nadal
Ranch Hand
Posts: 156
Java Netbeans IDE Postgres Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ulf Dittmer wrote:I'm fairly certain that the JVM would not make optimizations on a sub-method level at runtime. If "doSomethingElse" is not called with any parameter but "C", then the javac compiler could in theory optimize some of the code away. I don't know if it does; but you can check by examining the generated bytecode if you're really interested. See http://www.javaranch.com/journal/200607/ThreadsAndJavap.html for an introduction to using javap for this.


Thanks. Yes, I did. But the method remained as if the parameter "C" came from a regular variable and it wasn't hard-coded. Or at least that was what I was able to interpret from the javap output. I guess that the developers could make javap do this optimization (and many others) but they don't to keep the compiler as much simple as possible.

That's why I hoped that the JVM took care of it... Providing that the method were inlined, of course. Indeed, one of the first things that I checked was the size of the method doSomethingElse. If the switch compares ints, the size is moderate and it's likely that it can be inlined (with the default value of +MaxInlineSize). However, if the switch compares Strings, the size grows much more (in terms of bytecode) and can only be inlined if it's considered a hot spot and it doesn't exceed the maximum size. Running java with the flag -XX:+PrintInlining confirms that.

So I guess that, in practice, this kind of optimization could only be done after lots and lots of calls to the method. First, so that the JVM inlines the method. And later, so that the JVM collects enough statistics.
 
Avor Nadal
Ranch Hand
Posts: 156
Java Netbeans IDE Postgres Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim Cooke wrote:All sounds ok right? Wrong. Let's say the queue is quiet and the consumer spins reading null every time from the array slots. After x number of reads (10s or 100s of thousand) the compiler makes a decision that the read calls will never produce anything but null and will inline that code to just null. So now when the producer puts something on the queue, the consumer will never read it.


Although I was speaking about a constant value, I find that very interesting. Have you ever seen that in a real application? Because it would be really serious :O .
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Avor Nadal wrote:But I had the hope that this type of information had been leaked sometime, as others have ;) .

But even if that's true, what you'll know is how that JVM does it; it's unlikely to be a universal choice (unless someone comes up with some optimizing "mousetrap" that's so good that it simply can't be ignored).

So you come back to the "how much is enough?" question: I suspect there are broad generalisations you can probably make about most JVMs, but mor granular optimizations are likely to be down to individual authors.

As they say: To understand recursion, you must first understand recursion...

Winston
 
Tim Cooke
Marshal
Posts: 3870
233
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Avor Nadal wrote:Have you ever seen that in a real application? Because it would be really serious :O .

I haven't seen it personally, but I'm sure you could replicate it easily enough.

This is an issue that Martin Thompson encountered when he was writing a low latency queue for the LMAX Disruptor framework.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!