arrays versus pointers

[Jutho]

Dear julia users/developers,

I decided to ask my questions on the dev forum as they are rather technical in nature and might also foster some discussion on the design of julia arrays. Since the tuple overhaul, types like NTuple{N,Int} are bitstypes and it becomes even more favorable to implement immutable types to store all kinds of arrays / strided data / ... in similar spirit to SubArray; e.g. 

immutable StridedData{N,T}
 storage::Vector{T}
 offset::Int
 strides::NTuple{N,Int}
end

In my application, the dimension is stored externally since I am implementing some recursive (divide and conquer) algorithms and the dimensions are sliced all the time. The storage field essentially just indicates the block of memory in which I will be indexing, and therefore only its length is important, which is why I am using Vector{T} instead of Array{N,T} (it might actually originate from on original array with a different number of dimensions).

Now as far as I understand, StridedData can never become a bits type because of the field of type Vector, which essentially is due that a julia Vector supports resize! and push! etc. I've seen in one or more issues that this is a stumble block to further improve e.g. the efficiency of e.g. SubArray, because the pointer to the block of memory cannot be proven to be constant. So I basically have the following questions:

1) Is there a serious penalty from StridedData not being a bits type, e.g. when this is passed around a lot as an argument in a recursive function? Does this imply that e.g. the pointer to the memory will not live on the stack and will have to be read from the heap every time?

2) Is there a better alternative? I could use storage::Ptr{T} since I am only interested in referencing the block of memory, but to then actually read and store data, one needs to use `unsafe_load/store!`, which only work if T is a bits type. Is that correct? Why is this limitation in effect? 

3) Was it a wise design choice to give Array{T,1} the resize! functionality, thereby possibly jeopardizing the efficiency of all Array{T,N} objects. I would expect that vectors and multidimensional arrays as mathematical vectors, matrices and tensors which have a constant size throughout there lifetime versus one-dimensional lists that can grow and shrink are two very different use cases and very few programs actually combine the two functionalities, such that maybe these could have been different types. While I agree that this unified behavior is convenient, if this would really be blocking several optimizations for Array{T,N}, then maybe moving the resize! and push! behavior to a separate subtype of AbstractArray{T,1}, called e.g. List{T} or ArrayList{T}, might have been a better choice?

[Scott Jones]

On Wednesday, June 17, 2015 at 7:02:36 PM UTC-4, Jutho wrote:

Dear julia users/developers,

I decided to ask my questions on the dev forum as they are rather technical in nature and might also foster some discussion on the design of julia arrays. Since the tuple overhaul, types like NTuple{N,Int} are bitstypes and it becomes even more favorable to implement immutable types to store all kinds of arrays / strided data / ... in similar spirit to SubArray; e.g. 

immutable StridedData{N,T}
 storage::Vector{T}
 offset::Int
 strides::NTuple{N,Int}
end

In my application, the dimension is stored externally since I am implementing some recursive (divide and conquer) algorithms and the dimensions are sliced all the time. The storage field essentially just indicates the block of memory in which I will be indexing, and therefore only its length is important, which is why I am using Vector{T} instead of Array{N,T} (it might actually originate from on original array with a different number of dimensions).

Now as far as I understand, StridedData can never become a bits type because of the field of type Vector, which essentially is due that a julia Vector supports resize! and push! etc. I've seen in one or more issues that this is a stumble block to further improve e.g. the efficiency of e.g. SubArray, because the pointer to the block of memory cannot be proven to be constant. So I basically have the following questions:

1) Is there a serious penalty from StridedData not being a bits type, e.g. when this is passed around a lot as an argument in a recursive function? Does this imply that e.g. the pointer to the memory will not live on the stack and will have to be read from the heap every time?

2) Is there a better alternative? I could use storage::Ptr{T} since I am only interested in referencing the block of memory, but to then actually read and store data, one needs to use `unsafe_load/store!`, which only work if T is a bits type. Is that correct? Why is this limitation in effect? 

This is a question I have... how would you allocate the block of memory, and make sure it is released?

