Microsoft Developer Hoping To Land XArray Support For The Linux 4.17 Kernel
Wilcox is hoping to slowly convert radix tree usage over to using XArrays that he feels is better fitted for how radix trees are currently being used within the Linux kernel to store data. What he considers improvements with this new data structure over radix trees is XArrays has locking as part of its API, memory is not being pre-loaded, and there are improvements to the page cache by using XArray. XArray in this context is short for an eXtensible Array.
Here's some of the latest documentation on XArray:
The XArray is an abstract data type which behaves like a very large array of pointers. It meets many of the same needs as a hash or a conventional resizable array. Unlike a hash, it allows you to sensibly go to the next or previous entry in a cache-efficient manner. In contrast to a resizable array, there is no need for copying data or changing MMU mappings in order to grow the array. It is more memory-efficient, parallelisable and cache friendly than a doubly-linked list. It takes advantage of RCU to perform lookups without locking.
The XArray implementation is efficient when the indices used are densely clustered; hashing the object and using the hash as the index will not perform well. The XArray is optimised for small indices, but still has good performance with large indices. If your index can be larger than ULONG_MAX then the XArray is not the data type for you. The most important user of the XArray is the page cache.
With the v8 patches for XArray, Matthew Wilcox believes the support is in good shape for merging into the upcoming Linux 4.17 kernel. With this initial 63 patches also includes migrating some of the first users of this code over to XArray.
We'll see soon enough if it's going to fly for Linux 4.17.
16 Comments
