Обсуждение: [Patch] RBTree iteration interface improvement

Hello

While working on some new feature for PostgreSQL (which is still in
development and is irrelevant in this context) I noticed that current
RBTree implementation interface is following:

```
extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
extern RBNode *rb_iterate(RBTree *rb);
```

As you see it doesn't allow to do multiple iterations over a single
tree. I believe it's a major flaw for a general-purpose container.

Proposed patch introduces a new iteration interface that doesn't has
such a flaw. Naturally I wrote some unit tests, but I was not sure where
exactly to place them in PostgreSQL source code. For now I've just
uploaded them to GitHub:

https://github.com/afiskon/c-algorithms-examples/blob/master/rbtree_example.c

According to these tests new implementation works as fast as current
implementation and produces exactly same results.

I didn't dare to remove current interface since in theory some
extensions can use it. Still I believe such a move is worth considering.

--
Best regards,
Aleksander Alekseev

And as always, I didn't re-check a patch before sending it :) Here is a
corrected version without any fprintf's.

--
Best regards,
Aleksander Alekseev

On Wed, Jul 27, 2016 at 7:56 PM, Aleksander Alekseev
<a.alekseev@postgrespro.ru> wrote:
> Hello
>
> While working on some new feature for PostgreSQL (which is still in
> development and is irrelevant in this context) I noticed that current
> RBTree implementation interface is following:
>
> ```
> extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
> extern RBNode *rb_iterate(RBTree *rb);
> ```
>
> As you see it doesn't allow to do multiple iterations over a single
> tree. I believe it's a major flaw for a general-purpose container.
>

Can you explain use case where you need it?

-- 
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

> Can you explain use case where you need it?

Sure. You can consider RBTree as a container that always keeps its
elements in sorted order.  Now imagine you would like to write a code
like this:

```
/* iterate over items in sorted order */
while(item1 = left_right_walk(tree))
{
 /* another iteration, probably even in different procedure */ while(item2 = left_right_walk(tree)) {   /* ... some
logic... */ }
 

}
```

Currently you can't do it.

Or maybe you have different objects, e.g. IndexScanDesc's, that should
iterate over some tree's independently somewhere in indexam.c
procedures. Exact order may depend on user's query so you don't even
control it.

-- 
Best regards,
Aleksander Alekseev

Aleksander Alekseev <a.alekseev@postgrespro.ru> writes:
>> Can you explain use case where you need it?

> ... Or maybe you have different objects, e.g. IndexScanDesc's, that should
> iterate over some tree's independently somewhere in indexam.c
> procedures. Exact order may depend on user's query so you don't even
> control it.

It seems clear to me that the existing arrangement is hazardous for any
RBTree that hasn't got exactly one consumer.  I think Aleksander's plan to
decouple the iteration state is probably a good one (NB: I've not read the
patch, so this is not an endorsement of details).  I'd go so far as to say
that we should remove the old API as being dangerous, rather than preserve
it on backwards-compatibility grounds.  We make bigger changes than that
in internal APIs all the time.

Having said that, though: if the iteration state is not part of the
object, it's not very clear whether we can behave sanely if someone
changes the tree while an iteration is open.  It will need careful
thought as to what sort of guarantees we can make about that.  If it's
too weak, then a separated-state version would have enough hazards of
its own that it's not necessarily any safer.
        regards, tom lane

