「正規表現の積」に関する考察

元問題はこちらです。

i-i.hatenablog.jp

準備

用語の定義

一般的な形式言語の用語

  • アルファベットΣ は、文字列に含まれてよい文字の集合のことです。元問題では小文字ラテンアルファベット26文字ですが、一般化しておきます。
  • 言語とは、文字列の集合のことです。以下の話では、言語はすべて無限集合です(これは扱う問題の性質によるものです)。議論の展開によっては普通に「文字列の集合」と書いてある部分もありますが、意味は同じです。

マッチする という言葉の意味について、念のため

  • 正規表現 文字列全体にマッチ は、C++std::regex_match動作のことを言うことにします。正規表現の前に^、後ろに$がついている状況を考えるとわかりやすいです。
  • 正規表現 文字列の一部にマッチ は、C++std::regex_search動作のことを言うことにします。形式的には、正規表現の前後に.*を付け加えてできる正規表現がその文字列 全体にマッチ することと等価です。

この問題に特殊化された用語(方言)

  • 正規表現 は、アルファベット・.*|から構成される文字列とします。.は任意のアルファベット一文字にマッチ、*はクリーネ閉包、|は選言と解釈され、エスケープは必要ありません(基本正規表現の動作と同じです)。クリーネ閉包は、アルファベットまたは.にのみ適用できます(かっこがないため文字列への適用ができません)。

    • この定義は、通常の意味での正規表現からかけ離れたものになっています。通常の意味での正規表現との違いについて論じるときには、「真の正規表現」という言葉を使うことで区別します。
  • 正規表現rが文字列の集合Sを 認識する とは、Sに含まれるすべての文字列sについて、正規表現rは文字列sの 一部にマッチ し、Sに含まれないすべての文字列sについて、正規表現rは文字列sの 一部にマッチ しないことを言います。

定義に使うのは 全体にマッチ ではありません。この定義のもと、 正規表現 は、真の正規表現より記述力が低いです。例えば、「aを含まない文字列」という言語を記述できません。

問題の形式的定義

正規表現Aと正規表現Bが与えられる。ただし、正規表現Aと正規表現Bには*|は含まれない(.は含まれうる)。次の条件を満たす文字列sの集合をSとする。

正規表現Aは文字列sの 一部にマッチ する。かつ、正規表現Bは文字列sの 一部にマッチ する。」

このようなSを認識する正規表現rに含まれる選言演算子|)の最小個数を求めよ。

AにもBにも含まれないアルファベットの要素があることを仮定してもよい。

元問題との対応

  • アルファベットはΣ = { 'a', 'b', 'c', ..., 'z' }の26文字からなる集合である。
  • 問題は以下の形式で入力される。ここで、AとBの末尾には改行文字がつく(Bの後に改行がつくかは明示されていないが)。
A
B
  • 出力は十進数で(明示されていないが)。
  • Aの長さ|A|とBの長さ|B|はそれぞれ1以上10以内であるとき、これを2秒以内に解けるアルゴリズムを構成せよ。ただし、メモリ制約は512MBとする。

考察

Sを認識する正規表現は必ず存在する

あまり形式的ではありませんが、そのような正規表現を構成することは可能です。例として、A=b.a.、B=.a.bの場合(サンプルケース4)を考えます。

b . a .
. a . b b.a..*.a.b
. a . b b.a.a.b
. a . b b.aa.b
. a . b b.a.b
. a . b baab
. a . b NG
. a . b .abba.
. a . b .a.b.a.
. a . b .a.b.*b.a.

こうして出てくる単正規表現をすべてつなげたb.a..*.a.b|b.a.a.b|b.aa.b|b.a.b|baab|.abba.|.a.b.a.|.a.b.*b.a.はSを認識する正規表現になります。

このような方法で、|A|+|B|+1個の単正規表現の選言である、高々|A|+|B|個しか選言演算子を含まない、Sを認識する正規表現を構成することは常に可能です。

もちろん、サンプルケース4の解説を見ればわかるように、この方法で構成した正規表現は選言演算子最小性を満たすとは限りません。

この方法で出てくる単正規表現を、 基本解 と呼ぶことにします。

a*のようなアルファベットの要素に対するクリーネ閉包も活用されるはず

サンプルケースにはそのような例はありませんが、A=baa、B=aabの時、Sを認識する正規表現としてbaa.*aab|baaa*b|aabaa|aab.*baaを選べば必要な選言演算子は最小の3つになるはずです。この時、a*を含まない正規表現では必要な選言演算子の数が多くなるはずです。

このような場合、複数の単正規表現がマッチする部分を持つような文字列(例えばbaaaabにはbaa.*aabにマッチする部分もあるし、baaa*bにマッチする部分もある)があることが事態を複雑化させている原因でしょう。

選言演算子の最小化をするのは困難な問題のように思えます。排他的選言ではなく普通の選言になっていることが原因でしょう。

この手の、xorなら簡単だがorだと困難という問題はいくつかあります。

  • xor-SATはPですが、SATはNP完全です。
  • DFAやNXAの状態数最小化はPですが、NFAの状態数最小化はPSPACE完全です。ここで、DFAは決定性有限状態オートマトン(Deterministic Finite Automaton)、NFAは非決定性有限状態オートマトン(Nondeterministic Finite Automaton)であり、NXA (Nondeterministic Xor Automaton)は、NFAで暗黙に使われているor演算をxorに置き換えたものです。

二番目の話は、d.y.d.の2010/12/13の記事で知りました。