I'd thought that Ptr{T} meant that julia did no management of the memory (Ref{T} is needed for it to be GCed).

 

3) Was it a wise design choice to give Array{T,1} the resize! functionality, thereby possibly jeopardizing the efficiency of all Array{T,N} objects. I would expect that vectors and multidimensional arrays as mathematical vectors, matrices and tensors which have a constant size throughout there lifetime versus one-dimensional lists that can grow and shrink are two very different use cases and very few programs actually combine the two functionalities, such that maybe these could have been different types. While I agree that this unified behavior is convenient, if this would really be blocking several optimizations for Array{T,N}, then maybe moving the resize! and push! behavior to a separate subtype of AbstractArray{T,1}, called e.g. List{T} or ArrayList{T}, might have been a better choice?

I can only say that Array{T,1} is used extensively for things like strings, for IOBuffer, and many other places where push! and append! are used constantly.  It would be major breakage if that changed (but maybe it should, during the upcoming "ArrayMegeddon" in 0.5).  I've been changing Array{T,1} in the UTF conversion code to always specify Vector{T}, so it might be easier to find and replace those cases in the future... (I've also been changing things so that the size is calculated initially, so even for immutable strings, it doesn't need resizable vectors).

[Arch Robison]

For (1), it's tough to tell without actually running a benchmark of interest.  My guess is that passing StridedData around on the heap is not a serious penalty as far as reads go.  But the additional heap allocation could be a penalty if you are generating lots of those objects.  I tried running code_llvm on a simple example and it appears that for N=1 T=Float32, the StridedData was being put on the heap

For item (3), I'll plead for first exploring better optimizers before complicating the language.  Having two different types, one for non-resizeable and one for resizeable arrays, would create a steeper learning curve and might not buy much in performance.  The big savings from knowing that the size does not change would seem to come from hoisting loop invariants, eliminating bounds checks, and (on some architectures) induction variables.  But consider a loop that  calls some function that might change the size of an array, and thus possibly preclude said optimizations:

1. If the call uses generic dispatch, that overhead will swamp any savings from the optimization anyway.
   
2. If the call uses non-generic dispatch, interprocedural analysis could figure out whether the call subjects an array parameter to resizing.  
3. If the call is completely inlined, the current type-based alias analysis in Julia already figures out that the array was not resized.

I'm guessing that the interprocedural analysis required for (2) could be fairly cheap, but have not thought through the details.  Interprocedural analysis could probably help determine when to stack-allocate objects like StridedData.

Of course a generic call on a rarely executed path in the loop can obviate the "swamp" argument in case (1), though I don't know how often they occur in practice.  Doing the interprocedural analysis at the Julia level might help there since it could summarize the effects of generic dispatch.

[Stefan Karpinski]

That's a great summary of the arguments for not restricting this. Quite often "a rarely executed path in the loop" is an error path which we may know doesn't return, but there might be situations where the usual loop path is predictable but the unusual loop path is not – but that could be handled by having a loop body that optimistically assumes that the generic call doesn't happen and thus that the array size doesn't change; if the branch with the generic call does happen, it can jump to a pessimistic version of the loop that guards against array size changing. A somewhat complex transformation, but not a totally crazy one.

Actually, the idea that we should maybe allow pushing and popping columns and rows from matrices and the analogous higher-dimensional operations has grown on me over time, but I'm not entirely convinced that it would be a good idea. It's a sufficiently complex operation that people sometimes want to do, that it might be worth having a really good implementation of it that's as fast as it can be done for those cases where it's really what someone needs.

[Jutho]

Thanks for the responses. That only leaves my questions of point 2. Why is it that the unsafe_read and unsafe_store! only work for bitstypes? In fact the manual only mentions this restriction for unsafe_store!, but it seems this also holds true for unsafe_read? Does an A::Array{T,1} for abstract T not just store its elements by references, such that pointer(A,ind) just holds itself a pointer to a julia object. Then one should be able to copy that pointer to another location pointer(B,ind) of some B::Array{T,1} ? Or is that view to simplistic (I have no idea what I am talking about here...).