2
\$\begingroup\$

Introduction and context

I am working on a small application which involves sorting 20GB files as one of the operations. This is being done, due to memory constraints, by breaking them into ~1GB chunks, sorting in memory and then writing back to disk. Then, as stage 2, reading the head of each file and picking the smallest/largest and streaming to the final output file.

This falls into the domain of External sorting.

This CR will focus on just one small part of that which involves "picking which chunk to take the next element from" when streaming to the final file. It turns out that this part, and specifically the element comparison, is CPU bound and the bottleneck. The elements being sorted are std::array<std::byte, 20>, so a non-trivial comparison, which compiles down to memcmp.

EDIT It turns out that we can be significantly faster than memcmp with some very simple "big 64-bits load, byte-swap and compares".

See my self answer below END-EDIT

So we need a data structure which makes it easy to pick the next element. Typically there are around 20 chunks, so my first attempt was just using std::min_element because linear search can be really fast for a small number of elements. When I discovered the comparisons were the CPU bottleneck I moved to using a std::priority_queue. This reduced the comparisons by > 2x, so that was a big gain.

For clarification, that reduction in the number of comparisons, also brought a 2x speed up in the full application, from 6mins for the merge stage of the 20 x 1GB files, down to 3mins. But at 3mins, the CPU is still @ 100% and almost all inside the operator< of the 20 byte array.

This CR is about whether we can do better still, by reducing the number of comparisons further.

You cannot change/update elements in a std::priority_queue, and that is exactly what we we need to do. This is the algorithm of the critical loop

  std::priority_queue<head, std::vector<head>, decltype(cmp)> heads(cmp);

  while (!heads.empty()) {
    const head& t = heads.top();
    sorted.write(t.value);
    std::size_t chunk_idx = t.idx;
    heads.pop();
    if (auto& chunk = chunks[chunk_idx]; chunk.current != chunk.end) {
      heads.push({*(chunk.current), chunk_idx});
      ++(chunk.current);
    }
  }

So, it seems very inefficient to call queue.pop() and then queue.push() both of which need to move elements through the heap. It would seem more efficient to just "change" the .top() (having read it and written it to output), to the new value (essentially calling std::next or ++ on the iterator of that chunk) and then "re-heapifying".

Let get under the hood of std::priority_queue. The canonical way to do this using the c++ STL heap algorithms is:

  // Note I am using a max-heap, but the comparator is customisable below
  std::pop_heap(heap.begin(), heap.end(), comp);
  heap.pop_back();
  heap.push_back(newval);
  std::push_heap(heap.begin(), heap.end(), comp);

Most heap implementations use primitives underneath called something like "bubble/sift up/down". All we actually need is the bubble_down implementation and call that on the changed, top() element.

The c++ standard does not offer primitives, but implementations are not hard and there are 2 (one iterative and one recursive) in the code below.

Investigation Focus

  1. Relatively small heaps (3 => 100 elements, but easily adjustable in code below)
  2. Operation: Update the heap.top() element ONLY
  3. Optimisation criteria = number of comparisons to re-heapify

This is a very simple case. No question of "knowing where the element to be changed is in the heap" - a typical concern with this approach. So surely we can do better, right...?

The code below studies 4 implementations:

  1. STL way as above (using libstdc++-11). This is the base case. (Note that I believe libc++ is less sophisticated in this area).
  2. A recursive "bubble down" algo
  3. An iterative "bubble down" algo
  4. A libstd++ __adjust_heap followed by __push_heap algo

I generate random heap sizes, contents and replacement value and iterate 1M times.

Findings

  1. The STL is Good
  2. The recursive and iterative bubble down alogs are nearly identical (expected, because the compiler, on -O3, "tailcall optimises" the recursion away) and, surprisingly, consistently have more comparisons than the STL even for this very specialised case. So just using a heap-primitive doesn't give you any gains.
  3. We can beat the STL using... the STL , by copying out the code of the unpublished functions, "cleaning them up" (of underscores etc) and using them in a specialised way to solve this limited, specialised problem. Gains are in the order of 10-20%. A modest, but significant gain?

