2つの配列を結合するときは何故 push! よりも append! が推奨されるのか?
sizehint! を何故使うべきなのか?

とかあたりの話。今回は一次元配列 (Vector) のみの話で、多次元配列は扱いません。

最近今更ながらデータ構造とアルゴリズムを勉強しているのですが、その手の本を読むと,

配列はサイズが固定だけれども、各要素には $O(1)$ でアクセスできる
リストはサイズを可変にできるけれども、各要素へのアクセスは $O(n)$ かかる*1

と書いてあります。一方で Julia で配列と呼ばれているものは push! や pop! 使って自由に要素数変えることができるのでリストなのかと思いきや、ベンチマークを見る限り各要素へのアクセスは $O(1)$ で行えるようなので配列のようでもあります。配列とリストの良いとこ取りしているような性質を持っているけど、結局のところ Julia の配列って何なの？と疑問で夜も寝られない生活が続いたので、疑問を払拭すべく調べてみました。

概要

他の言語と仕組みに大差ないと思うので重要なことを手短に言うと

push!, pop! の計算量は $O(1)$
Julia の配列の growth factor は 2。
Julia の配列の capacity は pop! で小さくならない。
配列の大体のサイズがわかっているときは sizehint! を使うべし。
頻繁に push!, pop! を使用する場合は DataStructures.jl から適切なデータ構造を使うべし。

※ 今回は Julia 1.1.0 のソースコードを元にしました。今後のバージョンアップで変更になる可能性は十分にあります。

概要
環境
動的配列
DataStructures.jl の Deque
番外編: memory overcommit
まとめ
参考

環境

ArchLinux
Julia 1.1.0

julia> versioninfo()
Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-4460T CPU @ 1.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, haswell)
Environment:
  JULIA_EDITOR = nvim
  JULIA_SHELL = /bin/bash

動的配列

要素の追加

push!

Julia の場合、配列を作ると( [a, b], rand(10)とか) まずはその分のメモリが確保されデータが保存されます。

例としてここでは v = [a, b] という配列を作ったとします。ここに push!(v, c) とすると、

元の配列の2倍の大きさのメモリ領域を確保 (_aligned_malloc, _aligned_realloc, malloc, realloc あたりを使っているっぽい)
新しく確保した領域に元のデータをコピー
3番目の要素に c を代入

という流れで要素が追加されます。

f:id:goropikarikun:20190321120035p:plain

ここでさらに push!(v, d) とすると確保した領域の4番目に空きがあるのでそこに d が代入されます。さらに push!(v, e) とすると今度は空き領域がないので、また 1 ~ 3 の手順に従って要素が追加されます。以降一連の操作の繰り返しで空き領域がなくなったら倍々で配列が大きくなっていきます。 Julia の場合は2倍ずつ大きくなっていきますが Java だったら1.5倍、Python だったら約1.125倍と拡張のされ方は言語によってまちまちです。この何倍されるかという量は growth factor と呼ばれます。また動的にサイズが変わる配列は動的配列と呼ばれます。*2

今回は、配列*3全体の大きさを表す変数を capacity、要素数の変数を length と呼ぶことにします。

配列サイズが大きくなったら capacity が更新され、要素が追加されたら length が 1 増やされます。

f:id:goropikarikun:20190321120213p:plain

en.wikipedia.org

www.geeksforgeeks.org

さて、本当に capacity が倍々に増えるのか実験してみましょう。

Julia の関数に capacity を取得する関数はおそらく用意されていないので、C言語経由で読み取ってみます。

header = if ispath("/usr/include/julia/julia.h")
    "/usr/include/julia"
elseif ispath("$(dirname(Base.julia_cmd()[1]))/../include/julia/julia.h")
    "$(dirname(Base.julia_cmd()[1]))/../include/julia"
else
    println("Can't find julia.h. Please input the path to the file.")
    path = readline()
    while (!ispath(path) )
        println("Can't find julia.h. Please input the path to the file.")
        path = readline()
    end
    path
end
C_code = raw"""
#include "julia.h"

int jl_array_maxsize(jl_array_t *a) {
    return a->maxsize; // maxsize が上記の capacity に相当する
}
"""

const Clib = tempname()
open(`gcc  -I $header -fPIC -O3  -msse3 -xc -shared -o $(Clib * "." * Libdl.dlext) -`, "w") do f
    print(f, C_code) 
end
arraycap(v) = ccall((:jl_array_maxsize, Clib), Int32, (Any,), v)

julia> v = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> for i in 1:10
           push!(v, i)
           println("# of elements = $(lpad(i, 3)): cacacity = $(arraycap(v))")
       end
