NimでAtCoder Beginners Selectionを解いてみた！

はじめに

昔にNimの競プロ記事を書いていたのですが、今改めてNimで競プロを始めるならやっぱりAtCoder Beginners Selectionの解説があった方が便利だよなーと思ったので 、マイナー言語Nimを普及させるために解いた記事を書いておきます。 Nimをご存じない方は、この記事を読んで、書きやすそうだなと思ってもらえれば幸いです。

僕のNimの競プロライブラリはこちらにあります。

古いAtCoder用Nim0.13.0のドキュメントやビルド情報はこちらにまとめてあります。

最新のNimの場合は こういう感じで コードの内部実装が手軽に読めるという特徴があります。

また、訳あって入力のとり方はやや非自明な取り方をしていますが、これは自分に合うものを使用してください。

入力のとり方について補足

入力が

n
A1 A2 A3 ... An
B1
B2
...
Bn

とあった時に通常は以下のように書くことが多いです。

let n = stdin.readLine.parseInt()
let A = stdin.readline().split().map(parseInt) # 一行の中で空白で分割して取る
let B = newSeqWith(n,stdin.readLine().parseInt()) # 行ごとに取る

この書き方では、場合に応じて２つの書き方を使い分けないといけない欠点があります。 長いしややこしいですよね。

なので最近ではC言語のscanfを使ってこう書いています。

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan())
let B = newSeqWith(n,scan())

意味が明確かつ簡略になって、かなり見やすくなりました！ 便利！

1 Product

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
if (scan() * scan()) mod 2 == 0 : echo "Even"
else:echo "Odd"

ちなみに scan() なしだと let tmp = stdin.readLine.split().map(parseInt);let a = tmp[0];let b = tmp[1] と書かないといけなくてつらいです。

2 Placing Marbles

import sequtils
echo stdin.readLine().filterIt(it=='1').len

配列の操作には なんとかit が便利です。 Nimは fun(a,b,c) を a.fun(b,c) と書ける(UFCS)のでメソッドチェイン的なことができて便利です。

あとは getchar を使う解法もあります。

proc getchar():char {. importc:"getchar",header: "<stdio.h>",discardable .}
echo newSeqWith(3,getchar()).filterIt(it=='1').len

3 Shift only

import sequtils
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var A = newSeqWith(n,scan())
var ans = 0
while A.allIt(it mod 2 == 0):
  A = A.mapIt(it div 2)
  ans += 1
echo ans

allIt などの便利な なんとかIt を使っていきましょう。 定数への代入は let 、変数への代入には var を使います。

while A.all(proc(x:int):bool = x mod 2 == 0):
  A = A.map(proc (x:int):int = x div 2)

のように関数を作成して書いてもOKです。

また、 import future (最新のNimでは import sugar) をすると

while A.all(x => x mod 2 == 0):
  A = A.map(x => x div 2)

みたいな感じにも書けます。 なんとか It は 言語機能にあるわけではなく、配列を操作するタイプで個別に実装しているだけなので、 こういうラムダ式形式の書き方も応用性は広く覚えておいて損はないです。

4 Coins

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let a = scan()
let b = scan()
let c = scan()
let x = scan()
var ans = 0
for ia in 0..a:
  for ib in 0..b:
    for ic in 0..c:
      if 500 * ia + 100 * ib + 50 * ic == x : ans += 1
echo ans

forループは for i in 0..n で n を含み、 for i in 0..<n で n を含まない意味でループを回せます。

5 Some Sums

import sequtils,math
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let a = scan()
let b = scan()
var ans = 0
for i in 1..n:
  let isum = ($i).mapIt(it.ord - '0'.ord).sum()
  if a <= isum and isum <= b: ans += i
echo ans

数字の文字列化は $ 演算子を使います。 文字コードの数値を取得するには ord を使います。

6 Card Game for Two

import sequtils,algorithm
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let A = newSeqWith(n,scan()).sortedByIt(-it)
var alice = 0
var bob = 0
for i,a in A:
  if i mod 2 == 0 : alice += a
  else : bob += a
echo abs(alice - bob)

import algorithm の後、 破壊的にソートする場合は sort() が、新たに作成する場合は sorted が使えます。 今回の場合は、ソートのキーを指定する .sortedByIt(-it) の他に、通常のソート .sorted(cmp,Descending) と書くのもありです。 for a in A ではなく for i,a in A と書くことで、 i に配列のindex を取得することができ、便利なことが多いです。