Typical results:

method                              avg_cmp_cnt
std::heap / std::priority_queue     7.568285
bubble up recursively               8.031054
bubble up iteratively               8.047352
libstc++ __adjust_heap              6.327297

The code:

#include "fmt/core.h"
#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <cstdlib>
#include <execution>
#include <iostream>
#include <random>
#include <stdexcept>

template <std::unsigned_integral T>
T log2(T x) {
  T log = 0;
  while (x >>= 1U) ++log;
  return log;
}

template <typename T, typename Comp = std::less<>>
void print_heap(const std::vector<T>& heap, Comp comp = {}) {
  std::size_t levels = log2(heap.size()) + 1;
  unsigned    width  = 6 * (1U << (levels - 1U));
  std::cout << "\n\n";
  for (const auto& e: heap) std::cout << e << " ";
  std::cout << "\n";
  std::cout << fmt::format("is_heap = {:}\n\n", std::is_heap(heap.begin(), heap.end(), comp));
  if (heap.empty()) {
    std::cout << "<empty heap>\n";
    return;
  }
  unsigned idx  = 0;
  bool     done = false;
  for (unsigned l = 0; l != levels; ++l) {
    for (unsigned e = 0; e != 1U << l; ++e) {
      std::cout << fmt::format("{:^{}}", heap[idx], width);
      ++idx;
      if (idx == heap.size()) {
        done = true;
        break;
      }
    }
    width /= 2;
    std::cout << "\n\n";
    if (done) break;
  }
}

template <typename T, typename Comp = std::less<>>
void replace_top_using_stl(std::vector<T>& heap, T newval, Comp comp = {}) {

  if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");

  assert(std::is_heap(heap.begin(), heap.end(), comp));

  std::pop_heap(heap.begin(), heap.end(), comp);
  heap.pop_back();
  heap.push_back(newval);
  std::push_heap(heap.begin(), heap.end(), comp);
}

template <typename T, typename Comp = std::less<>>
// NOLINTNEXTLINE recursion is tailcall eliminated by compiler
void bubble_down_recursively(std::vector<T>& heap, std::size_t i, Comp comp = {}) {
  const auto left  = 2 * i + 1;
  const auto right = 2 * i + 2;
  const auto n     = heap.size();

  using std::swap; // enable ADL

  if (left >= n) { // no children
    return;
  } else if (right >= n) { // left exists right does not.  NOLINT else after return
    if (comp(heap[i], heap[left])) {
      swap(heap[i], heap[left]);
      bubble_down_recursively(heap, left, comp);
    }
  } else { // both children exist
    // 'larger' is only well named if comp = std::less<>{}
    auto larger = comp(heap[right], heap[left]) ? left : right;
    if (comp(heap[i], heap[larger])) {
      swap(heap[i], heap[larger]);
      bubble_down_recursively(heap, larger, comp);
    }
  }
}

template <typename T, typename Comp = std::less<>>
void replace_top_using_bubble_down_recursively(std::vector<T>& heap, T newval, Comp comp = {}) {

  if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");

  assert(std::is_heap(heap.begin(), heap.end(), comp));

  heap[0] = newval;
  bubble_down_recursively(heap, 0, comp);
}

template <typename T, typename Comp = std::less<>>
void bubble_down_iteratively(std::vector<T>& heap, std::size_t i, Comp comp = {}) {
  const auto n = heap.size();

  while (true) {
    const std::size_t left  = 2 * i + 1;
    const std::size_t right = 2 * i + 2;

    std::size_t largest = i;

    if ((left < n) && comp(heap[largest], heap[left])) {
      largest = left;
    }
    if ((right < n) && comp(heap[largest], heap[right])) {
      largest = right;
    }

    if (largest == i) {
      break;
    }

    using std::swap; // enable ADL
    swap(heap[i], heap[largest]);
    i = largest;
  }
}

