boostorg / unordered Goto Github PK
View Code? Open in Web Editor NEWBoost.org unordered module
Home Page: http://boost.org/libs/unordered
License: Boost Software License 1.0
Boost.org unordered module
Home Page: http://boost.org/libs/unordered
License: Boost Software License 1.0
In the standard, empty()
is defined as:
// capacity
[[nodiscard]] bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
This simply just requires adding BOOST_ATTRIBUTE_NODISCARD
to the member functions.
Inserting in "hash order" can dramatically degrade the performance of insertion. This can be easily triggered by:
unordered_flat_map<int, int> map1(...);
unordered_flat_map<int, int> map2;
for (auto const& kv: map1) { map2.insert(kv); }
For users, this can be circumvented easily by either using the copy constructor or by calling reserve()
prior to insertion.
Situation
We are storing a unordered_map
, unordered_multi_map
and unordered_set
in a Boost Interprocess Shared Memory that is accessed by a 32bit process and a 64bit process. The 32bit process or the 64bit process can be the creator of the object.
Symptoms
If a 64bit process creates these containers, the 32bit process will crash trying to retrieve it and vice-versa.
If a 64bit process inserts object into one of the containers, the 32bit process will fail to retrieve them by hashing and vice-versa.
Solution
I had to modify some headers so that the sizeof of the unordered's implementation is exactly the same in 32 and 64bits.
In my own code, I force the hashing to be on 32bit instead of size_t
. There is some issues internally around the policy. It will fall on a different logic and yield different result if on 32bit or 64bit.
See patch attached.
boost-1.68.0-fix-interoperability-32-64-unordered.patch.zip
See related issue for Boost Multi-Index boostorg/multi_index#17
This repo currently has 55 branches
All branches which are merged to develop (have a "0" in the 2nd number of the table above, i.e. "0 commits ahead of develop") can be safely deleted.
Also there are branches with no activity in 13-15 years. Some don't have any commits with content (check the "Compare" button), e.g. https://github.com/boostorg/unordered/compare/svn-branches/cpp0x
Others may be so outdated it might make sense to just remove them.
That makes working with the repo harder and clones/checkouts larger, so a cleanup is due
P1690R1 added a transparent overload of count()
that avoids creating an intermediate object when getting the count.
See: https://en.cppreference.com/w/cpp/container/unordered_map/count
Consider this program:
#include <boost/unordered_set.hpp>
#include <iostream>
static bool log_allocate=false;
template<class T> struct allocator
{
using value_type=T;
allocator()=default;
template<class U> allocator(allocator<U> const &)noexcept{}
template<class U> bool operator==(allocator<U> const &)const noexcept{return true;}
template<class U> bool operator!=(allocator<U> const&)const noexcept{return false;}
T* allocate(std::size_t n)const
{
if(log_allocate)std::cout<<"allocate: "<<n<<"\n";
return std::allocator<T>().allocate(n);
}
void deallocate(T* p,std::size_t n)const noexcept{std::allocator<T>().deallocate(p,n);}
};
int main()
{
boost::unordered_set<int,boost::hash<int>,std::equal_to<int>,::allocator<int>> s(100);
for(int i=0;i<s.bucket_count()-1;++i)s.insert(i);
std::cout<<"bucket count: "<<s.bucket_count()<<"\n";
std::cout<<"about to rehash\n";
log_allocate=true;
s.rehash(0);
std::cout<<"bucket count: "<<s.bucket_count()<<"\n";
}
The output against develop is
bucket count: 193
about to rehash
allocate: 194
allocate: 4
bucket count: 193
where it can be seen that, even though bucket_count
remains the same after rehashing, reallocation has indeed happened. The problem lies in table::rehash
:
template <typename Types>
inline void table<Types>::rehash(std::size_t num_buckets)
{
num_buckets = (std::max)(
min_buckets(size_, mlf_), buckets_.bucket_count_for(num_buckets));
if (num_buckets != this->bucket_count()) {
this->rehash_impl(num_buckets);
}
}
Unnecessary reallocation happens because, in the example, num_buckets != this->bucket_count()
but buckets_.bucket_count_for(num_buckets) == this->bucket_count()
. A simple fix is to rewrite as:
template <typename Types>
inline void table<Types>::rehash(std::size_t num_buckets)
{
num_buckets = buckets_.bucket_count_for(
(std::max)(min_buckets(size_, mlf_), num_buckets));
if (num_buckets != this->bucket_count()) {
this->rehash_impl(num_buckets);
}
}
The fix in the 'develop' branch is for the Embarcadero C++ clang-based compilers.
Running:
exbigboss@DESKTOP-I99BGOL:~/cpp/boost-root$ ./b2 -a libs/unordered/test cxxstd=20 toolset=clang-12
generates several warnings of the form:
In file included from libs/unordered/test/unordered/assign_tests.cpp:8:
In file included from ./boost/unordered_set.hpp:17:
In file included from ./boost/unordered/unordered_set.hpp:20:
In file included from ./boost/unordered/detail/set.hpp:6:
./boost/unordered/detail/implementation.hpp:4344:17: warning: ISO C++20 considers use of overloaded operator '==' (with operand types 'test::test_detail::list_iterator<test::object>' and 'test::test_detail::list_iterator<test::object>') to be ambiguous despite there being a unique best viable function [-Wambiguous-reversed-operator]
if (i == j)
~ ^ ~
./boost/unordered/unordered_set.hpp:1714:14: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::set<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::hash, test::equal_to>>::insert_range_equiv<test::test_detail::list_iterator<test::object>>' requested here
table_.insert_range_equiv(first, last);
^
./boost/unordered/unordered_set.hpp:1559:13: note: in instantiation of function template specialization 'boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::insert<test::test_detail::list_iterator<test::object>>' requested here
this->insert(f, l);
^
libs/unordered/test/unordered/assign_tests.cpp:49:9: note: in instantiation of function template specialization 'boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::unordered_multiset<test::test_detail::list_iterator<test::object>>' requested here
T x(v.begin(), v.end());
^
libs/unordered/test/unordered/assign_tests.cpp:251:18: note: in instantiation of function template specialization 'assign_tests::assign_tests1<boost::unordered::unordered_multiset<test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>>' requested here
UNORDERED_TEST(assign_tests1,
^
libs/unordered/test/unordered/../helpers/./list.hpp:116:12: note: ambiguity is between a regular call to this operator and a call with the argument order reversed
bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
^
You can see similar issues raised in the CI here:
https://github.com/boostorg/unordered/runs/4216196265?check_suite_focus=true#step:6:5429
Consider a new group14
structure with uses 14 bytes for reduced hashes and 2 bytes for marking overflow.
Compare performance against current group15
implementation.
While testing boost::unordered_flat_set
, I noticed my code is reliably running over 10% faster if I __forceinline
all the function calls that the boost::unordered_flat_set
makes in my hot path. My hot path is only doing .contains()
, so anything called by .contains()
, including the .contains
itself, is where I added __forceinline
. So that in my own code where I call .contains()
, looking at the disassembly there is no call
anywhere any more, it's fully inlined. I think I had to add __forceinline
to 6 functions inside boost code.
It is a bit inconvenient to manually add __forceinline
to all those functions though - it's definitely worth the 10% performance gain, but I am quite sure that the next time I update boost in a few years, I'll forget to apply these changes again, and then my performance will be worse.
Assuming you don't want to add __forceinline
to those functions by default, could there maybe some define like BOOST_FORCEINLINE_UNORDERED_SET
that automatically enables forceinlining all the important functions?
I am already compiling with maximum optimization level of MSVC, so by default it doesn't want to inline it, MSVC often needs to be forced to inline stuff.
Avoid the cost of hashing by directly linearly searching the table.
detail\prime_fmod.hpp:120 triggers a runtime check failure #1 on msvc (Run-Time Check Failure #1 - A cast to a smaller data type has caused a loss of data.)
Looks intentional due to the cast of boost::uint32_t(hash).
It could be guarded somehow to not trigger this runtime failure when using msvc compiler.
Microsoft suggests the following:
Run-Time Check Failure #1 - A cast to a smaller data type has caused a loss of data. If this was intentional, you should mask the source of the cast with the appropriate bitmask. For example:
char c = (i & 0xFF);
Docs in the reference appear to be missing for:
unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a);
unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
const allocator_type& a)
These weren't part of the original documentation and will require new text.
The rest of the containers will need to be audited as well.
Implement small proof-of-concept of an unordered flat map that stores elements in nodes, granting them reference stability.
This would (most likely) enable a full compliant implementation of the unordered_flat_map.
Attempt to wrap unordered_flat_map<unique_ptr<K, T>>
and begin development from there.
// lookup
const_iterator find(const key_type&) const;
template <class Key>
typename boost::enable_if_c<detail::are_transparent<Key, H, P>::value,
const_iterator>::type
find(const Key& k) const;
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
const_iterator find(CompatibleKey const&, CompatibleHash const&,
CompatiblePredicate const&) const;
Why aren't there any non-const lookup methods for unordered_set
?
unordered_map
has them, Boost and repo docs also state that they should be a part of the unordered_set
interface. Not to mention that they are present in std::unordered_set
.
Am I missing something?
In the documentation of the CGAL library we have links to unordered map and set. As this has changed we have broken links (see our issue).
Wouldn't it make sense that you add redirections in the .htacess file at https://github.com/boostorg/website/?
Users have noted that certain warnings will trigger for the SFINAE used in the main implementation.hpp
file as noted here #8
Due to the busy lives of contributors, this issue can be directly tackled by a separate PR which refactors the SFINAE into the return type thus fixing the error and also updating the code to be more in line with current style recommendations.
gdb pretty-printers will probably also be needed.
Unordered could use some sprucing up by replacing its own homespun allocator traits with the utilities in Core:
https://www.boost.org/doc/libs/develop/libs/core/doc/html/core/allocator_access.html
unordered_map
is missing documentation for the try_emplace
series of member functions
unordered_flat_map<string,string> m;
string_view key;
m[key] = ""; // does not work
m.insert_or_assign( key, "" ); // does not work
I'd like to replace our usage of absl::flat_hash_map with boost::unordered_flat_map.
But this missing functions cannot be simulated without performance losses.
Seems like we don't have (InputIterator,InputIterator,Allocator)
and (std::initializer_list,Allocator)
deduction guides for set types as mandated by the resolution of LWG2713.
This is a super issue for all compiler-generated warnings for the Unordered test suite.
In test/helpers/metafunctions.hpp
the following code generates error: βthisβ pointer is null [-Werror=nonnull]
with GCC 11:
template <class Container> struct has_unique_keys
{
static char flip(typename Container::iterator const&);
static long flip(std::pair<typename Container::iterator, bool> const&);
BOOST_STATIC_CONSTANT(bool,
value = sizeof(long) ==
sizeof(flip(
((Container*)0)->insert(*(typename Container::value_type*)0))));
};
Potential solutions include:
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnonnull"
BOOST_STATIC_CONSTANT(bool,
value = sizeof(long) ==
sizeof(flip(
((Container*)0)->insert(*(typename Container::value_type*)0))));
#pragma GCC diagnostic pop
and:
value = sizeof(long) == sizeof(flip(unordered_declval<Container&>().insert(unordered_declval<typename Container::value_type>())))
for when unordered_declval
exists.
I'm not familiar with boost codebase multi-lib structure so apologies if this is in wrong sub-repo, but I get lots of these errors after upgrading to latest WinSDK 10.0.19041.0 version (I have no idea why 10.0.18xx didn't raise it):
include\boost\unordered\detail\implementation.hpp(1452,7): error C4996: 'std::allocator::is_always_equal': warning STL4010: Various members of std::allocator are deprecated in C++17. Use std::allocator_traits instead of accessing these members directly. You can define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING or _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS to acknowledge that you have received this warning.
I saw boostorg/regex#67 - is this something which is not consistent across different boost libs? I've fixed it in my project but was surprised to come across it.
I have discovered that if I have an empty hash table and call reserve(size)
, the hash table, instead of allocating a big enough bucket table to insert size * load
items, deletes whatever table it has, and then waits until I am in my critical path to allocate the bucket table.
This bug was installed in fe3d612f
on 2009-10-04 10:37:36.
In order to work around this bug, I have to insert a dummy element, call reserve(size)
, and then erase the dummy element.
This behavior violates the entire purpose of reserve()
, which is to front-load allocations so that they will not stall time-critical operations.
Gnu libstdc++ and Clang libc++ std::unordered_set
both implement reserve(size)
correctly.
#include <boost/unordered_set.hpp>
#include <new>
#include <functional>
#include <iostream>
#include <cstdlib>
int total_allocation = 0;
struct B {
B() : i(++count) {}
static int count;
int i;
bool operator==(B const& b) { return i == b.i; };
bool operator!=(B const& b) { return i != b.i; };
};
int B::count = 0;
template<typename T> struct A : B {
using value_type = T;
A() = default;
template <class U> A(const A<U>&) noexcept {}
T* allocate(std::size_t n) {
std::cout << " " << i << " allocated " << n << " x " << sizeof(T) << '\n';
total_allocation += n * sizeof(T);
return (T*) std::calloc(n, sizeof(T));
}
void deallocate(T* p, std::size_t n) noexcept {
std::cout << " " << i << " deallocated " << n << " x " << sizeof(T) << '\n';
total_allocation -= n * sizeof(T);
std::free(p);
}
};
int main() {
boost::unordered_set<int, std::hash<int>, std::equal_to<int>, A<int>> s(1000'000);
std::cout << "Bucket table allocation = " << total_allocation
<< ", expected at least " << sizeof(int*) * 1000'000 << '\n';
s.insert(0);
s.reserve(2000'000);
s.erase(0);
std::cout << "Bucket table allocation = " << total_allocation
<< ", expect at least " << sizeof(int*) * 2000'000 << '\n';
s.reserve(3000'000);
std::cout << "Bucket table allocation = " << total_allocation
<< ", expected at least " << sizeof(int*) * 3000'000 << '\n';
return total_allocation == 0;
}
Output is
Bucket table allocation = 0, expected at least 8000000
2 allocated 1 x 24
3 allocated 1572870 x 8
3 allocated 3145740 x 8
3 deallocated 1572870 x 8
2 deallocated 1 x 24
Bucket table allocation = 25165920, expect at least 16000000
3 deallocated 3145740 x 8
Bucket table allocation = 0, expected at least 24000000
More info found here.
There may be to many individual test binaries which slow down the build/CI. See e.g. https://github.com/boostorg/unordered/runs/6779803837?check_suite_focus=true
For b2 -j3 libs/%LIBRARY%/test toolset=msvc-14.3 cxxstd=14,17,20,latest address-model=32,64 variant=debug,release embed-manifest-via=linker
it already yields (at least) 422=16 variants of each test.
In the test Jamfile we have 54 run-tests and 4 compile-tests yielding at least 928 compilations. That job already takes over an hour on GHA. With coverage collection it is even over 3h and counting.
And it seems the calculation is still to low: ...updated 7154 targets...
O.o
Is it possible to trim that down? E.g. combine more tests into single compilation units as especially on Windows firing up the compiler/linker is very expensive (in terms of time).
Also I'm not sure where the additional factor of 7 (in the targets) is coming from. Maybe that could also be trimmed down somehow.
Dear All
Can you implement template equal_range like std library?
template< class K >
std::pair<iterator,iterator> equal_range( const K& x );
can read more in:
https://en.cppreference.com/w/cpp/container/unordered_multimap/equal_range
API described here.
E.g. here
unordered/include/boost/unordered/unordered_flat_map.hpp
Lines 407 to 418 in d036994
Since the call to boost::throw_exception
generates a fair bit of code and is typically "cold", we want this extracted into a separate BOOST_NOINLINE function so that the rest of at
can be inlined.
In addition, we also typically want to either pass BOOST_CURRENT_LOCATION to boost::throw_exception
, or switch to boost::throw_with_location
(again with supplying a location to it).
As a further refinement, it's possible to add a default source_location argument to at
so that the location in the exception ends up being the point of calling at
, instead of the point inside of at
. This however changes the signature of at
, so it should be a separate change, should we decide to do it.
When using bcp in version 1.69.0 to move boost to a different designated namespace, file boost/unordered/detail/implementation.hpp does not get changed and requires manual fixing.
Near line 1603 of the aforementioned file, the several uses of macro BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE keep on using the original namespace.
The memory_tracker
is a helper used by the allocators in the test suite to make sure that allocate + construct calls are matched up properly with destruct + deallocation calls. The memory_tracker
also keeps track of how many allocators are alive and referencing it.
Unfortunately, the destructor's usage of BOOST_TEST
does not work as was intended by the original author.
The destructor is defined here:
~memory_tracker() { BOOST_TEST(count_allocators == 0); }
and the memory tracker is included in the unit tests as an object in namespace scope:
namespace detail {
// This won't be a problem as I'm only using a single compile unit
// in each test (this is actually required by the minimal test
// framework).
//
// boostinspect:nounnamed
namespace {
test::detail::memory_tracker tracker;
}
}
Unfortunately, this destructor does not have the desired effect when running the test suite. Namely, tests in Unordered are run via this macro:
#define RUN_TESTS() \
int main(int, char**) \
{ \
BOOST_UNORDERED_TEST_COMPILER_INFO() \
::test::get_state().run_tests(); \
return boost::report_errors(); \
}
The tracker
's lifetime is static which means that its destructor is run after main has already ended so all errors are ignored by the test runner. To this end, a developer can erroneously refactor the cxx11_allocator
and mess up the reference counting without even knowing.
Stack overflow linked question
Following code compile (MSVC C++ latest) using std::unordered_map but not with the new boost:unordered_flat_map:
#include "boost/unordered/unordered_flat_map.hpp"
#include <unordered_map>
class Foo
{
public:
Foo() = default;
explicit Foo(int x) : m_x_(x) {};
private:
int m_x_;
std::mutex mtx;
};
int main(int argc, char** argv)
{
boost::unordered_flat_map<int,Foo> map_test; //compile with std::unordered_map
map_test.try_emplace(1,1);
return 0;
}
I dont expect it to work with flat_map as with std::map , guessing as the map need reordering, elements need to be able to move/copy. But I dont get why its working with std::unordered_map and not boost:unordered_flat_map.
If I'm reading it right, it looks like the internal table is not storing the calculated hashes of the node keys. Instead, the hash is calculated on insertion to determine the bucket, and then thrown away. After that, only key-equality is used for things like find()
, erasure, equality, etc.
That's fine when the key is something small, like an int
, but is slow when the key is not small. Even for string type keys, if the container happens to have a lot of keys of the same string lengths, then equality checking is not cheap. And of course people use custom types for keys too, with potentially non-trivial equality comparisons.
On the other hand, if you stored the full calculated hash in the nodes, you could skip past entries in the same bucket that don't have a matching full-hash, thereby improving performance. (at the expense of memory, obviously)
Another example is rehashing when the load-factor is exceeded. Right now it looks like it has to re-calc the hash of every single node, whereas if it had stored the full-hash it wouldn't need to.
LLVM/clang's libc++
unordered containers store the full-hash, and gcc's libstdc++
does as well in specific cases (e.g., for string-ish types, or if the user specifies the hashing is slow).
So I'm wondering if you've considered doing that, or believe the memory tradeoff isn't worth it?
The containers can use one of two policies: a "prime_policy" (
), which uses prime numbers for the bucket count (unordered/include/boost/unordered/detail/implementation.hpp
Lines 287 to 294 in 5e8b6a9
Generally, the mix64_policy is selected when size_t is 64 bit, and prime_policy is used otherwise (
unordered/include/boost/unordered/detail/implementation.hpp
Lines 2681 to 2696 in 5e8b6a9
However, when the key is integral (int
and above), prime_policy is selected as a special case (
unordered/include/boost/unordered/detail/implementation.hpp
Lines 2698 to 2702 in 5e8b6a9
The comment claims that the prime policy is a lot faster for consecutive integral keys, but since it performs a modulo operation, which is an expensive div instruction, on benchmark/uint64.cpp
mix64_policy is slightly faster for me (~23 seconds against ~24 seconds under msvc-14.2 64 bit release).
Therefore, we should consider removing this special case, and use mix64_policy for integral keys, too.
mix64_policy contains code that scrambles the hash value (
unordered/include/boost/unordered/detail/implementation.hpp
Lines 2640 to 2646 in 5e8b6a9
// Multiplier taken from https://arxiv.org/pdf/2001.05304.pdf
// Computationally Easy, Spectrally Good Multipliers for Congruential Pseudorandom Number Generators
// Guy Steele, Sebastiano Vigna, September 28, 2021
key *= 0xf1357aea2e62a9c5;
key ^= key >> 32;
which for me is about 20% faster and should have good enough scrambling properties. So we should consider this alternative.
We probably want a mix32_policy, too, for the 32 bit case.
See: https://cplusplus.github.io/LWG/issue2713
This is a blocker for the deduction guides mentioned in #149
https://en.cppreference.com/w/cpp/container/unordered_map/insert
The unordered_map
implementation is missing insert
overloads:
insert_return_type insert(node_type&& nh);
iterator insert(const_iterator hint, node_type&& nh);
Outlined here by cppref.
Described here.
unordered/include/boost/unordered/unordered_map.hpp
Lines 748 to 756 in c8abaf3
These seem at odds with what's in the STL found here: https://en.cppreference.com/w/cpp/container/unordered_map/find
and http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0919r2.html as well.
Looking at the benchmarks at the beta docs, it looks like the two Erasure With Duplicate elements cases against Visual Studio 2019 + Dinkumware were slower. It would be great if this could be addressed for the v1.80 final release.
Thanks!
Currently all the tests are broken. To be clear: it's not the the library code that's broken, but the tests itself. There are multiples issues:
Compiling the test suite using, for example:
./b2 -a libs/unordered/test cxxstd=20 toolset=clang-12
on Ubuntu 20.04 will generate many such warnings:
In file included from libs/unordered/test/unordered/assign_tests.cpp:15:
libs/unordered/test/unordered/../objects/cxx11_allocator.hpp:265:5: warning: definition of implicit copy assignment operator for 'cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>' is deprecated because it has a user-declared copy constructor [-Wdeprecated-copy]
cxx11_allocator(cxx11_allocator const& x) : cxx11_allocator_base<T>(x) {}
^
./boost/unordered/detail/implementation.hpp:452:20: note: in implicit copy assignment operator for 'test::cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>' first required here
second() = x.second();
^
./boost/unordered/detail/implementation.hpp:3462:25: note: in instantiation of member function 'boost::unordered::detail::compressed<test::cxx11_allocator<boost::unordered::detail::ptr_bucket, test::propagate_assign>, test::cxx11_allocator<boost::unordered::detail::ptr_node<std::pair<const test::object, test::object>>, test::propagate_assign>>::assign' requested here
allocators_.assign(x.allocators_);
^
./boost/unordered/detail/implementation.hpp:3425:13: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::object, test::hash, test::equal_to>>::assign<std::integral_constant<bool, true>>' requested here
assign(x, is_unique,
^
./boost/unordered/unordered_map.hpp:166:16: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<test::cxx11_allocator<test::object, test::propagate_assign>, test::object, test::object, test::hash, test::equal_to>>::assign<std::integral_constant<bool, true>>' requested here
table_.assign(x.table_, boost::unordered::detail::true_type());
^
libs/unordered/test/unordered/assign_tests.cpp:38:9: note: in instantiation of member function 'boost::unordered::unordered_map<test::object, test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>::operator=' requested here
x = x;
^
libs/unordered/test/unordered/assign_tests.cpp:251:18: note: in instantiation of function template specialization 'assign_tests::assign_tests1<boost::unordered::unordered_map<test::object, test::object, test::hash, test::equal_to, test::cxx11_allocator<test::object, test::propagate_assign>>>' requested here
UNORDERED_TEST(assign_tests1,
^
This also shows up in the CI:
https://github.com/boostorg/unordered/runs/4216196265?check_suite_focus=true#step:6:847
This code segfaults in 1.80.0 but not 1.79.0 (nor using std::unordered_set):
boost::unordered_set<std::string> a;
boost::unordered_set<std::string> b = std::move(a);
boost::unordered_set<std::string> c = std::move(a);
c.clear(); // <-- segfault
Based on the standard, the first move should leave a
in a "valid but unspecified state"; since a
should still be valid, moving from it a second time presumably should not corrupt c
(even if the contents of c
are technically unspecified afterward).
Note: it appears that unordered_map also exhibits the same behavior.
I have a user-defined type which is allocator aware:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L108-L122
This user-defined type I would like to store in an unordered_map, which is allocated in an mmap file using boost interprocess:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L331-L337
Finally I use emplace to store an entry in this map:
https://github.com/kleunen/tilemaker/blob/win_ci_build/include/osm_store.h#L375-L380
On MSVC and linux/g++ this works fine. However, if I compile on MacOS, with g++ and probably libc++ as STL, the unordered_map construct seems to default initialize the VarIntVector and not pass the scoped allocator. Which fails, because the interprocess allocator is not default constructable, it needs a reference to a segment manager.
2021-03-20T07:14:56.5388750Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/container/scoped_allocator.hpp:443:32: error: constructor for 'boost::container::dtl::scoped_allocator_adaptor_base<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>>' must explicitly initialize the base class 'boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>' which does not have a default constructor
2021-03-20T07:14:56.5391710Z BOOST_CONTAINER_FORCEINLINE scoped_allocator_adaptor_base()
2021-03-20T07:14:56.5392270Z ^
2021-03-20T07:14:56.5395420Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/container/scoped_allocator.hpp:644:32: note: in instantiation of member function 'boost::container::dtl::scoped_allocator_adaptor_base<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64>>::scoped_allocator_adaptor_base' requested here
2021-03-20T07:14:56.5397550Z BOOST_CONTAINER_FORCEINLINE scoped_allocator_adaptor()
2021-03-20T07:14:56.5398080Z ^
2021-03-20T07:14:56.5400950Z /Users/runner/work/tilemaker/tilemaker/include/osm_store.h:120:25: note: in instantiation of member function 'boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >::scoped_allocator_adaptor' requested here
2021-03-20T07:14:56.5402840Z VarIntVector(A alloc = A())
2021-03-20T07:14:56.5403260Z ^
2021-03-20T07:14:56.5413170Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/detail/implementation.hpp:2040:11: note: in instantiation of function template specialization 'boost::unordered::detail::func::construct_from_args<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<boost::unordered::detail::node<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5420390Z construct_from_args(
2021-03-20T07:14:56.5420750Z ^
2021-03-20T07:14:56.5428320Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/detail/implementation.hpp:3774:54: note: in instantiation of function template specialization 'boost::unordered::detail::func::construct_node_from_args<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<boost::unordered::detail::node<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5434010Z node_tmp b(boost::unordered::detail::func::construct_node_from_args(
2021-03-20T07:14:56.5434560Z ^
2021-03-20T07:14:56.5441480Z /usr/local/share/vcpkg/installed/x64-osx/include/boost/unordered/unordered_map.hpp:226:23: note: in instantiation of function template specialization 'boost::unordered::detail::table<boost::unordered::detail::map<boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> >, const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >, std::__1::hash<unsigned long long>, std::__1::equal_to<unsigned long long> > >::emplace_unique<const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
2021-03-20T07:14:56.5446600Z return table_.emplace_unique(
2021-03-20T07:14:56.5447020Z ^
2021-03-20T07:14:56.5453500Z /Users/runner/work/tilemaker/tilemaker/include/osm_store.h:377:30: note: in instantiation of function template specialization 'boost::unordered::unordered_map<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >, std::__1::hash<unsigned long long>, std::__1::equal_to<unsigned long long>, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<std::__1::pair<const unsigned long long, VarIntVector<unsigned long long, boost::container::scoped_allocator_adaptor<boost::interprocess::node_allocator<unsigned char, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > > >, boost::interprocess::segment_manager<char, boost::interprocess::rbtree_best_fit<boost::interprocess::mutex_family, boost::interprocess::offset_ptr<void, long, unsigned long, 0>, 0>, iset_index>, 64> > >::emplace<const std::__1::piecewise_construct_t &, std::__1::tuple<unsigned long long &>, std::__1::tuple<> >' requested here
https://pipelines.actions.githubusercontent.com/ya42YO45OlA9LAnHTfxsjT6uj2KbvrHrStfya2AgUYklRTQFd7/_apis/pipelines/1/runs/255/signedlogcontent/8?urlExpires=2021-03-20T07%3A21%3A48.5176130Z&urlSigningMethod=HMACV1&urlSignature=mLfAstpJX4HmQ9g2S%2FnGVYNFIkD9E6hB399%2B2xhuwDs%3D
https://github.com/kleunen/tilemaker/runs/2154401042?check_suite_focus=true
A declarative, efficient, and flexible JavaScript library for building user interfaces.
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. πππ
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google β€οΈ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.