Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Uladzislau Rezki <urezki@gmail.com>
Date:   Sat, 6 May 2023 13:42:24 +0200
To:     liuwf <liuwf@mailbox.org>
Cc:     linux-kernel@vger.kernel.org, joern@purestorage.com,
        torvalds@linux-foundation.org, urezki@gmail.com
Subject: Re: Library: [RFC PATCH] btree_blue - A simple btree with fast
 linear travesal and more. V4. and test data
Message-ID: <ZFY9IFM9zjFhvyPF@pc636>
References: <48d6f5a9788af056a212d0d5ba08219fdd592fbb.camel@mailbox.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <48d6f5a9788af056a212d0d5ba08219fdd592fbb.camel@mailbox.org>
Precedence: bulk

Hello, Liu.

Just one question. I tried to run your test-suite that compares
mapple_tree, btree, rb-tree and btree_blue. Also i wanted to have a
look at its performance in other workloads. Thus, i have one question:

>
> +void *btree_blue_remove(struct btree_blue_head *head, unsigned long *key)
> +{
> +	if (head->height == 0)
> +		return NULL;
> +
> +	return btree_blue_remove_level(head, key, 1);
> +}
> +EXPORT_SYMBOL_GPL(btree_blue_remove);
>
I added a small change:

<snip>
diff --git a/lib/btree_blue_test.c b/lib/btree_blue_test.c
index b0a73836523d..9dfbe9e6b8d5 100644
--- a/lib/btree_blue_test.c
+++ b/lib/btree_blue_test.c
@@ -530,6 +530,7 @@ static int btree_blue_test_init(void)
 
        t0 = ktime_get_ns();
        for (long i = 0; i < RANDOM_NR; i++) {
+               unsigned long *tmp_ptr;
                val_ptr =
                        btree_blue_remove(&btree_blue_root, &(data_set_2[i].k));
                if (!val_ptr) {
@@ -539,6 +540,14 @@ static int btree_blue_test_init(void)
                               i);
                        goto exit;
                }
+
+               tmp_ptr = btree_blue_remove(&btree_blue_root, &(data_set_2[i].k));
+               if (tmp_ptr) {
+                       err = -1;
+                       pr_err("btree_blue_remove %ld, val_ptr: 0x%lu, tmp_ptr: 0x%lu\n",
+                               i, (unsigned long) val_ptr, (unsigned long) tmp_ptr);
+                       goto exit;
+               }
        }
        t0 = ktime_get_ns() - t0;
        printk(KERN_EMERG "btree_blue %lu deletes use time: %lu ns\n",
<snip>

it removes two times same key. On a second removal i suspect
a ptr_val to be NULL but it is not:

<snip>
[   20.598023] btree 1000000 deletes use time: 251484314 ns
[   20.599360] btree_blue_remove 0, val_ptr: 0x17259549162592618731, tmp_ptr: 0x18273237390749509852
<snip>

Any thoughts?

Thanks!

--
Uladzislau Rezki