template <typename T, typename Comp = std::less<>>
void replace_top_using_bubble_down_iteratively(std::vector<T>& heap, T newval, Comp comp = {}) {

  if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");

  assert(std::is_heap(heap.begin(), heap.end(), comp));

  heap[0] = newval;                       // stick it in anyway
  bubble_down_iteratively(heap, 0, comp); // and fix the heap
}

// borrowed from libstdc++ __push_heap
template <typename RandomAccessIterator, typename Distance, typename Tp, typename Compare>
constexpr void push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex,
                         Tp value, Compare& comp) {
  Distance parent = (holeIndex - 1) / 2;
  while (holeIndex > topIndex && comp(*(first + parent), value)) {
    *(first + holeIndex) = *(first + parent);
    holeIndex            = parent;
    parent               = (holeIndex - 1) / 2;
  }
  *(first + holeIndex) = std::move(value);
}

// borrowed from libstdc++ __adjust_heap
template <typename RandomAccessIterator, typename Distance, typename Tp, typename Compare>
constexpr void adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, Tp value,
                           Compare comp) {
  const Distance topIndex    = holeIndex;
  Distance       secondChild = holeIndex;
  while (secondChild < (len - 1) / 2) {
    secondChild = 2 * (secondChild + 1);
    if (comp(*(first + secondChild), *(first + (secondChild - 1)))) secondChild--;
    *(first + holeIndex) = *(first + secondChild);
    holeIndex            = secondChild;
  }
  if ((len & 1) == 0 && secondChild == (len - 2) / 2) {
    secondChild          = 2 * (secondChild + 1);
    *(first + holeIndex) = *(first + (secondChild - 1));
    holeIndex            = secondChild - 1;
  }
  push_heap(first, holeIndex, topIndex, value, comp);
}

template <typename T, typename Comp = std::less<>>
void replace_top_using_adjust_heap(std::vector<T>& heap, T newval, Comp comp = {}) {

  if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");

  assert(std::is_heap(heap.begin(), heap.end(), comp));

  heap[0] = newval;
  adjust_heap(heap.begin(), 0L, heap.end() - heap.begin(), newval, comp);
}

template <typename T>
struct cmp_counter {
  static std::size_t cmpcount; // NOLINT must be static because STL takes Comp by value
  bool               operator()(T a, T b) {
    ++cmpcount;
    return a < b; // effectively std::less<>{};
  }
  static void reset() { cmpcount = 0; }
};
template <typename T>
std::size_t cmp_counter<T>::cmpcount = 0; // NOLINT global static

