目標(biāo)

Benchmarking in C++中描述了一個(gè)簡易的benchmark，將逐步分析如何實(shí)現(xiàn)該benchmark，及模板化思路。

應(yīng)用場景

衡量算法其中一種方法是BigO，以n為因子，判斷隨著數(shù)量級(jí)增大耗時(shí)增加情況，而且考慮到屏蔽一些隨機(jī)擾動(dòng)，需要進(jìn)行多次采樣比較。
譬如文中舉例比較std::vector和std::list時(shí)，進(jìn)行了10次采用，n的數(shù)量級(jí)從10的1次方直到10的5次方，輸出了2種情況下的耗時(shí)信息，再配合其可視化腳本輸出比較圖。

也就是說，這個(gè)benchmark將會(huì)支持多次采樣、多個(gè)因子、執(zhí)行多種算法測量。

最小實(shí)現(xiàn)

測量時(shí)，需要在執(zhí)行前記錄當(dāng)前時(shí)間戳，然后執(zhí)行完成后根據(jù)結(jié)束的時(shí)間戳計(jì)算出耗時(shí)。

auto start = std::chrono::high_resolution_clock::now();
//執(zhí)行函數(shù);
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start);

以上的代碼得出的duration就是毫秒量級(jí)的耗時(shí)記錄結(jié)果。

一個(gè)最小的耗時(shí)測量實(shí)現(xiàn)如下：

//invoke function and return time used
template<typename TTime = std::chrono::milliseconds>
struct measure
{
    template<typename F, typename ...Args>
    static typename TTime::rep execution(F func, Args&&... args)
    {
        auto start = std::chrono::high_resolution_clock::now();
        func(std::forward<Args>(args)...);
        auto duration = std::chrono::duration_cast<TTime>(std::chrono::high_resolution_clock::now() - start);
        return duration.count();
    }
};

其中用到了完美轉(zhuǎn)發(fā)std::forward來處理參數(shù)傳遞。

使用方法為：

auto oVal =  measure<>::execution(CommonUse<std::vector<int>>,1000);

這樣就得到了n=1000時(shí)的耗時(shí)毫秒數(shù)。

支持多種測量

當(dāng)希望支持多種測量時(shí)，就需要將測量結(jié)果存儲(chǔ)到map之中；實(shí)現(xiàn)時(shí)將其拆分為三塊：

1. 執(zhí)行函數(shù)獲取耗時(shí)
2. 耗時(shí)信息保存
3. 整合執(zhí)行和保存

執(zhí)行函數(shù)獲取耗時(shí)

struct measure
{
    //measure function implement
    template<typename F, typename TFactor>
    inline static auto duration(F&& callable, TFactor&& factor)
    {
        auto start = std::chrono::high_resolution_clock::now();
        std::forward<decltype(callable)>(callable)(std::forward<TFactor>(factor));
        return (std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start));
    }
}

保存測量結(jié)果

//save results
template<typename TFactor>
struct experiment_impl
{
    std::string _fctName;
    std::map<TFactor,std::vector<std::chrono::milliseconds>> _timings;
    experiment_impl(const std::string& factorName):_fctName(factorName){};
 
protected:
    ~experiment_impl() = default;
};

整合執(zhí)行和保存

定義了experment_model來在構(gòu)造時(shí)完成函數(shù)執(zhí)行和結(jié)果保存：

template<typename TFactor>
struct experment_model final :detail::experiment_impl<TFactor>
{
    //invoke function and save result
    template<typename F>
    experment_model(std::size_t nSample, F&& callable, const std::string& factorName, std::initializer_list<TFactor>&& factors)
        :experiment_impl<TFactor>(factorName)
    {
        for (auto&& factor:factors)
        {
            experiment_impl<TFactor>::_timings[factor].reserve(nSample);
            for (std::size_t i = 0 ; i < nSample ; i++)
            {
                experiment_impl<TFactor>::_timings[factor].push_back(measure::duration(std::forward<decltype(callable)>(callable),factor));
            }
        }
    }
 
};

封裝成benchmark來支持多次、多因子、多種測量：