選言演算子最小化は、論理式最小化に似た雰囲気がありますし、NFAの状態数最小化に似た雰囲気もあります。そのため、入力文字列長の多項式時間で解くのは困難かもしれません(論理式最小化は判定版がNP完全になる問題だったはずです)。

Open problem

基本解以外を使って選言演算子の数を減らせる場合

先ほど示したA=baa、B=aabの例は、基本解としては出てこない単正規表現baaa*bを使うことで選言演算子を減らすことができる場合です。

実験してみると、基本解に適当に以下の操作を施してできる単正規表現は有効利用できる場合があることがわかります。

  • aaa*に変換する(実際に選言演算子を減らす役に立つのはaa*に変換する手続きだけ?)

そのようにして作ることができる単正規表現を、 派生解 と呼ぶことにします(基本解も派生解に含まれます。また、派生解の中にはSに含まれない文字列の一部分にマッチしてしまう単正規表現も含まれます)。

【予想】単正規表現として派生解以外は有用ではない

形式的に書くと以下のような意味です。

正規表現rが 有用でない とは、以下の条件のいずれかを満たすことを言います。

  • 正規表現rは、Sに含まれない文字列の一部分にマッチする。
  • 以下の条件を満たす派生解r'が存在する。

第一の条件に当てはまる場合明らかにSを認識する正規表現に含まれませんし、第二の条件に当てはまる場合はrの代わりにr'を使ってもSを認識する正規表現となります。

これは、派生解以外の単正規表現を用いても、派生解のみ用いた場合に比べ選言演算子を減らすことはできない、という主張より強い主張です。

クリーネスタ演算子の出現回数

基本解においてクリーネスターは中央にしか出てきません。これ以外のところにクリーネスターを使うことは意味がないように思われます。

【予想】クリーネスタ演算子を二回以上使った単正規表現は有用ではない

先ほど示した例において、派生解であるbaaa*bの代わりにba*b*aabという派生解でない単正規表現を使っても選言演算子を減らすことができますが、これが認識する言語はbaaa*bが認識する言語の真部分集合であり、有用ではありません。

余談

正規表現 は多くの言語演算上で閉じている

真の正規表現よりも表現力が低いことは説明しました。まず、言語演算が閉じているかを確認してみます。

  • 選言
    • 間に|を挟んで連結した正規表現で認識できる。
  • 連言
    • 認識する正規表現は、基本解の構築と類似の手順で構成できる。
  • クリーネスタ
    • 正規表現で認識できる。正規表現の0回の繰り返しは空正規表現であり、それは任意の文字列の一部分にマッチする、つまり、その言語はΣ*(すべての文字列からなる集合)である点に注意したい。
  • 連接
    • 正規表現同士なら、間に.*を挟んで連結した単正規表現で認識できる。単正規表現でない場合でも、各構成単正規表現の順序対全てについて同様にしたものの選言として構成できる。
  • 鏡像
    • .*a*を仮想的に"一文字"とみなして、"一文字"ずつ逆順にした正規表現で認識できる。
  • 否定
    • 閉じていないどころか一切書けない。

クリーネスターは退化しているので実質使えないことになります。表現力は、真の正規言語より真に弱いstar-free言語よりさらに真に弱いものになります。 クリーネスタ演算子はstar-free正規表現では使えませんが、一文字へのクリーネスタ演算子は補集合演算で作り出すことができます。実際、.* \emptyset^ c空集合の補集合)として書けます。また、a* (\emptyset^ c \lbrack\hat{}a\rbrack \emptyset^ c)^ c(a以外の文字を何か一文字は含む文字列全体以外からなる集合)として表せます。 star-free正規表現だと書けるが正規表現で書けない言語には、「aを含まない文字列すべての集合」などがあります( (\emptyset^ c a \emptyset^ c)^ cのようにstar-free正規表現で書けます)。ちなみに真の正規表現だと書けるがstar-free正規表現で書けない言語には、「aを偶数回繰り返した文字列すべての集合」などがあります。

『VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る 』を解決した

タイトルの通りです。

症状は先々週の記事を参照してください。

lpha-z.hatenablog.com

「c1xx C1083」でググったところ、以下のウェブサイトを見つけ、そこに書かれていることをやったところ解決できました。

developercommunity.visualstudio.com

解決法は、問題の発生しているフォルダをzipで圧縮し、それを解凍して元の位置に戻す、たったそれだけです。

もう少し具体的には、

  1. まず問題の発生しているフォルダをzipで圧縮する。
  2. 問題の発生しているフォルダを削除する。
  3. Windowsエクスプローラーから 圧縮したzipファイルを解凍し、元の位置に作成する

どうやら、WSL上で作ったファイルは、そのファイルシステムが大文字小文字を区別するような設定になってしまい、それが悪さをするようです。 zipで圧縮した後解凍した場合、Windowsがファイルを生成するため、ファイルシステムWindowsデフォルトの大文字小文字を区別しない設定になります。 これによりVisualStudioが望んでいる形式のファイルシステムとなり、エラーが消えることになります。

使っているgitリポジトリによっては、あまりにも大量のファイルを操作することになるため、非常に時間がかかります。 また、一部のファイルが欠けてしまうことも発生しましたが、やり直したところうまくいった、というよくわからないことも発生しました。

また、先ほどのウェブサイトには、そんな大層なことをしなくても、単にファイルシステムに大文字小文字区別をしない設定を付ける方法として、

fsutil.exe file setCaseSensitiveInfo <path> disable

を実行すればよい、とも書かれていましたが、まだ試していません。