int main() {

  using ValueType = int;
  
  struct method {
    using cb_t = void (*)(std::vector<ValueType>&, ValueType, cmp_counter<ValueType>);
    std::string label;
    cb_t        cb;
  };
  auto methods = std::vector<method>{
      {"std::heap / std::priority_queue", &replace_top_using_stl},
      {"bubble up recursively", &replace_top_using_bubble_down_recursively},
      {"bubble up iteratively", &replace_top_using_bubble_down_iteratively},
      {"libstc++ __adjust_heap", &replace_top_using_adjust_heap},
  };

  std::cout << fmt::format("{:35s} {:s}\n", "method", "avg_cmp_cnt");
  for (auto& method: methods) {
    auto prng              = std::mt19937_64(1); // NOLINT fixed seed for repeatability
    auto heap_element_dist = std::uniform_int_distribution<>(1, 100);
    auto heap_size_dist    = std::uniform_int_distribution<std::size_t>(3, 100);

    const std::size_t number_of_trials = 1'000'000;

    std::size_t total_cmpcount = 0;
    cmp_counter<ValueType> comp;
    for (unsigned i = 0; i != number_of_trials; ++i) {
      std::vector<int> h(heap_size_dist(prng));
      std::generate(h.begin(), h.end(), [&] { return ValueType(heap_element_dist(prng)); });

      std::make_heap(h.begin(), h.end(), comp);

      auto newval = ValueType(heap_element_dist(prng));
      cmp_counter<ValueType>::reset();
      method.cb(h, newval, comp);
      total_cmpcount += cmp_counter<ValueType>::cmpcount;

      if (!std::is_heap(h.begin(), h.end(), comp)) {
        std::cerr << method.label << "NOT A HEAP ANYMORE!!\n";
        return EXIT_FAILURE;
      }
    }
    std::cout << fmt::format("{:35s} {:f}\n", method.label,
                             double(total_cmpcount) / number_of_trials);
  }
}
\$\endgroup\$
12
  • \$\begingroup\$ Not sure that the best metric is the compare count. \$\endgroup\$ Mar 8, 2022 at 18:16
  • \$\begingroup\$ @MartinYork I would argue it is for my use case, because the CPU is spending > 80% in comparing 2 std::array<std::byte, 20>. I proved that to be the case. I am trying to "reduce the thing that the CPU is spending all its time on". And that for me is the no of comparisons, because I doubt I can improve memcmp. TBH, no of comparisons is also a very standard metric for sorting algorithms? (Note that this code is using ValueType = int, for ease of debugging and printing, which is perhaps misleading. The actual application is 20 byte arrays, as explained). \$\endgroup\$ Mar 8, 2022 at 18:20
  • \$\begingroup\$ @MartinYork When I switched from std::min_element to std::priority_queue and the number of comparisons more than halved, the wall clock execution time for the merge stage went from 6mins to 3mins. And it's still all at 100% CPU. All in operator< for the 20 byte array. Unbelievably for me, the bottleneck is NOT the disk for this stage. \$\endgroup\$ Mar 8, 2022 at 18:26
  • 2
    \$\begingroup\$ @OliverSchönrock The problem was the assert(std::is_heap(..., comp)) calls that were also counting, if I add -DNDEBUG to the compiler options I get the same results as you. \$\endgroup\$
    – G. Sliepen
    Mar 8, 2022 at 20:20
  • 1
    \$\begingroup\$ Are your structures padded to full 4 or 8 bytes? If you use a 1-byte alignment and store data in an array, the 20-byte arrays in consecutive elements may be mis-aligned with respect to each other. Then memcmp can not optimize memory access with long word reads and must iterate byte by byte in the worst case. (That, however, should not matter, as hash keys should need just one byte comparison in 255/256 cases on average... provided they are quite well distributed.) \$\endgroup\$
    – CiaPan
    Mar 9, 2022 at 9:33

3 Answers 3

2
\$\begingroup\$

Minimizing comparisons

All the algorithms you have tested need \$O(\log N)\$ comparisons. The __adjust_heap() method seems to save about one comparison on average. I am not sure if you can do much better than that using heaps or trees to sort the priority queue.

It might be possible to do a space vs. time tradeoff. If you could find a way to compress the keys such that the index into an array of buckets that is several times larger than the number of chunks, then inserting or removing a key from that array would on average not need any comparisons, as a bucket would most likely be empty on insertion or have 1 element on removal. Then the remaining problem is finding the first bucket with an item in it, which would have its own cost that scales with the number of buckets, but which can probably be done very cheaply. The trick is then finding a balance so maintaining this array is cheaper than maintaining a heap.

As for the code itself:

Use std::ranges

You are using C++20 features, but I'm missing the use of std::ranges, which would simplify some of the code.

Use std::bit_width() to implement log2()

I am a bit surprised that both GCC and Clang did not manage to optimize your naive implementation of the integer base-2 logarithm. But if you use std::bit_width() - 1, they manage to replace the loop with a lzcnt instruction on x86 architectures.

Make your code even more generic

