オーディオアプリケーションの最適化の発表資料

optimization_test.cpp

// Boost.Timerを使用しているので、Boost.SystemとBoost.Timerのライブラリをリンク時に指定すること。
// ex) clang++ -std=c++14 optimization_test.cpp -O3 -lboost_system-mt -lboost_timer-mt
// 出来上がったバイナリを実行する時に、関数名をそのまま引数に渡して呼び出すと、テスト用の関数が実行される
// ex) ./a.out false_sharing_test

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <memory>
#include <thread>
#include <sstream>
#include <atomic>
#include <boost/timer/timer.hpp>

using namespace std;

template<class T>
struct array2d {
    array2d(int x, int y) : data_(x, std::vector<T>(y)) {}
    
    std::vector<T> & operator[](int x) { return data_[x]; }
    
private:
    std::vector<std::vector<T>> data_;
};

template<class T>
struct array3d {
    array3d(int x, int y, int z) : data_(x, array2d<T>(y, z)) {}
    
    array2d<T> & operator[](int x) { return data_[x]; }
    
private:
    std::vector<array2d<T>> data_;
};

void access_order_test();
void use_loop_blocking_test();
void use_loop_blocking_test_for_sample_interleaving();
void cache_thrashing_test();
void false_sharing_test();
void fast_abs_test();

int main(int argc, char **argv)
{
    if(argc != 2) { return 0; }
    
    auto test_case_name = std::string(argv[1]);
    if(test_case_name == "use_loop_blocking_test") {
        use_loop_blocking_test();
    } else if(test_case_name == "use_loop_blocking_test_for_sample_interleaving") {
        use_loop_blocking_test_for_sample_interleaving();
    } else if(test_case_name == "access_order_test") {
        access_order_test();
    } else if(test_case_name == "cache_thrashing_test") {
        cache_thrashing_test();
    } else if(test_case_name == "false_sharing_test") {
        false_sharing_test();
    } else if(test_case_name == "fast_abs_test") {
        fast_abs_test();
    }
}

// メモリアクセスは、飛び飛びにアクセスするよりも、
// 連続した領域に順番にアクセスしていくほうが速いというのを検証するテスト
void access_order_test()
{
    // http://cocodrips.hateblo.jp/entry/2014/01/26/134501 を改変
    
    int const kSize = 500;
    array3d<int> arr(kSize, kSize, kSize);
    
    int sum = 0;
    std::cout << "Preferable Order" << std::endl;
    {
        sum = 0;
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < kSize; i++) {
            for (int j = 0; j < kSize; j++) {
                for (int k = 0; k < kSize; k++) {
                    arr[i][j][k] = i * j * k;
                    sum += arr[i][j][k];
                }
            }
        }
    }
    std::cout << "sum : " << sum << std::endl;
    
    std::cout << "Wrong Order" << std::endl;
    {
        sum = 0;
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < kSize; i++) {
            for (int j = 0; j < kSize; j++) {
                for (int k = 0; k < kSize; k++) {
                    arr[k][j][i] = i * j * k;
                    sum += arr[k][j][i];
                }
            }
        }
    }
    std::cout << "sum : " << sum << std::endl;
}

