Skip to content

Instantly share code, notes, and snippets.

@mmozeiko mmozeiko/sort.cpp
Last active Jun 16, 2019

Embed
What would you like to do?
radix sort benchmark, compile with C++11
#include <stdint.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <chrono>
typedef int32_t s32;
typedef uint32_t u32;
typedef float r32;
inline u32 FloatToU32Key(r32 Key)
{
u32 KeyBits = *((u32*)&Key);
u32 Mask = -(s32)(KeyBits >> 31) | 0x80000000;
KeyBits ^= Mask;
return KeyBits;
}
inline u32 GetByteN(u32 Value, u32 ByteIndex)
{
return (Value >> (8*ByteIndex)) & 0xFF;
}
static void RadixSort(r32 *Entries, r32* Temp, u32 Count)
{
r32 *Source = Entries;
for (u32 DigitIndex=0; DigitIndex<4; DigitIndex++)
{
u32 Counts[256] = {};
for (u32 Index=0; Index<Count; Index++)
{
u32 Key = FloatToU32Key(Source[Index]);
u32 Digit = GetByteN(Key, DigitIndex);
Counts[Digit]++;
}
u32 TotalCount = 0;
for (u32 Index=0; Index<256; Index++)
{
u32 CurrentCount = Counts[Index];
Counts[Index] = TotalCount;
TotalCount += CurrentCount;
}
for (u32 Index=0; Index<Count; Index++)
{
u32 Key = FloatToU32Key(Source[Index]);
u32 Digit = GetByteN(Key, DigitIndex);
Temp[Counts[Digit]++] = Source[Index];
}
r32 *Swap = Source;
Source = Temp;
Temp = Swap;
}
}
static void RadixSortInPlaceImpl(r32 *Entries, u32 Start, u32 End, u32 DigitIndex)
{
u32 Counts[256] = {};
for (u32 Index=Start; Index<End; Index++)
{
u32 Key = FloatToU32Key(Entries[Index]);
u32 Digit = GetByteN(Key, DigitIndex);
Counts[Digit]++;
}
u32 Offsets[256];
Offsets[0] = Start;
for (u32 Index=1; Index<256; Index++)
{
Offsets[Index] = Counts[Index-1] + Offsets[Index-1];
}
for (u32 Index=0; Index<256; Index++)
{
while (Counts[Index] > 0)
{
u32 Original = Offsets[Index];
u32 Source = Original;
r32 Key = Entries[Source];
do
{
u32 Digit = GetByteN(FloatToU32Key(Key), DigitIndex);
u32 Target = Offsets[Digit]++;
Counts[Digit]--;
r32 Temp = Entries[Target];
Entries[Target] = Key;
Key = Temp;
Source = Target;
}
while (Source != Original);
}
}
if (DigitIndex > 0)
{
for (u32 Index=0; Index<256; Index++)
{
u32 NewStart = (Index == 0 ? Start : Offsets[Index-1]);
u32 NewEnd = Offsets[Index];
if (NewEnd - NewStart > 1)
{
RadixSortInPlaceImpl(Entries, NewStart, NewEnd, DigitIndex - 1);
}
}
}
}
static void RadixSortInPlace(r32 *Entries, u32 Count)
{
RadixSortInPlaceImpl(Entries, 0, Count, 3);
}
static void InsertionSort(r32* Entries, u32 Start, u32 End)
{
for (u32 Index=Start+1; Index < End; Index++)
{
r32 Value = Entries[Index];
if (Entries[Index-1] > Value)
{
u32 Index2 = Index;
do
{
Entries[Index2] = Entries[Index2-1];
}
while (--Index2 > Start && Entries[Index2-1] > Value);
Entries[Index2] = Value;
}
}
}
static void RadixSortInPlaceImplOpt(r32 *Entries, u32 Start, u32 End, u32 DigitIndex)
{
u32 Counts[256] = {};
for (u32 Index=Start; Index<End; Index++)
{
u32 Key = FloatToU32Key(Entries[Index]);
u32 Digit = GetByteN(Key, DigitIndex);
Counts[Digit]++;
}
u32 Offsets[256];
Offsets[0] = Start;
for (u32 Index=1; Index<256; Index++)
{
Offsets[Index] = Counts[Index-1] + Offsets[Index-1];
}
for (u32 Index=0; Index<256; Index++)
{
while (Counts[Index] > 0)
{
u32 Original = Offsets[Index];
u32 Source = Original;
r32 Key = Entries[Source];
do
{
u32 Digit = GetByteN(FloatToU32Key(Key), DigitIndex);
u32 Target = Offsets[Digit]++;
Counts[Digit]--;
r32 Temp = Entries[Target];
Entries[Target] = Key;
Key = Temp;
Source = Target;
}
while (Source != Original);
}
}
if (DigitIndex > 0)
{
for (u32 Index=0; Index<256; Index++)
{
u32 NewStart = (Index == 0 ? Start : Offsets[Index-1]);
u32 NewEnd = Offsets[Index];
if (NewEnd - NewStart > 1)
{
if (NewEnd - NewStart < 64)
{
InsertionSort(Entries, NewStart, NewEnd);
}
else
{
RadixSortInPlaceImplOpt(Entries, NewStart, NewEnd, DigitIndex - 1);
}
}
}
}
}
static void RadixSortInPlaceOpt(r32 *Entries, u32 Count)
{
RadixSortInPlaceImplOpt(Entries, 0, Count, 3);
}
int main()
{
printf("%-10s%10s%10s%15s%15s\n", "Count", "Quick", "Radix", "RadixInplace", "RadixInplOpt");
for (u32 Count=64; Count<=(1<<20); Count*=2)
{
std::vector<r32> Values(Count);
for (u32 Index=0; Index<Count; Index++)
{
Values[Index] = (r32)(rand() - RAND_MAX/2) / RAND_MAX;
}
std::vector<r32> QSort = Values;
auto qsort1 = std::chrono::steady_clock::now();
std::sort(&QSort[0], &QSort[0] + Count);
auto qsort2 = std::chrono::steady_clock::now();
std::vector<r32> Temp(Count);
std::vector<r32> Entries = Values;
auto rsort1 = std::chrono::steady_clock::now();
RadixSort(&Entries[0], &Temp[0], Count);
auto rsort2 = std::chrono::steady_clock::now();
if (Entries != QSort) { printf("error with radix sort\n"); exit(0); }
Entries = Values;
auto irsort1 = std::chrono::steady_clock::now();
RadixSortInPlace(&Entries[0], Count);
auto irsort2 = std::chrono::steady_clock::now();
if (Entries != QSort) { printf("error with inplace radix sort\n"); exit(0); }
Entries = Values;
auto irsortO1 = std::chrono::steady_clock::now();
RadixSortInPlaceOpt(&Entries[0], Count);
auto irsortO2 = std::chrono::steady_clock::now();
if (Entries != QSort) { printf("error with inplace radix sort opt\n"); exit(0); }
auto qsort = qsort2 - qsort1;
auto rsort = rsort2 - rsort1;
auto irsort = irsort2 - irsort1;
auto irsortO = irsortO2 - irsortO1;
printf("%-10u%10.2f%10.2f%10.2f%15.2f\n", Count,
std::chrono::duration<double, std::milli>(qsort).count(),
std::chrono::duration<double, std::milli>(rsort).count(),
std::chrono::duration<double, std::milli>(irsort).count(),
std::chrono::duration<double, std::milli>(irsortO).count());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.