relocation

[arturbac]

@Quuxplusone I would like to discuss relocation with You
I prepared everything with minimizing in mind non trivial copy and move to only types that are not trivially moveable/copyable and for cases when they are noxecept. As I cannot safely move elements if move operator of elements is possibly throwing. In such case I had to make deep copy and destroy (when not trivially destructible).
So everything is built from blocks of logic depending on attributes.
In some places when I am moving elements from one to other containers there is option to skip destruction of moved elements if theirs destructor is trivial, hovever there are some types that have destructor not trivial by after move we know that they are not needing destruction as they are empty. example after moving small vector that was dynamically allocated moved from vector will be empty. So I prepared in such places functions relocate_...
The only thing (mostly) I have to do is replace std::is_trivialy_destructible in uninitialized functions with some attribute is trivialy relocatable.
I read https://quuxplusone.github.io/blog/2024/06/15/who-uses-trivial-relocation/ >5 times and I still can not figure out whats the difference from my perspective of the two approaches, my containers what I am missing...
were is the possible optimization I am missing with my approach to reduce destruction when it is not needed.
First of all I need stable implementation which is aiming at space reduction, small_vectors and static vectors are all about that compared to std::vector
Second is dynamic allocation reduction
Third is static_vector ability to use in interprocess memory as it is address independent (holding size instead of end pointer and having only in class storage)
Fourth is moving whenever possible instead of deep copy , so some kind of performance improvment.
Fifth would be relocation, already skipping destruction of trivially destructible, and still missing skipping destruction when object after move is in state it doesn't need destruction (empty after move)

So I am probably going with adl specialized function lookup
if some consteval bool adl_is_relocatable( T const * ) noexcept; returns true then will skip destruction.
Ill define it for my types, std ones and use is_trivially_destructible for default implementation of it.
Any comments, ideas, improvements to my approach ?

When You look at ex include/small_vectors/detail/vector_func.h
inline constexpr vector_outcome_e insert
when thre is reallocation it is already using uninitialized_relocate_n for non throwing So i just need to fix in inline constexpr void uninitialized_relocate_n conxtexpr condition to this adl ...
if constexpr(!std::is_trivially_destructible_v<value_type>)
std::destroy_at(std::addressof(*src));

[arturbac]

This seems to at least allow for types that are consteval capable relocatable test if destruction can be skipped
Testing if type needs explicit destruction even when empty as constexpr context must free all dynamic memory allocated in context

#include <concepts>
#include <type_traits>
#include <memory>
#include <vector>
#include <string>

template <typename T, typename = void>
struct is_constexpr_constructible_t : std::false_type {};


template <typename T>
struct is_constexpr_constructible_t<T, std::void_t<decltype(T())>> 
    : std::bool_constant<noexcept(T()) > {};

template <typename T>
inline constexpr bool is_constexpr_constructible_v = is_constexpr_constructible_t<T>::value;

template <typename T>
concept constexpr_constructible = is_constexpr_constructible_v<T>;


template<typename T>
constexpr bool simple_relocation_test()
{
    std::allocator<T> alloc;
    auto ptr{alloc.allocate(1)};
    std::construct_at(ptr);
    T tmp{std::move(*ptr)};
    alloc.deallocate(ptr, 1);
    return true;
}
template<typename T>
consteval auto is_reclocation_non_destructible() noexcept -> bool
  {
  if constexpr(std::is_trivially_destructible_v<T>)
    return true;
  else if constexpr (constexpr_constructible<T>)
    {
    return simple_relocation_test<T>();
    }
  return false;
  }

template<typename T>
concept simple_reclocatable =is_reclocation_non_destructible<T>();

struct constexpr_type
  {
  constexpr constexpr_type() = default;
  constexpr ~constexpr_type() = default;
  };

struct non_constexpr_type
  {
  non_constexpr_type() {}

  ~non_constexpr_type() {}
  };
struct non_trivial_t
  {
  int * ptr_;

  constexpr non_trivial_t() : ptr_{new int()} {}

  constexpr non_trivial_t(non_trivial_t const & rh) : ptr_{new int(*rh.ptr_)} {}

  constexpr ~non_trivial_t() { delete ptr_; }
  };
  
static_assert(constexpr_constructible<constexpr_type>);
static_assert(!constexpr_constructible<non_constexpr_type>);
static_assert(!constexpr_constructible<non_trivial_t>);

static_assert(simple_reclocatable<int>);
static_assert(simple_reclocatable<std::string>);
static_assert(simple_reclocatable<std::vector<int>>);
static_assert(simple_reclocatable<constexpr_type>);
static_assert(!simple_reclocatable<non_constexpr_type>);
static_assert(!simple_reclocatable<non_trivial_t>);

clang18 + llvmlibc++

