Return to Answer

Avoid copying allocator in common case; minor improvements elsewhere

edited Feb 11, 2024 at 16:00

87.3k
14
104
322

As far as I can make out, there's nothing to stop allocator traits' destroy() or deallocate() from throwing, so perhaps we ought to handle any exceptions, especially in register_cleanup()'s stored function which is called from within noexcept context (specifically, in a destructor).

Also in register_cleanup(), we could eliminate the need to store the allocator in the common case of a stateless allocator. If the traits tells us that all instances are equivalent, we may be able to create a new one for cleanup rather than capturing this one:

 using traits = std::allocator_traits<A>;
 if constexpr (traits::is_always_equal::value &&
 std::is_default_constructible_v<A>) {
 cleanup = [](T* elems, std::size_t count) {
 A alloc;
 for (T* it = elems + count; it-- > elems; )
 traits::destroy(alloc, it);
 traits::deallocate(alloc, elems, count);
 };
 } else {
 cleanup = [alloc](T* elems, std::size_t count) {
 for (T* it = elems + count; it-- > elems; )
 traits::destroy(alloc, it);
 traits::deallocate(alloc, elems, count);
 };
 }

 // allocate and populate content (for constructors)
 template<class A>
 void copy_content(std::ranges::input_range auto&& other, A alloc)
 {
 if (count == 0) {
 register_empty_cleanup();
 return;
 }
 elemsusing traits = std::allocator_traits<A>allocator_traits<A>;
 elems = traits::allocate(alloc, count);
 T* p = begin();
 try {
 register_cleanup(alloc);
 for (auto q = other.begin(); p != end(); ++p, ++q)
 std::allocator_traits<A>traits::construct(alloc, p, *q);
 } catch (...) {
 while (p-- != begin())
 std::allocator_traits<A>traits::destroy(alloc, p);
 std::allocator_traits<A>traits::deallocate(alloc, elems, count);
 throw;
 }
 }

The helper function prompts a possibility of one or two additional constructors - we could accept a sized_range (possibly of rvalues, thanks to std::views::as_rvalue, helping us move values from other containers).

 ~dynamic_array()
 {
 if (cleanup) // or, if"if (elemeselems)"
 cleanup(elems, count);
 }

We ought to std::fowardforward() the arguments there.

 // allocate and populate content (for constructors)
 template<class A>
 void copy_content(std::ranges::input_range auto&& other, A alloc)
 {
 if (count == 0) {
 register_empty_cleanup();
 return;
 }
 elems = std::allocator_traits<A>::allocate(alloc, count);
 T* p = begin();
 try {
 register_cleanup(alloc);
 for (auto q = other.begin(); p != end(); ++p, ++q)
 std::allocator_traits<A>::construct(alloc, p, *q);
 } catch (...) {
 while (p-- != begin())
 std::allocator_traits<A>::destroy(alloc, p);
 std::allocator_traits<A>::deallocate(alloc, elems, count);
 throw;
 }
 }

The helper function prompts one or two additional constructors - we could accept a sized_range (possibly of rvalues, thanks to std::views::as_rvalue, helping us move values from other containers).

 ~dynamic_array()
 {
 if (cleanup) // or, if (elemes)
 cleanup(elems, count);
 }

We ought to std::foward the arguments there.

 using traits = std::allocator_traits<A>;
 if constexpr (traits::is_always_equal::value &&
 std::is_default_constructible_v<A>) {
 cleanup = [](T* elems, std::size_t count) {
 A alloc;
 for (T* it = elems + count; it-- > elems; )
 traits::destroy(alloc, it);
 traits::deallocate(alloc, elems, count);
 };
 } else {
 cleanup = [alloc](T* elems, std::size_t count) {
 for (T* it = elems + count; it-- > elems; )
 traits::destroy(alloc, it);
 traits::deallocate(alloc, elems, count);
 };
 }

 // allocate and populate content (for constructors)
 template<class A>
 void copy_content(std::ranges::input_range auto&& other, A alloc)
 {
 if (count == 0) {
 register_empty_cleanup();
 return;
 }
 using traits = std::allocator_traits<A>;
 elems = traits::allocate(alloc, count);
 T* p = begin();
 try {
 for (auto q = other.begin(); p != end(); ++p, ++q)
 traits::construct(alloc, p, *q);
 } catch (...) {
 while (p-- != begin())
 traits::destroy(alloc, p);
 traits::deallocate(alloc, elems, count);
 throw;
 }
 }

 ~dynamic_array()
 {
 if (cleanup) // or, "if (elems)"
 cleanup(elems, count);
 }

