Battre la recherche binaire en utilisant la ligne de cache de l'UC

Question

À des fins éducatives, j'essaie de battre binary search en utilisant la ligne de cache de l'UC.

https://github.com/nmmmnu/beating_binsearch/blob/master/improved.h

Si vous décommentez #define EXIT_ONLY, la recherche fonctionne comme binary search normale, sauf s'il y a quelques éléments, la recherche est devenu linear search.

Comme prévu cela effectue plus rapidement que binary search.

Cependant, je veux améliorer le futur, donc si vous commentez #define EXIT_ONLY, alors "petit" linear search est fait au lieu d'accéder seulement à l'élément "middle".

En théorie, les valeurs pour la recherche linéaire doivent être dans la ligne de cache de l'UC et l'accès doit être "gratuit".

Cependant, en pratique, cette recherche est beaucoup trop lente que la normale binary search.

Si le code CACHE_COUNT_2 est égal à 1, la vitesse est comparable mais plus lente. Je n'ai jamais essayé de dérouler le cycle _linear().

Quelle pourrait être l'explication de l'exécution plus lente?

Repo avec tous les fichiers est ici:
https://github.com/nmmmnu/beating_binsearch

Answer 1

Je ne la version déroulai de la recherche,

https://github.com/nmmmnu/beating_binsearch/blob/master/improved_unroll.h

ici est le code en question:

char search(uint64_t const start1, uint64_t const end1, const T *data, const T key, uint64_t &index) const{ 
    /* 
    * Lazy based from Linux kernel... 
    * http://lxr.free-electrons.com/source/lib/bsearch.c 
    */ 

    uint64_t start = start1; 
    uint64_t end = end1; 

    char cmp = 0; 

    //while (start < end){ 
    while (start < end){ 
    // uint64_t mid = start + ((end - start)/2); 
     uint64_t mid = start + ((end - start) >> 1); 

     //char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid); 

     #define _LINE_HALF_SIZE 7 
     #define _LINE(i)      \ 
     if (i >= end){       \ 
      start = mid + _LINE_HALF_SIZE + 1; \ 
      continue;       \ 
     }          \ 
               \ 
     cmp = comp.cmp(data[i], key);   \ 
               \ 
     if (cmp == 0){       \ 
      index = i;       \ 
      return 0;       \ 
     }          \ 
               \ 
     if (cmp > 0){       \ 
      end = i + 1;      \ 
      continue;       \ 
     } 

     _LINE(mid - 7); 
     _LINE(mid - 6); 
     _LINE(mid - 5); 
     _LINE(mid - 4); 
     _LINE(mid - 3); 
     _LINE(mid - 2); 
     _LINE(mid - 1); 
     _LINE(mid ); 
     _LINE(mid + 1); 
     _LINE(mid + 2); 
     _LINE(mid + 3); 
     _LINE(mid + 4); 
     _LINE(mid + 5); 
     _LINE(mid + 6); 
     _LINE(mid + 7); 

     #undef _LINE 

     start = mid + _LINE_HALF_SIZE + 1; 
    } 

    index = start; 
    return cmp; 
} 

semble qu'il y ait sont trop de prédictions de miss de branche, parce que si j'enlèvesuivant déclaration:

 if (i >= end){       \ 
      start = mid + _LINE_HALF_SIZE + 1; \ 
      continue;       \ 
     }          \ 

vitesse « magie » est devenu même ou encore mieux que classical binary search - bien sûr, parce que j'éliminé la branche de l'algorithme n'a pas vraiment fonctionné correctement, mais cela est une indication claire pourquoi l'algorithme est plus lent que classical binary search .

Answer 2

Il y a quelques problèmes dans votre code. Par exemple, ce code ne prend pas en compte les limites de la ligne de cache.

while (end - start > CACHE_COUNT_MIN){ 
// uint64_t mid = start + ((end - start)/2); 
uint64_t mid = start + ((end - start) >> 1); 

etc ...

char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid); 

lignes de cache sont attribuées sur les adresses modulo la taille de la ligne. Ainsi, pour analyser une ligne de cache complète, vous voudriez masquer les bits pertinents de l'adresse. Même s'il s'agit d'un cache, vous passerez quand même des cycles d'accès à la ligne (plus il est élevé dans la hiérarchie).

La recherche binaire est déjà l'un des algorithmes les plus efficaces en cache pour la recherche basée sur la comparaison, même si l'améliorer grâce à la connaissance du cache peut être difficile. Vous éliminez la moitié de l'espace de recherche à chaque itération, ce qui évite déjà la plupart des échecs de cache, et c'est un espace linéaire, et vous augmentez la localité à chaque recherche. La prédiction peut même cacher certains des échecs.

Vous pouvez utiliser perf pour échantillonner des événements de performances dans votre code. De plus, pour avoir une idée de la façon dont la connaissance du cache est parfois utilisée pour optimiser les algorithmes, vous pouvez également jeter un oeil à certains des objets connus comme hopscotch hashing.