Proof-of-concept of an array-of-arrays implementations of an ordered multi-set

1-plot.md

ListLogLogPlot[
 {{{2^16, 0.017},
   {2^17, 0.039},
   {2^18, 0.091},
   {2^19, 0.236},
   {2^20, 0.631},
   {2^21, 1.745},
   {2^22, 5.034},
   {2^23, 14.535},
   {2^24, 40.234}},
  {{2^16, 0.015},
   {2^17, 0.029},
   {2^18, 0.063},
   {2^19, 0.142},
   {2^20, 0.333},
   {2^21, 0.796},
   {2^22, 1.856},
   {2^23, 4.317},
   {2^24, 10.182}}},
 Joined -> True]

2-vvmultiset.cpp

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory>
#include <set>

// https://en.wikipedia.org/wiki/Permuted_congruential_generator#Example_code
struct random_t {
    uint64_t state = 0x4d595df4d0f33173u;
    static constexpr uint64_t multiplier = 6364136223846793005u;
    static constexpr uint64_t increment = 1442695040888963407u;

    static uint32_t rotr32(uint32_t x, unsigned r) {
        return x >> r | x << ((32 - r) & 31);
    }

    void uniform(uint32_t& r) {
        uint64_t x = state;
        unsigned count = (unsigned)(x >> 59);
        state = x * multiplier + increment;
        x ^= x >> 18;
        r = rotr32((uint32_t)(x >> 27), count);
    }
};

template<typename T>
struct vv_multiset_t {
    struct buffer_t {
        T* ptr = nullptr;
        size_t capacity = 0;
        size_t pos = 0;
    };

    struct entry_t {
        buffer_t input_left;
        buffer_t input_right;
        buffer_t output;
        entry_t* next = nullptr;
    };

    entry_t* first_entry = nullptr;
    T* current_buffer_ptr = nullptr;
    size_t current_buffer_pos = 0;

    static constexpr size_t initial_size = 4;

    void push_buffer(T* ptr, size_t capacity) {
        if (!first_entry || first_entry->input_right.ptr) {
            entry_t* new_first_entry = new entry_t;
            new_first_entry->input_left.ptr = ptr;
            new_first_entry->input_left.capacity = capacity;
            new_first_entry->next = first_entry;
            first_entry = new_first_entry;
        } else {
            first_entry->input_right.ptr = ptr;
            first_entry->input_right.capacity = capacity;
            size_t output_capacity = first_entry->input_left.capacity + first_entry->input_right.capacity;
            first_entry->output.ptr = (T*)malloc(sizeof(T) * output_capacity);
            first_entry->output.capacity = output_capacity;
        }
    }

    void merge_step() {
        entry_t* entry = first_entry;
        while (entry) {
            if (entry->output.ptr) {
                T* move_from = nullptr;
                bool left_empty = entry->input_left.pos == entry->input_left.capacity;
                bool right_empty = entry->input_right.pos == entry->input_right.capacity;
                T* ptr_left = entry->input_left.ptr + entry->input_left.pos;
                T* ptr_right = entry->input_right.ptr + entry->input_right.pos;
                if (!left_empty && !right_empty) {
                    if (*ptr_left < *ptr_right) {
                        move_from = ptr_left;
                        entry->input_left.pos += 1;
                    } else {
                        move_from = ptr_right;
                        entry->input_right.pos += 1;
                    }
                } else if (!left_empty) {
                    move_from = ptr_left;
                    entry->input_left.pos += 1;
                } else if (!right_empty) {
                    move_from = ptr_right;
                    entry->input_right.pos += 1;
                }
                assert(move_from);
                if (move_from) {
                    T* move_to = entry->output.ptr + entry->output.pos;
                    new (move_to) T(std::move(*move_from));
                    move_from->~T();
                    entry->output.pos += 1;
                    if (entry->output.pos == entry->output.capacity) {
                        free(entry->input_left.ptr);
                        free(entry->input_right.ptr);
                        push_buffer(entry->output.ptr, entry->output.capacity);
                    }
                }
            }
            entry = entry->next;
        }
        entry_t** prev_entry_next_ptr = &first_entry;
        while (entry_t* entry = *prev_entry_next_ptr) {
            if (entry->output.ptr && entry->output.pos == entry->output.capacity) {
                *prev_entry_next_ptr = entry->next;
                free(entry);
            } else {
                prev_entry_next_ptr = &entry->next;
            }
        }
    }

    void insert(T new_value) {
        if (!current_buffer_ptr) {
            current_buffer_ptr = (T*)malloc(sizeof(T) * initial_size);
            current_buffer_pos = 0;
        }
        size_t insertion_pos = current_buffer_pos;
        while (insertion_pos > 0 && current_buffer_ptr[insertion_pos - 1] > new_value) {
            new (&current_buffer_ptr[insertion_pos]) T(std::move(current_buffer_ptr[insertion_pos - 1]));
            current_buffer_ptr[insertion_pos - 1].~T();
            insertion_pos -= 1;
        }
        new (&current_buffer_ptr[insertion_pos]) T(std::move(new_value));
        current_buffer_pos += 1;
        merge_step();
        if (current_buffer_pos == initial_size) {
            push_buffer(current_buffer_ptr, initial_size);
            current_buffer_ptr = nullptr;
        }
    }
};

int main(int argc, char const* const* argv) {
    size_t total_count;
    if (argc < 2 || !sscanf(argv[1], "0x%lx", &total_count)) {
        printf("bad arg");
        return 1;
    }
    // vv_multiset_t<uint32_t> vm;
    std::multiset<uint32_t> vm;
    random_t random;
    printf("total_count: %20lu\n", total_count);
    for (size_t i = 0; i < total_count; ++i) {
        uint32_t x;
        random.uniform(x);
        x %= 0xff;
        vm.insert(x);
        // printf("state %3lu:\n", i + 1);
        // if (vm.current_buffer_ptr) {
            // printf("  current_buffer_ptr:");
            // for (size_t i = 0; i < vm.current_buffer_pos; ++i) {
                // printf(" %3u", vm.current_buffer_ptr[i]);
            // }
            // printf("\n");
        // }
        // auto entry = vm.first_entry;
        // while (entry) {
            // printf("  entry:\n");
            // if (entry->input_left.ptr) {
                // printf("    input_left :");
                // for (size_t i = entry->input_left.pos; i < entry->input_left.capacity; ++i) {
                    // printf(" %3u", entry->input_left.ptr[i]);
                // }
                // printf("\n");
            // }
            // if (entry->input_right.ptr) {
                // printf("    input_right:");
                // for (size_t i = entry->input_right.pos; i < entry->input_right.capacity; ++i) {
                    // printf(" %3u", entry->input_right.ptr[i]);
                // }
                // printf("\n");
            // }
            // if (entry->output.ptr) {
                // printf("    output     :");
                // for (size_t i = 0; i < entry->output.pos; ++i) {
                    // printf(" %3u", entry->output.ptr[i]);
                // }
                // printf("\n");
            // }
            // entry = entry->next;
        // }
        // printf("\n");
    }
}