Use memmove optimisations when appropriate

[tcbrindle]

When using contiguous iterators with trivially copyable/movable value types, we should be able to optimise copy/move and their backwards versions to use std::memmove. This would have knock-on benefits for several other algorithms which end up copying or moving elements in their implementations.

Unfortunately memmove is not constexpr, so we'd need to use C++20 std::is_constant_evaluated to detect whether we're being called at compile-time (and should therefore just use the normal implementation) or at run-time. The preprocessor define __cpp_lib_is_constant_evaluated is supported in GCC and Clang to find out whether is_constant_evaluated is available, but I'm not sure about MSVC.

[tcbrindle]

Could we potentially also use memcmp is an optimisation in find, and memset as an optimisation in fill?

[jwakely]

memcmp can be used for equal. memset can be used for fill, but only for single-byte value types. Libstdc++ doesn't use memcmp or memchr or anything in find.

You can also use memcmp for lexicographical_compare but only for unsigned types, and not for types larger than a byte on little-endian processors.

[tcbrindle]

Thanks for the info Jonathan!

[CaseyCarter]

FWIW, we do use memchr for find when the needle has integer type and the haystack elements are chars and !is_constant_evaluated():

https://github.com/microsoft/STL/blob/484fbc9742f895030047977efc55dc8950a37086/stl/inc/xutility#L5423-L5426

(Yes, I have an action item to teach this about contiguous_iterators.)

[ericniebler]

When using the mem* functions from an algorithm used with raw pointers as iterators, be sure to check the pointers for null before calling the mem* functions. IIRC, they don't appreciate being called with null.

[jwakely]

IIRC, they don't appreciate being called with null.

Doing so is undefined behaviour.