sbgl_sort.h File Reference

Sorting utilities for the SBgl batching system. More...

#include "sbgl_types.h"
#include <stdint.h>

Include dependency graph for sbgl_sort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	sbgl_radix_sort (sbgl_SortKey *keys, uint32_t *values, uint32_t count, sbgl_SortKey *temp_keys, uint32_t *temp_values)
	Performs a stable radix sort on an array of 64-bit keys and associated 32-bit values.

Detailed Description

Sorting utilities for the SBgl batching system.

Definition in file sbgl_sort.h.

Function Documentation

sbgl_radix_sort()

void sbgl_radix_sort	(	sbgl_SortKey *	keys,
		uint32_t *	values,
		uint32_t	count,
		sbgl_SortKey *	temp_keys,
		uint32_t *	temp_values )

Performs a stable radix sort on an array of 64-bit keys and associated 32-bit values.

This implementation uses a Least Significant Digit (LSD) approach with 8 passes of 8-bit buckets to achieve O(N) complexity for 64-bit keys with low memory overhead.

Parameters

keys	Pointer to the array of sorting keys. Modified in place.
values	Pointer to the array of associated indices or values. Modified in place.
count	The number of elements to sort.
temp_keys	Workspace buffer for keys. Must be at least 'count' in size.
temp_values	Workspace buffer for values. Must be at least 'count' in size.

Definition at line 8 of file sbgl_sort.c.

  {
    if (count <= 1 || !temp_keys || !temp_values) {
        return;
    }
 
    sbgl_SortKey* src_keys = keys;
    sbgl_SortKey* dst_keys = temp_keys;
    uint32_t* src_values = values;
    uint32_t* dst_values = temp_values;
 
    // The system performs 8 passes, each processing 8 bits of the 64-bit key.
    // This uses 256 buckets per pass, significantly reducing cache misses and stack zeroing.
    for (int pass = 0; pass < 8; ++pass) {
        uint32_t counts[256] = { 0 };
        uint32_t offsets[256] = { 0 };
        int shift = pass * 8;
 
        // Build histogram for the current 8-bit digit.
        for (uint32_t i = 0; i < count; ++i) {
            uint8_t bucket = (uint8_t)((src_keys[i] >> shift) & 0xFF);
            counts[bucket]++;
        }
 
        // Compute prefix sums to find starting offsets for each bucket.
        uint32_t total_offset = 0;
        for (uint32_t i = 0; i < 256; ++i) {
            offsets[i] = total_offset;
            total_offset += counts[i];
        }
 
        // Scatter elements into the destination buffer based on the current digit.
        for (uint32_t i = 0; i < count; ++i) {
            uint8_t bucket = (uint8_t)((src_keys[i] >> shift) & 0xFF);
            uint32_t pos = offsets[bucket]++;
            dst_keys[pos] = src_keys[i];
            dst_values[pos] = src_values[i];
        }
 
        // Swap source and destination pointers for the next pass.
        sbgl_SortKey* tk = src_keys;
        src_keys = dst_keys;
        dst_keys = tk;
 
        uint32_t* tv = src_values;
        src_values = dst_values;
        dst_values = tv;
    }
 
    // Since 8 passes are performed, the pointers naturally swap back to the original buffers.
    // This confirms src_keys points to 'keys' and src_values points to 'values'.
}