この方法は、先々週の記事で「表示されるパスが全て大文字になる」という症状を発生させたときの対処法としてあげられていました。 先々週の段階ではその症状は発生していなかったため、この対処法を試すことはありませんでした。 しかし、他のgitリポジトリで試してみたところこの症状が発生したこと、解決策が同じだったことから、実は症状は同じであったようです。

文脈自由言語の階層について

去年もこんな話を書いた気がします。

文脈自由言語の階層についての情報ってネット上ではまとまった形ではあまり手に入らないような気がします。調べたことをまとめておきます。

文脈自由文法と文脈自由言語の違い

文脈自由文法と文脈自由言語という、二つの混同しやすい用語があります。

まず、「言語」とは(有限)文字列の(無限かもしれない)集合のことです。○○言語というのは、特定の特徴を持つ言語の集合(言語クラス)のことです。 文脈自由言語とは、与えられた文字列がその集合に属しているかの判定(メンバーシップ問題)がプッシュダウンオートマトンを用いると解けるような言語です。その集合は普通は無限集合ですが、有限集合であっても問題ありません。ただし、有限集合であれば自明に正規文法で記述できる正規言語になるため、わざわざ文脈自由言語という必要がありません(有限集合なので/foo|bar|baz/のようにすべての要素を枚挙することが可能です)。 正規言語のメンバーシップ問題は有限状態オートマトンで解かれますが、非決定性があってもなくてもどちらでも同じになります。一方、文脈自由言語のメンバーシップ問題を解くためのプッシュダウンオートマトンには、これとは違い非決定性が必要です。なお、非決定性が必要とはいっても、文脈自由言語のメンバーシップ問題は全探索的考え方で多項式時間で解くことができます。

一方、「文法」とはそのような集合を記述する方法のことです。一般にある集合を記述する方法は複数ありえるので、「言語」と「文法」の違いは重要になります。 集合の元が無限にある場合、その集合を記述するには一工夫必要です。実際の記述には、BNF記法や正規表現など、読みやすい形がいくつか提案されています。なお、いわゆる正規表現は、正規言語を超えた記述能力を持つような拡張が加えられていることがあるので注意が必要です(たとえば後方参照は、文脈自由言語すら超えた表現力を持ちます)。

LL(0)

前から読んでいき、先読みをせずに次の構造が何であるかを予言する必要があるため、LL(0)文法で記述できる集合は、単元集合のみです。

また、LL(0)言語も同様に単元集合だけであり、正規言語に真に包含されます。

LL(1)

前から読んでいき、一トークンの先読みだけにより、どの生成規則を適用するかを決めることができるような文法をLL(1)文法と言います。

また、そのような文法で記述することができる言語をLL(1)言語と言います。つまり、「頑張ればLL(1)文法であるような文法が作れる」ような言語です。LL(1)言語だからと言って、文法を適当に作った場合にはLL(1)文法である保証はないということです。また、現実的な問題として、その文法の生成する構文木が作りたい構文木と一致している保証はありません。実際、a+b*cのような「数式」はうまく作ったLL(1)文法で解析できるにはできるのですが、変な構文木になってしまいます。

正規言語はLL(1)言語の真部分集合になります。

正規言語ではなく、文脈自由言語であるような集合として有名な  \lbrace a^ n b^ n | n > 0\rbrace はLL(1)言語です。その他、「対応の取れた括弧」などもLL(1)言語です。

LR(0)

前から読んでいき、先読みなしにこのトークンがどの生成規則から生成されたものかを決めることができるような文法をLR(0)文法と言います。 先読みがないとはいえ、生成規則が生成するトークンすべてがあっていることを確かめてから構文木を作成するため、ある程度強力です。 しかし、正規言語の一部は受理できないなど、偏った性能を持ちます。

具体的には、xを一文字以上の文字列、w,yを空でもよい文字列としたとき、wとwxとyが言語に含まれているならば、yxも言語に含まれている、という性質を持った言語のみ受理可能です(参考文献[1]"On LR(k) Grammars and Languages"の定理3.1)。

LL(1)だがLR(0)ではない言語

LL(1)言語であってもLR(0)言語ではない言語は、先読みが本質的に重要な言語です。  \lbrace ab^ n | n > 0\rbrace \cup \lbrace cd^ n | n > 0\rbrace がそれに当たります。ここで、b(d)の後にb(d)が続くのかが先読みの必要な情報であり、a(c)を読んだ、という情報を手放さずに先読みを行えるかという点が重要になります。一方、  \lbrace ab^ n | n > 0\rbrace を解析するためにはaを読んだという情報は不要なため、LR(0)でも解析できます。参考文献[1]によれば、aもabもcもこの言語に入っているのにcbはこの言語に入っていないのでLR(0)では解析できないと書かれていました。

LR(0)だがLL(k)ではない言語

LL(k)言語ではない、というのはどんなに大きな有限のkを持ってきてもLL(k)文法では記述できない、という言語です。  \lbrace a^ nb^ n | n > 0 \rbrace \cup \lbrace a^ nc^ n | n > 0 \rbrace がそれに当たります。aを見た時点では、それがbに対応するものかcに対応するものかわからないため、二つあるであろう生成規則のどちらを選ぶべきかわかりません。また、aが続く数は無制限であるため、kトークン先読みではこの問題を解決することができません。

LL(2)

LL(1)との違いは先読みトークン数の増加だけですが、LL(1)を厳密に包含するクラスであり、LL(1)よりも高い記述力を持った言語クラスです。

一般に、LL(k+1)言語はLL(k)言語を厳密に包含するクラスです(参考文献[2]"Properties of Deterministic Top Down Grammars")。

