1
Help us understand the problem. What are the problem?

posted at

updated at

Organization

【Golang】AND と MOD(Modulo)の速度の違いと反復処理の高速化【論理積と剰余の速度差】【論理演算】

Go 言語(以下 Golang)で、イテレーションやループ内の反復処理に、&(AND, 論理積)と %(MODULO, 剰余演算)を使った場合の速度の違いが知りたい。

「golang 論理演算 AND MOD 速度 違い」でググっても、ピンポイントのタイトルの記事がなかったので、自分のググラビリティとして。

TL; DR (今北産業)

  • %MOD 演算)と &AND 演算)で、演算自体の差はなかった
    (コンパイラが同じ処理に変換するため)

  • コンパイラが同じ処理に自動変換できないような処理の場合は、AND の方が MOD の 93% も速い
    (例えば、データの書き換えなどが発生するようなもの)

  • &AND演算 でも %剰余演算 のように 0,1,2,3,0,1,2,3,0... といった反復ができる
    (反復単位が「偶数」の場合に限る。その場合、偶数の反復数 - 1 を使う。具体的には以下を参照)

    0〜3の4つごとの反復(iterの値が、どちらも同じように反復していることに注目)
     loop := 10
     dMOD := 4 // n=2, 2^n=4 
     dAND := 3 // n=2, (2^n)-1=3
    
     fmt.Println("MOD")
     for i := 0; i < loop; i++ {
     	iter := i%dMOD // dMOD の値がゼロでないこと
     	fmt.Printf("  Index: %v, Iter: %v\n", i, iter)
     }
    
     fmt.Println("AND")
     for i := 0; i < loop; i++ {
     	iter := i&dAND // i の値がマイナスでないこと
     	fmt.Printf("  Index: %v, Iter: %v\n", i, iter)
     }
     // Output:
     // MOD
     //   Index: 0, Iter: 0
     //   Index: 1, Iter: 1
     //   Index: 2, Iter: 2
     //   Index: 3, Iter: 3
     //   Index: 4, Iter: 0
     //   Index: 5, Iter: 1
     //   Index: 6, Iter: 2
     //   Index: 7, Iter: 3
     //   Index: 8, Iter: 0
     //   Index: 9, Iter: 1
     // AND
     //   Index: 0, Iter: 0
     //   Index: 1, Iter: 1
     //   Index: 2, Iter: 2
     //   Index: 3, Iter: 3
     //   Index: 4, Iter: 0
     //   Index: 5, Iter: 1
     //   Index: 6, Iter: 2
     //   Index: 7, Iter: 3
     //   Index: 8, Iter: 0
     //   Index: 9, Iter: 1
    

TS; DR (たかが n バイトデータごとのループ処理で悩んだコマケーこと)

Golang を勉強する中で、[]byte データを n バイト単位でゴニョゴニョする必要がありました。n バイトをゴソッと読み込んで処理しては、ゴソッと次を読み込むような感じです。

しかし、単純な for 〜 range では 1 バイトごとの読み込み or 処理になります。

1バイトごとにゴニョゴニョする例
for i, v range MyByteSliceData {
    // v を使ってゴニョゴニョ (v = 1 byte データ)
}

n バイト単位のスライス同士を XOR する

今回ゴニョゴニョしたかった内容ですが、具体的には 4 バイトごとに読み込んだバイナリ(バイト)データを、前の 4 バイトデータに XOR排他的論理演算 をしたかったのです。そして最終的に得た 4 バイトのデータをアイーンしかったのです。そうです、私が排他おじさんです。

何故 XOR かは秘密。🤫シーッhush hash

しかし、for 〜 を使う以外に方法が思いつかなかったので、要素数が 4 の byte 型の配列([4]byte)に、頭から順番に XOR していくことにしました。

4バイト単位で読み込んでゴニョゴニョする例
var foo = [4]byte

