Skip to content

nBitCompactSingleSortWGSL

Overview

Performs a N-bit radix sort of an array in workgroup memory (which can be of length workgroupSize * grainSize), using a more complicated/computational but lower-memory approach by packing the accumulated bits (that we scan over) into a more compact form (packed into either a u32/vec2u/vec3u/vec4u, depending on the bitVectorSize parameter).

NOTE: This is a stable sort, but it only sorts things BASED ON ONLY N (bitsPerInnerPass) BITS of the key (so it's not a full sort). You'll want to run this multiple times (giving different sections of bits each time, from lower to higher) in order to achieve a full sort.

@author Jonathan Olson <jonathan.olson@colorado.edu>

Type nBitCompactSingleSortWGSLOptions

import type { nBitCompactSingleSortWGSLOptions } from 'scenerystack/alpenglow';
  • order: BitOrder<T>
    Currently mostly used for the type, but we might be able to use it for more later. (TODO)
  • bitsScratch: WGSLVariableName
    var<workgroup> array<u32|vec2u|vec3u|vec4u, workgroupSize> TODO: we can pack this more efficiently, no?
  • valueScratch: WGSLVariableName
    var<workgroup> array<T, workgroupSize * grainSize>
  • lengthExpression: WGSLExpressionU32
  • getBits: ( value: WGSLExpressionT ) => WGSLExpressionU32
  • earlyLoad?: boolean
    (controls whether we load the values early or late - might affect register pressure)
  • bitsPerInnerPass: number
    e.g. 2 for a two-bit sort
  • bitVectorSize: number
    (½/¾) for (u32/vec2u/vec3u/vec4u) e.g. 4 for a vec4u
  • & RakedSizable & LocalIndexable

Source Code

See the source for nBitCompactSingleSortWGSL.ts in the alpenglow repository.