Правила распространения @inbounds в Юлии

Question

Я ищу разъяснения по правилам проверки границ в Джулии. Это означает, что если я положу @inbounds в начале цикла for,

@inbounds for ... end

тогда только для "одного слоя" распространяются границы, поэтому, если внутри этого есть цикл for, @inbounds не отключите там проверку границ? И если я использую @propagate_inbounds, он пойдет внутри вложенного цикла?

И правильно ли говорить @inbounds всегда побеждает @boundscheck? Единственное исключение, если функция не встроенная, но это случай предыдущего правила "одного слоя", поэтому @propagate_inbounds бы отключить проверку границ даже при вызове функции без вложений?

Answer 1

Когда руководство говорит о @inbounds распространяясь через "один слой", это конкретно относится к границам вызовов функций. Тот факт, что он может влиять только на функции, которые являются встроенными, является второстепенным требованием, которое делает его особенно запутанным и сложным для тестирования, поэтому давайте не будем беспокоиться о вставке до тех пор, пока позже.

@inbounds макрос аннотирует вызовы функций так, что они могут исключить проверки границ. Фактически, макрос будет делать это для всех вызовов функций в выражении, которое ему передано, включая любое количество вложенных for петли, begin блоки, if операторы и т. д. И, конечно же, индексирование и индексированное присваивание - это просто "сахара", которые ниже вызовов функций, поэтому они влияют на них одинаково. Все это имеет смысл; как автор кода, который обернут @inboundsвы можете увидеть макрос и убедиться, что это безопасно.

Но @inbounds макрос говорит Юлии сделать что-нибудь смешное. Это меняет поведение кода, написанного в совершенно другом месте! Например, когда вы комментируете вызов:

julia> f() = @inbounds return getindex(4:5, 10);
       f()
13

Макрос эффективно проникает в стандартную библиотеку и отключает @boundscheck блок, позволяющий вычислять значения за пределами допустимой области диапазона.

Это жуткое действие на расстоянии… и, если оно не будет тщательно ограничено, оно может закончить удалением проверок границ из кода библиотеки, если это не предназначено или не является полностью безопасным для этого. Вот почему есть ограничение "в один слой"; мы хотим удалить проверки границ только тогда, когда авторы явно знают, что это может произойти, и включите удаление.

Теперь, как автор библиотеки, могут быть случаи, когда вы хотите включить @inbounds распространяться на все функции, которые вы вызываете в методе. Это где Base.@propagate_inbounds используется. В отличие от @inbounds, который аннотирует вызовы функций, @propagate_inbounds аннотирует определения методов, чтобы позволить внутреннему состоянию, с которым вызывается метод, распространяться на все вызовы функций, которые вы делаете в реализации метода. Это немного сложно описать абстрактно, поэтому давайте рассмотрим конкретный пример.

Пример

Давайте создадим игрушечный пользовательский вектор, который просто создает перемешанное представление в векторе, который он оборачивает:

julia> module M
       immutable ShuffledVector{A,T} <: AbstractVector{T}
           data::A
           perm::Vector{Int}
       end
       ShuffledVector{T}(A::AbstractVector{T}) = ShuffledVector{typeof(A), T}(A, randperm(length(A)))
       Base.size(A::ShuffledVector) = size(A.data)
       @inline function Base.getindex(A::ShuffledVector, i::Int)
           A.data[A.perm[i]]
       end
       end

Это довольно просто - мы оборачиваем любой векторный тип, создаем случайную перестановку, а затем при индексации просто индексируем в исходный массив, используя перестановку. И мы знаем, что все доступы к частям массива должны быть в порядке на основе внешнего конструктора… поэтому, даже если мы сами не проверяем границы, мы можем положиться на внутренние выражения индексации, которые выдают ошибки, если мы индексируем вне границ.

julia> s = M.ShuffledVector(1:4)
4-element M.ShuffledVector{UnitRange{Int64},Int64}:
 1
 2
 4
 3

julia> s[5]
ERROR: BoundsError: attempt to access 4-element Array{Int64,1} at index [5]
 in getindex(::M.ShuffledVector{UnitRange{Int64},Int64}, ::Int64) at ./REPL[5]:9