for i, v range MyByteSliceData {
    index := i%4    // index は 0,1,2,3,0,1... とループする
    foo[index] ^= v // 読み込んだ v を XOR でマッピング(v = 1 バイトデータ)
}

うーん。シンプルなものの、なんか、根本的な別の方法がありそうな気がします。

「ほら、ごらんGolang。素人はこれだから困る」と言われないように、よりベターな方法はないか Golang のスポンサー情報を探しに行きました。

ベクトル・データ(意味のある順に並んだ、数値のみで構成されている配列)をゴニョゴニョするのに速度が必要なものと言えば「ハッシュ関数」です。

新参で爆速のハッシュ・アルゴリズムである BLAKE3 の Golang 実装の 1 つ "github.com/lukechampine/blake3" の作者が "fastxor" という爆速パッケージを提供されていました。

var dst, a, b []byte の時、dst = (a xor b) を算出してくれるものです。しかも Pure Go での実装Golang だけで動くものに加え、cgo(C 言語によるモジュールを使ったパーサー)を使う場合には、AVX の GPU にも対応しています。

では、このパッケージは Pure Go ではどのように実装しているのか確認してみると、残念ながら入力の n バイトデータ(ab)は、ユーザーに委ねられていました。

XOR 演算も、for 〜 range ではないものの、普通に for ループを使って a ^ b していました。

func Bytes(dst, a, b []byte) int {
...
    for i := 0; i < n; i++ {
        dst[i] = a[i] ^ b[i]
    }
...
}

確かに XOR したかったのですが、今回は・・・ XOR したかっただけです。基本的には 「n バイト単位でデータを読み込む方法」が知りたかったのです。このパッケージは、「読み込んだ後」の XOR 処理には最適かもしれませんが、残念ながらニーズにはマッチしません。

さらに悲しいことに「"golang" "n バイトごと" 読み込む ファイル」でググっても、ほとんどヒットしないのです。

えぇええ⤴️ ... ... とマスオさんもビックリです。

n バイト単位で読み込む

n バイトごとにデータを読み込むサンプル

Golang で "n バイト" ごとにデータを読み込む

package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"strings"

	"github.com/pkg/errors"
)

func main() {
	// 入力データ例
	// ファイルから読み込む場合は:
	//   r, err := os.Open("helloworld.png")
	//   if err != nil {
	//     log.Fatal(err)
	//   }
	//   defer file.Close()
	data := "Hello, 世界"
	r := strings.NewReader(data)

	// r から 4 バイトごとに読み込んだスライスを得る([][4]bytes)
	chunks, err := Chunker(r, 4)
	if err != nil {
		log.Fatal(err)
	}
}

// Chunker は input から lenChunk バイトごとに読み込んだ `[]byte` のスライス(二次元スライス)を返します。
func Chunker(input io.Reader, lenChunk int) ([][]byte, error) {
	// 入力のスキャナーを作成
	scanner := bufio.NewScanner(input)

	// スキャン中、チャンク(ブツ切り)データを作る関数。返した以降の []byte データが
	// 次回呼び出し時に渡される。
	onChunk := func(data []byte, atEOF bool) (advance int, token []byte, err error) {
		lenChunk := 4
		chunk := make([]byte, lenChunk)

		for i := 0; i < len(data); i++ {
			if i == lenChunk {
				return i, chunk, nil
			}

			chunk[i] = data[i]
		}

		if !atEOF {
			return 0, nil, nil
		}

		// lenChunk 以下の残りの端数のバイトを返す。bufio.ErrFinalToken を返すのは、Scan に、
		// 「もぅデータはないよ」と伝えるためのものです。これ自体は Scan のエラーになりません。
		return 0, chunk, bufio.ErrFinalToken
	}

	// ブツ切り条件の関数をスキャナーにセットする
	scanner.Split(onChunk)

	// ブツ切りデータの初期化とスキャンの実行
	chunks := [][]byte{}
	for scanner.Scan() {
		chunks = append(chunks, scanner.Bytes())
	}

	if err := scanner.Err(); err != nil {
		return nil, errors.Wrap(err, "failed to read input")
	}

	// ブツ切りデータ(実行結果)を返す
	return chunks, nil
}

