コード生成におけるN+1問題とbulk actionとしてのegoist。あるいはMakefileについて。

例えば以下の画像の様な依存関係でコード生成1が行われるとする。入力となるファイルが幾つかあり、例えばjinja2のテンプレートなどで出力先の表現が記述されていて、これによりちょっとしたgoのコードやopenAPI docの一部を生成するというようなタスク。

画像では、x.go,x.yamlとy.goが生成されている。enumあたりのコードをイメージしてもらうのが手軽かもしれない。

コード生成におけるN+1

Makefileなどで素直に記述すると以下の様になると思う。これはこれでそこまで汚いわけではない。

default: output/x.yaml output/x.go output/y.go

output/x.yaml: _tools/gen.py _tools/x-yaml.j2 input/x.csv
  python $^ > $@
output/x.go: _tools/gen.py _tools/x-go.j2 input/x.csv
  python $^ > $@

output/y.go: _tools/gen.py _tools/y-go.j2 input/root.yaml
  python $^ > $@

# 本来はコードを生成するコマンド
_tools/gen.py:
  echo 'import sys; print(__file__, sys.argv[1:])' > $@

問題はpythonのprocessが出力されるファイルとテンプレートのセットの数だけ立ち上がってしまう点。この例では数個なので困らないが、対象が数十個・数百個などになってくるときつくなってくる。

そして、この種のプロセスのほとんどはインタプリタの起動とモジュールのロード時間だったりする。特に面白い最適化を行うようなコード生成ではなく、煩雑な物事への対応というような文脈でのコード生成においては、個々の処理自体は単純なものでただただ量や種類が多いというような場合が多い。特にweb系での文脈ではそれが顕著。

そのためこの種のロード時間などが固定コストのように効いてきて、全体の実行時間を遅くしてしまう。これをコード生成におけるN+1問題と呼ぶことにする。N+1問題は到るところに現れる。

(ちなみに、以前書いたこの記事にも近しい話題は載っている)

煩雑なコード生成における幾つかの不都合

生成処理を一度に実行させたい

入力としての依存を1つにまとめて一度に実行してしまうツールが欲しくなる。先程の話をコード生成におけるN+1とするなら、こちらはコード生成におけるbulk actionのような存在。これをどうにかできないだろうか?

cacheを効かせたい

Makefileなどで記述することで理想的には得られる良い点もある。それはキャッシュが効くようになること。例えばmakeではターゲットとその依存のmtimeを見て、ターゲットが古い場合に限りタスクを実行してくれる。これを上手く使うと、実行されるコマンドの量を減らせる。

一方でキャッシュを効かせようとしたビルドタスクの定義は地味にめんどくさい。

依存関係を1つのファイルに閉じ込めたい

一方で、Makefileなどに記述しようとすることで生じる嫌な点もある。それは生成ツール自体に直接依存関係を埋め込めないこと。全てを引数として受け取る形式は時折面倒に感じることがある。

例えば、先程のgen.pyにサブコマンドなどを用意してあげて、jinja2テンプレートなどのパスはスクリプトの中に埋め込んで置いてしまいたい。その場合はMakefileなどに引数を固定して置いておくことも不要になる。その場で直接コンソールから呼び出すということも手軽になる。

しかし、今度は依存関係がスクリプトの内部に隠れてしまう。隠れてしまってはキャッシュを効かせたりなどの処理を挟むことができなくなってしまう。

egoistの対応

github.com

これをegoistを使って解決したい。今回に限ってはgo用のフレームワークフレームワークとしての側面よりは、汎用的なコード生成用のタスクランナーとしての側面のほうが大きいかもしれない。

bulk action

egoistで作られるdefinitions.pyはデフォルトでbulk actionとしての機能を持っている。具体的には-を区切り文字として複数の操作を一度に渡すことができる。したがって以下と

$ egoist generate x
$ egoist egnerate y_go

以下は立ち上がるprocessの数を除けば同じ。

$ egoist generate x - generate y_go

どうにかして必要な操作を列挙する事ができれば - をつなげて一度に実行できる。

