binario efficienza di ricerca vs. efficienza ricerca lineare in FORTRAN

Question

Questa domanda riguarda l'efficienza di una ricerca lineare contro l'efficienza di una ricerca binaria per un array pre-ordinato in deposito contiguo ...

Ho un applicazione scritta in fortran (77!). Un'operazione frequente per la mia parte del codice è trovare l'indice in una matrice tale che gx(i) <= xin < gx(i+1). Ho attualmente implementato questo come un binary search - dispiace per le etichette istruzione e goto - Ho commentato quello che i statments equivalenti sarebbero utilizzando 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 

Tuttavia, oggi, stavo leggendo su Wikipedia ricerca binaria e mi sono imbattuto in questo:

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. 

non capisco completamente questa affermazione - la mia impressione è stata che recupera di cache sono stati raccolti in grandi (ish) pezzi alla volta, quindi se si parte all'inizio dell'array, pensavo che la maggior parte dell'array sarebbe già nella cache (almeno tanto quanto sarebbe per una ricerca lineare), quindi non pensavo che avrebbe avuto importanza.

Quindi la mia domanda è, c'è un modo per dire quale algoritmo funzionerà meglio (ricerca lineare o binaria?) C'è un limite di dimensione dell'array? Attualmente sto usando matrici di dimensioni di circa 100 elementi ...

Answer 1

Per i piccoli array, il problema non è la cache. Hai ragione: è probabile che un piccolo array venga memorizzato nella cache rapidamente.

Il problema è che è probabile che la previsione ramo fallisca per la ricerca binaria perché i rami vengono presi o saltati casualmente in modo dipendente dai dati. La previsione dei branch fallisce bloccando la pipeline della CPU.

Questo effetto può essere grave. Puoi facilmente cercare da 3 a 8 elementi in modo lineare nello stesso tempo necessario per eseguire un singolo ramo di ricerca binario (e devi eseguire più rami di ricerca binaria). Il punto esatto di break even deve essere misurato.

Lo stallo della pipeline della CPU è estremamente costoso. Un Core i7 può ritirare fino a 4 istruzioni per ciclo di clock (12 istruzioni giga al secondo a 3 GHz!). Ma solo, se non sei in stallo.

Esistono algoritmi senza branch che eseguono la ricerca binaria utilizzando istruzioni CPU con spostamento condizionale. Questi algoritmi fondamentalmente srotolano 32 passaggi di ricerca e usano uno CMOV in ogni passo (32 passi sono il massimo teorico). Sono privi di branch ma non stall free: ogni step successivo dipende dal 100% del precedente, quindi la CPU non può caricare in anticipo nel flusso di istruzioni. Deve aspettare tutto il tempo. Quindi non risolvono questo problema, lo migliorano solo leggermente.