[インデックス 16003] ファイルの概要

このコミットは、Go言語の386アーキテクチャ向けアセンブラ（8a）とリンカ（8l）に、PCMPEQBおよびPMOVMSKBという2つのSSE（Streaming SIMD Extensions）命令のサポートを追加するものです。これらの命令は、特に文字列の高速な比較処理において利用され、Goランタイムのパフォーマンス向上に寄与します。

コミット

commit 871177df6ac09ebccb793138dc0b9ccd8fca8cec
Author: Keith Randall <khr@golang.org>
Date:   Fri Mar 29 00:34:03 2013 -0700

    8a/8l: add PCMPEQB and PMOVMSKB to 386.
    
    Used by CL 8056043 for fast string equals.
    
    R=bradfitz
    CC=golang-dev
    https://golang.org/cl/8102044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/871177df6ac09ebccb793138dc0b9ccd8fca8cec

元コミット内容

8a/8l: add PCMPEQB and PMOVMSKB to 386.

Used by CL 8056043 for fast string equals.

R=bradfitz
CC=golang-dev
https://golang.org/cl/8102044

変更の背景

このコミットの主な背景は、Go言語における文字列およびバイトスライスの比較処理のパフォーマンスを向上させることです。コミットメッセージに記載されている「CL 8056043 for fast string equals」は、Goのランタイムにおけるruntime.memequal（文字列やバイトスライスの等価性チェックに使用される内部関数）の最適化を指しています。

従来のバイトごとの比較は、特に長い文字列の場合にCPUサイクルを多く消費します。現代のx86プロセッサが持つSIMD（Single Instruction, Multiple Data）命令セットを活用することで、複数のデータを並行して処理し、比較処理を大幅に高速化することが可能になります。PCMPEQBとPMOVMSKBは、このようなSIMDを活用した高速な比較を実現するための重要な命令であり、これらをGoのツールチェイン（アセンブラとリンカ）が認識し、利用できるようにすることがこの変更の目的です。これにより、Goプログラム全体の文字列操作がより効率的になり、特に文字列比較が頻繁に行われるアプリケーションのパフォーマンスが向上します。

前提知識の解説

x86アセンブリとGoのツールチェイン

Go言語は、そのコンパイラとツールチェインの一部として、特定のアセンブリ言語（Plan 9アセンブリ）を使用します。これは、パフォーマンスが重要な部分や、ハードウェア固有の機能を利用するために用いられます。

• 8a: 386アーキテクチャ向けのアセンブラです。アセンブリコードを機械語に変換します。
• 8l: 386アーキテクチャ向けのリンカです。オブジェクトファイルを結合して実行可能ファイルを生成します。 これらのツールは、Goの標準ライブラリやランタイムの低レベルな部分で、特定のCPU命令を利用するために不可欠です。

SIMD (Single Instruction, Multiple Data)

SIMDは、単一の命令で複数のデータ要素に対して同じ操作を同時に実行できるプロセッサの機能です。これにより、画像処理、科学計算、マルチメディア処理、そして文字列操作のような、データ並列性が高いタスクのパフォーマンスを劇的に向上させることができます。x86アーキテクチャでは、SSE（Streaming SIMD Extensions）が代表的なSIMD命令セットです。

PCMPEQB (Packed Compare Equal Bytes)

PCMPEQBはSSE命令の一つで、「Packed Compare Equal Bytes」の略です。この命令は、2つの128ビットXMMレジスタ（SIMD操作に使用されるレジスタ）内の対応するバイトを比較します。

• 動作: 各バイトペアを比較し、もし等しければ、結果のXMMレジスタの対応するバイトを0xFF（全ビットが1）に設定します。等しくなければ、0x00（全ビットが0）に設定します。
• 利点: 1回の命令実行で16バイト（128ビット / 8ビット/バイト）を並行して比較できるため、バイトごとの比較よりもはるかに高速です。

PMOVMSKB (Packed Move Mask Bytes)

PMOVMSKBもSSE命令の一つで、「Packed Move Mask Bytes」の略です。この命令は、XMMレジスタ内の各バイトの最上位ビット（MSB）を抽出し、それらを結合して汎用レジスタ（例: EAX）に16ビットのマスクとして格納します。