まぁこれでも同じ。

$ egoist generate x y_go

egoist scan

egoistのscanコマンドは依存関係を出力することができる。例えば、冒頭のMakefileに定義した依存関係をegoist上に持ってきた場合に以下の様な出力を得ることができる(definitions.pyのコードは後に貼る)。

$ python definitions.py scan
{
  "output/x.yaml": {
    "task": "x",
    "depends": [
      "_tools/gen.py",
      "input/x.csv",
      "_tools/x-yaml.j2"
    ]
  },
  "output/x.go": {
    "task": "x",
    "depends": [
      "_tools/gen.py",
      "_tools/x-go.j2",
      "input/x.csv"
    ]
  },
  "output/y.go": {
    "task": "y_go",
    "depends": [
      "_tools/gen.py",
      "_tools/y-go.j2",
      "input/root.yaml"
    ]
  }
}

依存関係を手にする事ができるならMakefileも手にすることができる。scanの内部で使われている処理を拝借していい感じの表現に変換してあげれば良い。

scanの一部を利用したmakegneコマンドの作成

ここで昨日の日記の内容が役に立つ。

各自が自由にサブコマンドを定義できるので、Makefileを生成するようなサブコマンドを用意してみる。キャッシュも効くようにする。

ちなみに昨日の日記のここの部分に対応する。

どうしてこのようにサブコマンドを自由に追加できるような機能が欲しくなったかというと、オプショナルなコマンドを追加したくなったため。具体的には依存関係をMakefileに落とし込むようなコマンドが欲しくなったが、それはさすがに全ての人に公開する必須のコマンドというほどでもなく、利用したい状況は絞られるかなーと思ったので。

makegenコマンドを作ることにした。defaultタスクが全体を実行するタスクになる(_gen.mkのコード自体は後に貼る)。

$ python definitions.py makegen > _gen.mk

これを利用するMakefileを書いてあげる。makegenで_gen.mkを更新しdefaultでコード生成を行う。

Makefile

makegen:
  rm -f _gen.mk && touch _gen.mk
  python definitions.py makegen | tee _gen.mk

include _gen.mk

.DEFAULT_GOAL = default

内部で行われている事自体は結構泥臭い感じかもしれない。

# 初回
$ make (一度に実行できる)
** .pre/output__x.yaml .pre/output__x.go .pre/output__y.go **
[F] update  ./output/x.yaml
[F] update  ./output/x.go
[F] update  ./output/y.go

# 2回目はキャッシュが効く (全部新しいので何も実行されない)
$ make
** .pre/output__x.yaml .pre/output__x.go .pre/output__y.go **

この生成されたMakefileを使うと以下の要件を満たした振る舞いをしてくれる。

  • make で全体を一度に1つのpythonプロセスでコード生成を行う
  • (make はキャッシュが効く)
  • make output/x.go で個別のファイルに対するコード生成を行う
  • (make output/x.go はキャッシュが効く)

後者の個別のファイルに対するコード生成は以下の様な形で行う

# 強制的にXのタスクだけを実行してコード生成を行う
$ make -B output/x.go
** .pre/output__x.go **
[F] update  ./output/x.yaml
[F] update  ./output/x.go

