Messages in this thread | | | Date | Tue, 17 Mar 2020 06:40:43 -0700 | From | Matthew Wilcox <> | Subject | Re: [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.
| |