7 Kagami Mochi

import sequtils,tables
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
echo newSeqWith(n,scan()).toCountTable().len

古いNim 0.13.0では deduplicate がO(N2) かかるので注意が必要です。 最新のではソート済み情報を渡せるので大丈夫ですが。

8 Otoshidama

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
let y = scan()
for ia in 0..n:
  for ib in 0..(n-ia):
    let ic = n - ia - ib
    if ic >= 0 and ia * 10000 + ib * 5000 + ic * 1000 == y :
      echo ia," ",ib," ",ic
      quit 0
echo "-1 -1 -1"

proc 内ではないためreturn が書けないのですが、実は quit 0 でプログラムを終了できます。

9 Daydream

import strutils
var S = stdin.readLine()
proc check():bool =
  for word in ["dreamer","eraser","erase","dream"]:
    if S.endsWith(word):
      S = S[0..^(word.len+1)]
      return true
  return false
while S.len > 0:
  if not check(): quit "NO",0
echo "YES"

Nim は文字列操作も割と得意です。

10 Traveling

proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc scan(): int = scanf("%lld\n",addr result)
let n = scan()
var (ct,cx,cy) = (0,0,0)
for _ in 0..<n:
  let (t,x,y) = (scan(),scan(),scan())
  let (dt,dx,dy) = (t-ct,x-cx,y-cy)
  if dx.abs + dy.abs > dt or abs(dx + dy) mod 2 != dt mod 2: quit "No",0
  (ct,cx,cy) = (t,x,y)
echo "Yes"

Nimはタプルの分割代入が可能なため、必要に応じて使っていきましょう。

最後に

Nimはマイナー言語ですが、AtCoderでも毎回片手では数えられない程度の人数がNimで解いて提出しています！ 書きやすくて速い最高の言語であるNimの使用者が増えてくれるといいな〜〜〜

就活をしてしまっていました...

最初のころのぼく

就活を終えたぼく

いかがでしたか？

入る会社では多分飲酒コーディングはできないと思いますが、規定を読んだ限りでは業務中に飲酒をしてはいけないとは明文化されていなかったので可能性はあるかもしれませんね！

ちなみに僕はほろ酔いで真っ赤になります！！！！！！！！！！！！！！

Nim で yukicoder の最短時間を取って遊ぶ その2

やっていきで現在425問といて58問最短になった. ☆3からはみんな最短取るやる気を出してきたので最短が難しくなってた.... getchar_unlocked()の力だけで倒せる問題は置いておくとしてその他の問題を備忘録.

No.697 池の数はいくつか

https://yukicoder.me/submissions/312381

愚直に地図中の池の数を数えるだけ. queueや再帰を使ったりして何周もするように書いてしまうと遅いので, 最低限のunionfindを使って一回で実行・計測すると最短を取れる.

No.634 硬貨の枚数1

https://yukicoder.me/submissions/312348

この問題は予めある程度結果を計算できる. Nimでは const C = (proc():seq[int] = ... )() と書けばコンパイル時定数代入として 150万回まで計算できるので最短を取るのは容易.

No.554 もconstが使えて楽.

No.523 はconstにすると150万回を超えたので渋々埋め込み. No.502 も. No.027 も.

No.537 ユーザーID

https://yukicoder.me/submissions/310597

SFFやミラーラビンで殴ると最短が取れる.

No.414 も. No.376 も. No.312 も

No.342 一番ワロタｗｗ

https://yukicoder.me/submissions/311076

unicodeの文字列処理.Nimで何も考えずに書くだけで意外にも最短を取れた.

No.304 鍵

https://yukicoder.me/submissions/304950

ランダムに鍵を試すだけのコードだが,何となく乱数のシードを 61725 にすると最短を取れた.

No.233 めぐるはめぐる (3)

https://yukicoder.me/submissions/313061

二つの順列を組み合わせて無駄な名前を作らないようにするのがまず第一条件. その上でstringを経由している暇はないため,全て char* で管理して unordered_set<size_t> に喰わせるときには hash<string>() にして喰わせると string 的な気持ちで書いたまま最短が取れる.

No.120 傾向と対策：門松列（その１）

https://yukicoder.me/submissions/312133

