"for x in A" array iteration should imply @inbounds?

[stevengj]

Here's something odd I noticed when looking at #11241. Compare the following two functions:

function foo(s::Vector{UInt8})
    for c in s
        c >= 128 && return false
    end
    return true
end
function bar(s::Vector{UInt8})
    for i = 1:length(s)
        @inbounds s[i] >= 128 && return false
    end
    return true
end

I would have thought that these would be roughly equivalent in terms of speed, but code_native shows that vastly less code is generated for bar than for foo:

julia> code_native(foo, (Vector{UInt8},))
    .section    __TEXT,__text,regular,pure_instructions
Filename: none
Source line: 2
    pushq   %rbp
    movq    %rsp, %rbp
Source line: 2
    cmpq    $0, 8(%rdi)
    jle L65
    movq    8(%rdi), %rdx
    xorl    %ecx, %ecx
L21:    cmpq    %rdx, %rcx
    jae L72
    movq    (%rdi), %rsi
    xorb    %al, %al
    cmpb    $0, (%rsi,%rcx)
    js  L67
Source line: 3
    leaq    1(%rcx), %rax
    addq    $2, %rcx
    cmpq    %rcx, %rdx
    movq    %rax, %rcx
    jge L21
L65:    movb    $1, %al
L67:    movq    %rbp, %rsp
    popq    %rbp
    ret
Source line: 2
L72:    movq    %rsp, %rax
    leaq    -16(%rax), %rsi
    movq    %rsi, %rsp
    incq    %rcx
    movq    %rcx, -16(%rax)
    movabsq $jl_bounds_error_ints, %rax
    movl    $1, %edx
    callq   *%rax

julia> code_native(bar, (Vector{UInt8},))
    .section    __TEXT,__text,regular,pure_instructions
Filename: none
Source line: 2
    pushq   %rbp
    movq    %rsp, %rbp
Source line: 2
    movq    8(%rdi), %rcx
    testq   %rcx, %rcx
    jle L43
Source line: 3
    movq    (%rdi), %rdx
    xorb    %al, %al
L22:    cmpb    $0, (%rdx)
    js  L45
    incq    %rdx
    decq    %rcx
    jne L22
L43:    movb    $1, %al
L45:    popq    %rbp
    ret

Note in particular that foo apparently still thinks that it can throw a BoundsError, even though for c in s should always be in-bounds.

Is this a known issue?

[ScottPJones]

Have you tried putting the @inbounds before the for in foo?

[stevengj]

@ScottPJones, you're right, @inbounds for c in s shortens the generated code for foo to

    .section    __TEXT,__text,regular,pure_instructions
Filename: none
Source line: 2
    pushq   %rbp
    movq    %rsp, %rbp
Source line: 2
    cmpq    $0, 8(%rdi)
    jle L50
    movq    (%rdi), %rcx
    movl    $1, %edx
    xorb    %al, %al
L25:    cmpb    $0, (%rcx)
    js  L52
Source line: 3
    incq    %rcx
Source line: 2
    incq    %rdx
Source line: 3
    cmpq    %rdx, 8(%rdi)
    jge L25
L50:    movb    $1, %al
L52:    popq    %rbp
    ret

which is only one instruction longer than for bar, not too bad.

I guess the real issue is that @inbounds shouldn't be necessary here. The compiler should know that for x in A is always in bounds.

[ScottPJones]

It's good that you caught this... until this is fixed, at least I know how to improve the "abstract" versions of operating on strings (after #11004 hopefully is merged)

[stevengj]

I guess the problem is that for x in A could go out of bounds if A is some user-defined iterator type and there is a buggy iterator implementation. (i.e. someone writes a buggy next or done.) It would be nice to throw an exception in this case rather than crashing, hence the bounds checks are necessary.

But for debugged iterators, like the built-in array iterators, can we put an @inbounds in the next function etc. in order to turn off the bounds checks?

[johnmyleswhite]

We could, although the next function could still be unsafe if the iterator is invalidated inside the body of the for loop.

[ScottPJones]

So, it sounds like it still needs to be left up to the programmer to add @inbounds around the for...
(unless the compiler could be made a lot smarter, to be able to invalidate or add @inbounds on the next code based on the code in the loop)

[stevengj]

@johnmyleswhite, you mean if the array is resized inside the body of the for loop?

[johnmyleswhite]

@stevengj, that's an example of what I had in mind.

[simonster]

I don't think resizing should present an issue for Array iteration since done checks i > length(a). But for e.g. Dicts there could be problems.

Some related discussion in #7799 (comment).

[toivoh]

Another case that might give trouble is if someone uses start, next, and done manually and doesn't quite follow the iterator protocol.

Or if someone tampers with an iterator. You shouldn't do that of course, but should it be able to cause memory corruption?

[stevengj]

@toivoh,I'm thinking that the for construct itself could effectively insert the @inbounds. So that if you call the iterators manually it won't be there.

[toivoh]

That might be reasonable, but it should only apply to the iterator operations. But I still think it would have to be a new kind of @inbounds so that it won't apply unless the specific next and done methods have been marked as safe somehow.

[JeffBezanson]

I'm going to make the call that this would be too dangerous.

[nalimilan]

I guess the Polly work could help hoisting bounds check in the standard cases?

[stevengj]

See also #15291 for a way to address this.