# of elements =   1: cacacity = 4
# of elements =   2: cacacity = 4
# of elements =   3: cacacity = 4
# of elements =   4: cacacity = 4
# of elements =   5: cacacity = 8
# of elements =   6: cacacity = 8
# of elements =   7: cacacity = 8
# of elements =   8: cacacity = 8
# of elements =   9: cacacity = 16
# of elements =  10: cacacity = 16

期待通り capacity が4, 8, 16 と倍々になることが確認できました。*4

append!

push! と append! の docstring を見ると2つの配列を結合する場合は push! ではなく append! を使うことが推奨されています。

append!(v, w) としたとき裏では (w の capacity) <= (v の capacity) のとき 2 * (v の capacity) の大きさの capacity をもつ配列ができ、 (w の capacity) > (v の capacity) のときは (w の capacity) + (v の capacity) の大きさの capacity をもつ配列ができます。 w の要素を push! で v に追加していった場合、配列の生成とデータのコピーが複数回実行される可能性がありますが、append! を使った場合は配列の生成とデータのコピーが1回で済ませることができます。

要素の削除

要素の削除に関しては追加と比べると単純でpop!(v) とすると単に length が 1 減ります。 length が減るだけで末端のデータを消すこともなければ新しく小さい領域を確保してくることもありません。そのためポインタで指定すれば値を読み取ることができます。

f:id:goropikarikun:20190321170012p:plain

julia> v = rand(3)
3-element Array{Float64,1}:
 0.742018634943469 
 0.5140336610167988
 0.7877759863795775

julia> arraycap(v)
3

julia> pop!(v)
0.7877759863795775

julia> v[3] # アクセスはできない
ERROR: BoundsError: attempt to access 2-element Array{Float64,1} at index [3]
Stacktrace:
 [1] getindex(::Array{Float64,1}, ::Int64) at ./array.jl:729
 [2] top-level scope at none:0

julia> unsafe_load(pointer(v), 3) # pointer からいけば読み取れる
0.7877759863795775

julia> arraycap(v)
3 # capacity は変わらない。

先の例のように capacity = 4 に対して無駄な領域が1つ2つあったところで今どきのコンピュータに積まれているメモリ量を考えればどうってことありませんが、大きな配列から pop! で要素を大量に削除した場合無駄な領域が無視できなくなってきます。

このとき、言語によっては length が capacity に対してある一定以下になると領域を縮小する仕組みが備わっているためメモリの無駄を抑えることができます。追加するときは領域を拡大していきましたが、その反対のことをします。

一方で Julia では pop! でいくら length が小さくなっても領域を自動的に縮小する機構は備わっていません。

f:id:goropikarikun:20190321165903p:plain
※ 先に書いたとおり pop! しても要素が自体が消えることはありませんが、図ではわかりやすさのため消しています。

pop! を使ってもメモリの使用量が減らないことを確認してみます。

julia> run(`free -m`)
              total        used        free      shared  buff/cache   available
Mem:           7852        3922        1075         295        2853        3329
Swap:          4095         486        3609
Process(`free -m`, ProcessExited(0))

julia> n = 50_000_000
50000000

julia> v = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> for i in 1:n
           push!(v, i*10)
       end

julia> run(`free -m`)
              total        used        free      shared  buff/cache   available
Mem:           7852        4289         714         288        2847        2969
Swap:          4095         486        3609
Process(`free -m`, ProcessExited(0))

julia> varinfo()
name                    size summary                        
–––––––––––––––– ––––––––––– –––––––––––––––––––––––––––––––
Base                         Module                         
C_code             159 bytes String                         
Clib                24 bytes String                         
Core                         Module                         
InteractiveUtils 163.804 KiB Module                         
Main                         Module                         
ans                286 bytes Base.Process                   
arraycap             0 bytes typeof(arraycap)               
header              69 bytes String                         
n                    8 bytes Int64                          
v                381.470 MiB 50000000-element Array{Int64,1}

julia> for i in 1:n
           pop!(v)
       end

julia> println(arraycap(v))
57944740

julia> varinfo()
name                    size summary                 
–––––––––––––––– ––––––––––– ––––––––––––––––––––––––
Base                         Module                  
C_code             159 bytes String                  
Clib                24 bytes String                  
Core                         Module                  
InteractiveUtils 163.804 KiB Module                  
Main                         Module                  
ans                  0 bytes Nothing                 
arraycap             0 bytes typeof(arraycap)        
header              69 bytes String                  
n                    8 bytes Int64                   
v                   40 bytes 0-element Array{Int64,1}

julia> run(`free -m`)
              total        used        free      shared  buff/cache   available
Mem:           7852        4310         694         287        2847        2949
Swap:          4095         486        3609
Process(`free -m`, ProcessExited(0))

