hcat/vcat need to check the input for errors

[ViralBShah]

Output is incorrect size, with extra elements.

julia> [[1 2; 3 4] [5 6]]
2x4 Int64 Array
1 2 5 0
3 4 6 0

This should be an error, but gives a bizarre result.

julia> [[1 2; 3 4] [5 6 7]]
2x5 Int64 Array
1 2 5 7 0
3 4 6 0 0

Another example:

julia> [[1, 2, 3] 4]
3x2 Int64 Array
1 4
2 4
3 4

[GeorgeXing]

The first output is because [5 6] is treated as a 1x2 array, so the special case hcat{T}(A::Array{T,2}) is called. In there, the number of columns in the result is computed to be the sum of the number of columns of the inputs, which is 4. Then all the elements are copied in order, leaving only the first 6 initialized. If you instead put the 1-dimensional vector [5, 6], then you get the desired behavior. Indeed, I get:

julia> hcat([1 2; 3 4], [5 6])
2x4 Int64 Array
1 2 5 0 
3 4 6 580005134336 

julia> hcat([1 2; 3 4], [5, 6])
2x3 Int64 Array
1 2 5 
3 4 6 

There's not a single error check in any of the cat cases; should there be?

[ViralBShah]

Yes, all the cat code requires some error checks. It was all written early on to quickly get functionality, and has not yet been revisited. Some missing cases also need to be implemented - there are a couple of related open issues.

-viral

On 22-Aug-2011, at 5:45 AM, GeorgeXing wrote:

The first output is because [5 6] is treated as a 1x2 array, so the special case hcat{T}(A::Array{T,2}) is called. In there, the number of columns in the result is computed to be the sum of the number of columns of the inputs, which is 4. Then all the elements are copied in order, leaving only the first 6 initialized. If you instead put the 1-dimensional vector [5, 6], then you get the desired behavior. Indeed, I get:

julia> hcat([1 2; 3 4], [5 6])
2x4 Int64 Array
1 2 5 0
3 4 6 580005134336

julia> hcat([1 2; 3 4], [5, 6])
2x3 Int64 Array
1 2 5
3 4 6
There's not a single error check in any of the cat cases; should there be?

Reply to this email directly or view it on GitHub:
#183 (comment)

[GeorgeXing]

I can only find #116 and #38 as related issues -- what else is there?
I'd like to tackle this, but it seems I should get some performance tests first. What else should go into cat_perf.j?

[ViralBShah]

There was the other cat bug that you just closed, for cat along any dim.

I would have perf tests for small and large matrices, a few N-d cases etc. Also, it may be worthwhile to write the concatenation code using array assignments, and reuse as much as possible.

Eventually assign and ref will use memcpy and give speedups everywhere.

-viral

On 22-Aug-2011, at 4:17 PM, GeorgeXing wrote:

I can only find #116 and #38 as related issues -- what else is there?
I'd like to tackle this, but it seems I should get some performance tests first. What else should go into cat_perf.j?

Reply to this email directly or view it on GitHub:
#183 (comment)

[GeorgeXing]

Some preliminary test data. All the small cases deal with the same number of elements; same with all the large cases. Those marked with a 2 are arrayrefs; those which are not use a cat case. All things are the 2d case except the ones explicitly labeled nd.

julia> load("test/cat_perf.j")
small cat:          0.19777512550354004
large cat:          0.03951191902160645
small cat 2:        0.06725692749023438
large cat 2:        0.04082798957824707
small hcat:         0.13303399085998535
large hcat:         0.02049088478088379
small hcat 2:       0.06379318237304688
large hcat 2:       0.03898310661315918
small vcat:         1.81790494918823242
large vcat:         1.9143528938293457
small vcat 2:       0.06815600395202637
large vcat 2:       0.03951692581176758
small catnd:        2.60143899917602539
large catnd:        0.12837910652160645
small catnd 2:      1.05365109443664551
large catnd 2:      0.12747406959533691

Wow, vcat is really slow...

[ViralBShah]

Can you compare matlab?

On 23-Aug-2011, at 4:36 AM, GeorgeXingreply@reply.github.com wrote:

Some preliminary test data. All the small cases deal with the same number of elements; same with all the large cases. Those marked with a 2 are arrayrefs; those which are not use a cat case. All things are the 2d case except the ones explicitly labeled nd.

julia> load("test/cat_perf.j")
small cat: 0.19777512550354004
large cat: 0.03951191902160645
small cat 2: 0.06725692749023438
large cat 2: 0.04082798957824707
small hcat: 0.13303399085998535
large hcat: 0.02049088478088379
small hcat 2: 0.06379318237304688
large hcat 2: 0.03898310661315918
small vcat: 1.81790494918823242
large vcat: 1.9143528938293457
small vcat 2: 0.06815600395202637
large vcat 2: 0.03951692581176758
small catnd: 2.60143899917602539
large catnd: 0.12837910652160645
small catnd 2: 1.05365109443664551
large catnd 2: 0.12747406959533691
Wow, vcat is really slow...