「ほら、ごらんGolang。言ったじゃないの、ど素人が」と、ドキュメント嫁から吐き捨てるように叱られたので、隣の芝のスポンサー情報に頼らずに、情報がないか嫁の本家に頼ることにしました。

ドキュメント嫁の本家は、家に鍵をかけないオープンソースポリシーなので、勝手にあがって本家のライブラリを色々と漁ってみました。

すると、どうやらメモリ不足になりそうな「大きなファイルの読み込み」には「バッファ一時的な記憶領域」を使うのが常という情報を得ました。

チョコッと読んだら関数に渡して、続きを求められたら、またチョコッと渡す。そんな動きです。

「(おお。この「チョコッと読み込むサイズ」を指定できたらイケるんでね?)」と期待が膨らみます。

本妻公式のドキュメント嫁の言うことは正しかった。そう思いながら続きを読むと、関数側は「引数を io.Reader というお方に任せるのが常識」らしいことがわかりました。

つまり、引数の型が io.Readr の場合は、「いいお。リーダーにまかせろお」と言うことらしいです。

func MyHoge(input io.Reader){
   // Do fuga piyo from input
}

というのも、この io.Reader おじさんは、型々言わないタイプらしく「変数であろうが、配列であろうが、ファイルであろうが、俺様タイプであろうが、読み込める相手なら、どんな方でも読み込む」器の大きいのようです。

「読み込める相手なら」というのは、引数の型が Read() メソッドを実装していれば何でもいいという、「最低限の要件を網羅さえしていれば、相手は選ばない」という、なんとも貪欲なインターフェスの持ち主です。

そして、とりあえず、作ってみた「n バイトごとにデータを読み込む」サンプルがこちらです。

しかし、よくみると「汎用性が増しただけ」で、実質的には for 〜 でバイトごとに読み込む処理と変わらないことに気づきました。

となると、for 〜 内の処理をどうするか、工夫がないものか気になります。

数値の反復に MOD 以外でも AND が使えるなんて

すると、StakOverflow で以下を見つけました。質問自体は「XOR によるランダムな 4 バイト値が作りたい」という別の目的なのですが、その回答の以下のコードに目が行きました。

The application should xor the individual bytes. Something like this:

var random [4]byte
for i, b := range something {
   random[i&3] ^= b  // xor b on element of random
}

This sets

random[0] = random[0] ^ something[0] ^ something[4] ....
random[1] = random[1] ^ something[1] ^ something[5] ...
... and so on

("xoring a slice in Go" @ StackOverflow より)

「おお。まさに 4 バイト単位のマッピングやないけ。方向性は間違ってなかったんや」と、安堵したのも束の間、「... ... ん? &(あんど)?」と、配列のキーを i%4 を使わず i&3 を使って反復させていたのです。

... ... なんで &(AND 演算)でループするの?

割る数が偶数なら AND でもループできる

試してみると、確かにループします。エンジニアというよりは、猿人に近いnearサルなので、Wiki ってみたところ「剰余演算Modulo)」のページに以下の 1 文がありました。

ビット演算による効率化
剰余演算は、除算を行って余りを得る実装となるので、その分の処理時間を必要とする。特殊な場合においては、いくつかのハードウェア上でより高速な計算方法が存在する。

たとえば、数値の内部表現に2進法を用いているコンピュータでは、2のべき乗の剰余を計算する場合に、下記のようにビットごとのAND演算を利用することができる。

x % 2n == x & (2n - 1)

例を示す(x は正の整数とする)。

x % 2 == x & 1
x % 4 == x & 3
x % 8 == x & 7

剰余演算よりもビット演算のほうが効率よく処理できるデバイスやソフトウェアでは、この変換によってより高速に計算することができる。

