Re: Magnitude of Order "For Loop" performance deltas based on syntax change

[Christian Franke]

Tom McCurdy wrote:
> Bash Version: 4.3
> Patch Level: 11
> Release Status: release
>
> Description:
>         Two nearly identical "For Loop" setups have large deltas in 
> performance. See test program below. Was confirmed in IRC chat room by 
> multiple users. Input is very noticeable with around 100,000 values.
>
> The script was originally used to take an input file where the first 
> line would determine how many int values were to follow. The remaining 
> lines each had values that were sorted, and then the smallest 
> difference between any two values were found.
>
> Repeat-By:
>
> Using script below comment/uncomment each method to test.
> On my machine
> Method-1 finishes in around 2 seconds
> Method-2 finishes in around 72 seconds

I tested the scripts on Win10 with the current Cygwin x64 version of 
bash (4.3.46(7)):

Method-1: ~4 seconds
Method-2: ~24 seconds

Further observations:

- Method-1 could be slowed down significantly by modifications of the 
first two assignments in the for loop:

1) Swap current/next assignments:

         next=${Pi[$i+1]}
         current=${Pi[$i]}

Result: ~26 seconds

2) Do these assignments with 'let' statements instead:

         let current=Pi[i]
         let next=Pi[i+1]

Result: ~25 seconds

3) Do both:

         let next=Pi[i+1]
         let current=Pi[i]

Result: ~49 seconds


- Method-2 could be significantly speed up if the order of the array 
accesses is reversed:

  for (( i=0; i<N-1; i++)); do
      if (( -(Pi[i] - Pi[i+1]) < min )); then
          min=$((-(Pi[i]-Pi[i+1])))
      fi
  done

Result: ~3 seconds
(using 'let' in the 'min' assignment failed with syntax error - Bug?)


There is at least some (IMO unexpected) performance degradation if 
arrays are accessed not sequentially.


Thanks,
Christian