Just so you know, a similar issue exists in some of the Base types in
Julia. For example "sub" (to extract a subarray from an array that does
not copy the elements but rather provides a view of the original array) and
"Ref" (to create a pointer that can be passed to a C subroutine) both
allocate small reference objects on the heap rather than the stack. This
means that there is a significant loss of performance, e.g., if a code
repeatedly uses "sub" to extract a small subarray in an inner loop. In this
scenario, it is faster to copy the subarray into temporary preallocated
storage and then copy it back after modification. I believe that the core
Julia developers are working on optimizations so that functions like this
will allocate on the stack instead of the heap if the compiler can prove to
itself that the "sub" or "Ref" object will never escape from an inner
loop. I don't know what is the state of these optimizations.
Stack allocation in the general case (i.e., in the case when the object may
escape from a loop) does not seem feasible for "sub" objects, "Ref" objects
or tuples similar to your example. The reason is that the garbage
collector needs to know whether there is a live reference to a mutable data
structure, and if references to mutable data structures were copied around
like bits objects, the run-time system could not keep track of this.
-- Steve Vavasis
On Wednesday, August 17, 2016 at 9:09:31 AM UTC-4, Bill Hart wrote:
>
> We have a (time critical function) with the following prototype:
>
> heapinsert!{N}(xs::Array{Tuple{NTuple{N, UInt}, heap_s}, 1}, exp::NTuple{N
> , UInt}, x::heap_s)
>
>
> However, one line of code in the implementation is allocating gigabytes of
> memory, which is causing a massive performance deficit in our program:
>
> xs[1] = (exp, x)
>
> Note heap_s is just an ordinary Julia type here, which contains a couple
> of Ints and another heap_s. As far as I can see it is irrelevant. It should
> just be a pointer at the machine level.
>
> It seems that Julia allocates space for the tuple (exp, x) and then writes
> it into the array xs.
>
> Does anyone have any ideas how I can stop it from making this unnecessary
> allocation? It's slowing down multivariate polynomial multiplication by a
> factor of at least 2 (and possibly 10) and causing a massive blowout in
> memory allocation (this is really performance critical code).
>
> I've already tried making using an immutable rather than a tuple. Same
> problem. I'm tracing this using julia --track-allocation=all.
>
> Bill.
>