You did make a significant effort to make your code generic by templating it on the value type of the container and on the comparison functions, however you should be able to make it work on containers other than std::vector. I would just copy the interface of std::ranges::pop_heap() and related functions.

For extra fun, you could make cmp_counter() a function adapter, that by default adapts std::less but that would allow you to have it add a counter to any comparison operator.

Make use of front() and back()

Especially if you make your code more generic, you shouldn't assume that the containers are random accessible, and avoid code like heap[0] = .... Instead you can write things like:

heap.front() = newval;

And you can replace the pop() and push() operations with a single heap.back() = newval inside replace_top_using_stl().

Add more static and const

I already see good use of const, but no static outside of cmp_counter. Consider making most functions static. Furthermore, you can use const in more cases. And in particular, methods can be made a static const array.

Inconsistent use of fmt::format()

I see fmt::format() in a few places, but in other cases you just concatenate output using <<. I recommend using fmt::format() consistently. Even better, avoid having to write std::cout << by using fmt::print().

\$\endgroup\$
19
  • \$\begingroup\$ Good comments. I will think about the algorithmic nuggets. I started with more ranges, but there are still annoying gaps in it. I think it was std::generate here, and the the code slides torwards iterators. TBH, ranges i nice for me not because of begin and end, or becaue the | but because of proj support. I thought about containers other than vector, but really given the random access, nothing else will really do. good comments about static I don't fmt::print because unfortunately it won't be in std until c++23, so I am in the unsatisfying "in between land". \$\endgroup\$ Mar 8, 2022 at 21:22
  • 1
    \$\begingroup\$ I had the for over vector as fmt::format("{}", v) but then I put a different value type which implemented operator<< implemented and it no longer worked... so back to std::cout <<. Fair comment on front() back(), this was just lazy code, I would not "commit" that. Wan't aware of std::bit_width, so that's good. Re being generic When I splice this into the main code (if I do, because even 20% seems like not enough to make a real difference) I would use the std::ranges type signatures with Proj proj = std:identity. \$\endgroup\$ Mar 8, 2022 at 21:27
  • 2
    \$\begingroup\$ This is a good way to find "asserts with side effects": stackoverflow.com/a/35294344/1087626 and it finds those cmpcount ones in my code very easily! \$\endgroup\$ Mar 8, 2022 at 21:36
  • 1
    \$\begingroup\$ Oh, I didn't know about that trick, very nice! As for fmt vs std, unfortunately it seems like the standard library is much further behind on the latest standards than the compilers themselves, I've also found gaps in ranges support. So even in 2023 you might still not effectively have std::print. \$\endgroup\$
    – G. Sliepen
    Mar 8, 2022 at 21:39
  • 1
    \$\begingroup\$ There's nothing wrong with a static const C-array IMO. The answer below is not an answer to your original question. But if it's faster and you are no longer CPU-bound, that is great! \$\endgroup\$
    – G. Sliepen
    Mar 9, 2022 at 8:16
3
\$\begingroup\$

Don't assume you can't beat memcmp

This is not directly an answer to the algorithm focused CR above, however, it does successfully challenge the implicit assumption that "we can't beat memcmp" - with spectacular results.

If std::array<std::byte, 20>::operator< comparisons are the bottleneck, then we can:

  1. reduce the number of comparisons
  2. make those comparisons faster

The above CR, and its accepted answer, focus on 1.

It turns out that the potential for improvements is greater in 2.

In other words, it's relatively easy to "squeeze more out of the hardware" in doing those comparisons. To go faster than memcmp, by using the 64-bit bus and registers rather than compare a byte at a time, or whatever your version of memcmp is doing.

String Intrinsics are fast

The code below is not pretty and not entirely portable. It can probably be made portable, with some effort.