sort も priority_queue も必要で,Nimの標準ライブラリのそれではとてもじゃないが速度が足りない. なんと Nim のソートは マージソートなのだ！ 素直にC++で書いて最短.

No.50 おもちゃ箱

https://yukicoder.me/submissions/313570

BitDP. 最初は関数を作って再帰的に書いていたが, 実はn個の(O(n*2n)の)bitDPは for i in 0..<(1 shl n) って外側に書いて回すといい感じに回ってくれる.簡潔に書けて速くて便利.

No.009 モンスターのレベル上げ

https://yukicoder.me/submissions/313351

Nimの雑に書いた自作PriorityQueueではC++のそれには勝てなかったが, この問題の性質上,ある程度探索すると答えは早めに出るので打ち切っていいハズなので 現状の最短より10msくらい早い時間で打ち切るようにしたらACだったので発想の勝利.

Nim で yukicoder の最短時間を取って遊ぶ

はじめに

最近 Nim で yukicoder をやっています. 競技プログラミングとしてアルゴリズムを考えて楽しむのもいいのですが, 個人的にはどれだけプログラムをチューンできるかというISUCON的な遊び方をして楽しんでいます. yukicoder では最短実行時間をとるとゆるふわポイントが貯まり,ポイントランキングが可視化されるため,やりがいがあります. 現在やるだけの問題(☆2以下)を yukicoder で250問程解き,25問について最短時間を取得しました.

yukicoder.me

というわけで,この記事では,アルゴリズム的な改善は全て済んでおり,後は I/O など競技プログラミング的には問題の本質ではないところに改善の余地があるコードを想定し,これを 1ms でも速くして最短時間をとるメモを書きました.

自然数入力

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    var k = getchar_unlocked()
    if k < '0' : break
    result = 10 * result + k.ord - '0'.ord
let n = scan()

自然数の入力の取得には,Nimの場合 stdin.readline().parseInt() が, C++の場合 std::cin >> n や scanf("%d",&n) などがありますが,速ければ正義なので,スレッドセーフを気にしない getchar_unlocked を使って自分で自然数を組み立てる手があります.感覚的には,1000個以上変数があると効いてくる様子.

自然数出力

proc putchar_unlocked(c:char){.header: "<stdio.h>" .}
proc printInt(a:int32) =
  template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
  template mod10(a:int32) : int32 = a - (a.div10 * 10)
  var n = a
  var rev = a
  var cnt = 0
  while rev.mod10 == 0:
    cnt += 1
    rev = rev.div10
  rev = 0
  while n != 0:
    rev = rev * 10 + n.mod10
    n = n.div10
  while rev != 0:
    putchar_unlocked((rev.mod10 + '0'.ord).chr)
    rev = rev.div10
  while cnt != 0:
    putchar_unlocked('0')
    cnt -= 1

# 直で書いたほうが速い
  proc printInt(a0:int32) =
    template div10(a:int32) : int32 = cast[int32]((0x1999999A * cast[int64](a)) shr 32)
    template put(n:int32) = putchar_unlocked("0123456789"[n])
    proc getPrintIntNimCode(n,maxA:static[int32]):string =
      result = "if a0 < " & $maxA & ":\n"
      for i in 1..n: result &= "  let a" & $i & " = a" & $(i-1) & ".div10\n"
      result &= "  put(a" & $n & ")\n"
      for i in n.countdown(1): result &= "  put(a" & $(i-1) & "-a" & $i & "*10)\n"
      result &= "  return"
    macro eval(s:static[string]): auto = parseStmt(s)
    eval(getPrintIntNimCode(0,10))
    eval(getPrintIntNimCode(1,100))
    eval(getPrintIntNimCode(2,1000))
    eval(getPrintIntNimCode(3,10000))
    eval(getPrintIntNimCode(4,100000))
    eval(getPrintIntNimCode(5,1000000))
    eval(getPrintIntNimCode(6,10000000))
    eval(getPrintIntNimCode(7,100000000))
    eval(getPrintIntNimCode(8,1000000000))

getchar_unlocked の対として putchar_unlocked があり,これを使う手があります. 32bit整数xを (int32)(0x1999999A * (int64)(x)) で x / 10 相当のことが出来るのは知らなかったです...

配列確保

# x = newSeqWith(n,stdin.readLine().parseInt()) 相当
var x : array[100010,int32]
for _ in 0..<n : x[i] = stdin.readLine().parseInt().int32

