Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Java optimizer and redundant array evaluations

This is a very basic question about the Java optimization.

If you have a simple for loop to iterate through an array and use array.length in the header of the loop rather than evaluating it before so that you do it only once (which is what I almost always do):

for(int i=0; i<array.length;i++) { ... }

Can the statement be optimized so that the JVM knows whether the array is changing for the duration of the loop so that it does not reevaluate array.length every time?

like image 939
amphibient Avatar asked Feb 05 '13 15:02

amphibient


3 Answers

if another thread is not modifying the array concurrently, will array.length be effectively evaluated only once,

More critically, unless the field is volatile the JVM will make this assumption whether it is true or not.

like image 186
Peter Lawrey Avatar answered Sep 30 '22 13:09

Peter Lawrey


Arrays in Java are fixed length. The length cannot be changed after the array is created. There is no advantage to grabbing the length first and assigning it to a local variable.

like image 41
Steve Kuo Avatar answered Sep 30 '22 14:09

Steve Kuo


After spending way too much time debugging this, I got:

A:

  static String test(String[] arg){
     String a  ="";
     for(int i = 0, len = arg.length; i < len; i++)
      if (arg[i].length() > a.length()) a = arg[i];
     return a;
  }

B:

  static String test(String[] arg){
    String a  ="";
    for(int i = 0; i < arg.length; i++)
      if (arg[i].length() > a.length()) a = arg[i];
    return a;
  }

A byte code:

 static java.lang.String test(java.lang.String[]);
  Code:
   0:   ldc #2; //String 
   2:   astore_1
   3:   iconst_0
   4:   istore_2
   5:   aload_0
   6:   arraylength
   7:   istore_3
   8:   iload_2
   9:   iload_3
   10:  if_icmpge   36
   13:  aload_0
   14:  iload_2
   15:  aaload
   16:  invokevirtual   #3; //Method java/lang/String.length:()I
   19:  aload_1
   20:  invokevirtual   #3; //Method java/lang/String.length:()I
   23:  if_icmple   30
   26:  aload_0
   27:  iload_2
   28:  aaload
   29:  astore_1
   30:  iinc    2, 1
   33:  goto    8
   36:  aload_1
   37:  areturn

B byte code:

 static java.lang.String test(java.lang.String[]);
  Code:
   0:   ldc #2; //String 
   2:   astore_1
   3:   iconst_0
   4:   istore_2
   5:   iload_2
   6:   aload_0
   7:   arraylength
   8:   if_icmpge   34
   11:  aload_0
   12:  iload_2
   13:  aaload
   14:  invokevirtual   #3; //Method java/lang/String.length:()I
   17:  aload_1
   18:  invokevirtual   #3; //Method java/lang/String.length:()I
   21:  if_icmple   28
   24:  aload_0
   25:  iload_2
   26:  aaload
   27:  astore_1
   28:  iinc    2, 1
   31:  goto    5
   34:  aload_1
   35:  areturn

The important difference is line 33/31, where the goto jumps either to line 8 or 5. After (A) and before (B) the call of arraylength.

So without caching the length the bytecode actually does call arraylength in every iteration.

Of course javac does not optimize, only the JIT does. So what does the JIT do?

Usually nothing it seems. It was not listed in the -XX:+PrintCompilation list of compiled methods.

Only after calling the function 1 million times, it activated and removed the length check completely by unrolling the loop, if I read it correctly:

A disassembled:

