Re: [RFC PATCH bpf-next v2 0/3] bpf: support string key in htab

On Fri, Feb 18, 2022 at 5:54 AM Hou Tao [off-list ref] wrote:

quoted

We've been thinking about "dynamic pointer" concept where
pointer + length will be represented as an object.

I have seen the proposal from Joanne Koong on "dynamic pointers".
It can solve the storage problem of string, but the lookup of
string is still a problem. Hash is a option but can we support
two dynamic pointers points to the same internal object and use
the id of the internal object to represent the string ?

Let's have a discussion about dynptr in that thread.

quoted

The program will be able to allocate it and persist into a map value
and potentially into a map key.
For storing a bunch of strings one can use a strong hash and store
that hash in the key while keeping full string as a variable sized
object inside the value.

Will using a strong hash function impact the lookup performance because
each lookup will need to calculate the hash ?

quoted

Another approach is to introduce a trie to store strings, or dfa,
or aho-corasick, etc. There are plenty of data structures that are
more suitable for storing and searching strings depending on the use case.
Using hash table for strings has its downsides.
.

Before add support for string key in hash table, we had implement tries,
ternary search tree and hash table in user-space for string lookup. hash
table shows better performance and memory usage, so we decide to do string
support in hash table. We will revisit our tests and investigate new string
data structures.

What performance characteristics did you consider?
Just the speed of the lookup ?
How many elements are there in the map ?
Is it 80% or 10% full ?
Did you compare memory usage ?
Did you consider the speed of update/delete ?
preallocated or dynamic alloc ?

With dynamic pointers and further verifier improvements bpf programs
will be able to implement a hash table on their own.