我想索引std::string
生命周期为整个程序的子字符串,并int
使用一个好的旧方法将每个子字符串与关联起来std::map
。子字符串由空格分隔' '
。我生成了字符串并将其存储到文件中,使用以下 python 代码
import random
all_chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 123456789!\"·$%&/()=?¿¡'|@#¬"
for i in range(0, 50000000):
r = int(random.random() * len(all_chars))
print(all_chars[r], end = '')
std::string
所以,我想比较一下使用 a 分割 astd::string
和std::string_view
通过这两个(简单)函数存储子字符串的效率。
[[nodiscard]]
std::vector<std::string_view> split_sv(const std::string& s, char c) noexcept {
std::vector<std::string_view> res;
std::size_t b = 0;
std::size_t p = s.find(c);
while (p != std::string_view::npos) {
res.push_back( std::string_view{&s[b], p - b} );
b = p + 1;
p = s.find(c, b);
}
return res;
}
[[nodiscard]]
std::vector<std::string> split_s(const std::string& s, char c) noexcept {
std::vector<std::string> res;
std::size_t b = 0;
std::size_t p = s.find(c);
while (p != std::string::npos) {
res.push_back( s.substr(b, i - b) );
b = p + 1;
p = s.find(c, b);
}
return res;
}
分割算法显然比更快(正如预期的std::string_view
那样std::string
):
std::string_view 28.6 ms
std::string 107.6 ms
(旗帜-std=c++20 -O3
,gcc 11.4.0
)
但是,将这些子字符串存储到 中比中std::map
要慢。std::string_view
std::string
{
const std::vector<std::string_view> tokens = split(s, ' ');
std::map<std::string_view, int> m;
for (const std::string_view& t : tokens) {
m.insert( {t, 0} );
}
}
{
const std::vector<std::string> tokens = split(s, ' ');
std::map<std::string, int> m;
for (const std::string& t : tokens) {
m.insert( {t, 0} );
}
}
上述for 循环的执行时间仅为:
std::string_view 445.9 ms
std::string 411.7 ms
(旗帜-std=c++20 -O3
,gcc 11.4.0
)
差异不是很大,但我希望std::string_view
程序的两个部分的结果都更快。
为什么std::map<std::string, int>
更快gcc 11.4.0
?std::map<std::string, int>
通常比 更快std::map<std::string_view, int>
?
和中的完整 C++ 代码。
我使用 3 个不同的字符串种子运行代码,每个种子的空格数 (NBS) 都不同:一个只有一个空格,一个有 10 个空格,另一个有 20 个空格。下表显示了每个不同种子字符串的执行时间(以秒为单位)。我认为这会很有趣,因为快速测试结果与此不一致。
国家统计局 | 标记数/ 平均分割 长度(字符) |
功能 | map
|
map
|
unordered_map
|
unordered_map
|
---|---|---|---|---|---|---|
1 | 617864 / 83.97 | 分裂 | 0.010 | 0.153 | 0.023 | 0.025 |
店铺 | 0.441 | 0.408 | 0.106 | 0.167 | ||
10 | 4988259 / 9.35 | 分裂 | 0.594 | 0.883 | 0.469 | 0.206 |
店铺 | 4.430 | 3.806 | 1.361 | 1.470 | ||
20 | 8062256 / 5.20 | 分裂 | 0.696 | 0.981 | 0.559 | 0.298 |
店铺 | 6.568 | 5.590 | 1.820 | 1.892 |
21
最佳答案
2
这完全与缓存局部性相关。
当您将数据存储为s 时,对于您实际使用的非常有限数量的字符串,std::string
唯一必要的数据将本地放置在堆中。 (对于较小的字符串,SSO(小字符串优化)也会发挥作用,这些字符串将放置在“更本地”的位置)。 这非常有利于缓存。
当您使用“std::map”中的树时,大多数这些字符串将被频繁寻址,这将增加缓存的使用率。
当您使用std::string_view
对实际数据的每个引用时,必须在一个巨大的数组(您的初始巨大字符串)中完成,并且会很稀疏。由于您的数组很大并且不适合缓存,因此在大型内存数组中进行密集的随机跳跃将导致缓存使用效率低下。
有关原因的一些细节
缓存通常按行加载(假设为 64 字节),如果值存储位置较高,则一次加载即可获得许多有用值的机会更高。相反,如果位置较低,则需要加载更多页面,这最终会导致和缓存性能下降。
4
-
同意 – 差异很小,表明只有一小部分字符串是“小的”,但足以测量。记得 A 级统计的人可能可以计算出预期的比例 – 或者 OP 可以从文件中测量它。
– -
缓存局部性是微基准测试中一个被低估的方面。
– -
1@TobySpeight 和其他所有人,我添加了一个包含子字符串平均长度的表。
– -
我接受了你的回答,因为其他人似乎同意你的观点,因为这证实了我发帖前的怀疑。但为了让你的回答完美,它应该解释为什么
unordered_map
更快(更好的局部性?)。也许还可以解释为什么使用时比使用时unordered_map
更快,以及为什么似乎比更好。无论如何,谢谢你的努力string_view
string
libc++
map<string_view
libstdc++
–
|
我认为这里发生的事情是,使用 string_view 的拆分算法更快,因为子字符串调用是分配。然而,由于 SV 的间接性,SV 在构建映射时会稍微慢一些。希望这对您有所帮助。
1
-
5
split
在测量循环之外调用(我不是反对者)。问题是关于std::map::insert
!
–
|
string
都有string_view
一个find
成员函数。使用它。–
for (std::size_t i = 0; i < s.size(); ++i) { if (s[i] == c) { ...
c
– 如果不是在中搜索,那是什么s
?–
–
–
std::map
?有了libc++
,两者基本相等:–
|