Compiler Explorer

Source code

#include "https://raw.githubusercontent.com/DenisYaroshevskiy/algorithm_dumpster/master/single_headers/pack_single_header.h"

#include <iterator>
#include <type_traits>
#include <utility>

namespace unsq {
namespace _drill_down {

struct error_t {};

template <typename T>
struct type_t {
 using type = T;
};

template <typename T>
constexpr auto equivalent() {
 if constexpr (std::is_integral_v<T>)
 return type_t<T>{};
 else if constexpr (std::is_enum_v<T>)
 return type_t<std::underlying_type<T>>{};
 else if constexpr (std::is_pointer_v<T>) {
 static_assert(sizeof(T) == sizeof(std::int64_t));
 return type_t<std::int64_t>{};
 }
 // you asked for this
 else if constexpr (sizeof(T) == 1)
 return type_t<std::uint8_t>{};
 else if constexpr (sizeof(T) == 2)
 return type_t<std::uint16_t>{};
 else if constexpr (sizeof(T) == 4)
 return type_t<std::uint32_t>{};
 else if constexpr (sizeof(T) == 8)
 return type_t<std::uint64_t>{};
 else
 return error_t{};
}

template <typename>
struct is_const_pointer : std::false_type {};

template <typename T>
struct is_const_pointer<const T*> : std::true_type {};

}  // namespace _drill_down

template <typename I>
using ValueType = typename std::iterator_traits::value_type;

template <typename T>
using equivalent = typename decltype(_drill_down::equivalent<T>())::type;

template <typename I>
auto* drill_down(I _it) {
 using T = equivalent<ValueType>;
 auto* res = &*_it;
 if constexpr (_drill_down::is_const_pointer<decltype(res)>{}) {
 return reinterpret_cast<const T*>(&*_it);
 } else {
 return reinterpret_cast<T*>(&*_it);
 }
}

template <typename I>
// require ContigiousIterator
auto drill_down_range(I _f, I _l) {
 auto* f = drill_down(_f);
 auto* l = f + (_l - _f);

return std::pair{f, l};
}

template <typename I, typename T>
I undo_drill_down(I _f, T* f) {
 return _f + (f - drill_down(_f));
}

}  // namespace unsq

namespace unsq {
namespace _remove {

// Figure out a safe load. (| - page boundary)
// [f | l] => Ok from f, Ok from l - width
// [|f l] => Ok from f, Not Ok from l - width
// [f, l|] => Not ok from f, Ok from l - width
template <typename Pack, typename T>
std::pair<T*, simd::top_bits<simd::vbool_t<Pack>>> figure_out_safe_load(T* f, T* l) {
 using vbool = simd::vbool_t<Pack>;
 constexpr std::ptrdiff_t width = simd::size_v<Pack>;

T* page_boundary = simd::end_of_page(f);

if (page_boundary - f < width) {
 T* safe = l - width;
 return {safe, simd::ignore_first_n_mask<vbool>(f - safe)};
 }

return {f, simd::ignore_last_n_mask<vbool>(f + width - l)};
}

}  // namespace _remove

template <std::size_t width, typename I, typename PV>
// require ContigiousIterator && VectorPredicate<PV, equivalent<ValueType>
I remove_if(I _f, I _l, PV p) {
 using T = equivalent<ValueType>;
 auto [f, l] = unsq::drill_down_range(_f, _l);
 T* o = f;

using pack = simd::pack<T, width>;
 using vbool = simd::vbool_t<pack>;

// There is a tradeoff between doing aligned reads and more comresses
  // and unaligned with less compresses.
  // For now I do unaligned.

auto get_mmask = [&](const pack& ts) {
    const vbool test = p(ts);
    return ~get_top_bits(test); // p marks trues to remove
  };

while ((l - f) >= static_cast<std::ptrdiff_t>(width))
 {
 const pack ts = simd::load_unaligned<pack>(f);
 const auto mmask = get_mmask(ts);
 o = simd::compress_store_unsafe(o, ts, mmask);
 f += width;
 }

auto [safe, mmask_filter] = _remove::figure_out_safe_load<pack>(f, l);

const pack ts = simd::load_unaligned<pack>(safe);
 auto mmask = get_mmask(ts);
 mmask &= mmask_filter;

o = simd::compress_store_masked(o, ts, mmask);
  return unsq::undo_drill_down(_f, o);
}

template <std::size_t width, typename I, typename T>
I remove(I f, I l, const T& x) {
 using U = equivalent<ValueType>;
 using pack = simd::pack<U, width>;

auto xs = simd::set_all<pack>((U)x);

return unsq::remove_if<width>(f, l, [&](const pack& read) {
 return simd::equal_pairwise(read, xs);
 });
}

}  // namespace unsq

using type = char;
constexpr std::size_t width = 16;

type* remove_zeroes(type* f, type* l) {
 return unsq::remove<width>(f, l, 0);
}