最適化をするコンパイラには、2のべき乗による剰余演算を検出し、自動的にAND演算に変換するものもある。これによって、プログラマは性能を犠牲にすることなく、読みやすいソースコードを記述することができる。ただし、AND演算による場合、出力は常に正の数となるので、C言語のように剰余演算の結果の符号が被除数によって定まる言語では同じ動作はしない。したがって、被除数が負になる場合は、特別な注意が必要である。
ビット演算による効率化 | 剰余演算 @ Wikipedia より)

ほえー。すごい人たちは、こういうことをサラッと覚えてるんだろうな、と思いつつも、検証猿にまでなって体を壊した過去の悪い癖が出ました。

「... 本当、か?」と。

ベンチマークを取ってみる

Golang を勉強していて好きなところは、フォーマッター(go fmt)とテスト(go test)だけでなくベンチマーク(go test -bench)も標準装備されているところです。

さっそく、以下のテスト・コードでベンチマークを取ってみました。まずは、&(AND)と %(MOD)演算子を使ってみるだけの簡素なテストです。

0-3の4区切りのイテレーションを繰り返すテスト

func BenchmarkAND(b *testing.B) {
	ite := 3 // (2^n)-1, n=2

	b.ResetTimer()
	// ベンチ中 b.N は 1, 100, 10000 ... 1000000000 と 6 段階に変化する
	for i := 0; i < b.N; i++ {
		_ = i & ite
	}
}

func BenchmarkMOD(b *testing.B) {
	ite := 4 // 2^n, n=2

	b.ResetTimer()
	// ベンチ中 b.N は 1, 100, 10000 ... 1000000000 と 6 段階に変化する
	for i := 0; i < b.N; i++ {
		_ = i % ite
	}
}

上記テストを、以下のコマンドで実行してみます。

ベンチの実行と記録
go test -failfast -benchmem -benchtime=10s -count=10 -shuffle=on -bench=. | tee "bench.txt"

ところが、10 億回以上ループさせたのですが、分散度を加味しても&(AND)と %(MOD)に違いはありませんでした。どちらも 0.33 ナノ秒/処理でした。ってか、やっぱ Golang はやっ!

name   time/op
AND-4  0.33ns ± 1%
MOD-4  0.33ns ± 3%
実行結果のログ
  • benchstat による平均や分散などの統計
平均と分散
$ benchstat bench.txt
name   time/op
AND-4  0.33ns ± 1%
MOD-4  0.33ns ± 3%

name   alloc/op
AND-4   0.00B     
MOD-4   0.00B     

name   allocs/op
AND-4    0.00     
MOD-4    0.00    
  • ベンチマーク結果(bench.txt)を go-prettybenchtimeの速い順にソートした結果
処理時間が小さい順
$ cat bench.txt | go-prettybench -sort time
-test.shuffle 1650956445987289000
goos: darwin
goarch: amd64
pkg: KEINOS/sample/and-mod-speed
cpu: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
PASS
benchmark              iter    time/iter   bytes alloc        allocs
---------              ----    ---------   -----------        ------
BenchmarkAND-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.33 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   0.34 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000   0.35 ns/op        0 B/op   0 allocs/op
ok  	KEINOS/sample/and-mod-speed	7.601s
  • ベンチマークのログ
./bench.txtの内容
$ cat ./bench.txt
-test.shuffle 1650956445987289000
goos: darwin
goarch: amd64
pkg: KEINOS/sample/and-mod-speed
cpu: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
BenchmarkAND-4   	1000000000	         0.3294 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3519 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3359 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3296 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3367 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3322 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3302 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3288 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3353 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.3371 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3291 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3354 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3309 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3308 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3298 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3378 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3314 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3311 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3432 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	         0.3297 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	KEINOS/sample/and-mod-speed	7.601s

おそらく、これが Wikipedia にあった「コンパイラには、2のべき乗による剰余演算を検出し、自動的にAND演算に変換するものもある」に該当する気がします。結果が同じ速度だからです。

それでは「自動的に &(AND)演算に変換できない」場合の速度の違いはどうなのでしょうか。

