binaria eficiencia de búsqueda vs. eficiencia de búsqueda lineal en FORTRAN

Question

Esta pregunta se refiere a la eficacia de una búsqueda lineal frente a la eficiencia de una búsqueda binaria para una matriz de pre-ordenada en almacenamiento contiguo ...

tengo una aplicación escrita en fortran (77!). Una operación frecuente para mi parte del código es encontrar el índice en una matriz tal que gx(i) <= xin < gx(i+1). He implementado actualmente esto como una binary search - lo siento por las etiquetas de sentencia y goto - he comentado lo que las declaraciones provistas serían equivalentes usando fortran 90 ...

 i=1 
     ih=nx/2 
201  continue !do while (.true.) 
      if((xin.le.gx(i)).and.(xin.gt.gx(i+1)))then !found what we want 
       ilow=i+1; ihigh=i 
       s1=(gx(ihigh)-xin)/(gx(ihigh)-gx(ilow)) 
       s2=1.0-s1 
       return 
      endif 
      if(i.ge.ih)then 
       goto 202 !exit 
      endif 
      if(xin.le.(gx(ih))then !xin is in second half of array 
       i=ih 
       ih=nx-(nx-ih)/2 
      else !xin is in first half of array 
       i=i+1 
       ih=i+(ih-i)/2 
      endif 
     goto 201 !enddo 

Sin embargo, hoy en día, yo estaba leyendo en la Wikipedia sobre la búsqueda binaria y me encontré con esto:

Binary search can interact poorly with the memory hierarchy 
(i.e. caching), because of its random-access nature. For 
in-memory searching, if the span to be searched is small, a 
linear search may have superior performance simply because 
it exhibits better locality of reference. 

no entiendo completamente esta declaración - mi impresión fue que recupera la memoria caché se reunieron en trozos grandes (más o menos) a la vez, por lo que si partimos al comienzo de la matriz, pensé que la mayoría de la matriz ya estaría en la memoria caché (al menos tanto como lo sería para una búsqueda lineal), así que no pensé que eso fuera importante.

Así que mi pregunta es, ¿hay alguna manera de decir qué algoritmo tendrá un mejor rendimiento (búsqueda lineal o binaria?) ¿Hay un límite de tamaño de matriz? Actualmente estoy usando matrices de tamaño de alrededor de 100 elementos ...

Answer 1

Para matrices pequeñas, el problema no es el caché. Tiene razón: es probable que una pequeña matriz se almacene en caché rápidamente.

El problema es que la predicción de bifurcación es probable que falle en la búsqueda binaria porque las ramas se toman u omiten al azar de una manera dependiente de los datos. La predicción de la sucursal pierde el bloqueo de la tubería de la CPU.

Este efecto puede ser severo. Puede buscar fácilmente de 3 a 8 elementos de forma lineal en el mismo tiempo que lleva hacer una sola bifurcación de búsqueda binaria (y necesita hacer múltiples ramas de búsqueda binarias). El punto de equilibrio exacto debe medirse.

El bloqueo de la tubería de la CPU es extremadamente costoso. Un Core i7 puede retirar hasta 4 instrucciones por ciclo de reloj (¡12 giga-instrucciones por segundo a 3 GHz!). Pero solo, si no te estás estancando.

Hay algoritmos libres de ramificación que realizan búsqueda binaria utilizando instrucciones de CPU de movimiento condicional. Estos algoritmos básicamente desenrollan 32 pasos de búsqueda y usan un CMOV en cada paso (32 pasos son el máximo teórico). Están libres de ramificaciones, pero no estancados: cada paso siguiente depende en un 100% del anterior, por lo que la CPU no puede cargar más adelante en la secuencia de instrucciones. Tiene que esperar todo el tiempo. Entonces no resuelven este problema, solo lo mejoran un poco.