We ought to std::forward() the arguments there.

eliminate empty-cleanup function

Source Link

edited Feb 6, 2024 at 6:24

Toby Speight

edited Feb 6, 2024 at 6:24

Toby Speight

87.3k
14
104
322

We can get rid of register_empty_cleanup(), just by declining to call an unassigned std::function:

 ~dynamic_array()
 {
 if (cleanup) // or, if (elemes)
 cleanup(elems, count);
 }

We can get rid of register_empty_cleanup(), just by declining to call an unassigned std::function:

 ~dynamic_array()
 {
 if (cleanup) // or, if (elemes)
 cleanup(elems, count);
 }

Source Link

answered Feb 5, 2024 at 17:52

Toby Speight

answered Feb 5, 2024 at 17:52

Toby Speight

87.3k
14
104
322

Note: although the question is tagged C++17, I'm going to use some C++20 or later features in my review, as this simplifies the code. Many of my suggestions can be written in C++17, but at the expense of clarity.

I get some compilation warnings:

g++-14 -std=c++23 -fPIC -gdwarf-4 -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wmissing-braces -Wconversion -Wuseless-cast -Weffc++ 221719.cpp -o 221719
221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::size_t, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>; std::size_t = long unsigned int]’:
221719.cpp:349:65: required from here
 349 | dynamic_array<std::string> arr{n, Tracing_alloc<std::string>{}};
 | ^
221719.cpp:41:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++]
 41 | dynamic_array(std::size_t n, const A& a)
 | ^~~~~~~~~~~~~
221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(const LF_lib::dynamic_array<T>&, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>]’:
221719.cpp:357:68: required from here
221719.cpp:41:5: warning: 357 | dynamic_array<std::string> arr2{arr, Tracing_alloc<std::string>{}};
221719.cpp:41:5: warning: | ^
221719.cpp:99:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++]
 99 | dynamic_array(const dynamic_array& other, const A& a)
 | ^~~~~~~~~~~~~
221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::initializer_list<_Tp>, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>]’:
221719.cpp:363:35: required from here
221719.cpp:99:5: warning: 363 | Tracing_alloc<std::string>{}};
221719.cpp:99:5: warning: | ^
221719.cpp:128:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++]
 128 | dynamic_array(std::initializer_list<T> init, const A& a)
 | ^~~~~~~~~~~~~
221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::size_t, const A&) [with A = Tracing_alloc<Construct_throw>; T = Construct_throw; std::size_t = long unsigned int]’:
221719.cpp:368:74: required from here
221719.cpp:128:5: warning: 368 | dynamic_array<Construct_throw> arr4{n, Tracing_alloc<Construct_throw>{}};
221719.cpp:128:5: warning: | ^
221719.cpp:41:5: warning: ‘LF_lib::dynamic_array<Construct_throw>::cleanup’ should be initialized in the member initialization list [-Weffc++]
 41 | dynamic_array(std::size_t n, const A& a)
 | ^~~~~~~~~~~~~

These are easily suppressed with std::function<⋯> cleanup = {};, making the default-initialisation explicit.

The test program is Valgrind-clean, but does exit with failure status:

==1410317== HEAP SUMMARY:
==1410317== in use at exit: 0 bytes in 0 blocks
==1410317== total heap usage: 13 allocs, 13 frees, 75,735 bytes allocated
==1410317=わ=わ 
=わ=わ1410317== All heap blocks were freed -- no leaks are possible
==1410317=わ=わ 
=わ=わ1410317== For lists of detected and suppressed errors, rerun with: -s
==1410317== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
make[1]: *** [Makefile:74: 221719.run] Error 1

