MSVC STL の最近の改良
この記事は C++ Advent Calendar 2022 23 日目の参加記事です。
Microsoft Visual Studio の C++ 標準ライブラリ (MSVC STL) は、2019 年 9 月にオープンソース化され、GitHub 上で更新の様子を追跡できるようになりました。
リポジトリの最新コードは、リリース版の Visual Studio よりも数ヶ月ほど先行している点に注意が必要です。更新が反映されるタイミングは Changelog で確認できます。
本記事では、上記リポジトリで確認できる、最近実装された興味深い改良を 2 つ紹介します。
1. アルゴリズム関数のベクトル演算対応
範囲に対して検索の操作を行うアルゴリズム関数の一部が、適切な条件を満たす場合に、ベクトル演算 (SIMD) を用いて実行されるようになりました。
記事執筆時点での最新の MSVC STL では、std::find() は内部で次のような関数を呼びます。
メモリ非連続な範囲（例えば std::deque）や非 Trivial な要素型 (例えば要素が std::string）にも対応する汎用的な find() の実装は下記の部分です。
検索する範囲がメモリ連続であり、なおかつ要素が 1 バイトである場合は、副作用なしで単純な memchr() に置き換えることができ、コンパイラによる効率的なコードの生成を助けることができます。下記の部分が、その考えに基づいて以前から実装されていたコードです。
しかし、1 バイトの要素を検索するような機会は多くなく、この最適化が役に立つケースは限定的でした。VS 2022 17.3 では、1, 2, 4, 8 バイトの整数型、ポインタ型、std::byte を検索する際に、SSE2 または AVX2 命令を用いる実装が新たに追加されました。
該当箇所は次の部分です。
__std_find_trivial() は最終的に次のような関数を呼び出します。
vector_algorithms.cpp 全体を読むと、_mm_cmpeq_epi32() や _mm256_cmpeq_epi32() のような SSE2 / AVX2 の整数比較命令が呼ばれることがわかります。
ベンチマーク
std::ranges::find() によって配列 T[8192] から要素を検索する処理 1,000,000 回の所要時間を計測した ベンチマーク によると、ベクトル演算対応によって 2～9 倍の実行速度向上 が報告されています。
| 配列 | 従来 | SIMD 実装 | 速度向上 |
|---|---|---|---|
std::uint8_t[8192] |
0.123933s | 0.0566276s | 2.19 倍 |
std::uint16_t[8192] |
0.911876s | 0.0979886s | 9.31 倍 |
std::uint32_t[8192] |
0.917381s | 0.185901s | 4.93 倍 |
std::uint64_t[8192] |
0.975016s | 0.357151s | 2.73 倍 |
ベクトル演算に対応した関数
std::find() 以外の関数についてもベクトル演算対応が進められています。下記に現時点での状況をまとめます。
| 関数 | 対応バージョン |
|---|---|
std::swap_ranges() |
VS 2022 以前 |
std::ranges::swap_ranges() |
VS 2022 以前 |
std::array::swap() |
VS 2022 以前 |
std::reverse() |
VS 2022 以前 |
std::ranges::reverse() |
VS 2022 以前 |
std::reverse_copy() |
VS 2022 以前 |
std::ranges::reverse_copy() |
VS 2022 以前 |
std::find() |
VS 2022 17.3 |
std::ranges::find() |
VS 2022 17.3 |
std::count() |
VS 2022 17.3 |
std::ranges::count() |
VS 2022 17.3 |
std::min_element() |
VS 2022 17.4 |
std::ranges::min_element() |
VS 2022 17.4 |
std::max_element() |
VS 2022 17.4 |
std::ranges::max_element() |
VS 2022 17.4 |
std::minmax_element() |
VS 2022 17.4 |
std::ranges::minmax_element() |
VS 2022 17.4 |
リポジトリの Issues から、次のような関数についてもベクトル演算対応が検討されていることがわかります。
| 関数 | 関連 Issue |
|---|---|
std::search() |
#2453 |
std::ranges::search() |
#2453 |
std::ranges::min() |
#2803 |
std::ranges::max() |
#2803 |
std::ranges::minmax() |
#2803 |
std::find_last() |
#3274 |
std::ranges::find_last() |
#3274 |
2. 乱数の一様分布アルゴリズムの高速化
乱数生成器から、一定の範囲に一様分布する整数を得るときには、C++11 で導入された std::uniform_int_distribution を使います。その内部で使えるアルゴリズムについて、2019 年に新しい高速な手法が発表されました。
基本的には除算の削減が高速化に貢献しています。次の記事に概要がまとまっています。
この改良アルゴリズムは、2020 年に libstdc++ にマージ され、約 2 倍の速度向上が報告されました。
MSVC STL においても、そのアルゴリズムを採用することになり、VS 2022 17.5 でマージされました。下記の Conversation では、およそ 1～2 倍前後の高速化と、とくに x86 では std::mt19937, x64 では std::mt19937_64 のようにターゲットプラットフォームに合った乱数生成器と組み合わせたときに効果が顕著であることが報告されています。
アルゴリズム変更に伴う注意
このアルゴリズムの変更に伴い、MSVC STL の std::uniform_int_distribution は、過去バージョンとは異なる結果のパターンを出力するようになります。
#include <iostream>
#include <random>
int main()
{
std::mt19937 rng;
std::uniform_int_distribution<int> ud{ 0, 100 };
for (int i = 0; i < 5; ++i)
{
std::cout << ud(rng) << '\n';
}
}
VS 2022 17.4 まで
53
20
50
22
63
VS 2022 17.5 以降
82
13
91
84
12
C++ 規格は uniform_int_distribution のアルゴリズムを規定していないため、今後もこのような変更が起こりえます。互換性が重要な場合は自前の実装を用意するとよいでしょう（例えば Siv3D は abseil の uniform_int_distribution クラスを利用しているため、この変更の影響を受けません）。
おわりに
今回紹介した例のように、標準ライブラリの関数は高度な最適化が行われ、自前でループを書くよりも数倍高速に実行されるケースがあります。こうした標準ライブラリ実装の改良の恩恵を受けられるよう、自身のコードを見直してみましょう。
本記事では、標準ライブラリ実装の高速化に注目しましたが、MSVC STL の Changelog および関連 Issues は、変更内容やその目的などが読みやすく整理されていて、C++ 規格の学習や、C++ におけるライブラリ設計の良い参考資料になります。ぜひ活用してみてください。
Discussion