• 動作: XMMレジスタの各バイト（16個）から最上位ビットを取り出し、それらを連結して16ビットの整数値を生成します。
• 利点: PCMPEQBの結果と組み合わせることで、16バイトの比較結果を効率的にサマライズできます。例えば、PCMPEQBの結果が全て0xFF（全てのバイトが等しい）であれば、PMOVMSKBは0xFFFFというマスクを生成します。これにより、16バイトのブロック全体が等しいかどうかを単一のレジスタ値のチェックで判断できます。

技術的詳細

このコミットは、GoのツールチェインがPCMPEQBとPMOVMSKB命令を認識し、それらを使用できるようにするための変更です。具体的には、以下のファイルが修正されています。

1. src/cmd/8a/lex.c: Goのアセンブラ（8a）の字句解析器（lexer）に、新しい命令名（PCMPEQBとPMOVMSKB）を追加します。これにより、アセンブラがこれらの命令を有効なニーモニックとして認識できるようになります。
2. src/cmd/8l/8.out.h: Goのリンカ（8l）が使用する命令コードの列挙型（enum）に、新しい命令に対応する定数（APCMPEQBとAPMOVMSKB）を追加します。これは、リンカがこれらの命令を内部的に識別するために必要です。
3. src/cmd/8l/optab.c: Goのリンカ（8l）のオペレーションテーブルに、PCMPEQBとPMOVMSKB命令のエンコーディング情報（オペコード、オペランドの型、命令の長さなど）を追加します。これにより、リンカはこれらの命令を正しく機械語に変換し、実行可能ファイルに含めることができるようになります。

これらの変更により、Goのコンパイラやランタイムは、必要に応じてこれらのSIMD命令を生成し、文字列比較などの処理を高速化できるようになります。特に、PCMPEQBとPMOVMSKBを組み合わせることで、以下のような効率的な文字列比較ロジックが実現されます。

1. 比較したい文字列のチャンク（通常は16バイト）をXMMレジスタにロードします。
2. PCMPEQB命令を使用して、2つのチャンクをバイトごとに比較します。結果は、一致するバイトが0xFF、不一致が0x00となるXMMレジスタに格納されます。
3. PMOVMSKB命令を使用して、この結果XMMレジスタから16ビットのマスクを生成します。このマスクは、各バイトの比較結果の最上位ビットを連結したものです。
4. 生成されたマスクが0xFFFF（全てのビットが1）であるかをチェックします。もしそうであれば、その16バイトのチャンクは完全に一致しています。そうでなければ、不一致が存在します。

この手法は、ループ内でバイトごとに比較するよりもはるかに少ないCPUサイクルで、大量のデータを比較できるため、非常に効率的です。

コアとなるコードの変更箇所

src/cmd/8a/lex.c

--- a/src/cmd/8a/lex.c
+++ b/src/cmd/8a/lex.c
@@ -760,10 +760,12 @@ struct
 	"ORPS",		LTYPE3,	AORPS,
 	"PADDQ",	LTYPE3,	APADDQ,
 	"PAND",		LTYPE3,	APAND,
+	"PCMPEQB",	LTYPE3,	APCMPEQB,
 	"PMAXSW",	LTYPE3,	APMAXSW,
 	"PMAXUB",	LTYPE3,	APMAXUB,
 	"PMINSW",	LTYPE3,	APMINSW,
 	"PMINUB",	LTYPE3,	APMINUB,
+	"PMOVMSKB",	LTYPE3,	APMOVMSKB,
 	"PSADBW",	LTYPE3,	APSADBW,
 	"PSHUFB",	LTYPE3, APSHUFB,
 	"PSUBB",	LTYPE3,	APSUBB,

src/cmd/8l/8.out.h

--- a/src/cmd/8l/8.out.h
+++ b/src/cmd/8l/8.out.h
@@ -534,10 +534,12 @@ enum
 	AORPS,
 	APADDQ,
 	APAND,
+	APCMPEQB,
 	APMAXSW,
 	APMAXUB,
 	APMINSW,
 	APMINUB,
+	APMOVMSKB,
 	APSADBW,
 	APSUBB,
 	APSUBL,

src/cmd/8l/optab.c

