Arraypocalypse Now and Then

[mbauman]

This issue supersedes the 0.4 work towards array nirvana (#7941), and will tracks the issues we aim to complete during 0.5 and beyond — now updated through work on 0.7. This is an umbrella issue and will track specific tasks in other issues. Please feel free to add things that I've missed.

Required underlying technologies

• Julia native bounds checking and removal (#7799). Several tries have been made at this, but I believe the current plan of action is to make @inbounds elide code blocks hidden within an @boundscheck macro, propagating down only one level of inlining (extensible bounds checking removal julia#7799 (comment)). This is a strong requirement for the subsequent steps. (implemented in elide code marked with @boundscheck(...). julia#14474)
• ReshapedArrays (#10507). Requires better performance: https://groups.google.com/d/msg/julia-dev/7M5qzmXIChM/kOTlGSIvAwAJ

Major 0.5 breaking behavior changes

• Drop dimensions indexed by a scalar (Taking vector transposes seriously #42; more generally, APL-style slicing where the rank of a slice is the sum of the ranks of the indexes, see below). PR at RFC: Drop dimensions indexed by scalars julia#13612.
• Flip the switch on the concatenation deprecation (#8599)
• Remove default no-op behavior for (c)transpose (#13171)
• Change change sub behaviour to slice (#16846)

Major 0.6 breaking behavior changes

• Vector transpose returns a covector (Taking vector transposes seriously #42). Implementation in Introduce RowVector as the transpose of a vector julia#19670.
• Vector conjugation returns lazy wrapper (#20047)

Possible future breaking changes

• Matrix transposition and conjugation return lazy wrappers (#25364)
• Return slices as views. A first attempt at this was at RFC: Return views from UnitRange indexing of Arrays julia#9150. Still unclear whether the possible performance changes are consistent and large enough to be worth the breakage. See range indexing should produce a subarray, not a copy julia#3701.
• Should reductions drop dimensions? array reductions (sum, mean, etc.) and dropping dimensions julia#16606

New functionality

• Allow expression of varargs of defined length (#11242). This allows us to take full advantage of RFC: Give AbstractArrays smart and performant indexing behaviors for free julia#10525.
• Ditch special lowering of Ac_mul_Bt, use dispatch on the lazy transpose wrappers instead. (#5332, sunset linalg jazz julia#25217)
• Dimensions indexed by multidimensional arrays add dimensions (full APL-style: the dimensionality of the result is the sum of the dimensionalities of the indices). (#15431)
• Allow any index type in non-scalar indexing (#12567). Tighten scalar indexing to indices <: Integer and widen non scalar indexing to <: Union{Number, AbstractArray, Colon} (RFC: Allow any index type in nonscalar indexing julia#12567 (comment)). More systematic conversion of indices such that any index type can be converted into an Int or AbstractArray: RFC: Speedier, simpler and more systematic index conversions julia#19730
• Easier creation of immutable arrays with tuples and WIP: add support for working with immutables (#11902) julia#12113.

Other speculative possibilities

• A mutable fixed-size buffer type, which would allow for a Julia-native Array definition (#12447); this type could also be used for I/O buffers and string storage.
• Base IndexSet IntSet on BitArray or perhaps any AbstractArray{Bool}. (#20456)
• Rework nonscalar indexing to prevent calling find on logical arrays and simply wrap it with an IndexSet LogicalIndex instead? (#19730)
• Negated indexing with complement IndexSet (NegatedIndex type julia#1032) or special Not type? (Perhaps in a package: https://github.com/mbauman/InvertedIndices.jl)
• Deprecate the linearization of trailing dimensions when more than one index is provided (partial linear indexing). (#20079)
• Only allow indexing into N-dimensional arrays with 1 or N indices, deprecating "partial" indexing and trailing singleton dimensions (Omitted and additionally indexed dimensions in getindex julia#5396 and deprecate (then remove) generalized linear indexing julia#14770). Initial attempt at WIP/RFH: Deprecate generalized linear indexing julia#20040. Only allow linear indexing when there is exactly one index provided. Only allow omitting indices (using less than N indices in an N-dimensional array) when all omitted dimensions are of length 1. Only allow trailing indices (more than N indices) when all indices are 1 (singletons). (#21750)
• Find alternate syntax for typed arrays – indexing into a type (T[...]) is kind of a bad pun. This syntax is especially bad since some variations are parsed as indexing into a type while others are parsed as special forms (typed hvcat, typed comprehensions)
• Change hashing to run-length encoding of the diff of arrays, which would allow integer ranges and arrays to hash as equal again. (Hashing integer ranges  julia#12226 (comment), Make arrays and ranges hash and compare equal julia#16401)
• Move sparse arrays out of base into a standard package. (#25249)
• Allow nontraditional indices (#16260)
• @sub @view macro (#16564)

[tbreloff]

This looks like a great list Matt, thanks. I'm a little scared of the
fallout but it'll be a huge leap forward for the language.

On Tuesday, September 15, 2015, Matt Bauman notifications@github.com
wrote:

This issue supersedes the 0.4 work towards array nirvana (#7941
JuliaLang/julia#7941), and will track the
issues we aim to complete during 0.5. This is an umbrella issue and will
track specific tasks in other issues. Please feel free to add things that
I've missed (at least during the first half of 0.5).

Required underlying technologies

• Julia native bounds checking and removal (#7799
  extensible bounds checking removal julia#7799). Several tries have
  been made at this, but I believe the current plan of action is to make
  @inbounds elide code blocks hidden within an @BoundsCheck macro,
  propagating down only one level of inlining (#7799 (comment)
  extensible bounds checking removal julia#7799 (comment)).
  This is a strong requirement for the subsequent steps.
• ReshapedArrays (#10507
  WIP: ReshapedArrays julia#10507). Requires better
  performance:
  https://groups.google.com/d/msg/julia-dev/7M5qzmXIChM/kOTlGSIvAwAJ

Breaking behavior changes

• Drop dimensions indexed by a scalar (#4774 (comment)
  Taking vector transposes seriously #42)
• Return slices as views. A first attempt at this was at RFC: Return views from UnitRange indexing of Arrays julia#9150
  RFC: Return views from UnitRange indexing of Arrays julia#9150. Special attention may
  be needed for BitArrays.
• Flip the switch on the concatenation deprecation (#8599
  WIP: Make [a, b] non-concatenating julia#8599)

New functionality

• Allow expression of varargs of defined length (#11242
  NTuples made me sad (so I nixed them) julia#11242). This allows us to
  take full advantage of RFC: Give AbstractArrays smart and performant indexing behaviors for free julia#10525
  RFC: Give AbstractArrays smart and performant indexing behaviors for free julia#10525.
• Transpose returns a covector or transpose type (#4774 (comment)
  Taking vector transposes seriously #42)
• Ditch special lowering of Ac_mul_Bt, use dispatch instead.
• Dimensions indexed by multidimensional arrays add dimensions (full
  APL-style: the dimensionality of the result is the sum of the
  dimensionalities of the indices)
• Allow any index type in non-scalar indexing (#12567
  RFC: Allow any index type in nonscalar indexing julia#12567)
• Easier creation of immutable arrays with tuples and WIP: add support for working with immutables (#11902) julia#12113
  WIP: add support for working with immutables (#11902) julia#12113.

Other speculative possibilities

• A mutable fixed-size buffer type, which would allow for a
  Julia-native Array definition (#12447
  Introduce Buffer type and make Array an abstraction on top of it julia#12447)
• Base IndexSet on BitArray or perhaps any AbstractArray{Bool}.
• Rework nonscalar indexing to prevent calling find on logical arrays
  and simply wrap it with an IndexSet instead?
• Negated indexing with complement IndexSet? (Perhaps in a package)

—
Reply to this email directly or view it on GitHub
#255.

[JeffBezanson]

Yes, great list! Let's roll up our sleeves!

[tbreloff]

Are there any pieces of this that are unclaimed? I'd like to help, but I
don't want to step on anyone's toes.

On Tuesday, September 15, 2015, Jeff Bezanson notifications@github.com
wrote:

Yes, great list! Let's roll up our sleeves!

—
Reply to this email directly or view it on GitHub
#255.

[StefanKarpinski]

It's a phenomenal list. There's actually only a few changes that are very breaking, which is nice, but those are significant enough.

[mbauman]

There is definitely more than enough work to go around! I don't think any of these tasks are claimed.

Things like dropping scalar dimensions are rather simple changes, but will take a lot of work finding and fixing bugs... and that part is easy to collaborate on. Same goes for views (if you ignore the perf issues with ReshapedArrays and inbounds). Anyone is welcome to dig in!

[jakebolewski]

Views is hard, you have to make it through bootstrap without 🔪 yourself in the 👀.

[StefanKarpinski]

Having just done a bunch of work to get string changes through bootstrap, I'm inclined to believe this.

[milktrader]

Thanks for doing this @mbauman, so much to digest

[jiahao]

I've added "Remove default no-op behavior for (c)transpose" as an item. I expect much complaining, but as we've discussed before, it's simply wrong to assume that <:Any is a scalar and the logic error rears its head every time one tries to wrap and/or implement custom array/matrix types. cc @jakebolewski @andreasnoack

[StefanKarpinski]

I think we need to think through the options for that carefully. It's pretty idiomatic to write A' to transpose a non-complex matrix.

[mbauman]

Isn't it possible that the (c)transpose wrapper will solve this issue? There's a lot of design work that will need to go into it, but:

transpose(A::AbstractVectorOrMatrix) = TransposeType(A) # Will call `transpose` upon indexing, too
transpose(::AbstractArray) = error("cannot take transpose of 3+ dim array") # yeah, error methods aren't the best…
transpose(x) = x

[carnaval]

related: I think some of the typing problems in linalg (and transpose behavior) comes from the fact that we represent a blocked linear operator as an array of arrays. We may want to switch to a new type that knows of the various sizes inside it for that, I remember discussing that with @andreasnoack. 0.5 might be a time to at least think about it.

[jiahao]

Isn't it possible that the (c)transpose wrapper will solve this issue?

Maybe; we'd have to think about it.

The blocking issue last time is that transpose has to be recursive to handle cases like Matrix{Matrix} (Example: A = [rand(1:5, 2, 2) for i=1:2, j=1:2]; A') correctly, but people want to write A' on 2D arrays on non-numeric types (e.g. images, as Matrix{<:Colorant}) and expect the transpose to not apply to the scalar elements. The no-op transpose(x::Any) method exists to handle these cases. However, this definition conflicts with matrix-like objects, which have the algebraic semantics of matrices but are not stored internally in any array-like form, and hence by JuliaLang/julia#987 should not be an AbstractArray (QRCompactWYQ is the poster child, but we have many such examples). If you introduce a new matrix-like type, you have to explicitly define (c)transpose otherwise you get the no-op fallback which is a source of many bugs.

To be clear, the behavior we would break explicitly is the claim (which you can find in the help for permutedims) that

Transpose is equivalent to permutedims(A, [2,1]).

This equivalence makes no sense for types that are not AbstractArrays and that are AbstractArrays of non-scalars, and we actually do have matrix-like types that need this more abstract sense of transpose.

[tbreloff]

I think assuming that a Matrix{Matrix} will automatically recursively
transpose the elements is bad and dangerous. I'd rather see a special type
BlockMatrix{Matrix} that does what you're looking for.

On Wed, Sep 16, 2015 at 10:30 AM, Jiahao Chen notifications@github.com
wrote:

Isn't it possible that the (c)transpose wrapper will solve this issue?

Maybe; we'd have to think about it.

The blocking issue last time is that transpose has to be recursive to
handle cases like Matrix{Matrix} (Example: A = [rand(1:5, 2, 2) for
i=1:2, j=1:2]; A') correctly. However, people want to write A' on 2D
arrays on non-numeric types (e.g. images, as Matrix{<:Colorant}) and
expect the transpose to not apply to the scalar elements. The no-op
transpose(x::Any) method exists to handle these cases. However, this
definition conflicts with matrix-like objects, which have the algebraic
semantics of matrices but are not stored internally in any array-like form,
and hence by JuliaLang/julia#987 JuliaLang/julia#987 should
not be an AbstractArray (QRCompactWYQ is the poster child, but we have
many such examples). If you introduce a new matrix-like type, you have to
explicitly define (c)transpose otherwise you get the no-op fallback which
is a source of many bugs.

To be clear, the behavior we would break explicitly is that

Transpose is equivalent to permutedims(A, [2,1]).

would now be false. This equivalence makes no sense for types that are not
AbstractArrays, and we actually do have matrix-like types that need this
more abstract sense of transpose.

—
Reply to this email directly or view it on GitHub
#255.