envoyproxy/envoy

djb2CaseInsensitiveHash may cause excessive probing with Abseil hash tables

Open

#11.720 geöffnet am 23. Juni 2020

Auf GitHub ansehen
 (3 Kommentare) (0 Reaktionen) (0 zugewiesene Personen)C++ (5.373 Forks)batch import
area/perfhelp wanted

Repository-Metriken

Stars
 (27.997 Stars)
PR-Merge-Metriken
 (Durchschn. Merge 8T) (378 gemergte PRs in 30 T)

Beschreibung

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

Contributor Guide

Research-Richtung
Untersuchen Sie die Implementierung von djb2CaseInsensitiveHash und ersetzen Sie sie durch das absl::Hash Framework, um übermäßiges Sondieren zu reduzieren.
Tech Stack
cpp
Domain
backend
Issue Type
Performance
SchwierigkeitGeschätzte Implementierungsschwierigkeit für neue Contributors, von 1 für sehr kleine Änderungen bis 5 für Expertenarbeit.
3
Geschätzte ZeitEin grober Zeitrahmen, um zu recherchieren, zu implementieren, zu testen und einen Pull Request vorzubereiten.
Halber Tag
AktivitätsstatusWie verfügbar das Issue gerade wirkt: frisch, aktiv, stale, blockiert oder wartet auf Maintainer-Input.
Aktiv
KlarheitWie klar das Issue die erwartete Änderung, Akzeptanzkriterien und den nächsten Schritt erklärt.
Klar
Voraussetzungen
C++Abseilhash tables
EinsteigerfreundlichkeitEin Score von 1 bis 100, der schätzt, wie zugänglich dieses Issue für First-Time Contributors ist.
50