lkml.org 
[lkml]   [2020]   [Mar]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] Add next, prev pointer in xa_node at the lib/xarray.c
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.

\
 
 \ /
  Last update: 2020-03-17 14:42    [W:0.032 / U:1.816 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site