행렬 전치 및 열 주요 메모리 레이아웃 유지

Dec 10 2020

문제 설명 : 행렬의 행 노름

랜덤 행렬 M의 모든 열의 규범을 계산하는이 장난감 예제를 고려하십시오.

julia> M = rand(Float64, 10000, 10000);

julia> @time map(x -> norm(x), M[:,j] for j in 1:size(M)[2]);
  0.363795 seconds (166.70 k allocations: 770.086 MiB, 27.78% gc time)

그런 다음 행 표준을 계산합니다.

julia> @time map(x -> norm(x), M[:,i] for i in 1:size(M)[1]);
  1.288872 seconds (176.19 k allocations: 770.232 MiB, 0.37% gc time)

두 실행 사이의 요소는 매트릭스의 메모리 레이아웃 (열 주요) 때문이라고 생각합니다. 실제로 행 규범의 계산은 연속적이지 않은 데이터에 대한 루프이므로 캐시 미스가있는 벡터화되지 않은 코드가 생성됩니다. 두 표준 계산에 대해 동일한 실행 시간을 갖고 싶습니다.

M행의 규범을 계산할 때 동일한 속도를 얻기 위해의 레이아웃 을 행 전공 으로 변환 할 수 있습니까?

나는 무엇을 시도 했는가

나는 함께 노력 transpose하고 permutedims는 이러한 기능을 사용하는 경우 메모리가 행 주 (원래 행렬의 주요 그래서 열)에 지금 것 같다, 성공하지.

julia> Mt = copy(transpose(M));

julia> @time map(x -> norm(x), Mt[j,:] for j in 1:size(M)[2]);
  1.581778 seconds (176.19 k allocations: 770.230 MiB)

julia> Mt = copy(permutedims(M,[2,1]));

julia> @time map(x -> norm(x), Mt[j,:] for j in 1:size(M)[2]);
  1.454153 seconds (176.19 k allocations: 770.236 MiB, 9.98% gc time)

내가 사용하는 copy새로운 레이아웃을 강제하려고 여기.

전치의 열 중심 레이아웃 또는 원래 행렬의 행 중심 레이아웃을 어떻게 강제 할 수 있습니까?

편집하다

@mcabbott와 @ przemyslaw-szufel이 지적했듯이 내가 보여준 마지막 코드에 오류가 있었는데 Mt, 열의 표준 대신 행의 표준을 계산했습니다 .

Mt대신 줄 의 규범에 대한 테스트 :

julia> Mt = transpose(M);
julia> @time map(x -> norm(x), M[:,j] for j in 1:size(M)[2]);
  1.307777 seconds (204.52 k allocations: 772.032 MiB, 0.45% gc time)

julia> Mt = permutedims(M)
julia> @time map(x -> norm(x), M[:,j] for j in 1:size(M)[2]); 
  0.334047 seconds (166.53 k allocations: 770.079 MiB, 1.42% gc time)

그래서 결국에는 permutedims예상대로 칼럼 메이저 매장 인 것 같습니다 . 실제로 Julia 배열은 항상 column-major에 저장됩니다. 열 중심 저장된 행렬 transpose의 행 중심이기 때문에 일종의 예외 view입니다.

답변

3 PrzemyslawSzufel Dec 11 2020 at 02:39

여기에는 몇 가지 문제가 있습니다.

코드를 잘못 벤치마킹하고 있습니다. 대부분의 경우 첫 번째 실행에서 컴파일 된 코드를 테스트하고 두 번째 실행에서 컴파일되지 않은 코드 (따라서 컴파일 시간 측정)를 테스트합니다. 항상 @time두 번 실행 하거나 대신 BenchmarkTools를 사용해야합니다.
코드가 비효율적입니다-불필요한 메모리 복사
M의 유형은 불안정하므로 측정에는 일반적으로 Julia 기능을 실행하는 경우가 아닌 유형을 찾는 시간이 포함됩니다.
람다가 필요하지 않습니다. 함수를 직접 구문 분석 할 수 있습니다.
@mcabbott에서 언급했듯이 코드에 버그가 포함되어 있으며 동일한 것을 두 번 측정하고 있습니다. 코드를 정리하면 다음과 같습니다.

julia> using LinearAlgebra, BenchmarkTools

julia> const M = rand(10000, 10000);

julia> @btime map(norm, @view M[:,j] for j in 1:size(M)[2]);
  49.378 ms (2 allocations: 78.20 KiB)

julia> @btime map(norm, @view M[i, :] for i in 1:size(M)[1]);
  1.013 s (2 allocations: 78.20 KiB)

이제 데이터 레이아웃에 대한 질문입니다. Julia는 열 중심 메모리 레이아웃을 사용하고 있습니다. 따라서 열에서 작동하는 작업은 행에서 작동하는 작업보다 빠릅니다. 한 가지 가능한 해결 방법은 다음의 전치 사본을 갖는 것입니다 M.

const Mᵀ = collect(M')

복사하는 데 약간의 시간이 필요하지만 나중에 성능을 일치시킬 수 있습니다.

julia> @btime map(norm, @view Mᵀ[:,j] for j in 1:size(M)[2]);
  48.455 ms (2 allocations: 78.20 KiB)

julia> map(norm, Mᵀ[:,j] for j in 1:size(M)[2]) == map(norm, M[i,:] for i in 1:size(M)[1])
true

2 DNF Dec 11 2020 at 18:00

규범을 계산할 때 각 열 / 행의 복사본을 만드는 데 많은 시간을 낭비하고 있습니다. view대신 s를 사용 하거나 더 나은 방법으로 eachcol/를 사용하십시오 eachrow.