--- a/src/cmd/8l/optab.c
+++ b/src/cmd/8l/optab.c
@@ -364,6 +364,12 @@ uchar	ysvrs[] =
 	Ym,	Ynone,	Zm_o,	2,
 	0
 };
+uchar	ymskb[] =
+{
+	Yxr,	Yrl,	Zm_r_xm,	2,
+	Ymr,	Yrl,	Zm_r_xm,	1,
+	0
+};
 uchar	yxm[] = 
 {
 	Yxm,	Yxr,	Zm_r_xm,	1,
@@ -950,10 +956,12 @@ Optab optab[] =
 	{ AORPS,	yxm,	Pm, 0x56 },
 	{ APADDQ,	yxm,	Pe, 0xd4 },
 	{ APAND,	yxm,	Pe, 0xdb },
+	{ APCMPEQB,	yxmq,	Pe ,0x74 },
 	{ APMAXSW,	yxm,	Pe, 0xee },
 	{ APMAXUB,	yxm,	Pe, 0xde },
 	{ APMINSW,	yxm,	Pe, 0xea },
 	{ APMINUB,	yxm,	Pe, 0xda },
+	{ APMOVMSKB,	ymskb,	Px, Pe,0xd7,0xd7 },
 	{ APSADBW,	yxm,	Pq, 0xf6 },
 	{ APSUBB,	yxm,	Pe, 0xf8 },
 	{ APSUBL,	yxm,	Pe, 0xfa },

コアとなるコードの解説

src/cmd/8a/lex.c の変更

このファイルでは、Goのアセンブラが認識する命令のリストに"PCMPEQB"と"PMOVMSKB"という文字列が追加されています。LTYPE3は命令のタイプを示し、APCMPEQBとAPMOVMSKBはそれぞれ対応する内部的な命令コードの定数です。これにより、Goのアセンブリコード内でこれらの命令を記述できるようになります。

src/cmd/8l/8.out.h の変更

このヘッダーファイルでは、リンカが使用する命令の列挙型enumに、APCMPEQBとAPMOVMSKBという新しい定数が追加されています。これらの定数は、アセンブラが生成したオブジェクトファイル内で、これらの命令を識別するために使用されます。

src/cmd/8l/optab.c の変更

このファイルは、リンカが各命令を機械語に変換するためのオペレーションテーブル（Optab optab[]）を定義しています。

• ymskb配列の追加: PMOVMSKB命令のオペランドの型とエンコーディングに関する情報がymskbという新しい配列で定義されています。YxrはXMMレジスタ、Yrlは汎用レジスタを示し、Zm_r_xmはメモリまたはXMMレジスタをソースとし、汎用レジスタをデスティネーションとするオペランド形式を示します。
• optab配列へのエントリ追加:
  • { APCMPEQB, yxmq, Pe ,0x74 }: PCMPEQB命令のエントリが追加されています。
    • APCMPEQB: 命令の内部コード。
    • yxmq: オペランドの型（XMMレジスタとXMMレジスタ/メモリ）。
    • Pe: 命令がSSE命令であることを示すプレフィックス。
    • 0x74: PCMPEQB命令のオペコード。
  • { APMOVMSKB, ymskb, Px, Pe,0xd7,0xd7 }: PMOVMSKB命令のエントリが追加されています。
    • APMOVMSKB: 命令の内部コード。
    • ymskb: オペランドの型（XMMレジスタと汎用レジスタ）。
    • Px, Pe: 命令がSSE命令であることを示すプレフィックス。
    • 0xd7,0xd7: PMOVMSKB命令のオペコード。

これらの変更により、Goのリンカは、アセンブリコード内で使用されるPCMPEQBとPMOVMSKB命令を正しく解釈し、対応するx86機械語命令に変換して実行可能ファイルを生成できるようになります。これにより、Goのランタイムや標準ライブラリがこれらの高性能なSIMD命令を直接利用し、文字列比較などの処理を最適化することが可能になります。

関連リンク

• https://golang.org/cl/8102044

参考にした情報源リンク

• https://stackoverflow.com/questions/14246996/how-to-use-pcmpeqb-and-pmovmskb-for-string-comparison
• https://docs.oracle.com/cd/E19455-01/806-3773/6_pcmpeqb.html
• https://leapcell.io/blog/go-string-optimization
• https://appspot.com/ (CL 8056043に関する情報源)