# parm0:    rsi:rsi   = '[Ljava/lang/String;'
  #           [sp+0x30]  (sp of caller)
  0x00007fdc296b30a0: mov    %eax,-0x6000(%rsp)
  0x00007fdc296b30a7: push   %rbp
  0x00007fdc296b30a8: sub    $0x20,%rsp         ;*synchronization entry
                                                ; - Acminesimple::test@-1 (line 3)
  0x00007fdc296b30ac: mov    0xc(%rsi),%ebp     ;*arraylength
                                                ; - Acminesimple::test@6 (line 4)
                                                ; implicit exception: dispatches to 0x00007fdc296b31ad
  0x00007fdc296b30af: movabs $0xeb8b7168,%rax   ;   {oop("")}
  0x00007fdc296b30b9: test   %ebp,%ebp
  0x00007fdc296b30bb: jle    0x00007fdc296b312e  ;*if_icmpge
                                                ; - Acminesimple::test@10 (line 4)
  0x00007fdc296b30bd: test   %ebp,%ebp
  0x00007fdc296b30bf: jbe    0x00007fdc296b3177
  0x00007fdc296b30c5: mov    %ebp,%ecx
  0x00007fdc296b30c7: dec    %ecx
  0x00007fdc296b30c9: cmp    %ebp,%ecx
  0x00007fdc296b30cb: jae    0x00007fdc296b3177
  0x00007fdc296b30d1: xor    %r8d,%r8d          ;*aload_0
                                                ; - Acminesimple::test@13 (line 5)
  0x00007fdc296b30d4: mov    0x10(%rsi,%r8,4),%edi  ;*aaload
                                                ; - Acminesimple::test@15 (line 5)
  0x00007fdc296b30d9: mov    0x14(%rdi),%r11d   ; implicit exception: dispatches to 0x00007fdc296b318d
  0x00007fdc296b30dd: mov    0x14(%rax),%r10d   ; implicit exception: dispatches to 0x00007fdc296b319d
  0x00007fdc296b30e1: cmp    %r10d,%r11d
  0x00007fdc296b30e4: jg     0x00007fdc296b30e9  ;*if_icmple
                                                ; - Acminesimple::test@23 (line 5)
  0x00007fdc296b30e6: mov    %rax,%rdi
  0x00007fdc296b30e9: inc    %r8d               ;*iinc
                                                ; - Acminesimple::test@30 (line 4)
  0x00007fdc296b30ec: cmp    $0x1,%r8d
  0x00007fdc296b30f0: jge    0x00007fdc296b30f7  ;*if_icmpge
                                                ; - Acminesimple::test@10 (line 4)
  0x00007fdc296b30f2: mov    %rdi,%rax          ;*iinc
                                                ; - Acminesimple::test@30 (line 4)
  0x00007fdc296b30f5: jmp    0x00007fdc296b30d4
  0x00007fdc296b30f7: cmp    %ecx,%r8d
  0x00007fdc296b30fa: jl     0x00007fdc296b3163
  0x00007fdc296b30fc: mov    %edi,%r10d
  0x00007fdc296b30ff: cmp    %ebp,%r8d
  0x00007fdc296b3102: jl     0x00007fdc296b310f
  0x00007fdc296b3104: mov    %r10d,%r9d
  0x00007fdc296b3107: jmp    0x00007fdc296b312b
  0x00007fdc296b3109: data32 xchg %ax,%ax
  0x00007fdc296b310c: mov    %r9d,%r10d         ;*aload_0
                                                ; - Acminesimple::test@13 (line 5)
  0x00007fdc296b310f: mov    0x10(%rsi,%r8,4),%r9d  ;*aaload
                                                ; - Acminesimple::test@15 (line 5)
  0x00007fdc296b3114: mov    0x14(%r9),%r11d    ; implicit exception: dispatches to 0x00007fdc296b318d
  0x00007fdc296b3118: mov    0x14(%r10),%ebx    ; implicit exception: dispatches to 0x00007fdc296b319d
  0x00007fdc296b311c: cmp    %ebx,%r11d
  0x00007fdc296b311f: cmovle %r10d,%r9d
  0x00007fdc296b3123: inc    %r8d               ;*iinc
                                                ; - Acminesimple::test@30 (line 4)
  0x00007fdc296b3126: cmp    %ebp,%r8d
  0x00007fdc296b3129: jl     0x00007fdc296b310c
  0x00007fdc296b312b: mov    %r9,%rax           ;*if_icmpge
                                                ; - Acminesimple::test@10 (line 4)
  0x00007fdc296b312e: add    $0x20,%rsp
  0x00007fdc296b3132: pop    %rbp
  0x00007fdc296b3133: test   %eax,0x5766ec7(%rip)        # 0x00007fdc2ee1a000
                                                ;   {poll_return}
  0x00007fdc296b3139: retq   
  0x00007fdc296b313a: mov    %r11d,%edi
  0x00007fdc296b313d: data32 xchg %ax,%ax       ;*iinc
                                                ; - Acminesimple::test@30 (line 4)
  0x00007fdc296b3140: movslq %r8d,%r10
  0x00007fdc296b3143: mov    0x14(%rsi,%r10,4),%r10d  ;*aaload
                                                ; - Acminesimple::test@15 (line 5)
  0x00007fdc296b3148: mov    0x14(%r10),%r9d    ; implicit exception: dispatches to 0x00007fdc296b318d
  0x00007fdc296b314c: mov    0x14(%rdi),%r11d   ; implicit exception: dispatches to 0x00007fdc296b319d
  0x00007fdc296b3150: cmp    %r11d,%r9d
  0x00007fdc296b3153: cmovle %edi,%r10d
  0x00007fdc296b3157: add    $0x2,%r8d          ;*iinc
                                                ; - Acminesimple::test@30 (line 4)
  0x00007fdc296b315b: cmp    %ecx,%r8d
  0x00007fdc296b315e: jge    0x00007fdc296b30ff  ;*if_icmpge
                                                ; - Acminesimple::test@10 (line 4)
  0x00007fdc296b3160: mov    %r10d,%edi         ;*aload_0
                                                ; - Acminesimple::test@13 (line 5)
  0x00007fdc296b3163: mov    0x10(%rsi,%r8,4),%r11d  ;*aaload
                                                ; - Acminesimple::test@15 (line 5)
  0x00007fdc296b3168: mov    0x14(%r11),%r10d   ; implicit exception: dispatches to 0x00007fdc296b318d
  0x00007fdc296b316c: mov    0x14(%rdi),%r9d    ; implicit exception: dispatches to 0x00007fdc296b319d
  0x00007fdc296b3170: cmp    %r9d,%r10d
                                                ; - Acminesimple::test@23 (line 5)
  0x00007fdc296b3175: jmp    0x00007fdc296b3140
  0x00007fdc296b3177: mov    %rsi,(%rsp)
  0x00007fdc296b317b: mov    $0xffffff86,%esi
  0x00007fdc296b3180: data32 xchg %ax,%ax
  0x00007fdc296b3183: callq  0x00007fdc29620320  ; OopMap{[0]=Oop off=232}
                                                ;*aload_0
                                                ; - Acminesimple::test@13 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b3188: callq  0x00007fdc2de8b7c0  ;*aload_0
                                                ; - Acminesimple::test@13 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b318d: mov    $0xfffffff6,%esi
  0x00007fdc296b3192: nop
  0x00007fdc296b3193: callq  0x00007fdc29620320  ; OopMap{off=248}
                                                ;*invokevirtual length
                                                ; - Acminesimple::test@16 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b3198: callq  0x00007fdc2de8b7c0  ;*invokevirtual length
                                                ; - Acminesimple::test@16 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b319d: mov    $0xfffffff6,%esi
  0x00007fdc296b31a2: nop
  0x00007fdc296b31a3: callq  0x00007fdc29620320  ; OopMap{off=264}
                                                ;*invokevirtual length
                                                ; - Acminesimple::test@20 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b31a8: callq  0x00007fdc2de8b7c0  ;*invokevirtual length
                                                ; - Acminesimple::test@20 (line 5)
                                                ;   {runtime_call}
  0x00007fdc296b31ad: mov    $0xfffffff6,%esi
  0x00007fdc296b31b2: nop
  0x00007fdc296b31b3: callq  0x00007fdc29620320  ; OopMap{off=280}
                                                ;*arraylength
                                                ; - Acminesimple::test@6 (line 4)
                                                ;   {runtime_call}
  0x00007fdc296b31b8: callq  0x00007fdc2de8b7c0  ;*arraylength
                                                ; - Acminesimple::test@6 (line 4)
                                                ;   {runtime_call}
  0x00007fdc296b31bd: hlt    
  0x00007fdc296b31be: hlt    
  0x00007fdc296b31bf: hlt    