Reply to this email directly or view it on GitHub:
#183 (comment)

[ViralBShah]

Generally, vcat is more difficult since the writes are interleaved, and it will cause more cache misses than hcat. I wouldn't expect it to be this slow though. The vcat implementation is all stride 1 access - so this is even more puzzling. I wonder if the codegen is missing something.

-viral

On 23-Aug-2011, at 4:36 AM, GeorgeXing wrote:

Some preliminary test data. All the small cases deal with the same number of elements; same with all the large cases. Those marked with a 2 are arrayrefs; those which are not use a cat case. All things are the 2d case except the ones explicitly labeled nd.

julia> load("test/cat_perf.j")
small cat: 0.19777512550354004
large cat: 0.03951191902160645
small cat 2: 0.06725692749023438
large cat 2: 0.04082798957824707
small hcat: 0.13303399085998535
large hcat: 0.02049088478088379
small hcat 2: 0.06379318237304688
large hcat 2: 0.03898310661315918
small vcat: 1.81790494918823242
large vcat: 1.9143528938293457
small vcat 2: 0.06815600395202637
large vcat 2: 0.03951692581176758
small catnd: 2.60143899917602539
large catnd: 0.12837910652160645
small catnd 2: 1.05365109443664551
large catnd 2: 0.12747406959533691
Wow, vcat is really slow...

Reply to this email directly or view it on GitHub:
#183 (comment)

[ViralBShah]

BTW, it would be great to also have hvcat tests, and matlab comparisons.

-viral

On 23-Aug-2011, at 4:36 AM, GeorgeXing wrote:

Some preliminary test data. All the small cases deal with the same number of elements; same with all the large cases. Those marked with a 2 are arrayrefs; those which are not use a cat case. All things are the 2d case except the ones explicitly labeled nd.

julia> load("test/cat_perf.j")
small cat: 0.19777512550354004
large cat: 0.03951191902160645
small cat 2: 0.06725692749023438
large cat 2: 0.04082798957824707
small hcat: 0.13303399085998535
large hcat: 0.02049088478088379
small hcat 2: 0.06379318237304688
large hcat 2: 0.03898310661315918
small vcat: 1.81790494918823242
large vcat: 1.9143528938293457
small vcat 2: 0.06815600395202637
large vcat 2: 0.03951692581176758
small catnd: 2.60143899917602539
large catnd: 0.12837910652160645
small catnd 2: 1.05365109443664551
large catnd 2: 0.12747406959533691
Wow, vcat is really slow...

Reply to this email directly or view it on GitHub:
#183 (comment)

[JeffBezanson]

The cases labeled just "cat" are using hvcat.

[JeffBezanson]

commit 3ee9cd0 improves vcat by moving the inner loop to assign. there is indeed some sub-optimal code generation going on, but we're better off this way since then we only need to optimize assign.
Many thanks George, this is a good example of a performance problem we didn't know about.

[ViralBShah]

Jeff's fix seems to have fixed vcat performance, but what's the matter with small catnd? Even small catnd2 is slow!

-viral

On 23-Aug-2011, at 4:36 AM, GeorgeXing wrote:

Some preliminary test data. All the small cases deal with the same number of elements; same with all the large cases. Those marked with a 2 are arrayrefs; those which are not use a cat case. All things are the 2d case except the ones explicitly labeled nd.

julia> load("test/cat_perf.j")
small cat: 0.19777512550354004
large cat: 0.03951191902160645
small cat 2: 0.06725692749023438
large cat 2: 0.04082798957824707
small hcat: 0.13303399085998535
large hcat: 0.02049088478088379
small hcat 2: 0.06379318237304688
large hcat 2: 0.03898310661315918
small vcat: 1.81790494918823242
large vcat: 1.9143528938293457
small vcat 2: 0.06815600395202637
large vcat 2: 0.03951692581176758
small catnd: 2.60143899917602539
large catnd: 0.12837910652160645
small catnd 2: 1.05365109443664551
large catnd 2: 0.12747406959533691
Wow, vcat is really slow...

Reply to this email directly or view it on GitHub:
#183 (comment)

[JeffBezanson]

It's because the ND arrays here have 1 row, so the inner loop of assign has just 1 iteration. If we used memcpy this case might get even worse.
cat(dim, Array...) can also be more efficient in the small array case by basing it on linear indexing instead of constructing an ntuple of indexes for each assignment. Using assign is good, but constructing all the tuples and range objects will dominate if the arrays involved have 4 elements.