Messages in this thread Patch in this message | | | From | JaeJoon Jung <> | Date | Wed, 18 Mar 2020 09:49:30 +0900 | Subject | Re: [PATCH] Add next, prev pointer in xa_node at the lib/xarray.c |
| |
Hi Matthew, Thank you for your deep response.
I think XArray is a very well-made structure that requires no further improvement if the indexes are dense in a 64-bit system.
Since xa_node is 576 bytes and is set to fit 7 per 4kB page, adding a data type to xa_node is rather a memory waste problem.
#define XA_CHUNK_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) XA_CHUNK_SIZE is 32 or 64
XA_CHUNK_SIZE is 32 or 64, and currently XAarray is 64 optimized, so modifying it may have a counterproductive effect.
There is a downside to the well-designed XArray, but if the indexes are not dense or deleted a lot, the memory of the slots in the xa_node is increased and the search cost for logn increases at f (n) = O (nlogn)
My worries are here and I hope you understand my efforts to solve it.
My attempts described below are meaningful when XA_CHUNK_SHIFT is 4 or 2, and can solve the slowdown in search speed when indexes are deleted and not concentrated.
When XA_CHUNK_SHIFT is 2(XA_CHUNK_SIZE is 4), the XArray configuration is as follows. (It is difficult to express the picture in text.)
xarray->head : xa_node : index: 0 16 32 48 +---+---+---+ | | | | +-----------------------+ | | +------------+ | +------------+ | | | | | | 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 +--+--+---+ +---+---+---+ +---+---+---+ +---+---+---+ | | | | +-----+ | +-------+ +---------------+ | | | | 0 1 2 3 <==>... <==> 16 17 18 19 <==>... <==> 32 33 34 35 <==>... <==> 48 49 ..
In the above, if xa_node is connected to next and prev, it does not search the parent node, so the logn disappears from f (n) = O (nlogn), which improves search efficiency with f (n) = O (n). In fact, this is already well-known in traditional algorithms, but I hope you can understand it with the effort applied to XArray.
Best Regards, JaeJoon Jung.
On Tue, 17 Mar 2020 at 22:40, Matthew Wilcox <willy@infradead.org> wrote: > > On Tue, Mar 17, 2020 at 04:32:34PM +0900, JaeJoon Jung wrote: > > Hi Matthew, > > I add next, prev pointer in the xa_node to improve search performance. > > XArray currently has the following search capabilities: > > > > Search algorithm performance is O(n) = n x log(n) > > That's not how "big-O" notation is used. > https://en.wikipedia.org/wiki/Big_O_notation > > What you mean to say here is O(n.log(n)). > > > For example, > > XA_CHUNK_SHIFT 2 > > XA_CHUNK_SIZE 4 > > I'm not really interested in the performance of a cut-down radix tree. > You can re-run the numbers with a SHIFT of 6 and SIZE of 64 to get a > more useful set of performance numbers. > > > If you connect the leaf node with the next and prev pointers as follows, > > the search performance is improved to O (n) = n. > > But that's not free. Right now, the xa_node is finely tuned in > size to 576 bytes on 64-bit systems (32-bit systems are a secondary > consideration). That gets us 7 nodes per page. Increasing the size any > further reduces the number per page to 6, which is a pretty meaningful > increase in memory usage. > > > @@ -1125,6 +1125,8 @@ struct xa_node { > > unsigned char count; /* Total entry count */ > > unsigned char nr_values; /* Value entry count */ > > struct xa_node __rcu *parent; /* NULL at top of tree */ > > + struct xa_node __rcu *prev; /* previous node pointer */ > > + struct xa_node __rcu *next; /* next node pointer */ > > You should be indenting with tabs, not spaces. Or your mail system is > messing with your patches. >
| |