Elegir el algoritmo de ordenación

Las dos implementaciones anteriores resuelven el mismo problema con costes asintóticos distintos, y eso invita a pensar que la elección es una cuestión de tamaño de entrada. Lo es en parte, pero hay cuatro factores más que en la práctica deciden antes: si la clave se puede convertir en un entero, cuánta memoria auxiliar te sobra, si el orden de los empates tiene que ser reproducible, y si de verdad necesitas un orden total o te basta con agrupar.

La tabla

Las dos filas que más veces deciden son la de memoria y la de requisito de la clave.

La memoria. El radix necesita un segundo array del mismo tamaño para el ping-pong, más el array de conteos, más los buffers intermedios del scan. Para un millón de pares clave-carga son ocho megabytes de origen, ocho de destino y unos trescientos kilobytes de conteos. En una GPU integrada con presupuesto ajustado, o cuando el array es una fracción grande del total de VRAM, la bitónica gana por eliminación: trabaja en sitio y no reserva nada.

El requisito de la clave. El radix exige una función que convierta la clave en un entero sin signo preservando el orden. Para números es directo. Para una clave compuesta —ordenar por material y dentro de cada material por profundidad— hay que empaquetar los dos criterios en un entero, con los bits del criterio principal arriba, y eso obliga a cuantizar. Si la clave no cabe en 32 bits, o si el criterio de orden es una función que no se puede expresar así, la bitónica es la única opción, porque su comparador puede ser cualquier cosa.

El punto de cruce

Con claves de 32 bits y r = 4, el radix hace 8 pasadas independientemente del tamaño. La bitónica hace L(L+1)/2 pasos con L = log2(n). El cruce en número de accesos a memoria está aproximadamente donde L(L+1)/2 supera a 8 por el número de lecturas y escrituras por pasada, y en la práctica medida cae entre 10.000 y 100.000 elementos.

La primera fila necesita explicación porque contradice la cuenta. Con 1024 elementos y bloques de 512, la ordenación bitónica se resuelve con un dispatch de ordenación de bloque y una fusión, o sea tres o cuatro dispatches en total, mientras que el radix necesita sus 40 pase lo que pase. Por debajo del tamaño en que todo cabe en unos pocos bloques de memoria compartida, la bitónica gana siempre por sobrecoste fijo.

Tres cosas desplazan el cruce hacia arriba, o sea a favor de la bitónica:

Claves con muchos bits significativos que no se pueden recortar, porque el radix paga pasadas proporcionalmente. Elementos grandes que hacen que el radix mueva mucho más tráfico en su fase de dispersión, aunque ese factor se neutraliza ordenando índices. Y hardware con sobrecoste de dispatch alto, típicamente móviles, donde 40 dispatches con dependencias entre ellos ya se notan.

Y dos lo desplazan hacia abajo, a favor del radix: claves cortas, porque un índice de celda de 16 bits se ordena en cuatro pasadas, y arrays cuyo tamaño no es potencia de dos, porque la bitónica tiene que rellenar hasta la siguiente y en el peor caso ordena casi el doble de datos.

Cuando el rango de la clave es pequeño

Si la clave toma pocos valores distintos —un índice de celda en una rejilla de 64 por 64 por 64 son 262.144 valores, un material son 16, un cubo de profundidad son 256— no hace falta ordenar. Un counting sort de una sola pasada hace el trabajo con la maquinaria que ya tienes:

Contar cuántos elementos hay de cada valor, con un histograma atómico. Hacer el scan exclusivo del histograma, que da la posición inicial de cada valor. Dispersar cada elemento a su posición, reservándola con un atomicAdd sobre el desplazamiento de su cubo.

Son tres kernels, el scan en medio, y cinco dispatches en total. Es el mismo esqueleto que una pasada de radix, sin las otras siete. Es exactamente lo que hace la construcción de una rejilla espacial, y es la razón por la que ese problema no necesita un sort de propósito general aunque todo el mundo lo llame “ordenar las partículas por celda”.

La versión con atomicAdd en la dispersión no es estable: el orden dentro de cada cubo depende de la planificación. Si necesitas estabilidad, se sustituye el atomicAdd por el ranking local con scan que usa el radix, y el coste sube modestamente.

El límite del counting sort es la memoria del histograma: un rango de un millón de valores necesita un array de un millón de contadores, cuatro megabytes, más el coste de escanearlo. A partir de ahí compensa el radix, que trocea el rango en pasadas.

Medir de verdad

Cualquier decisión tomada sobre esta tabla sin medir es una conjetura razonable, no un dato. Y medir bien tiene tres requisitos que se incumplen a menudo.

Medir en la GPU, no en la CPU. El tiempo entre submit y la resolución de onSubmittedWorkDone incluye la cola del navegador y no es el tiempo del kernel. La herramienta correcta son las consultas de marca de tiempo, con la característica 'timestamp-query' si el adaptador la ofrece.

Medir con datos representativos. El bitonic sort tarda exactamente lo mismo con cualquier entrada, porque su red es fija; es una propiedad valiosa cuando el presupuesto de frame es estricto. El radix no depende de los datos en operaciones, pero sí en tráfico: con claves muy agrupadas, la dispersión escribe en pocos destinos y va más rápido que con claves uniformes. Medir solo con datos aleatorios uniformes da el peor caso del radix y puede llevar a descartarlo injustamente, o al revés si tus datos reales están casi ordenados.

Medir en el dispositivo objetivo. La relación entre coste de dispatch y ancho de banda es muy distinta en una GPU de escritorio y en un móvil. Un algoritmo con 40 dispatches y menos tráfico gana en el escritorio y puede perder en el móvil.

// Marcas de tiempo alrededor de un pass, si el adaptador lo permite.
const conTiempo = adapter.features.has('timestamp-query');
const querySet = conTiempo
  ? device.createQuerySet({ type: 'timestamp', count: 2 })
  : null;

const pass = enc.beginComputePass(
  querySet ? { timestampWrites: { querySet, beginningOfPassWriteIndex: 0,
                                  endOfPassWriteIndex: 1 } } : {});
// ... dispatches ...
pass.end();
if (querySet) { enc.resolveQuerySet(querySet, 0, 2, bufResolucion, 0); }