Подтвердить что ты не робот

Избегайте выделения памяти при индексировании массива в Julia

Вопрос: Я хотел бы индексировать массив без запуска распределения памяти, особенно при передаче индексированных элементов в функцию. Из чтения документов Julia я подозреваю, что ответ вращается вокруг, используя функцию sub, но не могу понять, как...

Рабочий пример: Я строю большой вектор Float64 (x), а затем индекс для каждого наблюдения в x.

N = 10000000
x = randn(N)
inds = [1:N]

Теперь я выполняю функцию mean по x и x[inds] (сначала я запускаю mean(randn(2)), чтобы избежать каких-либо несоответствий компилятора в синхронизации):

@time mean(x)
@time mean(x[inds])

Это идентичный расчет, но, как и ожидалось, результаты таймингов:

elapsed time: 0.007029772 seconds (96 bytes allocated)
elapsed time: 0.067880112 seconds (80000208 bytes allocated, 35.38% gc time)

Итак, существует ли способ решения проблемы распределения памяти для произвольного выбора inds (и произвольного выбора массива и функции)?

4b9b3361

ОТВЕТЫ

Ответ 1

РЕДАКТИРОВАТЬ: прочитайте также ответ, чтобы получить полную картину!

При использовании массива индексов ситуация сейчас невелика на Julia 0.4-pre (начало февраля 2015 года):

julia> N = 10000000;
julia> x = randn(N);
julia> inds = [1:N];
julia> @time mean(x)
elapsed time: 0.010702729 seconds (96 bytes allocated)
elapsed time: 0.012167155 seconds (96 bytes allocated)
julia> @time mean(x[inds])
elapsed time: 0.088312275 seconds (76 MB allocated, 17.87% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.073672734 seconds (76 MB allocated, 3.27% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.071646757 seconds (76 MB allocated, 1.08% gc time in 1 pauses with 0 full sweep)
julia> xs = sub(x,inds);  # Only works on 0.4
julia> @time mean(xs)
elapsed time: 0.057446177 seconds (96 bytes allocated)
elapsed time: 0.096983673 seconds (96 bytes allocated)
elapsed time: 0.096711312 seconds (96 bytes allocated)
julia> using ArrayViews
julia> xv = view(x, 1:N)  # Note use of a range, not [1:N]!
julia> @time mean(xv)
elapsed time: 0.012919509 seconds (96 bytes allocated)
elapsed time: 0.013010655 seconds (96 bytes allocated)
elapsed time: 0.01288134 seconds (96 bytes allocated)
julia> xs = sub(x,1:N)  # Works on 0.3 and 0.4
julia> @time mean(xs)
elapsed time: 0.014191482 seconds (96 bytes allocated)
elapsed time: 0.014023089 seconds (96 bytes allocated)
elapsed time: 0.01257188 seconds (96 bytes allocated)
  • Итак, хотя мы можем избежать выделения памяти, мы все еще медленнее (!).
  • Проблема заключается в индексировании массивом, а не в диапазоне. Вы не можете использовать sub для этого на 0.3, но можете на 0.4.
  • Если мы можем индексировать диапазон, то мы можем использовать ArrayViews.jl на 0,3 и его встроенный на 0.4. Этот случай в значительной степени похож на оригинальный mean.

Я заметил, что с меньшим количеством используемых индексов (вместо всего диапазона) разрыв намного меньше, а распределение памяти невелико, поэтому sub может стоить:

N = 100000000
x = randn(N)
inds = [1:div(N,10)]

@time mean(x)
@time mean(x)
@time mean(x)
@time mean(x[inds])
@time mean(x[inds])
@time mean(x[inds])
xi = sub(x,inds)
@time mean(xi)
@time mean(xi)
@time mean(xi)

дает

elapsed time: 0.092831612 seconds (985 kB allocated)
elapsed time: 0.067694917 seconds (96 bytes allocated)
elapsed time: 0.066209038 seconds (96 bytes allocated)
elapsed time: 0.066816927 seconds (76 MB allocated, 20.62% gc time in 1 pauses with 1 full sweep)
elapsed time: 0.057211528 seconds (76 MB allocated, 19.57% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.046782848 seconds (76 MB allocated, 1.81% gc time in 1 pauses with 0 full sweep)
elapsed time: 0.186084807 seconds (4 MB allocated)
elapsed time: 0.057476269 seconds (96 bytes allocated)
elapsed time: 0.05733602 seconds (96 bytes allocated)

Ответ 2

Просто используйте xs = sub(x, 1:N). Обратите внимание, что это отличается от x = sub(x, [1:N]); на julia 0.3 последний провалится, а на julia 0.4-pre последний будет значительно медленнее первого. На julia 0.4-pre, sub(x, 1:N) выполняется так же быстро, как view:

julia> N = 10000000;

julia> x = randn(N);

julia> xs = sub(x, 1:N);

julia> using ArrayViews

julia> xv = view(x, 1:N);

julia> mean(x)
-0.0002491126429772525

julia> mean(xs)
-0.0002491126429772525

julia> mean(xv)
-0.0002491126429772525

julia> @time mean(x);
elapsed time: 0.015345806 seconds (27 kB allocated)

julia> @time mean(xs);
elapsed time: 0.013815785 seconds (96 bytes allocated)

julia> @time mean(xv);
elapsed time: 0.015871052 seconds (96 bytes allocated)

Существует несколько причин, по которым sub(x, inds) медленнее, чем sub(x, 1:N):

  • Каждый доступ xs[i] соответствует x[inds[i]]; мы должны искать две ячейки памяти, а не одну.
  • Если inds не в порядке, вы получите плохое поведение кэша при доступе к элементам x
  • Он уничтожает возможность использования векторизации SIMD

В этом случае последний, вероятно, является самым важным эффектом. Это не ограничение Юлии; то же самое произойдет, если вы напишете эквивалентный код в C, Fortran или сборке.

Обратите внимание, что еще быстрее сказать sum(sub(x, inds)), чем sum(x[inds]), (до тех пор, пока последний не станет первым, который он должен был к тому времени, когда julia 0.4 официально отсутствует). Но если вам нужно выполнять много операций с xs = sub(x, inds), в некоторых случаях вам стоит сделать копию, даже если она выделяет память, просто чтобы вы могли использовать возможности оптимизации, когда значения хранятся в непрерывной памяти.