変数の値の書き換えに &(AND)と %(MOD)を使ってみる

&(AND)と %(MOD)そのものには違いはなかったので、今度はメモリ(変数の値)の書き換えに &(AND)と %(MOD)を使ってみることにしました。

下記は、[4]int 型の配列 d で、0〜3 のキーの値に順番に valAND もしくは MODULO していく例です。val の値の算出に +1 しているのは %(MOD)する際に割る数がゼロになることがあるからです。

func BenchmarkAND(b *testing.B) {
	ite := 3 // (2^n)-1, n=2

	var d [4]int

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		val := (i & ite) + 1
		d[i&ite] &= val
	}
}

func BenchmarkMOD(b *testing.B) {
	ite := 4 // 2^n, n=2

	var d [4]int

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		val := (i % ite) + 1
		d[i%ite] %= val
	}
}

それでは、同条件でベンチマークを実行してみたいと思います。

ベンチの実行と記録
go test -failfast -benchmem -benchtime=10s -count=10 -shuffle=on -bench=. | tee "bench.txt"

今度は圧倒的な差が出ました。

name   time/op
AND-4  0.74ns ± 1%
MOD-4  11.0ns ± 2%
実行結果のログ
  • benchstat による平均や分散などの統計
平均と分散
$ benchstat bench.txt
name   time/op
AND-4  0.74ns ± 1%
MOD-4  11.0ns ± 2%

name   alloc/op
AND-4   0.00B     
MOD-4   0.00B     

name   allocs/op
AND-4    0.00     
MOD-4    0.00    
  • ベンチマーク結果(bench.txt)を go-prettybenchtimeの速い順にソートした結果
処理時間が小さい順
$ cat bench.txt | go-prettybench -sort time
-test.shuffle 1650961233291887000
goos: darwin
goarch: amd64
pkg: KEINOS/sample/and-mod-speed
cpu: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
PASS
benchmark              iter     time/iter   bytes alloc        allocs
---------              ----     ---------   -----------        ------
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.74 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.75 ns/op        0 B/op   0 allocs/op
BenchmarkAND-4   1000000000    0.77 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.92 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.93 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.93 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.94 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.95 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   10.96 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   11.03 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   11.04 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   11.17 ns/op        0 B/op   0 allocs/op
BenchmarkMOD-4   1000000000   11.31 ns/op        0 B/op   0 allocs/op
ok  	KEINOS/sample/and-mod-speed	129.727s
  • ベンチマークのログ
./bench.txtの内容
$ cat ./bench.txt
-test.shuffle 1650961233291887000
goos: darwin
goarch: amd64
pkg: KEINOS/sample/and-mod-speed
cpu: Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
BenchmarkAND-4   	1000000000	         0.7719 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7443 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7390 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7386 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7394 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7412 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7402 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7376 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7460 ns/op	       0 B/op	       0 allocs/op
BenchmarkAND-4   	1000000000	         0.7419 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        11.04 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        11.31 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.94 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.95 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.92 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.93 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        11.17 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.93 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        11.03 ns/op	       0 B/op	       0 allocs/op
BenchmarkMOD-4   	1000000000	        10.96 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	KEINOS/sample/and-mod-speed	129.727s

これは、ベンチ中、見ていても明らかに違いがわかりました。(0.74 - 11.0) / 11.0 * 100 = -93.27 とすると、AND の方が MOD の 93% も速い計算になります。

結論

Wikipedia にあった通り、やはり AND の方が MOD より効率がいいようです。特に、値の書き換えなどが発生する場合は顕著に差が出ました。

機械学習や画像処理などで、n バイトデータをゴニョゴニョする必要がある場合で、AND でも同じことができるなら、そうすることにしました。まだまだ先は長いけど。

Register as a new user and use Qiita more conveniently

  1. You can follow users and tags
  2. you can stock useful information
  3. You can make editorial suggestions for articles
What you can do with signing up
1
Help us understand the problem. What are the problem?