LL(2)でないと記述できない言語の例はなかなか見ませんが、この論文には具体例が上がっています。具体的には、  \lbrace a^ n (b^ kd | b | cc)^ n | n > 0\rbrace という言語はLL(k+1)では記述できるものの、LL(k)では記述できない、というものだそうです。まず、  (b^ kd | b | cc) の先頭にはdが現れることがありません。そこで、k+1トークン先読みしてdが出現するかを確認することにより、 bk dを生成する規則を選ぶべきなのかbを生成する規則を選ぶべきなのかの判別が可能です。逆に直観的にわかるように、kトークンの先読みなしではそのどちらの規則を選ぶべきか判断がつきません(論文には形式的な証明が書いてありました)。ccが存在するのは、  b^ {k-1}d を自由な位置に挿入することができるような文法として書けてしまうことを防止するためだと思われます。

SLR法

Simple LR(1)法というアルゴリズムのことであり、SLR法と言ったらこれのことを指します。また、このアルゴリズムで解析可能な文法をSLR文法と呼びます。

LR(0)法により解析を行おうとして問題が発生するのは以下のパターンです。

  • 複数の異なる生成規則の右辺が完成した状況(reduce-reduce conflict)。どの生成規則だったと言うべきかわからない。
  • 生成規則の右辺が完成した状況だが、もっと長い生成規則の途中という可能性もある状況(shift-reduce conflict)。前者であればその生成規則だと言うべきタイミングは今しかないが、スルーすべきなのかもしれない。

こういう場合、次のトークンを先読みすることにより問題を解決できる可能性があります。各非終端記号の後に来うるトークンの集合(Follow-set)を事前に計算しておきます。先読みトークンの情報をこれに照らし合わせて判断するのがSLR法です。

SLR法は、LR(0)文法を全て解析することができます(真に包含します)。

LALR(1)法

LookAhead LR(1)法というアルゴリズムの名前であり、これを用いて解析可能な文法をLALR(1)文法と呼びます。

SLRでは単にその非終端記号の後に来うるトークンの集合を用いただけでした。ここにいたるまでの情報を利用し、直後に来うるトークンの集合をさらに選別したもの(Lookahead-set)を使うのがLALR(1)法です。

SLR法で解析できないがLALR(1)法で解析できる文法は、以下のような感じです。

(1) S→V=E
(2) S→E
(3) E→V
(4) V→p
(5) V→q
(6) V→*E

これが生成する言語に含まれる文字列は、**p = ***qのようなポインタ同士の代入文です。

この文法では、Vの後には=が来る可能性があります。しかしその情報を使っても、=を先読みした時に(3)の生成規則を使ってVをEに還元するべきか、それとも(1)の生成規則の途中なのでスルーすべきなのか、判断がつきません。これがSLR法で解析できない理由です。

一方、LALR(1)法では解析可能です。なぜなら、Eから生まれたVであれば後ろには文字列終端が来るはずなのでそれを先読みしたらEに還元すべきであり、Sから生まれたVであれば後ろには=が来るはずなのでそれを先読みしたらスルーすべき、とそこに至るまでの情報を活用して解析が可能だからです。

LALR(1)法は、SLR文法を全て解析できます(真に包含します)。

LR(1)法

これもアルゴリズムの名前であり、これを用いて解析可能な文法をLR(1)文法と呼びます。

LALR(1)法では、先読みトークンだけが異なる状態を同一視することで状態数を減らすということを行っています。 これを行わないのがLR(1)法です。

この違いによりLR(1)法では解析できるのにLALR(1)法では解析できない文法は、以下のようなものです。

S→[A]
S→[B)
S→(B]
S→(A)
A→a
B→a

LR(1)法は、LALR(1)文法を全て解析できます(真に包含します)。

LR(2)法、LR(k)法

先読みトークン数を増やしたLR法です。まずつかわれることがないので割愛します。LR(2)法はLR(1)文法を全て解析できるうえ、LR(1)法では解析できずLR(2)法を用いないと解析できないという文法も存在します(真に包含します)。 また、LL(k)文法はLR(k)法で解析することができます(真に包含します)。

決定性文脈自由言語

実は、SLR法、LALR(1)法、LR(1)法、LR(2)法、……LR(k)法で解析できる言語は、決定性文脈自由言語という言語クラスと一致することが知られています。

これは、SLR法<LALR(1)法<LR(1)法<LR(2)法<……という文脈自由文法の解析法の階層は、文脈自由言語には存在しないということです。つまり、うまく文法を記述しさえすれば、どんな決定性文脈自由文法でもSLR文法で書けるということです。

また、LL(k)言語やLR(0)言語は決定性文脈自由言語の真部分集合です。

あいまいでない文脈自由言語

「回文」や  \lbrace a^ nb^ n | n > 0\rbrace \cup \lbrace a^ nb^ {2n} | n > 0\rbrace などは、解析に非決定性が必要な言語です。これらはLL法やLR法では解析できず、全探索的考え方で動作するGLR法などで解析されます。

本質的にあいまいな文脈自由言語

言語に含まれる文字列について、複数の導出が可能になってしまうような文法をあいまいな文法と呼びます。たとえば、以下のような文法はあいまいな文法です。

S→S+S
S→x

たとえば、x+x+xの導出は二通りあります。右結合か左結合かを明示した文法とすればあいまいでない文法として記述できます。

しかし、どのように文法を記述しても文法があいまいな文法になってしまう言語もあります。それは本質的にあいまいな言語と呼ばれます。

 \lbrace a^ nb^ nc^ md^ m | n, m > 0\rbrace \cup \lbrace a^ nb^ mc^ md^ n | n, m > 0\rbrace

