Re: [CFReview] Red-Black Tree

On Fri, Jan 29, 2010 at 9:00 AM, Mark Cave-Ayland
<mark(dot)cave-ayland(at)siriusit(dot)co(dot)uk> 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 live since I see it as analogous to the hash table
> implementation, i.e. it's a template RB-Tree implementation designed to
> be used as required throughout the codebase. backend/access seems to be
> the home of index AMs only.

Not really. access/common has things in it like reloptions.c and
printtup.c, which are clearly not index AMs.

I suppose another option is to put it in lib. The only things there
right now are dllinfo.c and stringinfo.c, but in some ways generic
in-memory red-black trees seem analagous to generic string buffers.

> - You correctly picked up on the namespace issue, although I noticed
> that you left RED and BLACK as they were. Maybe RBRED and RBBLACK would
> be better, though not that there are any colour related defines around
> in a database backend to make a name clash probable.

Yeah, I thought about that. Since you came up with it independently,
that's enough to make me think it's a good idea.

> - I found the name of the "appendator" method misleading - perhaps
> "updater" would make more sense?

I like the existing name better. It's a little weird but I find it descriptive.

>> 2. I'm a little concerned about the performance implications of this
>> patch.  Looking at http://www.sai.msu.su/~megera/wiki/2009-04-03, it's
>> clear that the patch is a huge win in some cases.  But I'm also
>> surprised by how much performance is lost in some of the other cases
>> that you tested.  I suspect, on balance, that it's probably still a
>> good idea to put this in, but I wonder if you've profiled this at all
>> to see where the extra time is going and/or explored possible ways of
>> squashing that overhead down a little more.
>>
>> 3. In ginInsertEntry(), the "else" branch of the if statement really
>> looks like magic when you first read it.  I wonder if it would make
>> sense to pull the contents of EAAllocate() directly into this
>> function, since there's only one call site anyhow.
>
> God yes. This is not a good example of maintainable code - even with your
> comment I struggled for a while to try and figure it out :(  I would suggest
> that this is refactored appropriately before commit.

Yeah it took me a while.

I think we need Teodor and Oleg to prepare a new version of this patch
based on these suggestions. This part, in particular, I feel like
they need to rework rather than us. I don't know the GIN code well
enough to be confident of what I'm doing. I have to say that it would
be easier to understand what's going on here if there were a few more
comments...

> 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...

> I shall now continue my review of the associated KNNGiST patch.

...especially if there is to be any thought of getting ANOTHER patch
after this one committed, too.

...Robert