型特性ライブラリには、正確性と最適化という 2 つの主要な目標があります。今日は最適化について書きます。
この投稿は、型特性ライブラリに関するミニシリーズの最後の投稿です。私はすでに次の投稿を書いています:
- 型特性ライブラリ:型チェック
- 型特性ライブラリ:型の比較
- 型特性ライブラリ:
std::is_base_of - 型特性ライブラリ:正しさ
C++ での最適化について書き始める前に、短い逸話をお話ししたいと思います。私はクラスで生徒たちと次のような会話をすることがよくあります:
- 私:C++ に機能 ABC があるのはなぜですか?
- 生徒:わかりません
- 私:答えがない場合は、パフォーマンスとだけ言ってください。これは常に C++ で機能します。
そこで、最適化の観点から型特性ライブラリについて書きましょう。
最適化
この考え方は非常に単純で、標準テンプレート ライブラリ (STL) で使用されています。範囲の要素が十分に単純な場合、STL のアルゴリズムは std::copy, std::fill, のようになります または std::equal メモリに直接適用されます。 std::copy を使用して各要素を 1 つずつコピーする代わりに、すべてが 1 つの大きなステップで行われます。内部的には、C 関数は memcmp, memset, のように機能します。 memcpy 、または memmove 使用されています。 memcpy のわずかな違い と memmove それは memmove です オーバーラップするメモリ領域を処理できます。
アルゴリズム std::copy, std::fill, の実装 または std::equal シンプルな戦略を使用します。 std::copy ラッパーのようなものです。このラッパーは、要素が十分に単純かどうかをチェックします。その場合、ラッパーは作業を最適化されたコピー機能に委任します。そうでない場合は、保守的なコピー アルゴリズムが使用されます。この保守的なものは、各要素を次々にコピーします。正しい決定を下すために、型特性ライブラリの関数が頻繁に使用されます。
図は一般的な戦略を示しています:
それが理論でしたが、ここに実践があります。 std::fill が使用する戦略はどれですか ?
std::fill
std::fill は、範囲内の各要素に値を割り当てます。このリストは、std::fill の GCC にヒントを得た実装を示しています。
// fillGCC.cpp
#include <cstring>
#include <chrono>
#include <iostream>
#include <type_traits>
namespace my{
template <typename I, typename T, bool b>
void fill_impl(I first, I last, const T& val, const std::integral_constant<bool, b>&){
while(first != last){
*first = val;
++first;
}
}
template <typename T> // (2)
void fill_impl(T* first, T* last, const T& val, const std::true_type&){
std::memset(first, val, last-first);
}
template <class I, class T>
inline void fill(I first, I last, const T& val){
typedef std::integral_constant<bool,std::is_trivially_copy_assignable<T>::value
&& (sizeof(T) == 1)> boolType; // (1)
fill_impl(first, last, val, boolType());
}
}
const int arraySize = 100'000'000;
char charArray1[arraySize]= {0,};
char charArray2[arraySize]= {0,};
int main(){
std::cout << '\n';
auto begin = std::chrono::steady_clock::now();
my::fill(charArray1, charArray1 + arraySize,1);
auto last = std::chrono::steady_clock::now() - begin;
std::cout << "charArray1: " << std::chrono::duration<double>(last).count() << " seconds\n";
begin = std::chrono::steady_clock::now();
my::fill(charArray2, charArray2 + arraySize, static_cast<char>(1));
last= std::chrono::steady_clock::now() - begin;
std::cout << "charArray2: " << std::chrono::duration<double>(last).count() << " seconds\n";
std::cout << '\n';
}
コード例に戻ります。行 (1) の式 boolType() が true の場合、行 2 の最適化されたバージョンの my::fill_impl が使用されます。この亜種は、1 億エントリのメモリ全体を値 1 で埋めます。sizeof(char) は 1 です。
プログラムのパフォーマンスについて教えてください。最適化されていないパフォーマンスを測定するために、プログラムを最適化せずにコンパイルしました。
行 (2) の最適化されたバージョンは、約 10 倍高速です。興味深いことに、完全な最適化を有効にすると、コンパイラは両方のバリアントに対して同じコードを生成するため、両方のバリアントが同等に高速になります。また、汎用バージョン ((3) 行目) では memset を使用しています。 :fillGCC.cpp Compiler Explorer で最大限の最適化を行います。
std::fill, の古い GCC 実装を提示しました 新しいものは読みにくいからです。 GCC 6 実装の重要な部分は次のとおりです。
std::fill
// fill
// Specialization: for char types we can use memset.
template<typename _Tp>
inline typename
__gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type // (1)
__fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
{
const _Tp __tmp = __c;
if (const size_t __len = __last - __first)
__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
}
GCC 6 実装は SFINAE を使用します。関数テンプレート __fill_a の完全な特殊化 __builtin_memset. を使用 この実装の重要な部分は行 (1):__gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type. です。 この式を人間が読める形式に書き直して、正式な名前を使用しましょう。
std::enable_if<std::is_byte<Tp>::value, void>::type
式は、テンプレート パラメーター TP がバイト std::is_byte<T>::value であるかどうかを最初にチェックします。 .この式が true と評価される場合 のおかげで 型特性ライブラリ SFINAE の std::enable_if が作動します。SFINAE は Substitution Failure Is Not An Error の略で、関数テンプレートのオーバーロード解決中に適用されます。テンプレート パラメーターの置換が失敗した場合、特殊化はオーバーロード セットから破棄されますが、この失敗によってコンパイラ エラーは発生しません。これは、この具体的なケースを意味します:条件 std::is_byte<T>::value の場合 false を返し、この完全な特殊化は破棄され、別のバージョンの __fill_a
次は?
まず、2 週間のクリスマス休暇を作ります .次回は 2022 年 1 月 10 日に公開予定です。constexpr について書きます。 テンプレートと多くの共通点があり、C++20 でより強力になるためです。
第二に、長い間、C++ の専門的な教育を改善したいと考えていました。そのため、C++ のメンタリング プログラムを開始する予定です。まもなく、私のアイデアの詳細を公開します。