CPUの分岐予測の性能に対する影響を軽く試してみた

YouTubeで「本処理に関係ないように見える余計のソート処理を入れてみたらプログラムが逆に早くなったぞ！」という内容の動画を観て、実際に自分のマシンで検証してみました。

タスク設定と検証環境

今回は例の動画がやっていることをそのまま踏襲。まとめたら簡単です：

1. 長さ32768の配列を生成、0から255までの乱数で埋める
2. 配列にソートをかける（ここはコメントアウトで実行するかしないかを制御）
3. 処理の開始時間を記録
4. 配列を走査し、128より大きい数値を足していく、これを十万回やる
5. 処理の終了時間を計算、出力

以上です、簡単でしょう？プログラムの目的は乱数配列の中の128より大きい数値の合算を求めるのですが、ソートはもともと本命のロジックとはなんの関係もありません、入れられると無駄の処理が発生し、プログラムの実行時間が長くなるじゃないか？というのは一般的な考えです。ですが、場合によってはそれが違うんですよね。。。

実行環境はMac mini 2018（i7 8700B＋DDR4 2667MHz 8GBx2）、OSはmacOS Ventura 13.2.1です。今回はPython 3.11.2、C++(Clang++ 14.0.0)、Go 1.20.2の3つを検証していきたいと思います。

C++

例の動画はC++を用いて説明しています、動画内のプログラムをそのまま写させていただきました。ソートなしバージョンです。

test.cpp

#include <algorithm>
#include <ctime>
#include <iostream>

int main(){
    const unsigned arraySize = 32768;
    int data[arraySize];

    for(unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;
    
    // std::sort(data, data + arraySize);

    clock_t start = clock();
    long long sum = 0;

    for(unsigned i = 0; i < 100000; ++i){
        for(unsigned c = 0; c < arraySize; ++c){
            if(data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime <<std::endl;
    std::cout << "sum = " << sum << std::endl;
}

Python

上のC++プログラムの流れを沿って、Pythonに書き換えました。Pythonの実行時間は予想よりだいぶ長いので、ループの回数を10万回から1万回に減らします。今回の主旨はプログラミング言語間の性能比較ではないので大丈夫だと思います。

test.py

import random
import time

array_size = 32768
data = []
for i in range(array_size):
    data.append(random.randint(0, 256))

# data.sort()

start = time.time()

sum = 0

for i in range(10000):
    for c in range(array_size):
        if data[c] >= 128:
            sum += data[c]

elapsed_time = time.time() - start
print(elapsed_time)
print(sum)

Go

そしてC++からGoにも書き換えます、ここはちゃんと10万回ループさせます。（Go触ったことほぼないので、ChatGPTが書いていただきました）。Goではそのまま実行とコンパイルしてから実行の2通りがあります、今回はその両方計測します。

test.go

package main

import (
	"fmt"
	"math/rand"
	// "sort"
	"time"
)

func main() {
	const arraySize = 32768
	data := make([]int, arraySize)

	rand.Seed(time.Now().UnixNano())

	for c := 0; c < arraySize; c++ {
		data[c] = rand.Intn(256)
	}

	// sort.Ints(data)

	start := time.Now()
	var sum int64

	for i := 0; i < 100000; i++ {
		for c := 0; c < arraySize; c++ {
			if data[c] >= 128 {
				sum += int64(data[c])
			}
		}
	}

	elapsedTime := time.Since(start)

	fmt.Println(elapsedTime)
	fmt.Println("sum =", sum)
}

計測結果

全て三回計測＋平均、単位は秒です。

項目	結果1	結果2	結果3	結果平均
C++ソートなし	16.0401	16.0675	16.0602	16.0559
C++ソートあり	5.13379	5.11943	5.13653	5.12992
Pythonソートなし	37.4564	35.5442	35.3725	36.1244
Pythonソートあり	33.5054	32.8808	34.0636	33.4833
Goソートなしコンパイルなし	10.4625	10.4259	10.4261	10.4382
Goソートありコンパイルなし	1.67959	1.65897	1.67348	1.67068
Goソートなしコンパイルあり	10.3688	10.3756	10.3628	10.3691
Goソートありコンパイルあり	1.66802	1.67303	1.66343	1.66816

ソートを入れるとこで得られた性能改善効果はGo(6.23x↑)>C++(3.13x↑)>Python(1.08x↑)
プログラム自体の実行速度はGo>C++>>Python、Python3.11は大幅の速度改善を行なったものの、1/10の処理回数でこの時間、GoとC++にはまだ全然届かないですね。
そして意外とGoのコンパイル有無はここではあまり違いを見せていません、0.1秒くらいの時間短縮でした
コメントのほうに指摘をいただいて、Goのgo runコマンドはビルドして実行する仕様なので、「コンパイルあり」のほうとやっていることはあまり変わらない

軽く考察

まずソートによる性能向上はCPUの分岐予測が大きく関わっていることは間違いないと考えています。ソートにより配列の前半は全部128より小さい数値、後半は全部128より大きい数値になっています。言い換えると前半の処理は全部if文の判定はfalseで後半は全部trueになります。こうすることによってCPUの分岐予測機能はとても当たりやすくなり、CPUのパイプラインを効率的に利用できます。

そして、現代CPUのこういう特性をいかに活用できているかは異なるプログラム言語の間では大きく違います。最初にC++とPythonの結果だけを見た時に「これはコンパイラが通っているかどうかが鍵となるか？」と予想し、それを検証するためにコンパイルありでもなしでも実行できるGoを検証に入れましたが、Goの結果を見るとそんなことではないようです、結局言語の設計なのかな？

補足

コメントのほうに「参考にしたYouTube動画のリンクを貼るべき」という意見がありましたので：
https://www.youtube.com/watch?v=wHWjPbD0ZaE
台湾の学生向けコンピューティングワークショップの一つのセッションです。日本語でも英語でもないので、この記事読んでいる人は見ないだろと思って伏せました。