たとえば上に上げた言語は本質的にあいまいな言語です。 二つの集合の共通部分である  \lbrace a^ nb^ nc^ nd^ n | n > 0\rbrace は文脈自由言語ではないものの典型例になっています。 つまり、その部分に特殊化された文法を書けないため、二つの集合に対応した構文木のどちらとしても解析される(=あいまい)、という直観的な解釈が可能です。 Wikipediaには、とある本に証明が載っていると書いてありますがその証明は形式的なものではありませんでした。

文脈自由文法にまつわる決定不可能な問題

  • ある文脈自由文法が「全文字列」という言語を記述しているか否か(チューリングマシンの停止性問題を帰着できる)。
  • ある文脈自由文法が別のある文脈自由文法と同じ言語を記述しているか否か(先の問題を含むので当然決定不可能)。
  • ある文脈自由文法の記述する言語は、別のある文脈自由文法の記述する言語に包含されるか否か( A \subseteq B \wedge B \subseteq A の判定は先の問題と等価であるため)。
  • ある文脈自由文法が記述する言語と別の文脈自由文法が記述する言語の両方に含まれる文字列はあるか否か。
  • ある文脈自由文法があいまいか否か。
  • ある文脈依存文法が実は文脈自由言語を表しているか否か。

決定不可能な問題に対するよくある誤解として「この形式をしている問題は決定不可能」というものがありますが、「この形式をしている問題を 全て 解ける(統一的な)アルゴリズムはない」という意味であり、個々の問題インスタンスは決定可能です。たとえば、特定の文脈自由文法があいまいか否か、などは頑張れば証明が可能です。

参考文献

[1] M. M. Geller, M. A. Harrison, Theoretical Computer Science, 1977, 4, 245-276.

[2] D.J. Rosenkrantz, R.E. Stearns, Inf. Control, 1970, 17, 226-256.

VisualStudioを使っていると「移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る

タイトルの通りです。

具体的な症状は以下のような感じでした。

  • エクスプローラーからそのファイルをドラッグアンドドロップでVisualStudioに持ってくると、「(そのファイルのフルパス)は移動したか、名前が変更されたか、またはコンピュータに存在しません。」と出る。開こうとしているのだからまさにそこにあるはずなのですが。
  • #includeしているファイルのところで左クリックして出てくるメニューからそのファイルを開こうとすると、見つからなかったとエラーが出る。
  • そのファイルで定義されている関数を呼び出している部分を左クリックして出てくるメニューから定義に移動しようとすると、実行するのに十分なメモリがありませんでしたとエラーになる。
  • インテリセンスが働かない。また、予約語が青くなる以外に色がつかない。
  • そのファイルを変更したあとビルドしようとしても、「変更なし」とみなされてビルドができない。
  • VisualStudioを閉じたり、再起動したりしてもやはり同じ症状が出る。
  • 新たにディレクトリを作り、ソースコードgit cloneでコピーした後、CMakeをして作ったまっさらな状態から再度コンパイルしようとすると、No such file or directoryと出てコンパイルできない。

対処方法をググってみると、大半は、単に初心者がインクルードパスを適切に指定できていないというだけの話であって、今回の症状とは関係がなさそうに思われます。 なぜならそのフォルダにある他のファイルはちゃんとコンパイルできるし、そもそも以前はコンパイルできていたからです。

いくつか根深い問題を踏んで、解決したというウェブサイトを見つけました。

qiita.com

このウェブサイトによれば、WSL上でgitを使っていたとか、大文字小文字の区別だとか、そういった話が問題を引き起こすとのことです。 確かにgit mvでファイル名を変更した後に問題が発生したので、心当たりがあるということになります。 しかし、表示されるパスが全て大文字になっているということはないので、症状は異なります。

sgry.jp

このウェブサイトによれば、%TEMP%ディレクトリに一時ファイルが残ってしまうため、VisualStudioを再インストールするなどの方法をとってすら解決ができないとのことです。 しかし、%TEMP%ディレクトリにmsvcという文字列を含むファイルは見つからなかったため、どうも違うようです。

blogs.yahoo.co.jp

複数のソリューションを持つプロジェクトを扱っている場合にたまに出くわすと書いてあり、その条件に該当します。 .suoファイルを削除すれば問題を解決できると書いてあります(.suoファイルというのは、.suoという拡張子のファイルではなくて、.suoの四文字が名前であるファイルのことです)。 しかし削除しても症状が改善することはありませんでした。

解決方法(?)

とりあえず元の名前に変更したところ、いくつかの問題は解決しました。

  • エクスプローラーからドラッグアンドドロップでそのファイルを開くことができるようになった。
  • そのファイルを変更した後ビルドしようとすると、ちゃんと依存しているファイルが全てコンパイルされる。
  • 定義に移動しようとすると、実行するのに十分なメモリがありませんでしたとエラーが出る症状はそのまま。しかし、一日経ったら(※)改善した。
  • #includeしているファイルに飛ぼうとすると見つからなかったとエラーが出る症状はそのままだったが、やはり一日経ったら(※)改善した。
  • インテリセンスは依然働かないし、予約語が青くなる以外に色がつかないままである。

※PCは起動しっぱなしだったけれど、VisualStudioを閉じて開きなおしたのが原因かもしれないです。

典型的な「よくわからないけれどいろいろやったらなおった」という感じになって原因も対処方法もわからずじまいになってしまいました……。

makeの並列オプションは何を指定するべきか

最近何の縁があってか 鬼斬弐 というオープンソースのプロセッサシミュレータの開発を手伝っています。

github.com

