Red-Black tree traversal tests

Hello,

Postgres now has its own red-black tree implementation. This tree has 4
types of traversals. In the attachment, you can find module test that
checks the correctness of tree traversal strategies.

I hope that someone can find it useful.

Thank you for attention!

--
------
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi Victor,

> Postgres now has its own red-black tree implementation. This tree has 4
> types of traversals. In the attachment, you can find module test that
> checks the correctness of tree traversal strategies.
>
> I hope that someone can find it useful.

Great job! However, according to lcov report, some procedures declared
in rbtree.c are still not test covered even with your patch,
particularly:

* rb_find
* rb_leftmost
* rb_delete + dependencies (rb_delete_fixup, etc)

You can generate a corresponding report using this script [1].

I must say, I was a little surprised that rb_find is not used anywhere
in PostgreSQL code. Turned out that rbtree currently is used only by GIN
and it uses a small subset of all procedures.

If it's not too much trouble perhaps you could write a few more test so
we would have 100% test coverage for rbtree, could modify it safely and
be sure that it actually works when someone will need the rest of its
functionality?

[1]: https://github.com/afiskon/pgscripts/blob/master/code-coverage.sh

--
Best regards,
Aleksander Alekseev

Hi Victor,

> If it's not too much trouble perhaps you could write a few more test so
> we would have 100% test coverage for rbtree, could modify it safely and
> be sure that it actually works when someone will need the rest of its
> functionality?

Also I would recommend to add your patch to the nearest commitfest [1].
Otherwise there is a good chance that everyone will forget about it
quite soon.

[1]: https://commitfest.postgresql.org/14/

--
Best regards,
Aleksander Alekseev

Hello,

Thank you for the reviewing.
>> If it's not too much trouble perhaps you could write a few more test
>> so
>> we would have 100% test coverage for rbtree, could modify it safely
>> and
>> be sure that it actually works when someone will need the rest of its
>> functionality?

Done. Now all of the functions in rbtree.c are covered.

> Also I would recommend to add your patch to the nearest commitfest [1].
> Otherwise there is a good chance that everyone will forget about it
> quite soon.
>
> [1]: https://commitfest.postgresql.org/14/

Done. Here is the link: https://commitfest.postgresql.org/14/1225/

Thank you for attention!

--
------
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

I forgot to attach the patch. Sorry.
Here it is.
--
------
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi Victor,

> I forgot to attach the patch. Sorry.
> Here it is.

I would say that this patch is in a pretty good shape now. And I see a
99% code coverage of rbtree.c. Let's see what committers think.

--
Best regards,
Aleksander Alekseev

[ btw, please don't cc pgsql-hackers-owner, the list moderators don't
need the noise ]

Aleksander Alekseev <a(dot)alekseev(at)postgrespro(dot)ru> writes:
> I would say that this patch is in a pretty good shape now. And I see a
> 99% code coverage of rbtree.c. Let's see what committers think.

I took a quick look through the patch --- haven't tried to compile it
or anything like that --- and have a few comments:

* There's some typos, eg extention should be extension, triversal
should be traversal. Maybe try a spell checker?

* The diff complains about lack of file-ending newlines in several
places.

* There's something weird at the start of test.c:

