sub2ind bounds checking

[dressel]

I think sub2ind needs to do some bounds-checking. If I try something like:

#julia
sub2ind( (10,10), 11, 2)

Julia spits out 21. I was expecting it to throw an error. If you try the same thing in Matlab, it will do something like:

>> sub2ind( [10,10], 11, 2)
Error using sub2ind (line 52)
Out of range subscript.

I haven't been able to find anything about this in the developer's or user's groups, but please let me know if there is some reasoning for this somewhere. I feel it should throw an error. If not, maybe it should be noted in the standard library documentation.

[timholy]

Yes, it definitely should check. Are you up for fixing it, or do you need someone else to do it? If you want to try it yourself but are quite new to julia, @which sub2ind((10,10), 11, 2) will tell you where to look.

[dressel]

I'm up for fixing it, but won't get around to it until Thursday, if that's ok.

[timholy]

It's gone this long without...

[ivarne]

Is this related to #4044?

[timholy]

Not in any sense that I'm aware of---that's an issue about bounds-checking upon construction. I suppose the closest analog would be to check the first argument of sub2ind to make sure there are no negative entries.

SubArrays also need to do bounds checking eventually, but that's much more complicated (requires #8227).

[dressel]

So I've looked into this and I'm not sure now that we want to do this. I've run a simple test and it just comes back much slower if I check the bounds. I feel like this is important because people (like myself) usually stick this in some inner loop and run it many times.

If we don't bounds-check, the documentation definitely needs to be updated. An alternative might be to allow for optional bounds checking. What does anyone else think should be done?

[StefanKarpinski]

I suspect that the slowness was the reason for the lack of bounds checks in the first place.

[ivarne]

Seems like we have another usecase for #7799

[timholy]

@dressel, what if you use the @inline macro?

[lindahua]

sub2ind is used in many places for element accessing.

Consider the following implementation:

function getindex(a::SomeArray, i::Integer, j::Integer)
    # ... check whether i and j are in valid ranges ...
    a[sub2ind(size(a), i, j)]
end

It actually performs bound-checking for multiple times:

• Check the subscripts i and j at the level of getindex
• Check the subscripts i and j within sub2ind (suppose bound-checking is implemented within sub2ind)
• Check the linear index in the operation a[ . ].

We should definitely draw a line as to when/where we should do bounds checking, and how this works with @inbounds.

[StefanKarpinski]

I'm pretty ok with saying that sub2ind is just a utility function that does a particularly useful linear transformation of indices without doing any bounds checking. You still get bounds checks when you index into the actual array, so you can't index out of bounds entirely, you can just access an unexpected – but valid – element of the array.

[nalimilan]

OTOH silently returning a nonsensical value for sub2ind isn't great, and people can use @inbounds when indexing after calling it if they care. (If bounds checks were inlined, wouldn't the compiler be able to get rid of the redundant check anyway?)

[timholy]

In @lindahua's example, certainly you'd want to call a variant of sub2ind that has no bounds check, since you've already done the check. I still think bounds checks make sense here, but I agree that #8227 (or variant) should probably be merged first.

[lindahua]

Something like below?

check_bounds(siz, i, j) = (1 <= i <= siz[1] && 1 <= j <= siz[2]) || throw(BoundsError())
_sub2ind(siz, i, j) = i + siz[1] * (j-1)

@inline function sub2ind(siz, i, j)
   check_bounds(siz, i, j)
   _sub2ind(siz, i, j)
end

People can call _sub2ind when they think it is not necessary to perform bound checking within sub2ind.

[timholy]

Yes, that's a manual way to do it, but perhaps cleaner would be to hook this into @inbounds as in #8227.

[felixcremer]

Isn't this closed in #25113?
There sub2ind is deprecated and replaced by LinearIndices which throw a BoundsError.

[nalimilan]

Indeed!