Обратите внимание, что ошибка границ связана не с индексацией в ShuffledVector, а с индексацией в векторе перестановок. A.perm[5], Теперь, возможно, пользователь нашего ShuffledVector хочет, чтобы его доступ был быстрее, поэтому он пытается отключить проверку границ с помощью @inbounds:

julia> f(A, i) = @inbounds return A[i]
       f(s, 5)
ERROR: BoundsError: attempt to access 4-element Array{Int64,1} at index [5]
 in getindex at ./REPL[5]:9 [inlined]
 in f(::M.ShuffledVector{UnitRange{Int64},Int64}, ::Int64) at ./REPL[15]:1

Но они все еще получают предельные ошибки! Это потому что @inbounds аннотация только пыталась удалить @boundscheck блоки из метода, который мы написали выше. Он не распространяется на стандартную библиотеку, чтобы удалить проверку границ из A.perm массив, ни A.data спектр. Это довольно много, хотя они пытались убрать границы! Таким образом, мы можем вместо этого написать выше getindex метод с Base.@propagate_inbounds аннотация, которая позволит этому методу "наследовать" внутреннее состояние вызывающего:

julia> module M
       immutable ShuffledVector{A,T} <: AbstractVector{T}
           data::A
           shuffle::Vector{Int}
       end
       ShuffledVector{T}(A::AbstractVector{T}) = ShuffledVector{typeof(A), T}(A, randperm(length(A)))
       Base.size(A::ShuffledVector) = size(A.data)
       Base.@propagate_inbounds function Base.getindex(A::ShuffledVector, i::Int)
           A.data[A.shuffle[i]]
       end
       end
M

julia> s = M.ShuffledVector(1:4)
       s[5] # It still throws errors for out-of-bounds accesses
ERROR: BoundsError: attempt to access 4-element Array{Int64,1} at index [5]
 in getindex(::M.ShuffledVector{UnitRange{Int64},Int64}, ::Int64) at ./REPL[1]:9

julia> f(s, 5) # That @inbounds now affects the inner indexing calls, too!
0

Вы можете проверить, что нет веток с @code_llvm f(s, 5),

Но, на самом деле, в этом случае я думаю, что было бы гораздо лучше написать реализацию метода getindex с @boundscheck собственный блок:

@inline function Base.getindex(A::ShuffledVector, i::Int)
    @boundscheck checkbounds(A, i)
    @inbounds r = A.data[A.shuffle[i]]
    return r
end

Это немного более многословно, но теперь это на самом деле вызовет ошибку границ ShuffledVector введите вместо утечки детали реализации в сообщении об ошибке.

Эффект встраивания

Вы заметите, что я не проверяю @inbounds в глобальной области видимости выше, и вместо этого используйте эти маленькие вспомогательные функции. Это потому, что удаление проверки границ работает только тогда, когда метод встроен и скомпилирован. Поэтому простая попытка удалить границы в глобальной области не сработает, так как не может встроить вызов функции в интерактивный REPL:

julia> @inbounds getindex(4:5, 10)
ERROR: BoundsError: attempt to access 2-element UnitRange{Int64} at index [10]
 in throw_boundserror(::UnitRange{Int64}, ::Int64) at ./abstractarray.jl:272
 in getindex(::UnitRange{Int64}, ::Int64) at ./range.jl:450

В глобальном масштабе здесь не происходит компиляции или вставки, поэтому Джулия не может убрать эти границы. Точно так же Джулия не может встроить методы, когда есть нестабильность типа (например, при доступе к непостоянному глобальному), поэтому она также не может удалить эти проверки границ:

julia> r = 1:2
       g() = @inbounds return r[3]
       g()
ERROR: BoundsError: attempt to access 2-element UnitRange{Int64} at index [3]
 in throw_boundserror(::UnitRange{Int64}, ::Int64) at ./abstractarray.jl:272
 in getindex(::UnitRange{Int64}, ::Int64) at ./range.jl:450
 in g() at ./REPL[19]:2