[Quuxplusone]

I read https://quuxplusone.github.io/blog/2024/06/15/who-uses-trivial-relocation/ >5 times and I still cannot figure out what's the difference from my perspective of the two approaches, my containers what I am missing... where is the possible optimization I am missing with my approach to reduce destruction when it is not needed.

IIUC, the instances of uninitialized_relocate_n in your current insert are executed only when insert causes reallocation. (That is, they're optimizing "reallocation", not "insertion" per se.)
The "insertion" optimization that you could be doing is basically to replace these lines:

  detail::uninitialized_move_n(unext(itpos, uninit_move_pos), u_new_el_count, unext(itpos, old_el_count));
  vec.set_size_priv_(nic_sum(my.size(), u_new_el_count));
  std::move_backward(itpos, unext(itpos, uninit_move_pos), unext(itpos, nic_sum(u_new_el_count, uninit_move_pos)));
  std::copy(itbeg, itend, itpos);

with:

  // Assuming T is trivially relocatable and nothrow constructible,
  // then trivially relocate upward to "open a window" and then construct the new elements into place.
  // If we think any of these lines might throw, then we shouldn't take this codepath.
  vec.set_size_priv_(nic_sum(my.size(), u_new_el_count));
  detail::uninitialized_relocate_backward(itpos, unext(itpos, old_el_count), unext(itpos, u_new_el_count));
  std::uninitialized_copy(itbeg, itend, itpos);

This replaces ((move-construct + move-assign) + copy-assign) with (memmove + copy-construct).

folly::fbvector goes a little bit further and permits std::uninitialized_copy to throw; if an exception is thrown, then we catch it, memmove the old elements leftward to "close the window" again, and then rethrow the exception. This gives the strong exception guarantee.

---

Are you concerned about making your container work both with constexpr and without constexpr? Usually, the right approach there is simply to guard the optimized codepath under if (!std::is_constant_evaluated()), so that when your container is being used at compile time it simply doesn't try to use memmove at all. Does that advice help with any of your concerns, or am I missing the point?

---

Re: the rest of your comments, I'll have to read them again in a few days when I have more time.

[arturbac]

Thanks for insert hint You are right.
Whith the code above is_constexpr_constructible_t is actually not right, I have difficulties using SFINAE for simple_relocation_test() as it requires T to be constexpr constructible but I i cannot find a way to make such type trait or concept. Anyway this simple_relocation_test may be wrong as assumes the only reason for calling destruction is to free memory resources, but there could be some types using ex FILE handles which will pass test but will not be trivialy destructible in reality.

[arturbac]

folly::fbvector goes a little bit further and permits std::uninitialized_copy to throw; if an exception is thrown, then we catch it, memmove the old elements leftward to "close the window" again, and then rethrow the exception. This gives the strong exception guarantee.

I wonder if it is worth doing so, as catching exception with try catch is much slower than simple raii unwinding which I am using in code when no exception is thrown.

[Quuxplusone]

catching exception with try catch is much slower than simple raii unwinding

Actually, yeah, Folly uses an RAII ScopeGuard object to implement this. The point is just that you need something with the pattern

trivially relocate to open the window
try {
  construct the new elements (which might throw)
} but if an exception is thrown, then {
  destroy the new elements (`std::uninitialized_copy` does this automatically, btw)
  trivially relocate to close the window
  propagate the exception
}

It doesn't matter, semantically, if that's a ScopeGuard or if it's a try/catch block.

[arturbac]

but this approach still has a catch .. When exception is thrown and You want to move back elements to restore valid state nothing will prevent another exception to be thrown ...
This is not 100% safe approach IMHO. It is easy to imagine having some resource allocated during copy/move and exhausting it at some point of copy/move. Then first such case during this approach will cause situation that You will have to do std::terminate or leave container with undefined state ..

[Quuxplusone]

but this approach still has a catch .. When exception is thrown and You want to move back elements to restore valid state nothing will prevent another exception to be thrown ...

The only operations performed in the catch-block (during unwinding) are

• call destructors
• trivially relocate (i.e., memmove)

and neither of those operations can ever throw. (memmove definitely never throws. Destructors can throw, but you can gate the optimization on is_nothrow_destructible_v<T> if you're worried about that.)

It is true that you cannot use this optimization for every type T. It works only for types that are trivially relocatable. For non-trivially relocatable types, you have to continue using the insert/erase implementation that you already have (i.e., the implementation based on assignment). You would dispatch to one implementation or the other, based on if constexpr (is_trivially_relocatable_v<T> && is_nothrow_destructible_v<T>).

(You probably can assume is_nothrow_destructible_v<T>. The STL itself requires that destructors never throw at runtime, although it permits them to be non-noexcept at compile time.)