img - ¿Por qué la duplicación de R funciona mejor en los datos ordenados?

tags$style shiny

Question

Mientras comparaba la eficiencia de dos funciones en una respuesta para verificar si la lista contiene otra lista en R , me topé con un resultado interesante. La clasificación aumenta en gran medida la eficacia de la duplicated cuando el vector es grande. Esto fue una sorpresa ya que nunca había notado una diferencia considerable en mi propio trabajo al usar duplicated . De hecho, para los tamaños con los que trabajo todos los días, no hay una diferencia. Observar:

set.seed(1007)
s1 <- sample(10^2, 10^3, replace = TRUE)
s1_sort <- sort(s1)
library(microbenchmark)
microbenchmark(dp=duplicated(s1), dp_sort=duplicated(s1_sort), times=1000)
Unit: microseconds
   expr    min      lq     mean  median      uq      max neval cld
     dp 16.459 16.9425 22.06371 17.2965 22.5050 1541.137  1000   a
dp_sort 17.007 17.5005 25.54953 17.8200 23.3655 1549.198  1000   a

Como puede ver, no hay una diferencia notable en los tiempos cuando se ordena el vector. Sin embargo, en vectores muy grandes, los resultados son muy diferentes. Observar:

s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)
microbenchmark(dp=duplicated(s2), dp_sort=duplicated(s2_sort), times=100)
Unit: milliseconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 816.6883 847.9231 869.6829 861.8210 882.3978 1019.6339   100   b
dp_sort 287.6779 305.4779 322.8830 315.1198 324.9249  449.1734   100  a 

¡Casi 3 veces más rápido! Esto me llevó por el agujero del conejo, que comenzó aquí: r-source.../duplicated.R . Desde aquí vemos que duplicado hace una llamada a .Internal(duplicated(x,...)) . Luego, utilizando la función pryr::show_c_source(.Internal(duplicated(x))) y la workaround sugerida por @joran ( show_c_source actualmente está dando problemas ... ver ¿Está "show_c_source ()" borken? ), Vemos que el duplicated hace una llamada a do_duplicated . Finalmente, se revela el heart de lo duplicated (comienza en la línea 667 y termina en 988). Parece que todo el vector está en bucle y luego se produce un hash:

724     /* count unique entries */
725     k = 0;
726     for (i = 0; i < n; i++)
727         if (LOGICAL(dup)[i] == 0)
728             k++;

776     /* Build a hash table, ignoring information on duplication */
777     static void DoHashing(SEXP table, HashData *d)

No entiendo completamente todo el código, pero parece que la clasificación no debería importar. Recorremos todo el vector en cualquier caso (ordenados frente a no ordenados) y, en última instancia, llamamos a una variedad de funciones hash, que no deberían depender de si un vector está ordenado o no. Mi idea inicial fue que estaba ocurriendo algún tipo de predicción de rama (consulte esta pregunta ), pero desde la actualización de esta respuesta , parece que estas cosas ya no deberían importar.

¿¿Que esta pasando??

EDITAR

La brecha parece aumentar a medida que aumenta el tamaño del vector y el número de duplicados.

set.seed(496)
s3 <- sample(10^6, 10^8, replace = TRUE)
s3_sort <- sort(s3)
microbenchmark(dp=duplicated(s3), dp_sort=duplicated(s3_sort), times = 10)
Unit: seconds
   expr       min        lq      mean    median        uq       max neval cld
     dp 12.149932 12.175665 12.848843 12.495599 12.719861 15.589190    10   b
dp_sort  2.395636  2.401837  2.706674  2.551375  2.677556  4.373653    10  a 

Como señaló @alexis_laz, si no hay duplicados, el impacto de la clasificación se reduce considerablemente.

s4 <- sample(10^8)
s4_sort <- sort(s4)
microbenchmark(dp=duplicated(s4), dp_sort=duplicated(s4_sort), times = 10)
Unit: seconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 8.013995 8.130565 8.593626 8.197501 8.438703 10.639452    10   b
dp_sort 6.135788 6.158140 6.751101 6.256739 7.241381  8.913507    10  a 

Answer 1

El factor principal es la tasa de falta de memoria caché de la CPU y, como escalas de tamaño, fallas de página más caras. La duplicación se verifica por referencia a una tabla hash simple. Si la parte de la tabla hash que se consulta ya está en el caché de memoria de alta velocidad, estas búsquedas son mucho más rápidas. Para vectores pequeños, la tabla hash correspondiente encajará completamente en el caché de memoria de alta velocidad, por lo que el orden de acceso no es significativo, que es lo que vio en su primer punto de referencia.

Para vectores más grandes, solo algunos bloques de la tabla hash cabrán en el caché en un momento dado. Si los duplicados son consecutivos, la parte de la tabla hash necesaria para la búsqueda ya estará en el caché para las búsquedas posteriores. Por esta razón, el rendimiento aumenta en número de duplicados para vectores más grandes. Para vectores extremadamente grandes, es posible que la tabla hash ni siquiera se ajuste por completo a la memoria física disponible y se localice en el disco, lo que hace que la diferencia sea aún más notable.

Para probar esto, usemos el vector s2 la publicación original y su versión ordenada, pero también probemos los duplicados uno al lado del otro, pero por lo demás sin clasificar.

# samples as in original post
s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)

# in the same order as s2, but with duplicates brought together
u2 <- unique(s2)
t2 <- rle(s2_sort)
s2_chunked <- rep(u2,times=t2$length[match(u2,t2$values)])

También consideremos la clasificación por valor de hash. Voy a aproximar la codificación hash en R, pero aquí estamos tratando con valores de tamaño doble en lugar de poder usar largos sin firmar, por lo que no podremos usar operaciones a nivel de bits.

# in the order of hash value
K <- ceiling(log2(length(s2)*2))
M <- 2^K
h <- ((3141592653 * s2) %% 2^32)/2^(32-K)
ho <- order(h)
s2_hashordered <- s2[ho]

Lo que esperamos ver es que el rendimiento es similar para s2_sort y s2_chunked e incluso mejor para s2_hashordered . En cada uno de estos casos, hemos intentado minimizar los errores de caché.

microbenchmark(
 duplicated(s2), 
 duplicated(s2_sort), 
 duplicated(s2_chunked),
 duplicated(s2_hashordered),
 times=10)

Unit: milliseconds
                       expr      min       lq     mean   median       uq      max neval cld
             duplicated(s2) 664.5652 677.9340 690.0001 692.3104 703.8312 711.1538    10   c
        duplicated(s2_sort) 245.6511 251.3861 268.7433 276.2330 279.2518 284.6589    10  b 
     duplicated(s2_chunked) 240.0688 243.0151 255.3857 248.1327 276.3141 283.4298    10  b 
 duplicated(s2_hashordered) 166.8814 169.9423 185.9345 185.1822 202.7478 209.0383    10 a