yukicoder の実行時間の結果はテストケースで最も時間のかかったものとなります. 最も時間のかかるテストケースは,制約ぎりぎりのサイズの配列が必要になることが多いです. そのため,実行中に動的に配列を確保するよりも,始めからグローバル変数として制約の限界まで固定長の配列を確保しておく方が高速なことが多いです. 制約的に32bitで済むなら配列を int (64bit) から int32 (32bit) に変更しておくことで更に高速化できる可能性があります.

コンパイル時計算

let X = (proc() : seq[int] =
  return @[] # ... 実行時に計算される
)()
const X = (proc() : seq[int] =
  return @[] # ... コンパイル時に計算される
)()

素数表など,コンパイル時に予め計算しておくことが出来る場合があります. Nim の場合, 定数代入 let ではなく, コンパイル時定数代入 const を使って代入するだけでコンパイル時に計算してくれます.

Nim で プロファイリング結果を FlameGraph にする

この記事は KMC Advent Calendar 2018 - Adventar 7日目の記事です. ついでに、Nim Advent Calendar 2018 - Qiita の 7日目の記事でもあります. 前日のKMCアドベントカレンダーの記事は dnek_ さんの 運ゲー排除マインスイーパー💣脱Unity計画（Android編）＆SATによるソルバー改良 - dnekblog でした. がんばりますねー.

はじめに

Nimっていう最高の言語があるんですけどご存知でしょうか？ 過去のアドベントカレンダーでもその素晴らしさを語っているので, ご存知でない人はぜひ御覧ください. この記事では Nim は version 0.19.0 を使用しています.

プロファイリング

コードを書いていてパフォーマンスがあまり出ない時,どこがボトルネックとなっているかを調べることは重要です. プロファイリングをせず,ただ闇雲に時間がかかってそうと思った場所を直すという方法は往々にして思った結果が出ないものです.

幸いなことに Nim ではデフォルトでスタックトレースプロファイラーが搭載されています.

プロファイリングの手順は以下のとおりです.

  1. プロファイリングしたいNimのファイルに import nimprof を記述する.
  2. Nimのコンパイル時のコマンドに --profiler:on --stackTrace:on を加える

これで実行すると, profile_results.txt という以下のようなスタックトレース結果が生成されます.

total executions of each stack trace:
Entry: 1/510 Calls: 961/8114 = 11.84% [sum: 961; 961/8114 = 11.84%]
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssign 3422/8114 = 42.17%
  assign.nim: genericSeqAssign 3447/8114 = 42.48%
  matrix.nim: deepCopy 3415/8114 = 42.09%
  target.nim: tryUpdate 2486/8114 = 30.64%
Entry: 2/510 Calls: 948/8114 = 11.68% [sum: 1909; 1909/8114 = 23.53%]
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssignAux 3388/8114 = 41.75%
  assign.nim: genericAssign 3422/8114 = 42.17%
  assign.nim: genericSeqAssign 3447/8114 = 42.48%
  matrix.nim: deepCopy 3415/8114 = 42.09%
  target.nim: tryUpdate 2486/8114 = 30.64%
...
...

例えばこれは最近書いている解析用のプログラムの結果のものなのですが, この結果からtryUpdate関数のdeepCopy関数でのgenericSeqAssign, 要は大きな配列のコピーがネックとなっていることがわかります. これでも十分分かりやすいですが,できればもう少し視覚的に分かりやすく表示したいものです.

Flame Graph

Flame Graph の形式を用いることで, 上図のように視覚的に分かりやすく結果を見ることができます. Flame Graph の読み方などに関しては, (Go言語版の記事ですが) https://deeeet.com/writing/2016/05/29/go-flame-graph/ などが分かりやすいです.

さて, このFlame Graph の SVG を生成するPerlのコードはGithubにて公開されており, Go や Java など色々な言語 の Flame Graph を生成することができます, ただ,残念ながら調べた限りだと Nim の Flame Graph を生成するものはまだ無いようです.

Flame Graph 生成

無いなら作るしかないですね.早速作ってみましょう. 上記リポジトリに有る flamegraph.pl というファイルに,例えば以下のような入力を加えて実行すると, 図のような Flame Graph を作成することができるようです.

func1;func2 10
func3 8
func4;func5;func6 3

分かりやすいですね.

あとは profile_results.txt の結果をこの形式に変換すれば良さそうです. というわけで変換スクリプトを書いてみました.

