这个答案给出了短字符串优化(SSO)的一个很好的高级概述.但是,我想更详细地了解它在实践中是如何工作的,特别是在libc ++实现中:
为了符合SSO资格,字符串有多短？这取决于目标架构吗？
在访问字符串数据时,实现如何区分短字符串和长字符串？它m_size <= 16是一个简单的,还是一个标志,是其他成员变量的一部分？(我想这m_size或其中的一部分也可能用于存储字符串数据).
我专门针对libc ++问了这个问题,因为我知道它使用SSO,甚至在libc ++主页上也提到过.
以下是查看来源后的一些观察结果:
libc ++可以使用两个稍微不同的字符串类内存布局进行编译,这由_LIBCPP_ALTERNATE_STRING_LAYOUT标志控制.这两种布局还区分了little-endian和big-endian机器,这使我们总共有4种不同的变体.我将在下面的内容中假设"正常"布局和小端.
假设进一步size_type是4个字节并且value_type是1个字节,这就是字符串的前4个字节在内存中的样子:
// short string: (s)ize and 3 bytes of char (d)ata
sssssss0;dddddddd;dddddddd;dddddddd
^- is_long = 0
// long string: (c)apacity
ccccccc1;cccccccc;cccccccc;cccccccc
^- is_long = 1
由于短字符串的大小在高7位,因此在访问它时需要移位:
size_type __get_short_size() const {
return __r_.first().__s.__size_ >> 1;
}
类似地,长字符串容量的getter和setter用于__long_mask解决这个问题is_long.
我仍在寻找我的第一个问题的答案,即__min_cap短字符串的容量对不同的架构有什么价值？
其他标准库实现
这个答案很好地概述了std::string其他标准库实现中的内存布局.
我无法找到有关此信息的最新信息.
C++ 11版本的STL容器是否保证了一定程度的线程安全性？
由于性能原因,我确实希望他们不这样做.但话说回来,这就是为什么我们同时拥有std::vector::operator[]和std::vector::at.
我最近发现了一件奇怪的事情.似乎计算Collatz序列长度完全没有缓存比使用缓存所有元素快 2倍.std::unordered_map
注意我确实从问题提示中是否gcc std :: unordered_map实现缓慢？如果是这样 - 为什么？我试着用这些知识来std::unordered_map表现我的能力(我使用g ++ 4.6,它确实比g ++的最新版本表现更好,我试着指定一个声音的初始桶数,我使它完全等于最大值地图必须持有的元素数量).
相比之下,使用std::vector缓存一些元素几乎比没有缓存快17倍,比使用缓慢快近40倍std::unordered_map.
我做错了什么,或者这个容器是慢的,为什么？可以让它表现得更快吗？或者,哈希映射本质上是无效的,应该尽可能避免在高性能代码中使用？
有问题的基准是:
#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <ctime>
std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
static std::unordered_map <std::uint_fast64_t, std::uint_fast16_t> cache ({{1,1}}, 2168611);
if(cache.count(val) == 0) {
if(val%2 == 0)
cache[val] = getCollatzLength(val/2) + 1;
else
cache[val] = getCollatzLength(3*val+1) + 1;
}
return cache[val];
}
int main()
{
std::clock_t tStart = std::clock();
std::uint_fast16_t largest …