Dear, Greg Kroah-Hartman The representative data structures currently implemented in the Linux kernel are as follows. Linked List (include/linux/list.h) Hash List (include/linux/hash.h, hashtable.h) Red-Black Tree (lib/rbtree.c) XArray (lib/xarray.c) Maple Tree (lib/maple_tree.c) They have their own characteristics and pros and cons. Linked List: O(n) Hash List: O(1) + O(n) Red-Black Tree: O(log2(n)): child is 2: Rotation required to maintain left-right balance XArray: O(logm(n)): child is m: If the index is not dense, there is memory waste. Maple Tree: O(logm(n)): child is m: The structure for trees is large and complex. Since Linked List and Hash List are linear structures, the search time increases as n increases. Red-Black Trees are suitable for indices in the thousands range, as the tree becomes deeper as n gets too large. XArray is suitable for managing IDs and IDRs that are densely packed with tens of thousands of indices. Maple Tree is suitable for large indexes, but the algorithm for managing the tree is too complex. The Hash Tree I implemented manages the Tree with the characteristic of a hash that is accessed in O(1). Even if the tree gets deeper, the search time does not increase. There is no rotation cost because the tree is kept balanced by hash key. The algorithm for managing the tree is simple. Performance comparison when the number of indexes(nr) is 1M stored: The numeric unit is cycles as calculated by get_cycles(). Performance store find erase --------------------------------------------- XArray 4 6 14 Maple Tree 7 8 23 Hash Tree 5 3 12 --------------------------------------------- Please check again considering the above. On Tue, 6 Aug 2024 at 16:38, Greg Kroah-Hartman <gregkh@xxxxxxxxxxxxxxxxxxx> wrote: > > On Tue, Aug 06, 2024 at 04:32:22PM +0900, JaeJoon Jung wrote: > > Since I've been working on something called a new Hash Table, it may > > not be needed in the kernel right now. > > We don't review, or accept, changes that are not actually needed in the > kernel tree as that would be a huge waste of reviewer time and energy > for no actual benefit. > > sorry, > > greg k-h