[Exception Handler]

B disassembled:

# parm0:    rsi:rsi   = '[Ljava/lang/String;'
  #           [sp+0x20]  (sp of caller)
  0x00007fc749ebcf20: mov    %eax,-0x6000(%rsp)
  0x00007fc749ebcf27: push   %rbp
  0x00007fc749ebcf28: sub    $0x10,%rsp         ;*synchronization entry
                                                ; - Acfoamsimple::test@-1 (line 3)
  0x00007fc749ebcf2c: mov    0xc(%rsi),%r9d     ;*arraylength
                                                ; - Acfoamsimple::test@7 (line 4)
                                                ; implicit exception: dispatches to 0x00007fc749ebd029
  0x00007fc749ebcf30: movabs $0xeb8b7168,%rax   ;   {oop("")}
  0x00007fc749ebcf3a: test   %r9d,%r9d
  0x00007fc749ebcf3d: jle    0x00007fc749ebcfad  ;*if_icmpge
                                                ; - Acfoamsimple::test@8 (line 4)
  0x00007fc749ebcf3f: test   %r9d,%r9d
  0x00007fc749ebcf42: jbe    0x00007fc749ebcff5
  0x00007fc749ebcf48: mov    %r9d,%ebx
  0x00007fc749ebcf4b: dec    %ebx
  0x00007fc749ebcf4d: cmp    %r9d,%ebx
  0x00007fc749ebcf50: jae    0x00007fc749ebcff5
  0x00007fc749ebcf56: xor    %ecx,%ecx          ;*aload_0
                                                ; - Acfoamsimple::test@11 (line 5)
  0x00007fc749ebcf58: mov    0x10(%rsi,%rcx,4),%edx  ;*aaload
                                                ; - Acfoamsimple::test@13 (line 5)
  0x00007fc749ebcf5c: mov    0x14(%rdx),%r10d   ; implicit exception: dispatches to 0x00007fc749ebd009
  0x00007fc749ebcf60: mov    0x14(%rax),%r8d    ; implicit exception: dispatches to 0x00007fc749ebd019
  0x00007fc749ebcf64: cmp    %r8d,%r10d
  0x00007fc749ebcf67: jg     0x00007fc749ebcf6c  ;*if_icmple
                                                ; - Acfoamsimple::test@21 (line 5)
  0x00007fc749ebcf69: mov    %rax,%rdx
  0x00007fc749ebcf6c: inc    %ecx               ;*iinc
                                                ; - Acfoamsimple::test@28 (line 4)
  0x00007fc749ebcf6e: cmp    $0x1,%ecx
  0x00007fc749ebcf71: jge    0x00007fc749ebcf78  ;*if_icmpge
                                                ; - Acfoamsimple::test@8 (line 4)
  0x00007fc749ebcf73: mov    %rdx,%rax          ;*iinc
                                                ; - Acfoamsimple::test@28 (line 4)
  0x00007fc749ebcf76: jmp    0x00007fc749ebcf58
  0x00007fc749ebcf78: cmp    %ebx,%ecx
  0x00007fc749ebcf7a: jl     0x00007fc749ebcfe1
  0x00007fc749ebcf7c: mov    %edx,%r10d
  0x00007fc749ebcf7f: cmp    %r9d,%ecx
  0x00007fc749ebcf82: jl     0x00007fc749ebcf8f
  0x00007fc749ebcf84: mov    %r10d,%r8d
  0x00007fc749ebcf87: jmp    0x00007fc749ebcfaa
  0x00007fc749ebcf89: data32 xchg %ax,%ax
  0x00007fc749ebcf8c: mov    %r8d,%r10d         ;*aload_0
                                                ; - Acfoamsimple::test@11 (line 5)
  0x00007fc749ebcf8f: mov    0x10(%rsi,%rcx,4),%r8d  ;*aaload
                                                ; - Acfoamsimple::test@13 (line 5)
  0x00007fc749ebcf94: mov    0x14(%r8),%r11d    ; implicit exception: dispatches to 0x00007fc749ebd009
  0x00007fc749ebcf98: mov    0x14(%r10),%edi    ; implicit exception: dispatches to 0x00007fc749ebd019
  0x00007fc749ebcf9c: cmp    %edi,%r11d
  0x00007fc749ebcf9f: cmovle %r10d,%r8d
  0x00007fc749ebcfa3: inc    %ecx               ;*iinc
                                                ; - Acfoamsimple::test@28 (line 4)
  0x00007fc749ebcfa5: cmp    %r9d,%ecx
  0x00007fc749ebcfa8: jl     0x00007fc749ebcf8c
  0x00007fc749ebcfaa: mov    %r8,%rax           ;*if_icmpge
                                                ; - Acfoamsimple::test@8 (line 4)
  0x00007fc749ebcfad: add    $0x10,%rsp
  0x00007fc749ebcfb1: pop    %rbp
  0x00007fc749ebcfb2: test   %eax,0x5766048(%rip)        # 0x00007fc74f623000
                                                ;   {poll_return}
  0x00007fc749ebcfb8: retq   
  0x00007fc749ebcfb9: mov    %r10d,%edx
  0x00007fc749ebcfbc: nopl   0x0(%rax)          ;*iinc
                                                ; - Acfoamsimple::test@28 (line 4)
  0x00007fc749ebcfc0: movslq %ecx,%r10
  0x00007fc749ebcfc3: mov    0x14(%rsi,%r10,4),%r10d  ;*aaload
                                                ; - Acfoamsimple::test@13 (line 5)
  0x00007fc749ebcfc8: mov    0x14(%r10),%r8d    ; implicit exception: dispatches to 0x00007fc749ebd009
  0x00007fc749ebcfcc: mov    0x14(%rdx),%r11d   ; implicit exception: dispatches to 0x00007fc749ebd019
  0x00007fc749ebcfd0: cmp    %r11d,%r8d
  0x00007fc749ebcfd3: cmovle %edx,%r10d
  0x00007fc749ebcfd7: add    $0x2,%ecx          ;*iinc
                                                ; - Acfoamsimple::test@28 (line 4)
  0x00007fc749ebcfda: cmp    %ebx,%ecx
  0x00007fc749ebcfdc: jge    0x00007fc749ebcf7f  ;*if_icmpge
                                                ; - Acfoamsimple::test@8 (line 4)
  0x00007fc749ebcfde: mov    %r10d,%edx         ;*aload_0
                                                ; - Acfoamsimple::test@11 (line 5)
  0x00007fc749ebcfe1: mov    0x10(%rsi,%rcx,4),%r10d  ;*aaload
                                                ; - Acfoamsimple::test@13 (line 5)
  0x00007fc749ebcfe6: mov    0x14(%r10),%r8d    ; implicit exception: dispatches to 0x00007fc749ebd009
  0x00007fc749ebcfea: mov    0x14(%rdx),%r11d   ; implicit exception: dispatches to 0x00007fc749ebd019
  0x00007fc749ebcfee: cmp    %r11d,%r8d
  0x00007fc749ebcff1: jg     0x00007fc749ebcfb9  ;*if_icmple
                                                ; - Acfoamsimple::test@21 (line 5)
  0x00007fc749ebcff3: jmp    0x00007fc749ebcfc0
  0x00007fc749ebcff5: mov    %rsi,%rbp
  0x00007fc749ebcff8: mov    $0xffffff86,%esi
  0x00007fc749ebcfff: callq  0x00007fc749e29320  ; OopMap{rbp=Oop off=228}
                                                ;*aload_0
                                                ; - Acfoamsimple::test@11 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd004: callq  0x00007fc74e6947c0  ;*aload_0
                                                ; - Acfoamsimple::test@11 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd009: mov    $0xfffffff6,%esi
  0x00007fc749ebd00e: nop
  0x00007fc749ebd00f: callq  0x00007fc749e29320  ; OopMap{off=244}
                                                ;*invokevirtual length
                                                ; - Acfoamsimple::test@14 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd014: callq  0x00007fc74e6947c0  ;*invokevirtual length
                                                ; - Acfoamsimple::test@14 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd019: mov    $0xfffffff6,%esi
  0x00007fc749ebd01e: nop
  0x00007fc749ebd01f: callq  0x00007fc749e29320  ; OopMap{off=260}
                                                ;*invokevirtual length
                                                ; - Acfoamsimple::test@18 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd024: callq  0x00007fc74e6947c0  ;*invokevirtual length
                                                ; - Acfoamsimple::test@18 (line 5)
                                                ;   {runtime_call}
  0x00007fc749ebd029: mov    $0xfffffff6,%esi
  0x00007fc749ebd02e: nop
  0x00007fc749ebd02f: callq  0x00007fc749e29320  ; OopMap{off=276}
                                                ;*arraylength
                                                ; - Acfoamsimple::test@7 (line 4)
                                                ;   {runtime_call}
  0x00007fc749ebd034: callq  0x00007fc74e6947c0  ;*arraylength
                                                ; - Acfoamsimple::test@7 (line 4)
                                                ;   {runtime_call}
  0x00007fc749ebd039: hlt    
  0x00007fc749ebd03a: hlt    
  0x00007fc749ebd03b: hlt    
  0x00007fc749ebd03c: hlt    
  0x00007fc749ebd03d: hlt    
  0x00007fc749ebd03e: hlt    
  0x00007fc749ebd03f: hlt    

