On 01/11/2012 08:37 AM, David Sterba wrote:

Hi, a few thoughts and comments below:

On Tue, Jan 10, 2012 at 03:31:34PM +0800, Liu Bo wrote:

quoted

c) The level limit may need to be adjusted.
   I know it is a magic number, but now for simplicity we just keep it at 16,
   and then each skiplist is able to contain (2^32-1)/3 nodes at most.

(2^32-1)/3 = 1,431,655,765 that's a lot, I wonder what an average member
count of a skiplist would be and whether eg. maxlevel = 12 is not enough
(5,592,405 members).

hmm, sorry, I found I've made a mistake here,
let me correct it here (changelog will also be updated later):

As I set the probability to 1/4, the members linked on N+1 level list will be 1/4 of
those linked on N level list.

And what's more, in skiplist a node can be linked on multi levels, eg. a node with N+1 level will
also be linked on N level list.

So before the node count reaches to 4^(maxlevel - 1), the skiplist can maintain O(lgn),
and after that, it will be no more O(lgn) although we can still insert nodes into the skiplist.

That's the difference.

or you can set the maxlevel during skiplist creation, or predefine a
"small" skiplist with compile-time-set level to whatever < 16.

this can be tuned later of course.

Yes, I do set the maxlevel to 16 at the creation of a skiplist.

Here 4^(16 - 1) is 2^30, I don't think this is enough for some severe workloads which build large
amount of fragments.

Maybe we should make the maxlevel self-update.

quoted

--- /dev/null
+++ b/fs/btrfs/skiplist.c

@@ -0,0 +1,98 @@
+inline int sl_fill_node(struct sl_node *node, int level, gfp_t mask)

I suggest to pick the full prefix "skiplist_" instead of just "sl_",
it'll be IMHO more readable and googlable. (Out of curiosity I grepped
for the sl_ prefix and it's used by drivers/net/slip/slip.c).

I did hesitate for a while between "skiplist_" and "sl_"...
and I just wanna make it be similar to "rb_".

Anyway, I'm ok with "skiplist_".

quoted

+{
+	struct sl_node **p;
+	struct sl_node **q;
+	int num;
+
+	BUG_ON(level > MAXLEVEL);
+
+	num = level + 1;
+	p = kmalloc(sizeof(*p) * num, mask);
+	BUG_ON(!p);

you can drop the BUG_ON

quoted

+	if (!p)

        ^^^^^^^

quoted

+		return -ENOMEM;
+	q = kmalloc(sizeof(*q) * num, mask);
+	BUG_ON(!q);

        ^^^^^^^^^^

ok, just in case.

quoted

+	if (!q) {
+		kfree(p);
+		return -ENOMEM;
+	}
+
+	node->next = p;
+	node->prev = q;
+	node->level = level;
+	return 0;
+}
+

diff --git a/fs/btrfs/skiplist.h b/fs/btrfs/skiplist.h
new file mode 100644
index 0000000..3e414b5
--- /dev/null
+++ b/fs/btrfs/skiplist.h
+
+#define MAXLEVEL 16
+/* double p = 0.25; */
+
+struct sl_node {
+	struct sl_node **next;
+	struct sl_node **prev;
+	unsigned int level;
+	unsigned int head:1;

the bitfield will use another sizeof(int) bytes, but the level is at
most 16, you can reduce it's size eg to unsigned short.
on the other hand, the structure has to start at address aligned to
sizeof(void*) and the bytes after 'head' up to next sizeof(void*)
boundary will be left unusable anyway. then, 'head' could be a full int
or bool so the compiler is not restricted and forced to keep state of
the single bit. if access to these items is exptected to be frequent,
the diffenence could be mesurable.

I see.  Thanks a lot for your advice!

thanks,
liubo

quoted

+};

david
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html