On Thu, Jul 28, 2016 at 1:57 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Aleksander Alekseev <a.alekseev@postgrespro.ru> writes:
>>> Can you explain use case where you need it?
>
>> ... Or maybe you have different objects, e.g. IndexScanDesc's, that should
>> iterate over some tree's independently somewhere in indexam.c
>> procedures. Exact order may depend on user's query so you don't even
>> control it.
>
> It seems clear to me that the existing arrangement is hazardous for any
> RBTree that hasn't got exactly one consumer.  I think Aleksander's plan to
> decouple the iteration state is probably a good one (NB: I've not read the
> patch, so this is not an endorsement of details).  I'd go so far as to say
> that we should remove the old API as being dangerous, rather than preserve
> it on backwards-compatibility grounds.  We make bigger changes than that
> in internal APIs all the time.
>
> Having said that, though: if the iteration state is not part of the
> object, it's not very clear whether we can behave sanely if someone
> changes the tree while an iteration is open.  It will need careful
> thought as to what sort of guarantees we can make about that.  If it's
> too weak, then a separated-state version would have enough hazards of
> its own that it's not necessarily any safer.

+1 to all of that.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

> > Having said that, though: if the iteration state is not part of the
> > object, it's not very clear whether we can behave sanely if someone
> > changes the tree while an iteration is open.  It will need careful
> > thought as to what sort of guarantees we can make about that.  If
> > it's too weak, then a separated-state version would have enough
> > hazards of its own that it's not necessarily any safer.  
> 
> +1 to all of that.
> 

The old API assumes that tree doesn't change during iteration. And it
doesn't do any checks about this. The new API behaves the same way. In
this sense patch at least doesn't make anything worse.

> It seems clear to me that the existing arrangement is hazardous for
> any RBTree that hasn't got exactly one consumer.  I think
> Aleksander's plan to decouple the iteration state is probably a good
> one (NB: I've not read the patch, so this is not an endorsement of
> details).  I'd go so far as to say that we should remove the old API
> as being dangerous, rather than preserve it on
> backwards-compatibility grounds.  We make bigger changes than that in
> internal APIs all the time.

Glad to hear it! I would like to propose a patch that removes the old
API. I have a few questions though.

Would you like it to be a separate patch, or all-in-one patch is fine
in this case? I also would like to include unit/property-based tests in
this (these) patch (patches). However as I understand there are
currently no unit tests in PostgreSQL at all, only integration/system
tests. Any advice how to do it better?

-- 
Best regards,
Aleksander Alekseev

> > It seems clear to me that the existing arrangement is hazardous for
> > any RBTree that hasn't got exactly one consumer.  I think
> > Aleksander's plan to decouple the iteration state is probably a good
> > one (NB: I've not read the patch, so this is not an endorsement of
> > details).  I'd go so far as to say that we should remove the old API
> > as being dangerous, rather than preserve it on
> > backwards-compatibility grounds.  We make bigger changes than that in
> > internal APIs all the time.
>
> Glad to hear it! I would like to propose a patch that removes the old
> API. I have a few questions though.
>
> Would you like it to be a separate patch, or all-in-one patch is fine
> in this case? I also would like to include unit/property-based tests in
> this (these) patch (patches). However as I understand there are
> currently no unit tests in PostgreSQL at all, only integration/system
> tests. Any advice how to do it better?

OK, here is a patch. I think we could call it a _replacement_ of an old API, so
there is probably no need in two separate patches. I still don't know how to
include unit test and whether they should be included at all. Thus for now
unit/property-based tests could be found only on GitHub [1].

As usual, if you have any questions, suggestions or notes regarding this patch,
please let me know.

[1] https://github.com/afiskon/c-algorithms/tree/master/test

--
Best regards,
Aleksander Alekseev

On 08/22/2016 01:00 PM, Aleksander Alekseev wrote:
>>> It seems clear to me that the existing arrangement is hazardous for
>>> any RBTree that hasn't got exactly one consumer.  I think
>>> Aleksander's plan to decouple the iteration state is probably a good
>>> one (NB: I've not read the patch, so this is not an endorsement of
>>> details).  I'd go so far as to say that we should remove the old API
>>> as being dangerous, rather than preserve it on
>>> backwards-compatibility grounds.  We make bigger changes than that in
>>> internal APIs all the time.
>>
>> Glad to hear it! I would like to propose a patch that removes the old
>> API. I have a few questions though.
>>
>> Would you like it to be a separate patch, or all-in-one patch is fine
>> in this case? I also would like to include unit/property-based tests in
>> this (these) patch (patches). However as I understand there are
>> currently no unit tests in PostgreSQL at all, only integration/system
>> tests. Any advice how to do it better?
>
> OK, here is a patch. I think we could call it a _replacement_ of an old API, so
> there is probably no need in two separate patches. I still don't know how to
> include unit test and whether they should be included at all. Thus for now
> unit/property-based tests could be found only on GitHub [1].
>
> As usual, if you have any questions, suggestions or notes regarding this patch,
> please let me know.

