On Fri, Feb 18, 2022 at 5:54 AM Hou Tao <houtao1@xxxxxxxxxx> wrote: > > > 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. > > 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 ? > > > 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.