# 2度目はキャッシュが効く
$ make output/x.go
make: `output/x.go' is up to date.

やりましたね。🎉

やっている事自体は昔書いたこの記事の実装に近い。

出力するファイルは、気分によってはninja-build用のものなどに移行するかもしれない。

番外

依存関係が手に入るということは、ちょっと手を加えて上げれば依存関係のグラフを作る事もできる。実際冒頭の画像はそのようにして作られた。graphgenというコマンドも用意してみた。.dotファイルを吐き出すのでgraphvizに渡してあげれば冒頭の画像が得られた。

$ dot -Tpng <(python definitions.py graphgen) > /tmp/a.png

コード例

書いてみたコードはここに貼る。実行を試すためのコードなので内部の処理自体はdummy。

(ちなみに完全に動作する例は https://github.com/podhmo/egoist/tree/master/examples/e2e/customize/02makegen-command にある)

structure

$ tree
.
├── Makefile
├── _gen.mk
├── _setup.mk
├── _tools
│   ├── gen.py
│   ├── x-go.j2
│   ├── x-yaml.j2
│   └── y-go.j2
├── commands
│   ├── __init__.py
│   ├── graphgen.py
│   └── makegen.py
├── definitions.py
├── graph.dot
├── input
│   ├── root.yaml
│   └── x.csv
└── output
    ├── x.go
    ├── x.yaml
    └── y.go

4 directories, 17 files

definitions.py

import typing as t
from egoist.app import create_app, SettingsDict, parse_args

settings: SettingsDict = {"rootdir": "", "here": __file__}
app = create_app(settings)


app.include("commands.makegen")
app.include("commands.graphgen")
app.include("egoist.directives:define_dir")
app.include("egoist.directives:define_file")


@app.define_dir("egoist.generators.dirkit:walk", rename="output")
def x(
    *,
    gen_py: str = "_tools/gen.py",
    x_yaml_ja2: str = "_tools/x-yaml.j2",
    x_go_ja2: str = "_tools/x-go.j2",
    x_csv: str = "input/x.csv",
):
    from egoist.generators.dirkit import runtime

    inputs = [gen_py, x_yaml_ja2, x_csv]
    with runtime.create_file("x.yaml", depends_on=inputs) as wf:
        print(_gen(inputs), file=wf)

    inputs = [gen_py, x_go_ja2, x_csv]
    with runtime.create_file("x.go", depends_on=inputs) as wf:
        print(_gen(inputs), file=wf)


@app.define_file("egoist.generators.filekit:walk", rename="output/y.go")
def y_go(
    *,
    gen_py: str = "_tools/gen.py",
    y_go_ja2: str = "_tools/y-go.j2",
    root_yaml: str = "input/root.yaml",
):
    from egoist.generators.filekit import runtime

    with runtime.create_file() as wf:
        print(_gen([gen_py, y_go_ja2, root_yaml]), file=wf)


def _gen(files: t.List[str]) -> str:
    import pathlib

    return f"_tools/gen.py {[pathlib.Path(x).name for x in files]}"


if __name__ == "__main__":
    for argv in parse_args(sep="-"):
        app.run(argv)

commands/makegen.py

from __future__ import annotations
import typing as t
import logging
from functools import partial
from egoist.app import App, get_root_path
from egoist.types import AnyFunction

if t.TYPE_CHECKING:
    from argparse import ArgumentParser


def makegen(
    app: App,
    *,
    tasks: t.Optional[t.List[str]] = None,
    rootdir: t.Optional[str] = None,
    out: t.Optional[str] = None,
    relative: bool = True,
) -> None:
    import contextlib
    import os
    from egoist.components.tracker import get_tracker
    from egoist.commands.generate import generate

    app.commit(dry_run=True)

    if not bool(os.environ.get("VERBOSE", "")):
        logging.getLogger("prestring.output").setLevel(logging.WARNING)
    generate(app, tasks=tasks, rootdir=rootdir)

    root_path = get_root_path(app.settings, root=rootdir)
    deps = get_tracker().get_dependencies(root=root_path, relative=relative)

    with contextlib.ExitStack() as s:
        out_port: t.Optional[t.IO[str]] = None
        if out is not None:
            out_port = s.enter_context(open(out, "w"))
        print(emit(deps), file=out_port)


def emit(deps: t.Dict[str, t.List[str]]) -> str:
    from prestring.text import Module

    deps = {
        name: {"task": x["task"], "depends": sorted(x["depends"])}
        for name, x in deps.items()
    }

    m = Module(indent="\t")
    m.stmt(f"DEP ?= {' '.join(deps.keys())}")
    m.stmt(f"PRE ?= {' '.join(['.pre/' + k.replace('/', '__') for k in deps.keys()])}")
    m.sep()
    m.stmt('CONT ?= PRE=$< DEP="" $(MAKE) _gen')
    m.stmt("BULK_ACTION = .pre/bulk.action")
    m.sep()

    m.stmt("# goal task")
    m.stmt("default:")
    with m.scope():
        m.stmt('@CONT="exit 0" $(MAKE) _gen')
    m.sep()

    m.stmt("_gen: .pre $(DEP)")
    with m.scope():
        m.stmt("@echo '**' $(PRE) '**' > /dev/stderr")
        m.stmt(
            "( $(foreach p,$(PRE),{ test $(p) -nt $(subst __,/,$(patsubst .pre/%,%,$(p))) && cat $(p); }; ) ) | sort | uniq > $(BULK_ACTION) || exit 0"
        )
        m.stmt(
            """test -n "$$(cat $(BULK_ACTION))" && NOCHECK=1 python definitions.py $$(cat $(BULK_ACTION) | tr '\\n' ' ') || exit 0"""
        )
    m.sep()

    m.stmt("# .pre files (sentinel)")
    for name, metadata in deps.items():
        task = metadata["task"]
        args = metadata["depends"]
        pre_file = f".pre/{name.replace('/', '__')}"
        m.stmt(f"{pre_file}: {' '.join(args)}")
        with m.scope():
            m.stmt(f'echo "generate {task} -" > $@')
    m.sep()

    m.stmt("# actual dependencies")
    for name, metadata in deps.items():
        task = metadata["task"]
        args = metadata["depends"]
        pre_file = f".pre/{name.replace('/', '__')}"
        m.stmt(f"{name}: {pre_file}")
        with m.scope():
            m.stmt(f"@$(CONT)")

    m.sep()
    m.stmt(".pre:")
    with m.scope():
        m.stmt("mkdir -p $@")
    return str(m)


def setup(app: App, sub_parser: ArgumentParser, fn: AnyFunction) -> None:
    sub_parser.add_argument("--rootdir", required=False, help="-")
    sub_parser.add_argument("tasks", nargs="*", choices=app.registry._task_list)
    sub_parser.add_argument("--out")
    sub_parser.set_defaults(subcommand=partial(fn, app))


def includeme(app: App) -> None:
    app.include("egoist.components.tracker")
    app.include("egoist.directives.add_subcommand")
    app.include("egoist.commands.generate")
    app.add_subcommand(setup, fn=makegen)

_gen.mk

DEP ?= output/x.yaml output/x.go output/y.go
PRE ?= .pre/output__x.yaml .pre/output__x.go .pre/output__y.go

CONT ?= PRE=$< DEP="" $(MAKE) _gen
BULK_ACTION = .pre/bulk.action

# goal task
default:
   @CONT="exit 0" $(MAKE) _gen

_gen: .pre $(DEP)
   @echo '**' $(PRE) '**' > /dev/stderr
  ( $(foreach p,$(PRE),{ test $(p) -nt $(subst __,/,$(patsubst .pre/%,%,$(p))) && cat $(p); }; ) ) | sort | uniq > $(BULK_ACTION) || exit 0
  test -n "$$(cat $(BULK_ACTION))" && NOCHECK=1 python definitions.py $$(cat $(BULK_ACTION) | tr '\n' ' ') || exit 0

# .pre files (sentinel)
.pre/output__x.yaml: _tools/gen.py _tools/x-yaml.j2 input/x.csv
  echo "generate x -" > $@
.pre/output__x.go: _tools/gen.py _tools/x-go.j2 input/x.csv
  echo "generate x -" > $@
.pre/output__y.go: _tools/gen.py _tools/y-go.j2 input/root.yaml
  echo "generate y_go -" > $@

# actual dependencies
output/x.yaml: .pre/output__x.yaml
   @$(CONT)
output/x.go: .pre/output__x.go
   @$(CONT)
output/y.go: .pre/output__y.go
   @$(CONT)

.pre:
  mkdir -p $@

  1. 煩雑さを解消するためのちょっとした文字列操作のようなものに関しては、個人的にはコード出力と呼びたいが、code generationやコード生成という呼称が一般的な表現になっている気がする。