abseil / abseil/abseil-cpp

reserve doesn't prevent node/flat hash set/map from rehasing

未關閉
#906 3 則留言 0 個 reaction 已指派 1 人 已指派給 @manshreck 在 GitHub 檢視
Documentation
主要語言
C++
星號
18.1k
分支
3.2k
平均合併
20 小時 36 分鐘
30 天內合併 PR
1

描述

**Describe the bug**

Documentation states that `reserve(size_t)` allocates enough buckets to prevent a container from rehashing
```
// Sets the number of slots in the `flat_hash_set` to the number needed to
// accommodate at least `count` total elements without exceeding the current
// maximum load factor, and may rehash the container if needed.
```

However rehasing still might happen. Consider the following example:
```
{
const size_t N = 50;
absl::flat_hash_set set(N);
std::vector itrs;
itrs.reserve(N);

for (size_t i = 0; i < N; ++i) {
auto res = set.emplace(i);
itrs.emplace_back(res.first);
}

std::cerr << "Initial load factor:" << set.load_factor() << '\n';

for (size_t i = N+1; i < 1000000000000; ++i) {
auto it = itrs.back();
itrs.pop_back();
set.erase(it); // <-- remove an element first to fit reserved bucket count
auto res = set.emplace(i); // <--- might trigger rehashing
itrs.push_back(res.first);

std::cerr << "Load factor: " << set.load_factor() << '\n'; // <-- doesn't grow

size_t sum = 0;
for (auto it : itrs) {
sum += (*it); // triggers AssertIsFull
}
}
```

**What version of Abseil are you using?**
checked against `master` HEAD and [Abseil LTS 20200923, Patch 3](https://github.com/abseil/abseil-cpp/releases/tag/20200923.3)

**What operating system and version are you using**
Ubuntu 20.04 LTS

**What compiler and version are you using?**
```
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/9/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:hsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 9.3.0-17ubuntu1~20.04' --with-bugurl=file:///usr/share/doc/gcc-9/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,gm2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-9 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-9-HskZEa/gcc-9-9.3.0/debian/tmp-nvptx/usr,hsa --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
```

**What build system are you using?**
```
cmake version 3.16.3
```

貢獻指南

開啟貢獻指南

評估

這個 Issue 還沒有評估資料。

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。