This also seems to change the API so that instead of a single
rb_begin_iterate()+rb_iterate() pair, there is a separate begin and
iterate function for each traversal order. That seems like an unrelated
change. Was there a particular reason for that? I think the old
rb_begin_iterate()+rb_iterate() functions were fine, we just need to
have a RBTreeIterator struct that's different from the tree itself.

Note that the API actually used to be like that. rb_begin_iterate() used
to return a palloc'd RBTreeIterator struct. It was changed in commit
0454f131, because the implementation didn't support more than one
iterator at a time, which made the separate struct pointless. But we're
fixing that problem now.

Another unrelated change in this patch is the addition of
rb_rightmost(). It's not used for anything, so I'm not sure what the
point is. Then again, there don't seem to be any callers of
rb_leftmost() either.

I think we should something like in the attached patch. It seems to pass
your test suite, but I haven't done any other testing on this. Does it
look OK to you?

- Heikki

Hello, Heikki.

Thank you for your attention to this patch!

> This also seems to change the API so that instead of a single 
> rb_begin_iterate()+rb_iterate() pair, there is a separate begin and 
> iterate function for each traversal order. That seems like an unrelated 
> change. Was there a particular reason for that? I think the old 
> rb_begin_iterate()+rb_iterate() functions were fine, we just need to 
> have a RBTreeIterator struct that's different from the tree itself.

I'm trying to avoid calling procedures by a pointer, an old habit. When
I started to work on this patch I just needed a RB-tree implementation
for a pet project. I took one from PostgreSQL code. Then I found this
flaw of iteration interface and decided to fix it. The idea to merge
this fix back to PostgreSQL code appeared later so I just wrote code the
way I like.

These days code performance depends on many factors like whether code
fits into cache, i.e not only on whether you call a procedure directly
or using a pointer. Until someone finds a real bottleneck here I think
current rb_begin_iterate()+rb_iterate() interface should do just fine.
> Another unrelated change in this patch is the addition of 
> rb_rightmost(). It's not used for anything, so I'm not sure what the 
> point is. Then again, there don't seem to be any callers of 
> rb_leftmost() either.

It's just something I needed in tests to reach a good percent of code
coverage. Implementation of rb_rightmost is trivial so we probably can do
without it.

> I think we should something like in the attached patch. It seems to pass 
> your test suite, but I haven't done any other testing on this. Does it
> look OK to you?

Looks good to me.

-- 
Best regards,
Aleksander Alekseev

On 08/26/2016 04:07 PM, Aleksander Alekseev wrote:
>> Another unrelated change in this patch is the addition of
>> rb_rightmost(). It's not used for anything, so I'm not sure what the
>> point is. Then again, there don't seem to be any callers of
>> rb_leftmost() either.
>
> It's just something I needed in tests to reach a good percent of code
> coverage. Implementation of rb_rightmost is trivial so we probably can do
> without it.

Looking closer, we don't currently use any of the iterators besides the 
left-right iterator either. Nor rb_delete().

>> I think we should something like in the attached patch. It seems to pass
>> your test suite, but I haven't done any other testing on this. Does it
>> look OK to you?
>
> Looks good to me.

Ok, committed.

- Heikki

> Ok, committed.
> 
> - Heikki

Thanks a lot for committing this patch and also for your contribution to
it!

-- 
Best regards,
Aleksander Alekseev