ここ数日でRISC-VのRV64Gへの対応が急速に進められ、ベンチマークプログラムも動くものが増えてきたようです。 私はちまちま細かいバグを取り除く作業をやっています。


今日は、makeを並列で行うオプション-j付きで実行するとき、その引数(最大何並列にするか)を何にすべきか調査した話をします。

よく見かけるのは、以下のような言説です。

  • CPUのスレッド数を指定するべき

これはもっとも単純で、CPUの動かせるスレッド数より並列度を高くしても、本当に並列に実行できるわけではないので、これが最大の効率になるはず、といった考えから来るものでしょう。

  • CPUのコア数を指定するべき

同時マルチスレッディングで複数のスレッドが動かせるといっても、あくまで1つのCPUで行っているため、演算器が余っていなければ特に速くなることはありません。それどころか、キャッシュを複数のプロセスで共有するため、運が悪ければ並列にした方が遅くなることまであり得ます。コア数までの並列度なら、全てのプロセスが独立したコア上で動くため、そのような問題が発生することはないはずです。

  • CPUのスレッド数(あるいはコア数)より1少ない数を指定するべき

makeを行っている間、CPUはコンパイルだけを行うのではなく、OSの仕事やバックグラウンドプロセスなどを実行する必要もあります。そこで、そういったプロセスのために1スレッド(1コア)残しておこうといった発想だと思われます。実際、スレッド数以上の並列度を指定するとマウスやキーボードの反応が悪くなって他の作業をすることがほとんど不可能になることもあるので、多少コンパイルが遅くなってもよいという場合には悪くない、安定感のある選択肢でしょう。

  • CPUのスレッド数(あるいはコア数)より1大きい数を指定するべき

これはおそらく、あるプロセスですべきことが終わった瞬間、OSが次のプロセスを選ぶわけですが、このときに選ぶプロセスが存在しないと無駄な時間が発生するため、一つ余分に作っておこうという発想だと思われます。プロセスを立てるのに時間がかかる環境(CygwinやWSL)で有効な作戦かもしれません。コア数と書かれている場合もありますが、どういった理論によるものなのかはよくわかりません。論理コア数といった意味なのでしょうか?(この記事では、スレッド数=論理コア数、コア数=物理コア数、の意味です。)

  • 特に指定する必要はない

指定しなかった場合、プロセス数の上限がない(無限にプロセスを立てることができる)という指定をしたことになります。軽量な処理を大量に行う場合は、プロセスを立てるオーバーヘッドを隠すためにこのような指定が有効な場合もあるでしょう。ただし、コンパイルは重い処理でありかつメモリを大量に消費するため、無制限にプロセスを立てるとメモリ不足を引き起こし、スワップが発生してものすごく遅くなる可能性があります。そのため普通は何らかの数字を指定するのが一般的です。

実験

先ほど話した、鬼斬弐をmakeする時間を測ることによって、最適なオプションを探します。 使うのはmasterの現在の最新 662dea7501d48f6cd70ace0ba39d1ebf3a089715 です。一度makeをすることによりファイルをキャッシュに乗せた後、make cleanします。その後makeを並列オプションを変えて実行時間を計測し、毎回make cleanします。これにより、実行時間の計測は再現性の高い精度(誤差1%未満)で行うことができます。もしメジャーフォルトが発生した場合にはファイルがキャッシュから追い出されている可能性が高いため、その後の計測に悪影響を与える可能性があります。その場合、この手順を最初から行うことによりなるべく条件を均一にします。

計測は、E5-2603 v3(1.6GHz, 6Core 12Thread)上、ネイティブのGNU/Linuxで行いました。より多くのCPUの種類、環境での計測は今後の課題とさせてください。 また、コンパイルは二週間前に作ったgcc8.2.0(-O3 -march=nativeでセルフホストコンパイル済み)を使いました。コンパイルするだけならもっと古いバージョンのgccを使った方が速いようです。

オプション 実行時間 備考
指定なし(直列) 447秒
-j 2 235秒
-j 3 163秒
-j 4 128秒
-j 5 108秒
-j 6 95.2秒 コア数
-j 7 93.9秒
-j 8 94.4秒
-j 9 95.6秒
-j 10 95.2秒
-j 11 95.6秒
-j 12 95.8秒 スレッド数
-j 24 97.7秒
-j 98.1秒 メジャーフォルト発生するもスワップはなし

実験結果はこのようになりました。どうやらコンパイルする仕事は同時マルチスレッディングを使うとかえって遅くなる仕事であるようです。驚くべきことに、並列オプションは-j 7が最も速くコンパイルできるという結果になりました。コア数+1の設定が良いという言説はなかなか理解しがたいものですが、実験してみると正しいようです。理由はよくわかりませんが……。

-jを行った場合、メジャーフォルトが発生しました。しかし、スワップは起こらなかったので、単にキャッシュを追い出したに過ぎないようです。とはいえ、OSの仕事が増えてしまったため時間が余計にかかっています(systemの実行時間が、他の場合は40秒程度に対して-jの場合のみ46秒)。鬼斬弐のコンパイルでは150プロセス程度しか同時に実行されないため劇的な性能低下はまぬがれましたが、もっと大規模なものをビルドする場合はスワップが発生して悲惨なことになるものと思われます。このようにスワップが発生しないとわかっているのであれば、よく考えずに-jを指定しても最適なオプション指定と大差ないため、最適なオプションが分からないときはとりあえず-jを指定しておく、というのもあながち間違いとは言い切れない感じがあります。

今年ももう終わりですね。皆様よいお年を。

RISC-Vのシミュレーション環境を構築した

