Inline constant arrays

[kmsquire]

I just ran across a comment on Wes McKinney's old blog post on Julia, where the following function was posted:

julia> function f()
          ans = [1.0 2.0]
          for i=1:1000^2
             ans += [1.0 2.0]
          end
          return ans
       end
f (generic function with 1 method)

julia> f(); @time f();
elapsed time: 0.458983303 seconds (176000112 bytes allocated)

Ignoring the known issue that += allocates memory, the constant expression also seems to be reallocated for each loop; moving this outside the loop cuts the time by 1/3:

function f()
          p = [1.0 2.0]
          ans = [1.0 2.0]
          for i=1:1000^2
             ans += p
          end
          return ans
       end
f (generic function with 1 method)

julia> f(); @time f();
elapsed time: 0.292015111 seconds (128000176 bytes allocated)

I'll also note that removing += but leaving assignment of p inside the loop still allocates p every iteration:

julia> function f()
          ans = [1.0 2.0]
          for i=1:1000^2
             p = [1.0 2.0]
             for j = 1:length(ans)
                ans[j] += p[j]
             end
          end
          return ans
       end
f (generic function with 1 method)

julia> f(); @time f();
elapsed time: 0.15613266 seconds (64000112 bytes allocated)

Moving p outside drops the time to .005 sec, since almost no memory is allocated.

(Almost all of this is also obvious using the code_* functions.)

[kmsquire]

Of course, I didn't check to see if #3796 handles this...

[simonster]

To avoid changing behavior, this kind of optimization (not sure I'd call it inlining) would require us to know that +(::Array, ::Array) is a pure function. See also #414.

[kmsquire]

I missed #5008. This should probably be moved there...

[toivoh]

To make matters worse, +(::Array, ::Array) is not actually a pure function, and neither is [1.0 2.0], i.e. hcat. They both return new (and therefore different) arrays when called repeatedly with the same arguments. Only when you don't mutate the contents of the arrays and don't compare them by object identity do these functions behave as if they were pure. I'm not sure that we can expect the compiler to carry out all of that analysis.

I guess that what it would need to figure out is that a given array, during its lifetime, is used only for the constant values stored in it, and not for it's identity. And that's not even true if you look inside the implementation of +(::Array, ::Array)! I would love for the compiler to be able to figure that out, though :)

[JeffBezanson]

Correct that this is a far harder optimization to pull off than it seems.

[kmsquire]

What if constant arrays were made (deeply) immutable? Immutable arrays don't current exist in mainline julia, of course.

[tknopp]

I think this issue would be solved if one would use a tuple (representing a fixed size array, see #5857) instead of [1.0, 2.0]. Of course this would require that arithmetics would be implemented for tuples.

[lindahua]

Wondering using tuple would make optimization easier.

[tknopp]

This version runs much faster

function f()
      ans = [1.0 2.0]
      for i=1:1000^2
         tmp = (1.0, 2.0)
         ans[1] += tmp[1]
         ans[2] += tmp[2]
      end
      return ans
   end

When defining += for mixed tuple/arrays this should be writable as ans += (1.0, 2.0).

[tknopp]

Oh I further see that this would require that += is overloadable.

[oscardssmith]

I just ran timings on my machine (v 0.5.0) and it looks like this difference in timing is now gone. (although there still is lots of memory allocation, and tknpp's version is still 10x faster). Should this be closed?

[KristofferC]

I believe the current thinking is that cases like this are handled by https://github.com/JuliaArrays/StaticArrays.jl.