Array indexing with UInt is ~5x slower than with Int

[bicycle1885]

This is the benchmark script:

function mysum_int(data)
    sum = 0
    for i in Int(1):Int(endof(data))
        @inbounds sum += data[i]
    end
    return sum
end

function mysum_uint(data)
    sum = 0
    for i in UInt(1):UInt(endof(data))
        @inbounds sum += data[i]
    end
    return sum
end

let
    size = 128 * 2^20
    data = zeros(UInt8, size)
    println("mysum_int")
    mysum_int(data)
    @time mysum_int(data)
    @time mysum_int(data)
    @time mysum_int(data)

    println("mysum_uint")
    mysum_uint(data)
    @time mysum_uint(data)
    @time mysum_uint(data)
    @time mysum_uint(data)
end

And the result:

~/.j/v/BGZFStreams (master|✚1…) $ julia-dev access.jl
mysum_int
  0.022742 seconds (152 allocations: 9.028 KB)
  0.020606 seconds (4 allocations: 160 bytes)
  0.023985 seconds (4 allocations: 160 bytes)
mysum_uint
  0.118161 seconds (4 allocations: 160 bytes)
  0.116512 seconds (4 allocations: 160 bytes)
  0.118702 seconds (4 allocations: 160 bytes)

I don't know the internal, but I guess an index value is converted to Int before accessing and inexact check imposes the cost on it. data[Int(i)] results in the slowdown at the same level but data[reinterpret(Int, i)] doesn't show any slowdown.

---

julia> versioninfo()
Julia Version 0.5.0-dev+4934
Commit 1a1a9a6* (2016-06-25 02:49 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin14.5.0)
  CPU: Intel(R) Core(TM) i5-4288U CPU @ 2.60GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.7.1 (ORCJIT, haswell)

[eschnett]

Examining @code_native [1.0][Uint(1)] shows that this code has indeed two branches. I assume the reason they cannot be combined because Julia needs to throw two different errors depending on whether the unsigned index is too large for a signed integer, or is too large for the array.

The elegant solution is probably to define all getindex functions with Integer as index type, so that bounds checking sees the unsigned integer directly, avoiding the conversion.

[ViralBShah]

Cc @timholy

[timholy]

This can probably be tackled while we're in RC, or for 0.5.x.

[timholy]

I just took a peek at this, and doing it properly is well beyond the scope of my interests and what I have time for (finishing off #16973), so I'm marking this as "up for grabs." The getindex functions support Real, not just Integer, so we're already plenty general. However, for general AbstractArrays it seems very likely that to_index and bounds-checking might duplicate some conversion steps---and since these conversions are checked, they will be expensive.

In the specific case of Array, it's much more direct because of these definitions, but it might involve some changes to array.c and codegen.cpp since arrayref and the bounds-checking are defined/performed in C.

What's the use-case for indexing with unsigned integers, anyway? Arrays require Int sizes (they can't support arrays bigger than typemax(Int)), and unsigneds are evil in many ways.

[bicycle1885]

The actual use-case would be limited; that would be why we have never noticed this performance problem until now. I noticed this problem while profiling a decompressor which uses an unsigned integer to specify a byte offset. I can avoid the performance degradation by using the reinterpret(Int, index) trick, but I thought this should be fixed in the upstream.

[oscardssmith]

Good and bad news on this. In v 0.5.0, Good: uint performance is only 20% slower than int. Bad: I think that is only because int had a 4x regression.

[StefanKarpinski]

How could we possibly have had that bad a regression on array indexing and not have noticed it?

[yuyichao]

I cannot reproduce the regression on Int.

[oscardssmith]

That's possible, I was comparing direct times and assuming that there wouldn't be a 4x difference between computers (silly me). In that case, should this be closed as the difference is now fairly negligible?

[yuyichao]

I can still reproduce the Int, UInt difference.

[mbauman]

The key is this:

data[Int(i)] results in the slowdown at the same level but data[reinterpret(Int, i)] doesn't show any slowdown.

If that's still the case, then the issue isn't in the complexity of the indexing fallbacks, but, rather, it's simply that we choose to use a checked conversion to Int. We may be able to change that for UInt since the values that will be interpreted as negative will also be those that'll throw a bounds error, but this isn't the case for smaller integers.

This is particularly problematic since the optimal order of operations between checking bounds and index conversion is dependent on the index types themselves.

[bicycle1885]

This is particularly problematic since the optimal order of operations between checking bounds and index conversion is dependent on the index types themselves.

Yes, indexes to an array are always converted to Int before actual indexing. That's the problem here. I'm not sure whether it is possible or not, but it would be better to flip the order of operations so that any integer can be used as an index.

[mbauman]

Update:

For AbstractArrays, in general, we've now fixed the twice-conversion problems Tim mentions in #17103 (comment). We absolutely do need to convert to Int in those cases since that's what we require library creators to implement. Library creators, of course, are always free to define optimized indexing for any index type they like.

For Array, however, the rest of that comment still stands. It'd be a decent amount of work for this limited situation.

[KristofferC]

I think this is fixed as far as we can with #29784.