envoyproxy/envoy

djb2CaseInsensitiveHash may cause excessive probing with Abseil hash tables

Open

#11,720 opened on Jun 23, 2020

View on GitHub
 (3 comments) (0 reactions) (0 assignees)C++ (5,373 forks)batch import
area/perfhelp wanted

Repository metrics

Stars
 (27,997 stars)
PR merge metrics
 (Avg merge 8d) (378 merged PRs in 30d)

Description

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 direction
Investigate the djb2CaseInsensitiveHash implementation and replace it with absl::Hash framework to reduce excessive probing.
Tech stack
cpp
Domain
backend
Issue type
Performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
3
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
Half day
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
Active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
Clear
Prerequisites
C++Abseilhash tables
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
50