<commit_before>#include <stdint.h>
#include <string.h>
#include <vector>

using std::vector;

#include "per_thread.h"

void lsd_radix_sort(uint32_t *left, uint32_t *right)
{
    static per_thread<vector<uint32_t> > scratch;

    int width = right - left;
    if (!scratch.get())
        scratch.put(new vector<uint32_t>(width));
    scratch->reserve(width);
    uint32_t *cur = left, *other = &(*scratch)[0];
    uint32_t counts[256];
    /*
     * We do four passes
     * (0) input -> scratch
     * (1) scratch -> input
     * (2) input -> scratch
     * (3) scratch -> input
     *
     * So after the fourth pass, the input array is sorted and back in
     * the original storage.
     */

    for (int digit = 0; digit < 4; digit++) {
        memset(counts, 0, sizeof counts);
        for (int i = 0; i < width; i++) {
            counts[(cur[i] >> (8 * digit)) & 0xFF]++;
        }
        int total = 0;
        for (int i = 0; i < 256; i++) {
            int tmp = counts[i];
            counts[i] = total;
            total += tmp;
        }
        for (int i = 0; i < width; i++) {
            int d = (cur[i] >> (8 * digit)) & 0xFF;
            other[counts[d]++] = cur[i];
        }
        uint32_t *tmp = cur;
        cur = other;
        other = tmp;
    }
}
<commit_msg>lsd_radix_sort: Reduce passes over the buffer.<commit_after>#include <stdint.h>
#include <string.h>
#include <vector>

using std::vector;

#include "per_thread.h"

void lsd_radix_sort(uint32_t *left, uint32_t *right)
{
    static per_thread<vector<uint32_t> > scratch;

    int width = right - left;
    if (!scratch.get())
        scratch.put(new vector<uint32_t>(width));
    scratch->reserve(width);
    uint32_t *cur = left, *other = &(*scratch)[0];
    uint32_t counts[4][256];
    /*
     * We do four passes
     * (0) input -> scratch
     * (1) scratch -> input
     * (2) input -> scratch
     * (3) scratch -> input
     *
     * So after the fourth pass, the input array is sorted and back in
     * the original storage.
     */

    memset(counts, 0, sizeof counts);
    for (int i = 0; i < width; i++) {
        counts[0][(cur[i] >> 0 ) & 0xFF]++;
        counts[1][(cur[i] >> 8 ) & 0xFF]++;
        counts[2][(cur[i] >> 16) & 0xFF]++;
        counts[3][(cur[i] >> 24) & 0xFF]++;
    }

    for (int digit = 0; digit < 4; digit++) {
        int total = 0;
        for (int i = 0; i < 256; i++) {
            int tmp = counts[digit][i];
            counts[digit][i] = total;
            total += tmp;
        }
        for (int i = 0; i < width; i++) {
            int d = (cur[i] >> (8 * digit)) & 0xFF;
            other[counts[digit][d]++] = cur[i];
        }
        uint32_t *tmp = cur;
        cur = other;
        other = tmp;
    }
}

{'fraction_non_alphanumeric': 0.16581632653061223, 'fraction_numerical': 0.03097667638483965, 'mean_word_length': 1.9675675675675677, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3772992', 'n_tokens_mistral': 1022, 'n_tokens_neox': 973, 'n_words': 267}