profile_results.txt を flamegraph.pl 形式にするやつ · GitHub

いい感じに変換できてそうですね. スクリプトのご利用はご自由にどうぞ.

さいごに

以上、プロファイリングは大事でFlameGraphは見やすくて便利ということでした. ここまで読んでくださり、ありがとうございました.

Nimに興味を持たれたら、 Nim Advent Calendar 2018 - Qiita を読んだり、 Nim programming language | Nim を読んだりしてください.

明日のKMC AdventCalendar は Kana_kmc さんによる 16年間を振り返って整理する です.

追記

当初予定していたアドベントカレンダーの内容は,「太古のPythonを眺めてみる」でした. 便利なことに https://www.python.org/ftp/python/src/Python-0.9.1.tar.gz を解凍して configure して make すれば Python 0.9.1 という太古のバージョンを特に苦もなく動かすことができます. 太古のPythonでは,1タブ8スペースだったり != が <> だったり,classに__init__が無かったり文法がいろいろ違って楽しい...ということを書こうとしたのですがあまり深い内容が無かったのでやめてしまいました. 他の(virtualenvで取れないような)太古のバージョンも, https://www.python.org/ftp/python/src/ から容易に得ることができ,過去の遺産を残しているPythonはすごいなあと思いました.

isucon8本戦は低レイヤーがネックにならない良問だった

TLDR;

  • ISUCON8に参加した
  • 感想戦は41万点出た
  • ISUCON8本戦は低レイヤーがネックにならない良問だった

はじめに

ISUCON8に参加してきました. 私のチーム(百万円ドブリン)の状況は @nakario のブログに詳しく書いてあるのでそちらをご参照ください.

うちのチームでは @nakario が Goをゴリゴリゴリゴリと書きWebアプリケーション自体を高速化し, @aokabi が MySQL と Nginx を触ったり複数台構成の準備をしていました. 二人のプロがいるので僕は踊っているだけでよくて最高でした.

やったこと

予選

匿名関数を剥がしたり,高速化後のデッドロック要因の select ... for update の for update をなんとなく消す役割をしていた様子. 怪しいところを消すガチャ要員です.

本戦

Dockerを剥がしたりbcrypt をなんとかしようとしていました. pprof だけを見ると bcrypt しかCPUを食っていなかったからですね. CPUはネックではなかったので直す意味はなく,これは完全に罠だったので反省.

bcrypt について

結論としては signup の時のハッシュ化するときの cost を デフォルトの 10 から 4 (最低値)にする程度で十分です. ハッシュ化は 2^{cost} 回行われるため,この変更だけでハッシュ化は64倍早くなり,signup処理はほぼ一瞬になります.

bcryptが大変そうに見えるsigninは,実は成功するユーザー数はとても少なく, 例えば成功したユーザーのハッシュ化のコストを4にするなどの小手先の技では効果はありません. signinを完全に潰すには, DBに保存されているハッシュ値から元のパスワードを当てて全てコスト4にして保存するしか方法はありません. なお,もしもそれが出来たら bcrypt の脆弱性を見つけたのと同値ですのでISUCONより先にセキュリティ系の学会あたりに報告したほうがいいと思います.

ちなみに問題設計としては,signin はBan処理の実装だけで十分なようになっていました. ユーザーが多くなってくると, info や runTrade 関係の処理がネックを占めてくるようになり, signinのbcryptの比重は自然に減っていくため手を付ける機会は永遠に訪れないのです.

感想戦

本戦当日では5000点程度で終わってしまいましたが, それはそれとして日曜日に集まって感想戦をやっていました. これは賞金をもらえないので意味は無いように思えますが, どこまでチューニングできるものなのかを知れて大変楽しいものです.

twitter.com

最終的に41万点くらいでたので満足です.

41万点への道のり

https://github.com/aokabi/isucon8f (現在非公開repoですがそのうち公開してくれると思います)

感想戦では,aokabitが複数台構成を行い, nakario がISUCON8 本選問題の解説と講評 : ISUCON公式Blog に書かれている高速化作業を全部やってくれました.すごい.

goroutineの数でshare機能の有無を決めたり, singleflightを取り入れたり,Ban機能を実装したり,ロウソク足を改善したり,LIMIT 1 を入れたり, send_bulk をやったりを全部nakarioがやってくれました. すごすぎる. それを aokabi が4台に分散させたところで 6万点くらいまでいっていました.

