Re: [PATCH] Add next, prev pointer in xa_node at the lib/xarray.c

From: JaeJoon Jung
Date: Tue Mar 17 2020 - 20:49:46 EST


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@xxxxxxxxxxxxx> 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.
>