template<typename TFactor>
class benchmark
{
    std::vector<std::pair<std::string,std::unique_ptr<detail::experment_model<TFactor>>>> _data;
public:
    benchmark() = default;
    benchmark(benchmark const&) = delete;
public:
    template<class F>
    void run(const std::string& name, std::size_t nSample, F&& callable,
        const std::string& factorName, std::initializer_list<TFactor>&& factors)
    {
        _data.emplace_back(name,std::make_unique<detail::experment_model<TFactor>>(nSample,
            std::forward<decltype(callable)>(callable),factorName,
            std::forward<std::initializer_list<TFactor>&&>(factors)));
    }
}

使用方法

bmk::benchmark<std::size_t> bm;
bm.run("vector",10, CommonUse<std::vector<int>>,"number of elements",{10,100,1000,10000});
bm.run("list",10, CommonUse<std::list<int>>,"number of elements",{10,100,1000,10000});

支持無因子測量

那么當(dāng)要測試的是普通函數(shù)時(shí)，并沒有因子輸入，只是執(zhí)行了多次，那么就需要做出調(diào)整：

1. 執(zhí)行無因子函數(shù)獲取耗時(shí)
2. 耗時(shí)信息保存
3. 提供無因子版experiment_model
4. 提供無因子版benchmark.run

執(zhí)行無因子函數(shù)

//measure function void version
template<typename F>
inline static auto duration(F&& callable)
{
    auto start = std::chrono::high_resolution_clock::now();
    std::forward<decltype(callable)>(callable)();
    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start);
}

調(diào)整的方式為移除測量時(shí)的因子參數(shù)輸入。

保存測量結(jié)果

測量結(jié)果只是一個(gè)vector<milliseconds>，提供experment_impl的偏特化版本:

//save result void version
template<>
struct experiment_impl<void>
{
    std::vector<std::chrono::milliseconds> _timings;
    experiment_impl(std::size_t nSample):_timings(nSample){};
protected:
    ~experiment_impl() = default;
};

提供無因子版experiment_model

//invoke function and save result [void version]
template<typename F>
experment_model(std::size_t nSample, F&& callable)
    :experiment_impl<void>(nSample)
{
    for (std::size_t i = 0; i < nSample; i++)
    {
        experiment_impl<TFactor>::_timings.push_back(measure::duration(std::forward<decltype(callable)>(callable)));
    }
}

提供無因子版benchmark.run

由于benchmark需要支持無因子，而其存儲(chǔ)的內(nèi)容為experiment_model，那么需要提供基類，保證experiment_model在兩種情況下都適用：

struct experiment
{
    virtual ~experiment() {};
};
template<typename TFactor = void>
struct experment_model final :detail::experiment,detail::experiment_impl<TFactor>
{
  ......
};

同樣,benchmark需要移除模板參數(shù)TFactor

class benchmark
{
    std::vector<std::pair<std::string,std::unique_ptr<detail::experiment>>> _data;
   ......
}

然后是無因子版的run

template<class F>
void run(const std::string& name, std::size_t nSample, F&& callable)
{
    _data.emplace_back(name, std::make_unique<detail::experment_model<>>(nSample,
        std::forward<decltype(callable)>(callable)));
}

支持多分辨率測量

之前一直采用的是毫秒，在一些情況下函數(shù)執(zhí)行很快，需要采用微秒、納秒級(jí)別，那么就需要把之前寫死的std::chrono::milliseconds替換成模板參數(shù)，同步修改所有位置：

template<typename TTime ,typename TFactor>
struct experiment_impl
{
   ......
}
   ......
template<typename TTime>
struct measure
{
   ......
}
   ......
template<typename TTime,typename TFactor = void>
struct experment_model final :detail::experiment,detail::experiment_impl<TTime,TFactor>
{
   ......
}
   ......
template<typename TTime>
class benchmark
{
   ......
}

支持多種clock

在之前都采用的是std::chrono::high_resolution_clock，但是對(duì)MSVC2013來講存在問題:
Time measurements with High_resolution_clock not working as intended
這個(gè)版本可以采用std::chrono::steady_clock，那么實(shí)現(xiàn)多種clock即可，與多分辨率的方式一致，提供模板參數(shù)TClock替換std::chrono::high_resolution_clock,并將默認(rèn)參數(shù)設(shè)置為std::chrono::high_resolution_clock。

其它

• 輸出結(jié)果
• tic/toc