Nim言語で複数のコンパイラを試す for 競技プログラミング
初記事です。
Nim言語とコンパイラ
Nim言語にコンパイラを設定する項目があることをご存知でしょうか。
公式のガイドを覗いてみると、以下の記述があります。
To change the compiler from the default compiler (at the command line):
nim c --cc:llvm_gcc --compile_only myfile.nim︙
ということで、今回は主にAtCoder上で公開されているいくつかの問題について、コンパイラごとに速度を比較してみようと思います。
計測するコンパイラと計測方法
今回計測するコンパイラは以下の2つです。
使用できる言語とライブラリの一覧を確認してみるとC++についてはgccとclangが用意されていますが、C++にトランスパイルするNim言語も同じように言語仕様としては複数の候補からコンパイラを選択できるのです。 デフォルトだとgccが使われます。
コードの雛形は下のようになります。(以下はclangの例)
when not defined changecfg: const compile = staticExec("nim cpp --cc:clang -d:changecfg -d:danger --opt:speed -d:lto --checks:off -o:a.out Main.nim") {.fatal:compile.} # ここにコードを書く
中身としてはAtCoderでの実用を見据えてコンパイル時にこちらで用意した別のコマンドを動かしてコンパイルするという仕組みになっています。
AtCoderではじめに動かすコマンドではchangecfgが定義されていないのでwhen節を通り、こちらで指定したコマンドではchangecfgが定義されているのでwhen節を通りません。
--cc:clangのところでコンパイラを指定していて、コンパイラの比較でコードを変えるのはここだけです。
あとのオプションは最適化と出力ファイルの指定です。最適化については公式のFAQを参考にしました。
計測プログラムは概ね以下のようなコードを使いました。
import osproc, strutils, strformat, algorithm var res{.noInit.}:array[20,int] for i in 0..<20: stderr.writeLine(i) stderr.flushFile() let a = execProcess("time" & ' ' & "./a.out" & " < " & &"../testcase/in_{i:02}.txt" & " > out") let a0 = a.split[2] let ms = (ord(a0[0])-48)*60*1000+(ord(a0[2])-48)*1000+(ord(a0[4])-48)*100+(ord(a0[5])-48)*10+(ord(a0[6])-48) res[i] = ms discard execProcess("rm out") echo "result: " & $res res.sort() echo &"max: {res[19]} ms" echo &"min: {res[0]} ms" echo &"med: {(res[9]+res[10]+1) shr 1} ms"
環境
- Nim 1.6.14
- gcc 14.1.1
- clang 18.1.6
実際に計測してみる
表の単位はすべて [ms] です。 用意したコードは最後に載せてあります。
アッカーマン関数
こちらの記事にてPythonの高速化手段としてNim言語が紹介されていたのが記憶に残っていたので同じ関数を計算してみました。
- 求めるもの:
ack(3,10) - 入力: なし
- 試行回数: 20回
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 38 | 33 | 35 |
clang
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 140 | 123 | 126 |
clangと比べてgccが3.6倍ほど速いという結果になりました。記事の方を見るとclangの結果はかなり遅い方になりそうです。
ABC174 F - Range Set Query (Mo解法)
この解法です。 言語によってはこの解法で通すのは困難らしいです。 実装ではNim-ACLを使いました。
- 求めるもの: 問題の答え
- 入力: random06 のみ
- 試行回数: 20回
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 1347 | 1166 | 1277 |
clang
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 1330 | 1163 | 1276 |
ほぼ同じですね。同じ入力であるのにも関わらずまあまあ値にブレがあるのが少し気になる程度です。 実行時間制限: 2 sec なのでTLEはしません。
ABC348 F - Oddly Similar (O(N2 M)解法)
この解法です。 Nim使いで通している方もいるみたいですが、私は今までこの解法では通せませんでした。
- 求めるもの: 問題の答え
- 入力: 02_maximum_00.txt から 02_maximum_27.txt の28件
- 試行回数: 28回
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 3054 | 2591 | 2852 |
clang
| 最大値 | 最小値 | 中央値 |
|---|---|---|
| 568 | 488 | 531 |
gccと比べてclangが5.3倍ほど速いという結果になりました。しかもこの問題は 実行時間制限: 2 sec なのでコンパイラの選択がACとTLEを分けます。 この結果を見るとNim言語でもコンパイラの選択を考える必要が出てきそうに思えます。
総括
C++と同じように、Nim言語でもコンパイラの選択によって速度に差が出る場合があるということが分かりました。TLEを何とか通そうと考えているときは、コンパイラも見直してみましょう。
実は……？
ということでABC348 Fはclangならこの解法でも通るということが分かったので、とりあえずAtCoderのコードテストに作成したコードを出してみましょう。
おや？
通りませんね。
エラーを詳しく見てみましょう。
/judge/Main.nim(3, 10) Error: fatal error: Hint: used config file '/home/runner/.choosenim/toolchains/nim-1.6.14/config/nim.cfg' [Conf] Hint: used config file '/home/runner/.choosenim/toolchains/nim-1.6.14/config/config.nims' [Conf] ........................................................... Hint: clang++ -c -std=gnu++14 -funsigned-char -flto -O3 -fno-ident -I/home/runner/.choosenim/toolchains/nim-1.6.14/lib -I/judge -o /home/runner/.cache/nim/Main_r/@m..@shome@srunner@s.choosenim@stoolchains@snim-1.6.14@slib@sstd@sprivate@sdigitsutils.nim.cpp.o /home/runner/.cache/nim/Main_r/@m..@shome@srunner@s.choosenim@stoolchains@snim-1.6.14@slib@sstd@sprivate@sdigitsutils.nim.cpp [Exec] sh: 1: clang++: not found Error: execution of an external program failed: 'clang++ -c -std=gnu++14 -funsigned-char -flto -O3 -fno-ident -I/home/runner/.choosenim/toolchains/nim-1.6.14/lib -I/judge -o /home/runner/.cache/nim/Main_r/@m..@shome@srunner@s.choosenim@stoolchains@snim-1.6.14@slib@sstd@sprivate@sdigitsutils.nim.cpp.o /home/runner/.cache/nim/Main_r/@m..@shome@srunner@s.choosenim@stoolchains@snim-1.6.14@slib@sstd@sprivate@sdigitsutils.nim.cpp'
はい。実は、2024年7月8日現在のAtCoderのNim言語の環境ではclangが導入されていません。 言語アプデまで待ってclangのオプションをリクエストするかAtCoder_base64あたりを使ってバイナリ提出をするかしましょう。 バイナリ提出をするためのプログラムをNim言語で自作するときはstd/base64が便利だと思います。
バイナリ提出の例: Submission #55411865 - Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）
用意したコード
アッカーマン関数
when not defined changecfg: const compile = staticExec("nim cpp --cc:gcc -d:changecfg -d:danger --opt:speed -d:lto --checks:off -o:a.out Main.nim") {.fatal:compile.} proc ack(m,n:int):int = if m==0: return n+1 if n==0: return ack(m-1,1) return ack(m-1,ack(m,n-1)) echo ack(3,10)
ABC174 F - Range Set Query (Mo解法)
when not defined changecfg: const compile = staticExec("nim cpp --cc:gcc -d:changecfg -d:danger --opt:speed -d:lto --checks:off -o:a.out Main.nim") {.fatal:compile.} import sequtils, algorithm, strutils import atcoder/header import atcoder/extra/structure/mo proc solve(N,Q:int;c:seq[int];l,r:seq[int]):void = var mo = initMo(N,l.mapIt(it-1),r) var re0 = newSeq[int](N) var re1 = 0 var res = newSeqUninitialized[int](Q) proc al(a:int):void = if re0[c[a]-1] == 0: re1.inc() re0[c[a]-1].inc() return proc dl(a:int):void = re0[c[a]-1].dec() if re0[c[a]-1] == 0: re1.dec() return proc rem(i:int):void = res[i] = re1 return run(mo,al,al,dl,dl,rem) echo res.join("\n") return proc main():void = let N, Q = nextInt() let c = newSeqWith(N,nextInt()) var l = newSeqUninitialized[int](Q) var r = newSeqUninitialized[int](Q) for i in 0..<Q: l[i] = nextInt() r[i] = nextInt() solve(N,Q,c,l,r) main()
ABC348 F - Oddly Similar (O(N2 M)解法)
when not defined changecfg: const compile = staticExec("nim cpp --cc:clang -d:changecfg -d:danger --opt:speed -d:lto --checks:off -o:a.out Main.nim") {.fatal:compile.} import atcoder/header import sequtils proc solve(N:int, M:int, A:seq[seq[int16]]):void = var re0 = newSeqWith(N,newSeq[bool](N)) for i in 0..<M: for j in 0..<N-1: for k in j+1..<N: re0[j][k] = re0[j][k] xor (A[i][j]==A[i][k]) var res:int32 = 0 for i in 0..<N-1: for j in i+1..<N: res += re0[i][j].int32 echo res return proc main():void = var N = nextInt() var M = nextInt() var A = newSeqWith(M,newSeqUninitialized[int16](N)) for i in 0..<N: for j in 0..<M: A[j][i] = nextInt().int16 solve(N, M, A) return main()