varinfo で見ると v のサイズが小さくなっているように見えますが、free の結果から pop! の前後でほとんどメモリ使用量が変わっていないことがわかると思います。

メモリ上からデータが消えたわけではないので、パラメターをいじってやれば元の配列が復活します。

julia> C_code2 = raw"""
       #include "julia.h"

       void jl_set_array(jl_array_t *a, int n) {
           a->nrows = n;
           a->length = n;
           a->maxsize = n;
           a->offset = 0;

           return;
       }
       """;

julia> const Clib2 = tempname()
"/tmp/julianSkWap"

julia> open(`gcc  -I $header -fPIC -O3  -msse3 -xc -shared -o $(Clib2 * "." * Libdl.dlext) -`, "w") do f
           print(f, C_code2) 
       end

julia> setarraypar(v, n) = ccall((:jl_set_array, Clib2), Nothing, (Any,Int32,), v, n)
setarraypar (generic function with 1 method)

julia> setarraypar(v, Int32(n))

julia> v
50000000-element Array{Int64,1}:
        10
        20
        30
        40
        50
        60
        70
        80
        90
       100
         ⋮
 499999920
 499999930
 499999940
 499999950
 499999960
 499999970
 499999980
 499999990
 500000000

`sizehint!` で capacity を設定する

連続して push! を使っても自動的に capacity が大きくなっていきますが、最終的な配列に入る要素数が見積もれるのなら sizehint! を使って capacity を設定しましょう。こうすることでデータのコピー回数を減らすことができます。

sizehint! を使った場合とそうでない場合を比較してみます。

julia> using BenchmarkTools

julia> @benchmark begin
           v = Vector{Int}(undef, 0)
           for i in 1:1_000_000
               push!(v, i)
           end
       end
BenchmarkTools.Trial: 
  memory estimate:  9.00 MiB
  allocs estimate:  20
  --------------
  minimum time:     7.161 ms (0.00% GC)
  median time:      11.246 ms (0.00% GC)
  mean time:        10.909 ms (4.27% GC)
  maximum time:     30.634 ms (62.88% GC)
  --------------
  samples:          440
  evals/sample:     1

julia> @benchmark begin
           v = Vector{Int}(undef, 0)
           sizehint!(v, 1_000_000)
           for i in 1:1_000_000
               push!(v, i)
           end
       end
julia> @benchmark begin
                  v = Vector{Int}(undef, 0)
                  sizehint!(v, 1_000_000)
                  for i in 1:1_000_000
                      push!(v, i)
                  end
              end
BenchmarkTools.Trial: 
  memory estimate:  7.63 MiB
  allocs estimate:  2
  --------------
  minimum time:     8.224 ms (0.00% GC)
  median time:      8.445 ms (0.00% GC)
  mean time:        8.513 ms (0.00% GC)
  maximum time:     10.265 ms (0.00% GC)
  --------------
  samples:          540
  evals/sample:     1

sizehint! を使ったほうが約20%早くなりました。また sizehint! を使うとメモリの割り当て、GC が少なくなっていることがわかると思います。

sizehint! は capacity を大きくもできますが、小さくもできます*5 。 pop! 使って無駄な領域が大きくなった配列の capacity を小さくしてみます。

julia> n = 50_000_000
50000000

julia> v = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> for i in 1:n
           push!(v, i*10)
       end

julia> for i in 1:n
           pop!(v)
       end

julia> run(`free -m`);
              total        used        free      shared  buff/cache   available
Mem:           7852        4217         617         311        3017        2974
Swap:          4095         484        3611

julia> sizehint!(v, 10)
0-element Array{Int64,1}

julia> GC.gc()

julia> run(`free -m`);
              total        used        free      shared  buff/cache   available
Mem:           7852        3839         972         331        3039        3331
Swap:          4095         484        3611

sizehint! をすると新たにメモリ割り当てがされるので無駄に大きくなった配列は GC の対象になり、そのうち開放されます。

DataStructures.jl の Deque

今回は詳しくは扱いませんが普通の Julia の配列で pushfirst!, popfirst! をしたときの計算量は $O(n)$ ですが、 DataStructures.jl の Deque を使うと pushfirst!, popfirst! の計算量を $O(1)$ に抑えることができます。もちろん push!, pop! の計算量は $O(1)$ のままです。

加えて Julia の配列では pop! を使っても capacity が小さくなることはありませんでしたが Deque では自動的に配列サイズも小さくなっていきます。このとき、普通の配列をsizehint! 使って小さくしたときとは違って新たなメモリの割り当ては行われません。

頻繁に push! や pop! を使うことが想定される場合は普通の配列では非効率的なことがあるのでパフォーマンスを求める場合は用途にあったデータ構造を適宜選びましょう。

番外編: memory overcommit

この章は Julia とは直接の関係はありません。

