envoyproxy/envoy

djb2CaseInsensitiveHash may cause excessive probing with Abseil hash tables

Open

#11.720 aperta il 23 giu 2020

Vedi su GitHub
 (3 commenti) (0 reazioni) (0 assegnatari)C++ (5373 fork)batch import
area/perfhelp wanted

Metriche repository

Star
 (27.997 star)
Metriche merge PR
 (Merge medio 8g) (378 PR mergiate in 30 g)

Descrizione

Title: djb2CaseInsensitiveHash may cause excessive probing with Abseil hash tables

Description: My colleagues who implemented the Abseil containers (@fowles and @sbenzaquen) mentioned that djb2CaseInsensitiveHash will likely cause excessive probing with absl::{flat,node}_hash_{set,map}. StringUtil uses this hash [1] in an absl::flat_hash_set [2]. Ideally this would be built on top of the absl::Hash framework [3] instead.

Relevant Links: [1] https://github.com/envoyproxy/envoy/blob/02a526257a013e80bc508399446aac0234c3ec4e/source/common/common/utility.cc#L472 [2] https://github.com/envoyproxy/envoy/blob/02a526257a013e80bc508399446aac0234c3ec4e/source/common/common/utility.h#L170 [3] https://abseil.io/docs/cpp/guides/hash

Guida contributor

Direzione di ricerca
Investiga l'implementazione di djb2CaseInsensitiveHash e sostituiscila con il framework absl::Hash per ridurre il probing eccessivo.
Tech stack
cpp
Dominio
backend
Tipo issue
Performance
DifficoltàQuanto dovrebbe essere impegnativa per un nuovo contributor.
3
Tempo stimatoTempo stimato per completare e verificare uno scope piccolo.
Mezza giornata
Stato attivitàQuanto è probabile che la issue sia ancora attiva e reviewable.
Attiva
ChiarezzaQuanto chiaramente la issue descrive problema, scope e risultato atteso.
Chiara
Prerequisiti
C++Abseilhash tables
Adatta ai principiantiQuanto la issue è adatta a contributor alla prima esperienza.
50