Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-10 Thread Teodor Sigaev
Hey, but rb_freefunc is still there ... It will be reintroduced when ts_stat will be rewrited to use rbtree One very minor quibble: please make the $PostgreSQL$ lines be just that (i.e. remove everything between the : to the terminating $, keeping the latter) ok -- Teodor Sigaev

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-10 Thread Robert Haas
2010/2/10 Teodor Sigaev : >> So suppose at this point that step is the largest integer that can be >> represented... >>> >>> !       step ++; >> >> Boom. >>> >>> !       step>>= 1; > > step>>= 1; > step ++' > > Unboom? Yeah, that'll work. >>> ! >>> !       while(step>  0) { >>> !               in

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-10 Thread Alvaro Herrera
Teodor Sigaev escribió: > Also, rb_free is removed per Tom's comment. Can I commit the patch? Hey, but rb_freefunc is still there ... One very minor quibble: please make the $PostgreSQL$ lines be just that (i.e. remove everything between the : to the terminating $, keeping the latter) -- Alva

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-10 Thread Teodor Sigaev
So suppose at this point that step is the largest integer that can be represented... ! step ++; Boom. ! step>>= 1; step>>= 1; step ++' Unboom? ! ! while(step> 0) { ! int i; ! for (i = step-1; i< nentry; i += 2 * step) And similarly here...

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-09 Thread Robert Haas
2010/2/9 Teodor Sigaev : >>> Good idea, implemented. >> >> Hmm.  I think your implementation is prone to overflow in two places - >> both when computing step, and also when stepping through the array. > > Pls, point me, I don't see that > !       step |= (step >>  1); > !       step |= (step >>  2)

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-09 Thread Oleg Bartunov
On Mon, 8 Feb 2010, Tom Lane wrote: Robert Haas writes: On Mon, Feb 8, 2010 at 3:05 PM, Alvaro Herrera wrote: It seems a bit strange to have all the rb_free_recursive support and not use it anywhere ... and a freefunc callback even, whose only caller seems to set as null currently. ═Hmm, eve

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-09 Thread Teodor Sigaev
Good idea, implemented. Hmm. I think your implementation is prone to overflow in two places - both when computing step, and also when stepping through the array. Pls, point me, I don't see that ! step |= (step >> 1); ! step |= (step >> 2); ! step |= (step >> 4); ! s

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-09 Thread Alvaro Herrera
Robert Haas escribió: > On Mon, Feb 8, 2010 at 3:05 PM, Alvaro Herrera > wrote: > > How do we now that it works? > > Visual inspection? It's not very complicated. Well, that works if you assume the trivial/usual malloc/free coding style, but it fails in the hypothetical scenario I described ea

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Robert Haas
2010/2/8 Teodor Sigaev : >> I think that the code in ginInsertRecordBA() is needlessly complex. >> As far as I can see, nNodesOnCurrentLevel is always exactly one more >> than nNodesOnPreviousLevel, and I think step is also basically >> redundant with both of these although the relationship is a li

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Robert Haas
On Mon, Feb 8, 2010 at 10:43 PM, Tom Lane wrote: > Robert Haas writes: >> On Mon, Feb 8, 2010 at 3:05 PM, Alvaro Herrera >> wrote: >>> It seems a bit strange to have all the rb_free_recursive support and not >>> use it anywhere ... and a freefunc callback even, whose only caller >>> seems to set

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Tom Lane
Robert Haas writes: > On Mon, Feb 8, 2010 at 3:05 PM, Alvaro Herrera > wrote: >> It seems a bit strange to have all the rb_free_recursive support and not >> use it anywhere ... and a freefunc callback even, whose only caller >> seems to set as null currently.  Hmm, even in the knngist patch the >

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Robert Haas
On Mon, Feb 8, 2010 at 3:05 PM, Alvaro Herrera wrote: > It seems a bit strange to have all the rb_free_recursive support and not > use it anywhere ... and a freefunc callback even, whose only caller > seems to set as null currently.  Hmm, even in the knngist patch the > rb_freefunc stuff is unused

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Alvaro Herrera
It seems a bit strange to have all the rb_free_recursive support and not use it anywhere ... and a freefunc callback even, whose only caller seems to set as null currently. Hmm, even in the knngist patch the rb_freefunc stuff is unused. How do we now that it works? (What, for example, if we wer

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-08 Thread Teodor Sigaev
That looks pretty good. I confess I don't fully understand why it works. If we're inserting a bunch of equal-key entries, why does it matter what order we insert them in? Is there some code in here (where?) that breaks ties on the basis of where they are in the input data? Entries to insert i

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-05 Thread Robert Haas
2010/2/4 Teodor Sigaev : > Oleg's test (http://www.sai.msu.su/~megera/wiki/rbtree_test) are made with > v0.10 which is differ from 0.11 only by comments around ginInsertRecordBA() That looks pretty good. I confess I don't fully understand why it works. If we're inserting a bunch of equal-key ent

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-05 Thread Teodor Sigaev
That's all around 1% 0.7 patch = rbtest=# CREATE INDEX idin_rbtree_idx ON links2 USING gin (idin); CREATE INDEX Time: 1910741.352 ms rbtest=# CREATE INDEX idout_rbtree_idx ON links2 USING gin (idout); CREATE INDEX Time: 1647609.300 ms 0.11 patch == rbtest=# CREATE INDEX idin_

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-05 Thread Mark Cave-Ayland
Teodor Sigaev wrote: I would like to see point #2 of the following email addressed before commit. As things stand, it is not clear (at least to me) whether this is a win. Reimplementation of ginInsertRecordBA reduces difference of HEAD and HEAD+rbtree in regular case. Test suite is taken fr

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-04 Thread Teodor Sigaev
I would like to see point #2 of the following email addressed before commit. As things stand, it is not clear (at least to me) whether this is a win. Reimplementation of ginInsertRecordBA reduces difference of HEAD and HEAD+rbtree in regular case. Test suite is taken from http://www.sai.msu.s

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-04 Thread Oleg Bartunov
I'm in progress of preparing this page http://www.sai.msu.su/~megera/wiki/rbtree_test Hope, tests are easy to reproduce. This is slightly improved version of rbtree patch, Teodor didn't commit yet. Random array test and real-life examples are ok, I still working on test #1, which is quite arti

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-04 Thread Mark Cave-Ayland
Robert Haas wrote: Maybe we are now getting to the heart of the confusion. Mark wrote in his email: "Unfortunately I was not really able to reproduce the RND (teodor's) dataset, nor the random array test as the SQL used to test the implementation was not present on the page above." The SQL for

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Robert Haas
On Wed, Feb 3, 2010 at 4:51 PM, Oleg Bartunov wrote: > On Wed, 3 Feb 2010, Robert Haas wrote: > >>> I'll repeat my tests with current CVS HEAD. >> >> OK... can you post the exact queries that you are used for the >> previous round of testing? > > Robert, Mark posted all queries in his post ! See >

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Oleg Bartunov
On Wed, 3 Feb 2010, Robert Haas wrote: I'll repeat my tests with current CVS HEAD. OK... can you post the exact queries that you are used for the previous round of testing? Robert, Mark posted all queries in his post ! See http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Robert Haas
On Wed, Feb 3, 2010 at 4:17 PM, Oleg Bartunov wrote: > On Wed, 3 Feb 2010, Robert Haas wrote: > >>> Robert, Mark described the test he did >>> http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php >> >> So why did he get totally different answers than you? > > Because I did tests with

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Oleg Bartunov
On Wed, 3 Feb 2010, Robert Haas wrote: Robert, Mark described the test he did http://archives.postgresql.org/pgsql-hackers/2010-01/msg02927.php So why did he get totally different answers than you? Because I did tests with 8.3 and HEAD+rbtree, while Mark compared HEAD and HEAD+rbtree. Also,

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Robert Haas
2010/2/3 Oleg Bartunov : >>> I would like to see point #2 of the following email addressed before >>> commit.  As things stand, it is not clear (at least to me) whether >>> this is a win. >>> >>> http://archives.postgresql.org/pgsql-hackers/2010-01/msg02552.php >> >> Specifically, on this web page:

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Oleg Bartunov
On Wed, 3 Feb 2010, Robert Haas wrote: On Wed, Feb 3, 2010 at 8:48 AM, Robert Haas wrote: 2010/2/3 Teodor Sigaev : Can you rename RED and BLACK to RBRED and RBBLACK? Yes, of course, done. Any objections to commit? I would like to see point #2 of the following email addressed before commi

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Robert Haas
On Wed, Feb 3, 2010 at 8:48 AM, Robert Haas wrote: > 2010/2/3 Teodor Sigaev : >>> Can you rename RED and BLACK to RBRED and RBBLACK? >> >> Yes, of course, done. >> >> Any objections to commit? > > I would like to see point #2 of the following email addressed before > commit.  As things stand, it i

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Robert Haas
2010/2/3 Teodor Sigaev : >> Can you rename RED and BLACK to RBRED and RBBLACK? > > Yes, of course, done. > > Any objections to commit? I would like to see point #2 of the following email addressed before commit. As things stand, it is not clear (at least to me) whether this is a win. http://arch

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-03 Thread Teodor Sigaev
Can you rename RED and BLACK to RBRED and RBBLACK? Yes, of course, done. Any objections to commit? -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ rbtree-0.9.gz Description: Unix tar ar

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-02 Thread Robert Haas
2010/2/2 Teodor Sigaev : >>> >  With perhaps some minor tweaks to some of the names and a rework of >>> > the else >>> >  clause in ginInsertEntry(), I feel this patch is reasonably close to >>> > commit. >> >> Yeah, I think it can get there, but only if Oleg and Teodor provide an >> updated versio

Re: [HACKERS] [CFReview] Red-Black Tree

2010-02-02 Thread Teodor Sigaev
> With perhaps some minor tweaks to some of the names and a rework of the else > clause in ginInsertEntry(), I feel this patch is reasonably close to commit. Yeah, I think it can get there, but only if Oleg and Teodor provide an updated version pretty soon... Updated version of patch based o

Re: [HACKERS] [CFReview] Red-Black Tree

2010-01-29 Thread Tom Lane
Robert Haas writes: > On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland > wrote: >> ... In terms of location, I think utils/misc is a reasonable >> place for it to live since I see it as analogous to the hash table >> implementation, i.e. it's a template RB-Tree implementation designed to >> be u

Re: [HACKERS] [CFReview] Red-Black Tree

2010-01-29 Thread Robert Haas
On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland wrote: > I'm happy that the code is a reasonable implementation of an RB-Tree, at > least with respect to the link to the related public domain source that > was posted. In terms of location, I think utils/misc is a reasonable > place for it to liv

[HACKERS] [CFReview] Red-Black Tree

2010-01-29 Thread Mark Cave-Ayland
Hi Robert, I've also spent some time reviewing this patch since it is a pre-requisite to the KNNGiST patch. I did have a much more comprehensive list of suggestions, but it seems you've managed to resolve most of these with your latest re-write. Please find some more comments inline: Here's an