3

So I was examining the Integer's class source code (JDK 8) to understand how an int get converted to a String. It seems to be using a package private method called getChars (line 433) to convert an int to char array.

While the code is not that difficult to understand, however, there are multiple lines of code where they use bitwise shift operations instead of simple arithmetic multiplication/division, such as the following lines of code:

// really: r = i - (q * 100);
r = i - ((q << 6) + (q << 5) + (q << 2));

and

q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...

I just do not understand the point of doing that, is this actually an optimization and does it affect the runtime of the algorithm?

Edit:

To put it in a another way, since the compiler does this type of optimization internally, is this manual optimization necessary?

Community
  • 1
  • 1
razz
  • 9,770
  • 7
  • 50
  • 68
  • 1
    Does this answer your question? [Is shifting bits faster than multiplying and dividing in Java? .NET?](https://stackoverflow.com/questions/1168451/is-shifting-bits-faster-than-multiplying-and-dividing-in-java-net) – pafau k. May 28 '20 at 12:30
  • 1
    Well as far as I understand that [compilers does this optimization for us](https://stackoverflow.com/a/1168616/2038544), so why bother do that manually? – razz May 28 '20 at 12:34
  • One part of the answer might be [doing unsigned operations](https://stackoverflow.com/questions/9247804/why-does-jdk-use-shifting-instead-of-multiply-divide). Also you can't ensure you're always working in optimized environment. – pafau k. May 28 '20 at 12:44
  • @razz Well, you'd have to ask the authors of the code in order to know that... Random people on the Internet _guessing_ why someone did something a particular way isn't going to be useful, is it? – Sweeper May 28 '20 at 12:44
  • @Sweeper It is just my understanding that because it is in the official source code of Java then there must be a good reason, I might be wrong though. – razz May 28 '20 at 12:46
  • A compiler *might** optimize `q * 10` to the equivalent of `((q << 3) + (q << 1))`. Or it **might not**. "Pre-optimizing" the source code by actually writing `((q << 3) + (q << 1))` rather than `q * 10` removes all doubt. – Kevin Anderson May 28 '20 at 12:58
  • One reason may be that it's not worth to refactor. Why would you? It's running and is efficient. Maybe there're even some preferences of the developers involved. I think the biggest reason is that writing efficient code directly is more robust than relying on the compiler. Then you have to know *exactly* what you are doing of course, but if you do, it's probably more reliable. – akuzminykh May 28 '20 at 13:03

2 Answers2

3

I don't know the reason for this specific change and unless you find the original author, it's unlikely you'll find an authoritative answer to that anyway.

But I'd like to respond to the wider point, which is that a lot of code in the runtime library (java.* and many internal packages) is optimized to a degree that would be very unusual (and I dare say irresponsible) to apply to "normal" application code.

And that has basically two reasons:

  1. It's called a lot and in many different environment. Optimizing a method in your server to take 0.1% less CPU time when it's only executed 50 times per day on 3 servers each won't be worth the effort you put into it. If, however, you can make Integer.toString 0.1% faster for everyone who will ever execute it, then this can turn into a very big change indeed.
  2. If you optimize your application code on a specific VM then updating that VM to a newer version can easily undo your optimization, when the compiler decides to optimize differently. With code in java.* this is far less of an issue, because it is always shipped with the runtime that will run it. So if they introduce a compiler change that makes a given optimization no longer optimal, then they can change the code to match this.

tl;dr java.* code is often optimized to an insane degree because it's worth it and they can know that it will actually work.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
2

There are a couple reasons that this is done. Being a long-time embedded developer, using tiny microcontrollers that sometimes didn't even have a multiplication and division instruction, I can tell you that this is significantly faster. The key here is that the multiplier is a constant. If you were multiplying two variables, you'd either need to use the slower multiply and divide operators or, if they didn't exist, perform multiplication using a loop with the add operator.

Steve Moyer
  • 5,663
  • 1
  • 24
  • 34