そろそろクリスマスですね。ltmpcを作ってからもう一年たってしまったのかという思いでいっぱいです。

github.com

さて、前回作ったRISC-V用のgccですが、残念ながら手元にRISC-Vの命令セットが動くコンピュータがないため、コンパイルしたプログラムを動かすことができません。 そこで、シミュレータを使って動かします。

シミュレータにはいくつか種類がありますが、公式が出しているSpikeというシミュレータを使うことにします。 github.com

ただし、これ単体でビルドすることはできず、依存ライブラリを先にインストールしておく必要があります。さらに、Spikeのビルドに成功したとしても、proxy kernel(pk)がないとほとんどのプログラムは動きません。 proxy kernelというのは、要するにOSの仕事をやってくれるような(RISC-Vの命令を使った)プログラムコードのようです。

……という失敗があったので、Spikeだけをビルドしようとするのはやめましょう。素直に公式が出している、RISC-Vツールチェイン*1を全てビルドすることにします。

github.com

やり方は簡単で、

$ git clone https://github.com/riscv/riscv-tools.git
$ git submodule update --init --recursive
$ sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev libusb-1.0-0-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev device-tree-compiler pkg-config libexpat-dev
$ export RISCV=/home/lpha/riscv/toolchain
$ ./build.sh

とやればよさそうです。

ただ、apt-get を行った際に perl-base のバージョンと bison flex texinfo libtool-bin の依存バージョンが異なるという衝突が発生し、面倒なことになりました。 これらがインストールされていないとビルドに失敗するため、これは大きな問題となります(ビルドの途中で失敗するうえ、ビルドに失敗した後にやり直すとまた始めからになってしまうので大変な時間ロスになります)。

aptitude コマンドを使うと、この問題の解決策が三つ表示されます(これはおそらく、何がインストールされているかによると思われます)。 そのうち二つは「インストールをあきらめる」という趣旨でしたが、これでは解決になりません。 三つ目の解決策は「perlのバージョンを下げる」というものであり、これを実行することで依存関係の衝突の問題を解消することができました。

このままでは依存関係の衝突が解消されただけで、問題の bison flex texinfo libtool-bin はまだインストールできていないので、忘れずにインストールしておきます(これに気づかずに何度もビルドに失敗しました……)。

ビルドには、すごい時間がかかります。/usr/bin/timeコマンドで計測してみたところ、二時間ほどかかったようです。

RISC-V Toolchain installation completed!
2104.01user 1129.07system 1:49:00elapsed 49%CPU (0avgtext+0avgdata 543192maxresident)k
0inputs+0outputs (0major+150543612minor)pagefaults 0swaps

シミュレータを使うには、以下のようにします。

$ /home/lpha/riscv/toolchain/bin/spike pk Hello.out

あれ、おかしいですね、PCが負の番地に飛んでクラッシュしました。

どうやら、先週ビルドしたRISC-V用のgcc8.2.0が出すプログラムは微妙に狂っているようです。

ツールチェインの中に含まれるgcc7.2.0を使ってコンパイルしたものは正しく動きます。

$ /home/lpha/riscv/toolchain/bin/spike pk Hello.out
Hello, world!

一命令ごとに実行するためには、対話的デバッグ実行オプション-dをつけます。

$ /home/lpha/riscv/toolchain/bin/spike -d pk Hello.out
:

たとえば、until pc 0 1034cなどと打ち込むことで、プログラムカウンタ(PC)が0x1034cになるまで実行をスキップできます(実は落とし穴、後述)。 この時、pc 0となっているのは、0番のコアのPCがその値になるまで、という意味です。どうやらマルチコア対応もされているようですね、すごいです。

until pc 1034cなどと打ち間違えてもスルーしてしまうのはかなり不親切です。うっかりしがちなので気を付けます。

ここでエンターキーを押せば、一命令ずつ実行されていきます。

reg 0 spなどと打ち込むことでそのレジスタの値を出力することができます。このreg 0というのはやはり0番のコアのレジスタだという意味ですね。 レジスタの名前はどうもABIで定められたものしか使えず、x2のような指定ができない点は不便です。

reg 0とだけ打ち込むことで全部のレジスタの値を出力できます。

mem 0 7f7e9b50などと打ち込むことでメモリの特定番地の値を8Byte分ダンプすることができます(アラインがあっていなくても8Byte分出てきます)。

さて、0x1034c番地はHello.outのエントリーポイントなのですが、until pc 0 1034cと打ち込むとインタラプトが発生したと出力されます。 その後エンターキーを押して行ってもその付近(0x1034c番地にあるのは0x10378番地へのjal命令ですが、そこでもない)を実行している様子はないため、不可解な状況です。

これは実は、OSのローダープログラムが動いた後に本体プログラムにジャンプした瞬間であり、初めて見るメモリ番地だったので、命令メモリを参照した際にページフォルトが発生したのが原因です。 エンターキーを押して行った時に表示されるのは、プロキシカーネル内の、ページフォルトからの復帰コードだったわけです。

そのため、もう一度until pc 0 1034cと打ち込む必要があります。gdbみたいに上キーを押しても履歴が出てくるわけではないので本当に打ち込む必要があります。面倒くさいですね……。