The first approach was to use the _mm_cmpestri intrinsic, available with -msse4.2, for the first 16 bytes and then use a uint32_t comparison for the last 4 bytes:

  bool operator<(const pawned_pw& rhs) const {

    const __m128i simd_a = _mm_loadu_si128((__m128i*)(&hash));
    const __m128i simd_b = _mm_loadu_si128((__m128i*)(&rhs.hash));

    auto res = static_cast<unsigned>(_mm_cmpestri(simd_a, 16, simd_b, 16,
                                                  unsigned(_SIDD_CMP_EQUAL_EACH) |
                                                      unsigned(_SIDD_NEGATIVE_POLARITY) |
                                                      unsigned(_SIDD_UBYTE_OPS)));

    if (res != 16) {
      return hash[res] < rhs.hash[res]; // something in first 16 bytes differs
    }

    // this compiles to a load and `bswap` which should be cheap
    std::uint32_t tail     = __builtin_bswap32(*(std::uint32_t*)(&hash[16]));
    std::uint32_t rhs_tail = __builtin_bswap32(*(std::uint32_t*)(&rhs.hash[16]));
    return tail < rhs_tail;
  }

Simple, 64-bit unsigned ints are even faster

Once we have figured out how to do the necessary byte order reversal on the typical little endian systems, we can just go all the way, and do the first 16 bytes using 2 x 64-bit compares as well. It turns out this is significantly faster than the more sophisticated string compare intrinsic.

  bool operator<(const pawned_pw& rhs) const {

    // this compiles to a load and `bswap` which should be cheap
    // measured > 33% faster than hash < rhs.hash
    std::uint64_t head     = __builtin_bswap64(*(std::uint64_t*)(&hash[0]));
    std::uint64_t rhs_head = __builtin_bswap64(*(std::uint64_t*)(&rhs.hash[0]));
    if (head != rhs_head) return head < rhs_head;

    std::uint64_t mid     = __builtin_bswap64(*(std::uint64_t*)(&hash[8]));
    std::uint64_t rhs_mid = __builtin_bswap64(*(std::uint64_t*)(&rhs.hash[8]));
    if (mid != rhs_mid) return mid < rhs_mid;

    std::uint32_t tail     = __builtin_bswap32(*(std::uint32_t*)(&hash[16]));
    std::uint32_t rhs_tail = __builtin_bswap32(*(std::uint32_t*)(&rhs.hash[16]));
    return tail < rhs_tail;
  }

This implementation of operator< is ~50% (or 2x) faster than the naive hash < rhs.hash which calls memcmp.

That means the merge stage of the main application is now > 33% faster. ie from 3mins down to ~1:50min; a very significant gain. This is still using the std::priority_queue so we can harvest the gains from __adjust_heap as well, and they will be additive.

Although not fully additiive, as we are now in the happy position of the merge stage no longer being CPU bound. CPU now at ~75-80%.

Retain flexibility

For a slight bit of polish, we can notice that intrinsics much are nicer than embedded assembly, because they allow us to easily mix modern c++ features with low level machine instructions. Here, it turns out that we can trivially modify the above to support the c++20 operator<=>:

  std::strong_ordering operator<=>(const pawned_pw& rhs) const {

    // this compiles to a load and `bswap` which should be cheap
    // measured > 33% faster than hash < rhs.hash
    std::uint64_t head     = __builtin_bswap64(*(std::uint64_t*)(&hash[0]));     // NOLINT
    std::uint64_t rhs_head = __builtin_bswap64(*(std::uint64_t*)(&rhs.hash[0])); // NOLINT
    if (head != rhs_head) return head <=> rhs_head;

    std::uint64_t mid     = __builtin_bswap64(*(std::uint64_t*)(&hash[8]));     // NOLINT
    std::uint64_t rhs_mid = __builtin_bswap64(*(std::uint64_t*)(&rhs.hash[8])); // NOLINT
    if (mid != rhs_mid) return mid <=> rhs_mid;

    std::uint32_t tail     = __builtin_bswap32(*(std::uint32_t*)(&hash[16]));     // NOLINT
    std::uint32_t rhs_tail = __builtin_bswap32(*(std::uint32_t*)(&rhs.hash[16])); // NOLINT
    return tail <=> rhs_tail;
  }

