len() function vs. length variable. Paradox

[dmi...@gmail.com]

Hi all,

This days I'm practicing with Go a little writing sort algorithms and discovered strange thing:

in a bubble sort (don't leaf :D) there are two loops one inside another, just like this:

length := len(array)
for j := 1;j<length-1; j++ {
for i:=0; i<length-j; i++ {
if array[i]>array[i+1] {
Swap(&array,i,i+1)
}
}
} 

Just like always (in other programming languages) I assign the length of an array just before the loop to not execute the length calculation repeatedly BUT, when I made some tests, results that in GO, putting len(array) inside the loop make it FASTER !!! 

A code with a len() function is this one:

for j := 1;j<len(*array)-1; j++ {
for i:=0; i<len(*array)-j; i++ {
if (*array)[i]>(*array)[i+1] {
Swap(array,i,i+1)
}
}
}

Average execution time with a length variable 526000 microseconds sorting an array of 10000 int elements

Average execution time with a len() function   508000 microseconds sorting an array of 10000 int elements

I have made tests a lot o times on the same machine, an the result is always the same(+-).

So can somebody explain WHY is it faster to use len(array)  inside the loop? What about function call, stack allocation ?

[Jesse McNelis]

On Thu, Aug 29, 2013 at 5:41 AM, <dmi...@gmail.com> wrote:

Average execution time with a length variable 526000 microseconds sorting an array of 10000 int elements

Average execution time with a len() function   508000 microseconds sorting an array of 10000 int elements

I have made tests a lot o times on the same machine, an the result is always the same(+-).

So can somebody explain WHY is it faster to use len(array)  inside the loop? What about function call, stack allocation ?

The len() of an array is a constant known at compile time, since it's part of the type of the array.

Thus there is no function call at runtime for it.

Even for a slice len() is inlined, making it just an access of the length field of the slice.

--
=====================
http://jessta.id.au

[dmikam]

Wow, thats make sense... So on arrays using len() is faster then variable. And on slices it would be the same using len() and a variable. Is it right ? Are there some other types that has such optimization ? What about strings? I suppous they would work just like slices?

[GreatOdinsRaven]

I would try to write "idiomatic" Go code, and let the compiler writers optimize on their end. 

Current compiler optimizations are not documented in the spec, and they might (and probably will) change. Not only that, they might be different between not only implementations, but versions of the same compiler.

If you want to know the length of an array/slice - call len(). Capacity? cap(). Etc. Just write Go code the Go way, I guess, is my advice. 

[Dima]

Ok, thanks ! it's a good advice !

Un saludo !

2013/8/28 GreatOdinsRaven <dimiter....@gmail.com>

[Johann Höchtl]

Am Mittwoch, 28. August 2013 23:40:15 UTC+2 schrieb GreatOdinsRaven:

I would try to write "idiomatic" Go code, and let the compiler writers optimize on their end. 

Current compiler optimizations are not documented in the spec, and they might (and probably will) change. Not only that, they might be different between not only implementations, but versions of the same compiler.

And I would say optimizations will never be documented in the spec as long as they  have no influence on the semantics
Think of many undefined corner cases of C which open the door to "optimizations" and surprises at the same time.