Adding a bit of diagnostic, we see that this is due to catching the exception from Construct_throw(), and it seems that the test program should expect this, and simply has its return statuses the wrong way around (i.e. the test should fail if we don't get the exception):

 Construct_throw()
 {
 static int i = 0;
 if (i++ > 3)
 throw std::runtime_error("Construct_throw");
 }

#include <cstdlib>
#include <stdexcept>
int main()
 try {
 test(0);
 test(10);
 return EXIT_FAILURE;
 } catch (const std::exception& e) {
 std::cerr << e.what() << '\n';
 return EXIT_SUCCESS;
 }

The first two constructors can easily be combined into a single one by defaulting the allocator. And since we just copy it to alloc, we can accept it by value:

 template <class A = std::allocator<T>>
 explicit dynamic_array(std::size_t n, A alloc = {})

Similarly:

 template <class A = std::allocator<T>>
 dynamic_array(std::size_t n, const T& value, A alloc = {})

and

 template <class A = std::allocator<T>>
 dynamic_array(std::initializer_list<T> init, A alloc a = {})

But not

 template <class A = std::allocator<T>>
 dynamic_array(const dynamic_array& other, A alloc = {})

because this is no longer a copy constructor.

When constructing contents throws an exception, I think we're supposed to destroy in reverse order of construction:

 } catch (...) {
 while (p-- != begin())
 std::allocator_traits<A>::destroy(alloc, p);
 std::allocator_traits<A>::deallocate(alloc, elems, count);
 throw;

A similar change is required in register_cleanup():

 cleanup = [alloc](T* elems, std::size_t count) mutable {
 T* it = elems + count;
 while (it-- > elems)
 std::allocator_traits<A>::destroy(alloc, it);
 std::allocator_traits<A>::deallocate(alloc, elems, count);
 };

There's a lot of commonality among the different constructors. I think we can refactor that out into a private utility method.

 // allocate and populate content (for constructors)
 template<class A>
 void copy_content(std::ranges::input_range auto&& other, A alloc)
 {
 if (count == 0) {
 register_empty_cleanup();
 return;
 }
 elems = std::allocator_traits<A>::allocate(alloc, count);
 T* p = begin();
 try {
 register_cleanup(alloc);
 for (auto q = other.begin(); p != end(); ++p, ++q)
 std::allocator_traits<A>::construct(alloc, p, *q);
 } catch (...) {
 while (p-- != begin())
 std::allocator_traits<A>::destroy(alloc, p);
 std::allocator_traits<A>::deallocate(alloc, elems, count);
 throw;
 }
 }

We can then use that for most of the constructors:

 template <class A = std::allocator<T>>
 dynamic_array(std::size_t n, const T& value, A alloc = {})
 :count{n}
 {
 copy_content(std::views::repeat(value), alloc);
 }
 dynamic_array(const dynamic_array& other)
 :dynamic_array{other, std::allocator<T>{}}
 {
 }
 template <class A = std::allocator<T>>
 dynamic_array(const dynamic_array& other, A alloc)
 :count{other.size()}
 {
 copy_content(other, alloc);
 }
 template <class A = std::allocator<T>>
 dynamic_array(std::initializer_list<T> init, A alloc = {})
 :count{init.size()}
 {
 copy_content(init, alloc);
 }

We can't as easily use it for the first constructor (which default-constructs elements) because in that case T might be non-copyable.

I don't see any reason to disable move-assignment or move-construction. We could use copy-and-swap idiom for the latter.

The rbegin() and rend() look wrong to me:

using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 reverse_iterator rbegin() noexcept { return end(); }
const_reverse_iterator rbegin() const noexcept { return end(); }
 reverse_iterator rend() noexcept { return begin(); }
const_reverse_iterator rend() const noexcept { return begin(); }

I'm not sure how we're getting away with this, since the std::reverse_iterator constructor here is explicit - I don't see any exception that applies to bare pointers.

The set of relational operators can be replaced with <=> and std::lexicographical_compare_three_way() (there's no ranges version of this algorithm, likely due to it appearing after the ranges algorithms were written).

In the test program's allocator, we have

 template <typename... Args>
 void construct(T* ptr, Args&&... args)
 {
 std::cerr << "construct(" << ptr << ", args...)\n";
 std::allocator_traits<Base>::construct(*this, ptr, args...);
 }

We ought to std::foward the arguments there.

We could improve the Construct_throw test with a constructor that only throws every n invocations. That could help us ensure that we destruct the correct elements, in the correct order.

lang-cpp