@@ -0,0 +1,577 @@
+/*--------------------------------------------------------------------------

Maybe your compiler thinks that's a BOM? It's hard to see how it
compiles otherwise.

* I think it might be simpler to have the module expose just one SQL
function that invokes all these individual tests internally. Less
boilerplate text that way, and less to change if you add more tests
later. Also, you might consider passing in TEST_SIZE as an argument
of the SQL function instead of having it be hard-wired.

* We don't do C++-style (//) comments around here. Please use C
style. (You might consider running the code through pgindent,
which will convert those comments automatically.)

* It's also generally not per project style to use malloc/calloc/free
directly in backend code; and it's certainly not cool to use malloc or
calloc and then not check for a null result. Use palloc instead. Given
the short runtime of this test, you likely needn't be too worried about
pfree'ing stuff.

* _PG_init() declaration seems to be a leftover? <stdio.h> doesn't
belong here either, as postgres.h will bring that in for you.

* I know next to zip about red-black trees, but it disturbs me that
the traversal tests use trees whose values were inserted in strictly
increasing order. Seems like that's not proving as much as it could.
I wonder how hard it would be to insert those integers in random order.

* I'm not too pleased that the rb_find calls mostly just assume that
the find won't return NULL. You should be testing for that and reporting
the problem, not just dying on a null pointer crash if it happens.

* Possibly the tests should exercise rb_delete on keys *not* present.
And how about insertion of already-existing keys? Although that's
a bit outside the scope of testing traversal, so if you want to leave
it for some future expansion, that'd be OK.

I'll set this back to Waiting on Author. I do encourage you to finish
it up.

regards, tom lane

Dear Tom,

Thank you very much for your review. In the attachment you can find v2
of the patch.

On 2017-09-07 01:38, Tom Lane wrote:
> [ btw, please don't cc pgsql-hackers-owner, the list moderators don't
> need the noise ]
>
> Aleksander Alekseev <a(dot)alekseev(at)postgrespro(dot)ru> writes:
>> I would say that this patch is in a pretty good shape now. And I see a
>> 99% code coverage of rbtree.c. Let's see what committers think.
>
> I took a quick look through the patch --- haven't tried to compile it
> or anything like that --- and have a few comments:
>
> * There's some typos, eg extention should be extension, triversal
> should be traversal. Maybe try a spell checker?

Done. I fixed all spelling mistakes that i found.

>
> * The diff complains about lack of file-ending newlines in several
> places
>
> * There's something weird at the start of test.c:
>
> @@ -0,0 +1,577 @@
> +/*--------------------------------------------------------------------------
>
> Maybe your compiler thinks that's a BOM? It's hard to see how it
> compiles otherwise.

Now it is in UTF-8 without BOM. It seems that there is no such data in
the beginning
of the test.c

> * I think it might be simpler to have the module expose just one SQL
> function that invokes all these individual tests internally. Less
> boilerplate text that way, and less to change if you add more tests
> later. Also, you might consider passing in TEST_SIZE as an argument
> of the SQL function instead of having it be hard-wired.
You are right. Done.
>
> * We don't do C++-style (//) comments around here. Please use C
> style. (You might consider running the code through pgindent,
> which will convert those comments automatically.)

Fixed.

>
> * It's also generally not per project style to use malloc/calloc/free
> directly in backend code; and it's certainly not cool to use malloc or
> calloc and then not check for a null result. Use palloc instead.
> Given
> the short runtime of this test, you likely needn't be too worried about
> pfree'ing stuff.
>
> * _PG_init() declaration seems to be a leftover? <stdio.h> doesn't
> belong here either, as postgres.h will bring that in for you.
>
> * I know next to zip about red-black trees, but it disturbs me that
> the traversal tests use trees whose values were inserted in strictly
> increasing order. Seems like that's not proving as much as it could.
> I wonder how hard it would be to insert those integers in random order.
>
> * I'm not too pleased that the rb_find calls mostly just assume that
> the find won't return NULL. You should be testing for that and
> reporting
> the problem, not just dying on a null pointer crash if it happens.

Done.

>
> * Possibly the tests should exercise rb_delete on keys *not* present.
> And how about insertion of already-existing keys? Although that's
> a bit outside the scope of testing traversal, so if you want to leave
> it for some future expansion, that'd be OK.

Deletion requires to get pointer to the tree node. Otherwise it could
break
the tree. It is mentioned in the description of the rb_delete function.
" * "node" must have previously been found via rb_find or rb_leftmost."

Insertion of the same elements is managed by the specific implementation
of the tree. One of the input arguments of the rb_create function is
combiner function that will be called in case of repeated insertion.

However, during looking through this i found that nobody checks that
combiner function(as well as comparator, freefunc and allocfunc) is
not NULL. So if it was not specified, postgres will fall. I think that
it is better to add this checks.

>
> I'll set this back to Waiting on Author. I do encourage you to finish
> it up.
>
> regards, tom lane

--
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, Sep 8, 2017 at 9:03 PM, Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru> wrote:
> Thank you very much for your review. In the attachment you can find v2 of
> the patch.

FYI this version crashes for me:

test test_rbtree ... FAILED (test process exited with exit code 2)

It's trying to call rb->combiner which is null.

(lldb) bt
* thread #1: tid = 0x0000, 0x0000000000000000, stop reason = signal SIGSTOP
frame #0: 0x0000000000000000
* frame #1: 0x000000010c6fd9e0
postgres`rb_insert(rb=0x00007fe7e2029850, data=0x00007fff5380aa10,
isNew="") + 128 at rbtree.c:419
frame #2: 0x000000010cffbfb9
test_rbtree.so`testdelete(size=100000, delsize=10000) + 425 at
test.c:558
frame #3: 0x000000010cffb298
test_rbtree.so`testrbtree(fcinfo=0x00007fe7e200d9a8) + 104 at
test.c:630
frame #4: 0x000000010c6a03be
postgres`ExecInterpExpr(state=0x00007fe7e200d8c0,
econtext=0x00007fe7e200d570, isnull="") + 2702 at execExprInterp.c:672
frame #5: 0x000000010c6e005b
postgres`ExecEvalExprSwitchContext(state=0x00007fe7e200d8c0,
econtext=0x00007fe7e200d570, isNull="") + 59 at executor.h:309
frame #6: 0x000000010c6dffee
postgres`ExecProject(projInfo=0x00007fe7e200d8b8) + 78 at
executor.h:343
frame #7: 0x000000010c6dfd5c
postgres`ExecResult(pstate=0x00007fe7e200d458) + 332 at
nodeResult.c:136
frame #8: 0x000000010c6b2912
postgres`ExecProcNodeFirst(node=0x00007fe7e200d458) + 82 at
execProcnode.c:430
frame #9: 0x000000010c6af352
postgres`ExecProcNode(node=0x00007fe7e200d458) + 50 at executor.h:251
frame #10: 0x000000010c6ab0f6
postgres`ExecutePlan(estate=0x00007fe7e200d240,
planstate=0x00007fe7e200d458, use_parallel_mode='\0',
operation=CMD_SELECT, sendTuples='\x01', numberTuples=0,
direction=ForwardScanDirection, dest=0x00007fe7e200aa20,
execute_once='\x01') + 182 at execMain.c:1720
frame #11: 0x000000010c6aafcb
postgres`standard_ExecutorRun(queryDesc=0x00007fe7e2004040,
direction=ForwardScanDirection, count=0, execute_once='\x01') + 571 at
execMain.c:363
frame #12: 0x000000010c6aad87
postgres`ExecutorRun(queryDesc=0x00007fe7e2004040,
direction=ForwardScanDirection, count=0, execute_once='\x01') + 87 at
execMain.c:306
frame #13: 0x000000010c8b5bf2
postgres`PortalRunSelect(portal=0x00007fe7e2000040, forward='\x01',
count=0, dest=0x00007fe7e200aa20) + 306 at pquery.c:932
frame #14: 0x000000010c8b55ba
postgres`PortalRun(portal=0x00007fe7e2000040,
count=9223372036854775807, isTopLevel='\x01', run_once='\x01',
dest=0x00007fe7e200aa20, altdest=0x00007fe7e200aa20, completionTag="")
+ 762 at pquery.c:773
frame #15: 0x000000010c8b0f24
postgres`exec_simple_query(query_string="SELECT testrbtree(100000);")
+ 1316 at postgres.c:1109
frame #16: 0x000000010c8b0127 postgres`PostgresMain(argc=1,
argv=0x00007fe7e180bd10, dbname="contrib_regression",
username="munro") + 2375 at postgres.c:4103
frame #17: 0x000000010c7f712e
postgres`BackendRun(port=0x00007fe7e0d00db0) + 654 at
postmaster.c:4357
frame #18: 0x000000010c7f64b3
postgres`BackendStartup(port=0x00007fe7e0d00db0) + 483 at
postmaster.c:4029
frame #19: 0x000000010c7f54a5 postgres`ServerLoop + 597 at postmaster.c:1753
frame #20: 0x000000010c7f2c91 postgres`PostmasterMain(argc=8,
argv=0x00007fe7e0c03860) + 5553 at postmaster.c:1361
frame #21: 0x000000010c716799 postgres`main(argc=8,
argv=0x00007fe7e0c03860) + 761 at main.c:228
frame #22: 0x00007fff8333a5ad libdyld.dylib`start + 1
(lldb) f 1
frame #1: 0x000000010c6fd9e0 postgres`rb_insert(rb=0x00007fe7e2029850,
data=0x00007fff5380aa10, isNew="") + 128 at rbtree.c:419
416 /*
417 * Found node with given key. Apply combiner.
418 */
-> 419 rb->combiner(current, data, rb->arg);
420 *isNew = false;
421 return current;
422 }
(lldb) print *rb
(RBTree) $2 = {
root = 0x00007fe7e4419b60
node_size = 40
comparator = 0x000000010cffc310 (test_rbtree.so`cmp at int_rbtree.h:28)
combiner = 0x0000000000000000
allocfunc = 0x000000010cffc340 (test_rbtree.so`alloc at int_rbtree.h:37)
freefunc = 0x000000010cffc370 (test_rbtree.so`fr at int_rbtree.h:45)
arg = 0x0000000000000000
}

--
Thomas Munro
http://www.enterprisedb.com

On 2017-09-08 15:23, Thomas Munro wrote:
> On Fri, Sep 8, 2017 at 9:03 PM, Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru>
> wrote:
>> Thank you very much for your review. In the attachment you can find v2
>> of
>> the patch.
>
> FYI this version crashes for me:
>
> test test_rbtree ... FAILED (test process exited with exit
> code 2)
>
> It's trying to call rb->combiner which is null.
>
Thank you for pointing on it. Here is a fixed version.

--
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Victor Drobny <v(dot)drobny(at)postgrespro(dot)ru> writes:
> On 2017-09-08 15:23, Thomas Munro wrote:
>> It's trying to call rb->combiner which is null.

> Thank you for pointing on it. Here is a fixed version.

Actually, I think we *do* want the tests to call the combiner
occasionally ...

I whacked this around quite a bit and had gotten it to a state
that I thought was committable, when it occurred to me to wonder
why exactly we're going to this much effort to test the preorder
and postorder traversal logic. I'm inclined to think we should
rip that out, instead, because I can think of no reason that
anyone would ever want to use it in Postgres.

I'll make that argument in a separate thread, so it gets a little
more visibility in the pgsql-hackers firehose.

In the meantime, here's my version. Notable changes:

* Got rid of separate .h file; seemed pointless, especially
since the combiner function needs to know what the test
expectations are.
* Corrected the random-permutation algorithm.
* Made the preorder/postorder check logic more paranoid
(though I now feel that was a waste of effort).
* Improved English grammar in a lot of comments.
* Added some more test cases; code coverage report shows
that this exercises every non-error-case line in rbtree.c.
* Added an rbtree "rb_root()" function to avoid the unsafe
casting the previous version did to get the root pointer.
* Removed the assumption that the nil element is unique;
now it just knows that a leaf element points to itself.

We could dispense with rb_root(), as well as the test code's knowledge
about RBNIL representation, if we dropped the preorder/postorder cases
... which is another good reason to do so.

regards, tom lane

I wrote:
> In the meantime, here's my version. Notable changes:

I went ahead and pushed this, with the removal of the preorder/postorder
code, so we can see if the buildfarm finds out anything interesting.
Feel free to continue to submit improvements though.

One thing that occurred to me is that as-is, this is entirely black-box
testing. It doesn't try to check that the tree actually satisfies the
RB invariants, which is something that is interesting for performance
reasons. (That is, the code could pass these tests even though it
produces an unbalanced tree with horrible performance.) Is it worth
adding logic for that? Not sure. It's not like we are actively
changing the RB code or have reason to think it is buggy.

regards, tom lane