更に最後に nakario が info の N+1を消したり クッキーを活用したり といった処理を入れたところで20万点くらいまで行きました. 最終的にはコネクション数がネックになっていたように見えたので info の N+1 を消したりクッキーで不要なSQL通信を減らすと得点が爆上がりしたのを見ると面白いなあという感じです.

20万点からあと上げる作業では,要はコネクションを安定させながらユーザーを増やせばいいので, アプリに db.SetMaxIdleConns(1024) を加えてコネクションプールをしたり, nginxの設定でgoのアプリとの間のkeepaliveを設定したりしてコネクションを安定させました.

(編集注: nakario,aokabi担当分に関して,僕が間違った解釈をしている可能性があるので鵜呑みにはしないでくださいね).

ISUCON8本戦は低レイヤーな部分がネックにならない良問

ISUCON本戦まで,毎週日曜日にISUCONの過去問や公開社内ISUCONを解くという集まりをやっていました. その中でISUCON8本戦がすごいなあと思ったのは低レイヤーな部分がネックにならない作りになっていたところです.

低レイヤーについて,ここでは 標準ライブラリの実装では遅いので高速化する箇所 と定義します. 標準ライブラリでは様々な入力ケースに対応する必要があるので得てしてオーバーヘッドがかかります. これを高速化する作業は著しく保守性を損なうため通常のWebアプリケーションでは絶対にいじりたくない場所ですが, なんでもありのISUCONならこれをやる必要が出てきてしまうものです.

以下,過去問でそのレイヤーを見てみます.

ISUCON7本戦の低レイヤー

https://github.com/nakario/isucon7f2 ここでの低レイヤーは BigInt と json化 です.

BigIntの高速化については ISUCON7本戦でBigintを殺したかった話 - (/^^)/⌒●~*$ a(){ a|a& };a にて考察しています. json化の高速化作業は,リフレクション的な作業がgoで行われるのが遅い原因なので, json化するGoのコードを生成する fastJson を導入すれば消すことが出来ます.

ISHOCON2 の低レイヤー

GitHub - nakario/ishocon2 ここでの低レイヤーは PostのFormの読み込み と Goのテンプレートエンジンのレンダリング です.

Go の PostForm では,Formが1つしかなくても複数あった場合を想定して, フォームが1つの場合の解析と,複数の場合の解析と二度解析してしまいます. ですので標準ライブラリを読みながら複数の方の解析をしないPostFormを作ることで2倍位早くできます.

Goの標準ライブラリには html/template があり,大体のレンダリングエンジンにおいてこれを内部で使用しています. ただ,これは構文解析やeval的な操作をしてしまうので余計なオーバーヘッドがかかってしまいます. 解決方法は fastJsonと同じで,要はGoのコードにしてしまうことです. これを解決するために,.tmpl ファイルを静的解析して .go のファイルを生成するNimのコードを書いたので,よければ使ってください.

yisucon の低レイヤー

GitHub - nakario/yisucon ここでの低レイヤーは Goのテンプレートエンジンのレンダリング です.同じなので割愛.

ISOCON1 での低レイヤー

GitHub - Muratam/ishoisho1111: 158160点 ここでの低レイヤーは Goのテンプレートエンジンのレンダリング と 時刻のパースです.

時刻のパースはどうしてもformatの解析ののちscanという二度手間を挟んでしまうので, 直書きしてしまうことで解決します.

低レイヤーについて

以上見たように htmlやjsonを生成してユーザーに返すリクエストが多い問題では, どうしてもこういった低レイヤー部分がネックの一つになってしまうという問題があります. 今回の問題を41万点までチューニングしたわけですが, 一つもこういう低レイヤーの部分が表面化せず,良問だったなあと思いました.

例えばもし今回問題設計のバランスが悪ければ bcrypt のハッシュ化がネックになり得たわけで, 頑張れば定数倍高速化出来たのかなーとかちょっと思ったりしていました.

どうも過去問では僕はこういった部分ばかり率先して担当していたようで(低レイヤーは楽しいので), 今回の問題でずっと踊るしか出来なかったのはISUCON8本戦が低レイヤーが問題にならない良問だったからかなあと思いました.

最後に,ISUCONやそれに類する問題を作成・運営してくれた方々すべてに最上級の感謝を込めて結びとします.