SpikeはISAシミュレータとうたっていますが、実際にはページフォルトへの対応をproxy kernelのコード(これもRISC-Vの命令列で行ったりと、かなり深いレベルまでシミュレーションしてくれるようです。

ログを吐かせるオプション-lをつけて実行することで命令列をダンプすることができます。 これを使って0x1034c番地に来るのが何命令目なのかを数えてみたところ、285123命令目でした。本体プログラムが実行されるまでにこれだけの命令が実行されているとすると結構すごいですね。

*1:リポジトリの名前はtoolsになっているけれどなんでだろう

gcc8.2.0をソースからビルドした

環境構築がうまくいかないとつらいものです。うまくいったという情報がweb上にあるだけで助かったりします。

うまくいったので記録に残しておきます。

gcc8.2.0, x86向け

制約

  • 管理者ではないので/bin/とかそういうところにはインストールできません。/home/lpha/gcc82/以下にインストールすることにします。
  • もともとインストールされているgcc(というよりはデフォルトで指定されているアセンブラのas 2.25.1)のバージョンが低く*1-march=nativeコンパイルすると知らない命令だとエラーを出します*2。この部分を改善したいです。

方法

  • configureスクリプトのオプションとして、--prefix=/home/lpha/gcc82(最後にスラッシュがあってもなくても同じ)とつけることで、インストールパスを指定できます。
  • GNU binutilsも新しいものをインストールすることで、-march=nativeをつけてもアセンブラがエラーを出さないようにすることができます。

おおざっぱな手順

  1. GNU binutilsをインストールします。これにより、Haswell向けの命令をアセンブルすることができるアセンブラが手に入ります。
  2. もとからあるgccでgcc8.2.0を、Haswell向けの最適化なしでコンパイルし、gcc8.2.0(Haswell特有の命令を使わずに動作するプログラムになっている。Haswell特有の命令を出力できるコンパイラになっている*3)を手に入れます。
  3. 先ほどの成果物でもう一度gcc8.2.0をコンパイルすることでHaswell向けに最適化されたgcc8.2.0を得ることができます。
  4. さらにその成果物でもう一度gcc8.2.0をコンパイルしたとき、同じものが得られることをもって、サニティチェック(念のための確認)とします。

3.の手順は省略可能ですが、コンパイル速度は速い方がいいので最適化されたgccを手に入れることは意義があります。4.の手順も省略可能ですが、3ステージビルドの手順に従う方が楽です。一度のmakeコマンドで2.3.4.の手順が一気に行われます。代わりに三倍の時間がかかることは覚悟しなければなりません。

コマンド

wget https://ftp.gnu.org/gnu/binutils/binutils-2.31.tar.gz
wget http://ftp.gnu.org/gnu/gcc/gcc-8.2.0/gcc-8.2.0.tar.gz
tar xf binutils-2.31.tar.gz 
tar xf gcc-8.2.0.tar.gz & # 時間かかるから先に仕掛けておく、binutilsをmakeしている辺りで終わるはず
cd binutils-2.31
mkdir build
cd build
../configure --prefix=/home/lpha/gcc82/
make -j # 12スレッドで100秒くらい
make install -j
cd ..
cd ..
cd gcc-8.2.0
contrib/download_prerequisites
mkdir build
cd build
../configure --enable-languages=c,c++ --prefix=/home/lpha/gcc82/ --disable-multilib
make -j STAGE1_CFLAGS='-march=corei7-avx -O3' BOOT_CFLAGS='-march=native -O3'" # かかる時間は、ほとんどIO性能で決まる
make install

注意点

  • 二つの./configureで指定する--prefixは同じにすること
  • ./configureなどと、configureスクリプトをtarball(.tar.gzファイル)を展開したディレクトリ直下でやらない(buildディレクトリを作るなどする)こと
  • 逆に、contrib/download_prerequisitesはtarballを展開したディレクトリ直下で行うこと(contribディレクトリに入ってはいけない)

オプションについて

多くの「gccをソースからビルドしてみた」記事では、ブートストラップ(3回ビルドするやつ)をやっておらず、どのようにオプションを設定するべきかが分かりません。

以下の記事は3ステージビルドのオプションについても詳しく解説されており、有用でした。

CentOS6.xでGCC5.2をOS標準の4.4.7と共存できるようにソースビルドした - Qiita

gcc8.2.0, RV64GC

要するに、クロスコンパイラの作成です。

RV64GCとは、RISC-Vという命令セットアーキテクチャの64bit版で、使える命令セットがGeneral Instructions(整数系命令(I)・乗除算命令(M)・アトミック命令(A)・単精度浮動小数点数演算命令(F)・倍精度浮動小数点演算命令(D)の全部が使える)+Compressed Instructions(命令の長さが32bitではなく16bitの命令群)だということを示しています。

制約

  • Linux subsystem for Windowsを使って行ったので、sudo apt-get install ...などが使えます。
  • インストール先は、/home/lpha/rv64gc/以下にします。

コマンド

git clone --recursive https://github.com/riscv/riscv-gnu-toolchain # 30分くらいかかる
cd riscv-gnu-toolchain
sudo apt-get install autoconf automake autotools-dev curl libmpc-dev libmpfr-dev libgmp-dev gawk build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev

texinfoが、バージョンの依存関係の制約を満たせないと怒られましたが、aptitudeコマンドに促されるまま、一部の依存ライブラリのバージョンをダウングレードして通しました。もっとうまい方法はあったのでしょうか……?

./configure --prefix=/home/lpha/rv64gc
make linux -j # 8スレッドで45分

依存関係の問題を解決するのに多少手間取りましたが、それ以外には難しいところはありませんでした。

*1:as 2.25.1が出たのは2014年、Haswellが発売されたのは2013年6月なのになぜ対応していないのでしょう?

*2:しかし一部のAVX2命令には対応している

*3:これはgcc8.2.0をコンパイルしたのとはあまり関係なく、デフォルトで使用するアセンブラが先ほどインストールした新しいasになっていることが重要です