// ループ処理を行う際に、処理単位を分割することでキャッシュ効率を向上させる手法のテスト
// 分割しない場合と、分割する場合のパフォーマンスを計測する
void use_loop_blocking_test()
{
    int const kSize = 100;
    
    array2d<std::int64_t> a(kSize, kSize);
    array2d<std::int64_t> b(kSize, kSize);
    array2d<std::int64_t> c(kSize, kSize);
    
    int sum;
    for(int i = 0; i < kSize; ++i) {
        for(int j = 0; j < kSize; ++j) {
            b[i][j] = i + j;
            c[i][j] = i + j + 2;
        }
    }
    
    std::cout << "Don't use loop blocking" << std::endl;
    {
        sum = 0;
        for(int i = 0; i < kSize; ++i) {
            for(int j = 0; j < kSize; ++j) {
                a[i][j] = 0;
            }
        }
        
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < kSize; i++) {
            for (int j = 0; j < kSize; j++) {
                for (int k = 0; k < kSize; ++k) {
                    a[i][j] += b[i][k] * c[k][j];
                }
            }
        }
    }
    
    for(int i = 0; i < kSize; ++i) {
        for(int j = 0; j < kSize; ++j) {
            a[i][j] = 0;
        }
    }
    
    std::cout << "Use loop blocking" << std::endl;
    {
        for(int block_size = 10; block_size < 256; ++block_size) {
            std::cout << "block_size: " << block_size << std::endl;
            
            sum = 0;
            for(int i = 0; i < kSize; ++i) {
                for(int j = 0; j < kSize; ++j) {
                    a[i][j] = 0;
                }
            }
            
            {
                boost::timer::auto_cpu_timer t;
                
                for(int ib = 0; ib < kSize; ib += block_size) {
                    int const iend = std::min<int>(ib + block_size, kSize);
                    for(int jb = 0; jb < kSize; jb += block_size) {
                        int const jend = std::min<int>(jb + block_size, kSize);
                        for(int kb = 0; kb < kSize; kb += block_size) {
                            int const kend = std::min<int>(kb + block_size, kSize);
                            for (int i = 0; i < iend; i++) {
                                for (int j = 0; j < jend; j++) {
                                    for (int k = 0; k < kend; ++k) {
                                        a[i][j] += b[i][k] * c[k][j];
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

// wavファイルのデータ形式のように、1サンプルデータをチャンネル数で並べ、それをサンプル時間分並べたデータ構造と、
// プログラム上で扱いやすいような、チャンネル数の配列の中に、それぞれサンプル時間分のサンプルが並ぶデータ構造では、
// メモリアクセスする順番がことなるため、どちらで連続的に処理を行うと、もう一方は常にキャッシュ効率が悪くなってしまう
// そこで処理する単位を分割し、どちらもキャッシュ効率を高めるようにすると、パフォーマンスが向上すると考えられる。
// それを検証するテスト
void use_loop_blocking_test_for_sample_interleaving()
{
    int const kSize = 96000 * 60 * 5;
    array2d<std::int16_t> d(kSize, 2); // wavfile
    array2d<float> e(2, kSize); // プログラム上で持ちたい形式
    int sum;
    
    std::cout << "Don't use loop blocking" << std::endl;
    {
        sum = 0;
        
        boost::timer::auto_cpu_timer t;
        for (int smp = 0; smp < kSize; smp++) {
            for (int ch = 0; ch < 2; ch++) {
                e[ch][smp] = d[smp][ch] / 32768.0;
                sum += e[ch][smp];
            }
        }
    }
    
    std::cout << "Estimate preferable blocking size for sample interleaving." << std::endl;
    {
        for(int block_size = 1; block_size < 128; ++block_size) {
            std::cout << "block_size: " << block_size << std::endl;
            sum = 0;
            {
                boost::timer::auto_cpu_timer t;
                for (int smpb = 0; smpb < kSize; smpb += block_size) {
                    int smpend = std::min<int>(smpb + block_size, kSize);
                    for(int smp = smpb; smp < smpend; ++smp) {
                        for(int ch = 0; ch < 2; ++ch) {
                            e[ch][smp] = d[smp][ch] / 32768.0;
                            sum += e[ch][smp];
                        }
                    }
                }
            }
        }
    }
}

namespace cache_thrashing_test_data {
    int const kSize = 2048;
    int const kWay = 16;
    
    struct MayOccur {
        double a[kSize];
        double b[kSize];
    } mo[kWay];
    
    struct MayNotOccur
    {
        double c[kSize];
        double dummy[64];
        double d[kSize];
    } mno[kWay];
}

// CPUがデータをキャッシュする単位は、バイト単位ではなく、キャッシュラインと呼ばれる一定の大きさのデータのかたまりである
// CPUが、メモリ上のある変数Xの値を読み込み(1)、そこから2のべき乗だけ離れた位置にある変数Yに値を書き込む(2)と以下のような問題が起きる
// (1)のタイミングでXを含むメモリ領域がキャッシュに載せられたあと、
// (2)のタイミングでYを含むメモリ領域がキャッシュに載せられようとするが、
// 2のべき乗だけ離れた位置にあるメモリは、キャッシュラインの位置がかぶってしまう（セットアソシエイティブ方式）
// そのためCPUはXを含むメモリ領域をキャッシュから退避し、Yを新たにキャッシュに載せる
// その後また(1)が発生すると、CPUはYを含むキャッシュを退避し、Xを新たにキャッシュに載せる
// このような状態が続くと、毎回キャッシュが無効化され、キャッシュ効率が低下してしまう。
// これをキャッシュスラッシングと呼ぶ
// これにはCPU側で対策がされていて、キャッシュラインのテーブルを複数持つようにし、
// XとYのアドレスからキャッシュラインの位置を計算したときに同じ位置になってしまっても、
// それぞれを別のテーブルに割り当てるようにし、お互いのキャッシュラインが無効化されることがないようになっている
//（Nウェイセットアソシエイティブ方式）
// ただし、このテーブル数を超えたサイズのキャッシュがキャッシュラインに載せられようとしたときには、いずれかのキャッシュラインが無効化されるので、キャッシュ効率が低下する可能性がある。
// これにプログラム側で対処するには、大量にアクセスするいくつかのメモリ領域が、それぞれ2のべき乗倍だけ離れた位置にならないようにする。
// このプログラムでは、変数c, dの間にダミーの変数を設けて、アクセスする位置の差が2のべき乗倍にならないようにしている
void cache_thrashing_test()
{
    using namespace cache_thrashing_test_data;
    
    int const kRepeat = 100000;
    int sum = 0;
    
    std::cout << "Cache thrashing may not occur" << std::endl;
    {
        sum = 0;
        boost::timer::auto_cpu_timer t;
        for(int rep = 0; rep < kRepeat; ++rep) {
            for(int i = 0; i < kSize; ++i) {
                for(int w = 0; w < kWay; ++w) {
                    mno[w].c[i] += mno[w].d[i];
                    sum += mno[w].c[i];
                }
            }
        }
    }
    
    std::cout << "Cache thrashing may occur" << std::endl;
    {
        sum = 0;
        boost::timer::auto_cpu_timer t;
        for(int rep = 0; rep < kRepeat; ++rep) {
            for(int i = 0; i < kSize; ++i) {
                for(int w = 0; w < kWay; ++w) {
                    mo[w].a[i] += mo[w].b[i];
                    sum += mo[w].a[i];
                }
            }
        }
    }
}

namespace false_sharing_test_data
{
    int const kNumThreads = 16;
    int const kSkip = 16;
    
    struct FalseSharingMayNotOccur
    {
        int a_[kNumThreads * kSkip];
    } mno;
    
    struct FalseSharingMayOccur
    {
        int a_[kNumThreads];
    } mo;
}

// あるCPUコア1が変数Xにアクセスし(1)、その値を変更すると(2)、
// (1)のタイミングでXを含む周辺がコア1のキャッシュラインに載せられ、
// (2)のタイミングで、そのキャッシュラインのデータが変更される。
// このとき、他のコア2もXの近傍にある別の変数Yにアクセスしていたとしよう。
// そのとき、Yの周辺（そしてXも含まれる、(1)と同じメモリ領域）がコア2のキャッシュラインに載せられていることになる。
// (2)のときに、コア1でキャッシュライン内のデータが変更されると、
// CPUは他のコアに対してそのキャッシュラインが変更されたことを通知し、コア2のキャッシュラインは無効化される。
// そのため、コア2でYに再びアクセスしようとすると、Yの周辺を再びコア2のキャッシュラインに載せなければならなくなる。
// 逆にコア2でYの値を変更すると、コア1のキャッシュラインが無効化される
// これを繰り返すと、スレッド間でお互いにキャッシュラインを無効化し合うことになり、キャッシュ効率が低下してしまう。
// この問題を、フォールスシェアリング（偽の共有）と呼ぶ。
// この問題の面白い所は、ソース上ではコア1とコア2は別の位置にあるオブジェクトへアクセスしているはずなのに、それらが互いに影響を与えてしまうところである。
// この問題を防ぐには、コア1とコア2でアクセスするそれぞれのデータが、キャッシュラインのサイズより遠くなるようにする
// このコードではkSkipという変数でそれぞれのコアがアクセスするオブジェクトの位置を離すことで、フォールスシェアリングを回避している
void false_sharing_test()
{
    using namespace false_sharing_test_data;
    
    int const kRepeat = 4000;
    int sum1 = 0;
    int sum2 = 0;
    
    std::cout << "False sharing may not occur" << std::endl;
    {
        std::vector<std::thread> ths(kNumThreads);
        
        std::mutex mtx;
        double wall_time_sum = 0;
        double user_time_sum = 0;
        double sys_time_sum = 0;
        
        for(int n = 0; n < kNumThreads; ++n) {
            ths[n] = std::thread([&, n] {
                boost::timer::cpu_timer t;
                
                for(int i = 0; i < kRepeat; ++i) {
                    for(int j = 0; j < kRepeat; ++j) {
                        mno.a_[n * kSkip] += (i * j);
                        sum1 += mno.a_[n * kSkip];
                    }
                }
                
                auto e = t.elapsed();
                
                std::lock_guard<std::mutex> lock(mtx);
                wall_time_sum += e.wall / (1000 * 1000 * 1000.0);
                user_time_sum += e.user / (1000 * 1000 * 1000.0);
                sys_time_sum += e.system / (1000 * 1000 * 1000.0);
            });
        }
        
        for(int n = 0; n < kNumThreads; ++n) {
            ths[n].join();
        }
        
        std::cout
            << setw(2) << std::fixed << std::setprecision(6) << wall_time_sum / kNumThreads << "s wall, "
            << setw(2) << std::fixed << std::setprecision(6) << user_time_sum / kNumThreads << "s user + "
            << setw(2) << std::fixed << std::setprecision(6) << sys_time_sum / kNumThreads << "s sytem = "
            << setw(2) << std::fixed << std::setprecision(6) << (user_time_sum + sys_time_sum) / kNumThreads << "s CPU"
            << std::endl;
    }
    
    std::cout << "False sharing may occur" << std::endl;
    {
        std::vector<std::thread> ths(kNumThreads);
        
        std::mutex mtx;
        double wall_time_sum = 0;
        double user_time_sum = 0;
        double sys_time_sum = 0;
        
        for(int n = 0; n < kNumThreads; ++n) {
            ths[n] = std::thread([&, n] {
                boost::timer::cpu_timer t;
                
                for(int i = 0; i < kRepeat; ++i) {
                    for(int j = 0; j < kRepeat; ++j) {
                        mo.a_[n] += (i * j);
                        sum1 += mo.a_[n];
                    }
                }
                
                auto e = t.elapsed();
                
                std::lock_guard<std::mutex> lock(mtx);
                wall_time_sum += e.wall / (1000 * 1000 * 1000.0);
                user_time_sum += e.user / (1000 * 1000 * 1000.0);
                sys_time_sum += e.system / (1000 * 1000 * 1000.0);
            });
        }
        
        for(int n = 0; n < kNumThreads; ++n) {
            ths[n].join();
        }
        
        std::cout
            << setw(2) << std::fixed << std::setprecision(6) << wall_time_sum / kNumThreads << "s wall, "
            << setw(2) << std::fixed << std::setprecision(6) << user_time_sum / kNumThreads << "s user + "
            << setw(2) << std::fixed << std::setprecision(6) << sys_time_sum / kNumThreads << "s system = "
            << setw(2) << std::fixed << std::setprecision(6) << (user_time_sum + sys_time_sum) / kNumThreads << "s CPU"
            << std::endl;
    }
}

int abs_using_if(int x)
{
    return x >= 0 ? x : -x;
};

int abs_using_bitop(int x)
{
    std::uint32_t M = (x >> 31);
    return (x ^ M) - M;
};

// 発表資料のおまけの内容。キャッシュ関連の話とは無関係
//
// abs()を実装するとき、条件分岐を伴う、abs_using_if()よりも、ビット操作だけで完結するabs_using_bitopのほうが速いように思われる。
// しかし実際には、どちらもさほど変わらない。
// Intelの最近の命令セットには、フラグの状態に合わせてmovを行う命令があるので、条件分岐 + movを1命令で行える。
// したがって、最適化によってどちらも同じような性能になる
void fast_abs_test()
{
    int count = 0;
    {
        count = 0;
        {
            boost::timer::auto_cpu_timer t;
            for(int i = 0; i < 1000 * 1000 * 100; ++i) {
                auto tmp = -(i & 1) * i + ((i+1) & 1) * i;
                count += (count & i) + abs_using_if(tmp);
            }
        }
        std::cout << count << std::endl;
    }
    {
        count = 0;
        {
            boost::timer::auto_cpu_timer t;
            for(int i = 0; i < 1000 * 1000 * 100; ++i) {
                auto tmp = -(i & 1) * i + ((i+1) & 1) * i;
                count += (count & i) + abs_using_bitop(tmp);
            }
        }
        std::cout << count << std::endl;
    }
}