envoyproxy / envoyproxy/envoy

djb2CaseInsensitiveHash may cause excessive probing with Abseil hash tables

Open
#11,720 3 comments 0 reactions 0 assignees View on GitHub
area/perf help wanted
Dominant language
C++
Stars
28.9k
Forks
5.6k
Avg merge
1d 20h
Merged PRs (30d)
437

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](https://github.com/envoyproxy/envoy/blob/02a526257a013e80bc508399446aac0234c3ec4e/source/common/common/hash.h#L35) 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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.