And, of course, we would do operator== the same way, except we don't need to bother with the bswap for an equality comparison:

  bool operator==(const pawned_pw& rhs) const {
    std::uint64_t head     = *(std::uint64_t*)(&hash[0]);     // NOLINT
    std::uint64_t rhs_head = *(std::uint64_t*)(&rhs.hash[0]); // NOLINT
    if (head != rhs_head) return false;

    std::uint64_t mid     = *(std::uint64_t*)(&hash[8]);     // NOLINT
    std::uint64_t rhs_mid = *(std::uint64_t*)(&rhs.hash[8]); // NOLINT
    if (mid != rhs_mid) return false;

    std::uint32_t tail     = *(std::uint32_t*)(&hash[16]);     // NOLINT
    std::uint32_t rhs_tail = *(std::uint32_t*)(&rhs.hash[16]); // NOLINT
    return tail == rhs_tail;
  }

\$\endgroup\$
1
  • \$\begingroup\$ Using auto makes it nicer. \$\endgroup\$ May 29, 2022 at 15:51
1
\$\begingroup\$

Reducing the number of comparisons in heap operation
About half of the entries introduced to the heap end up being leaves.
One suggestion was to be realistic about this and
determine the path to the leaves before even looking at the new key.

/** re-heapify 0-based heap when heap[root] may break ordering below
 *    (not have priority over all its children). 
 * switched shall return true if its right operand has priority over its left. */
// index runs towards bottom of heap and bounces up to root, again
void 
bounce_iteratively(std::vector<T>& heap, std::size_t root, Comp switched = {}) {
    const auto
        n = heap.size(),
        first_leaf = n / 2,
        last_parent_of_two = (n-3) / 2;
    if (first_leaf <= root)
        return;
    std::size_t i = root;
    while (i <= last_parent_of_two) { // a first comparison per level
        const std::size_t
            left  = 2 * i + 1,
            right = left + 1;
        i = switched(heap[right], heap[left])) ? left : right;
    }
    if (i < first_leaf))// parent of one ...
        i = 2 * i + 1;  // repeated expression  // left;
  // all below can be replaced by call to (std::?)push_heap()??
    T addition = heap[root];
    using std::swap; // enable ADL
    for ( ; root < i ; i = (i-1)/2)
        if (switched(addition, heap[i])) {  // the second comparison per level
            swap(addition, heap[i]);
            break;
        }
    for ( ; root <= i ; i = (i-1)/2)
        swap(addition, heap[i]);  // no more comparisons
}

(This is actually close to what I'd expect replace_top_using_stl()'s pop_heap;pop_back;push_back;push_heap to do, esp. re. sequence of comparisons.)


- The obvious&ultimate way to reduce comparisons in a sort is to use a non-comparison sort.
  Even just partitioning the key space initially into 20 parts (to keep the number thereof) or 32 (to account for uneven distribution or perceived difficulty in computing part#), you could just keep writing/concatenate instead of merging.
- With n = 20, I'd evaluate binary search & insertion in an ordered array.
- You state alignof to report 4-byte aligned.
  While I don't see how to ruin 8-byte alignment with even numbers ([buffered] 1000 at a time) of 24(?)-byte struct pawned_pw, using alignas(8) was explicit. (24K seems a bit low for late mechanical mass storage devices - and for system calls.)

\$\endgroup\$
2
  • \$\begingroup\$ I'm increasingly out of my depth with C++, esp. modern C++. \$\endgroup\$
    – greybeard
    May 29, 2022 at 9:46
  • 1
    \$\begingroup\$ Would replacing heap.pop_back(); heap.push_back(newval); with heap.back() = newval; make any difference? \$\endgroup\$
    – greybeard
    May 29, 2022 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.