sizehint! を使うと裏では realloc とか使ってメモリを確保しているはずなのですが、明らかにメモリ足りてないだろという数値を設定してもエラーが出ないときがあります。

julia> v = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> sizehint!(v, 1024^3)
ERROR: OutOfMemoryError()
Stacktrace:
 [1] sizehint!(::Array{Int64,1}, ::Int64) at ./array.jl:1022
 [2] top-level scope at none:0

julia> sizehint!(v, 50*1024^2)
0-element Array{Int64,1}

julia> w = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> sizehint!(w, 50*1024^2)
0-element Array{Int64,1}

本当にメモリを確保しているというのならば、今頃 800MB くらいメモリを消費していてもよさそうなものですが、システムモニターを見る限りメモリ消費量は全然増えていません。ですが、C言語の本を読むと malloc はメモリ確保できなかったら NULL を返すと書いてあります。もしかして、capacity 変わっていないじゃないかと疑ってみたのですが調べてみるとちゃんと変わっています。

julia> v = Vector{Int}(undef, 0)
0-element Array{Int64,1}

julia> sizehint!(v, 50*1024^2)
0-element Array{Int64,1}

julia> arraycap(v)
52428800

sizehint! 使って push! したとき GC がほぼ 0 になったことを考えるとちゃんと領域を確保しているようなのですが、システムモニターで見る限りはほぼ変わっておらず。

Julia がうまいこと処理しちゃってるのかと思い直接C言語で malloc を使ってみても状況は変わらず。

どういうことかなぁと困っていたのですが、どうやら memory overcommit なるものが関係しているようです。

proger.blog10.fc2.com

上記の記事によるとまずは仮想メモリに割り当てられるとのこと。htop で見ると、なるほど確かに Julia のところが真っ赤になってる。

f:id:goropikarikun:20190322022611p:plain

malloc が失敗しなくても安心するなよという教訓を得ました。

まとめ

用途に応じて最適なデータ構造を選ぶことが大事
pop! 使いすぎるとメモリを無駄遣いする可能性がある
Juliaと仲良くなるためにはC言語とも仲良くする必要がある

参考

push!: https://github.com/JuliaLang/julia/blob/v1.1.0/base/array.jl#L851-L857
_growend: https://github.com/JuliaLang/julia/blob/v1.1.0/base/array.jl#L812-L813
jl_array_grow_end: https://github.com/JuliaLang/julia/blob/v1.1.0/src/array.c#L907-L911
jl_array_grow_at_end: https://github.com/JuliaLang/julia/blob/v1.1.0/src/array.c#L814-L890
jl_array_t: https://github.com/JuliaLang/julia/blob/v1.1.0/src/julia.h#L166-L185
pop!: https://github.com/JuliaLang/julia/blob/v1.1.0/base/array.jl#L1061-L1068
_deleteend: https://github.com/JuliaLang/julia/blob/v1.1.0/base/array.jl#L821-L822
jl_array_del_end: https://github.com/JuliaLang/julia/blob/v1.1.0/src/array.c#L1083-L1093
jl_array_del_at_end: https://github.com/JuliaLang/julia/blob/v1.1.0/src/array.c#L1027-L1050
sizehint!: https://github.com/JuliaLang/julia/blob/v1.1.0/base/array.jl#L1021-L1024
jl_array_sizehint: https://github.com/JuliaLang/julia/blob/v1.1.0/src/array.c#L1095-L1117
Dynamic array - Wikipedia
How do Dynamic arrays work? - GeeksforGeeks
mallocの落とし穴 - 組み込みLinuxでのmemory overcommit - 職業としてのプログラミング

gist216bda6b0d3fb339a238eb99179c5722

*1:より正確には片方向リストなら k 番目にアクセスする場合 O(k), 双方向リストならノード数 n のとき O( min(k, n-k) ) なわけですが、片方向リストの最悪の場合と言うことで。

*2:より正確にはサイズは動的に変わっているけれどもバックエンドに静的配列を使用しているもの。

*3:malloc で確保した領域を配列を読んでいいのかいささか疑問ですが便宜上配列と呼ぶことにします。

*4:初期の配列サイズが小さいときに限り capacity は倍々でなく 4 にセットされる。

*5:length より小さくはできません

goropikariの備忘録

Julia - 配列の実装について

概要

環境

動的配列

要素の追加

push!

append!

要素の削除

`sizehint!` で capacity を設定する

DataStructures.jl の Deque

番外編: memory overcommit

まとめ

参考

概要

環境

動的配列

要素の追加

push!

append!

要素の削除

sizehint! で capacity を設定する

DataStructures.jl の Deque

番外編: memory overcommit

まとめ

参考

`sizehint!` で capacity を設定する