Using Math.min(args.length, 20) instead of args.length like in the discussion starting question, it behaves similarly:

A-with-min:

 static java.lang.String test(java.lang.String[]);
  Code:
   0:   ldc #2; //String 
   2:   astore_1
   3:   iconst_0
   4:   istore_2
   5:   aload_0
   6:   arraylength
   7:   bipush  20
   9:   invokestatic    #3; //Method java/lang/Math.min:(II)I
   12:  istore_3
   13:  iload_2
   14:  iload_3
   15:  if_icmpge   41
   18:  aload_0
   19:  iload_2
   20:  aaload
   21:  invokevirtual   #4; //Method java/lang/String.length:()I
   24:  aload_1
   25:  invokevirtual   #4; //Method java/lang/String.length:()I
   28:  if_icmple   35
   31:  aload_0
   32:  iload_2
   33:  aaload
   34:  astore_1
   35:  iinc    2, 1
   38:  goto    13
   41:  aload_1
   42:  areturn

B-with-min:

static java.lang.String test(java.lang.String[]);
  Code:
   0:   ldc #2; //String 
   2:   astore_1
   3:   iconst_0
   4:   istore_2
   5:   iload_2
   6:   aload_0
   7:   arraylength
   8:   bipush  20
   10:  invokestatic    #3; //Method java/lang/Math.min:(II)I
   13:  if_icmpge   39
   16:  aload_0
   17:  iload_2
   18:  aaload
   19:  invokevirtual   #4; //Method java/lang/String.length:()I
   22:  aload_1
   23:  invokevirtual   #4; //Method java/lang/String.length:()I
   26:  if_icmple   33
   29:  aload_0
   30:  iload_2
   31:  aaload
   32:  astore_1
   33:  iinc    2, 1
   36:  goto    5
   39:  aload_1
   40:  areturn

(jit disassembled functions too long to post in answer)

like image 24
BeniBela Avatar answered Sep 30 '22 14:09

BeniBela