Skip site navigation (1) Skip section navigation (2)

Re: equal() perf tweak

From: Neil Conway <neilc(at)samurai(dot)com>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: PostgreSQL Patches <pgsql-patches(at)postgresql(dot)org>
Subject: Re: equal() perf tweak
Date: 2003-11-03 16:47:55
Message-ID: 1067878074.3089.348.camel@tokyo (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-patches
On Mon, 2003-11-03 at 10:04, Tom Lane wrote:
> You have effectively reverted the code to its previous slow state.

Erm, the original version of this code in CVS (from ~7 years ago) is the
following:

    case T_List:
	{
	    List *la = (List*)a;
	    List *lb = (List*)b;
	    List *l;

	    if (a==NULL && b==NULL)
		return (true);
	    if (length(a)!=length(b))
		return (false);
	    foreach(l, la) {
		if (!equal(lfirst(l), lfirst(lb)))
		    return (false);
		lb = lnext(lb);
	    }
	    retval = true;
	}
	break;

i.e. it is effectively the same as the code in CVS HEAD. To what
"previous state" does this patch revert the code?

> The problem with what you've done is that it recursively applies equal()
> to the list contents, which may take a very large number of cycles, only
> to eventually fail because one list is a prefix of the other.  The point
> of the current coding is to detect that condition before we recurse.

I don't understand: granted, this applies equal() to each element of the
list, but why would that be particularly slow?

equal() applied to the lfirst() of a list doesn't invoke equal() on a
T_List node (the tag of the lfirst() of the list is the data type of the
elements of the list), so there should only be a single level of
recursion.

I was going to benchmark this, but pulling the list code out of the rest
of the source is a bit hairy. Let me know if you think this would be
helpful.

-Neil



In response to

Responses

pgsql-hackers by date

Next:From: Neil ConwayDate: 2003-11-03 16:59:24
Subject: Re: adding support for posix_fadvise()
Previous:From: Christopher BrowneDate: 2003-11-03 16:32:49
Subject: RC1 on AIX - working thus far

pgsql-patches by date

Next:From: Neil ConwayDate: 2003-11-03 17:01:20
Subject: Re: bufmgr code cleanup
Previous:From: Tom LaneDate: 2003-11-03 15:04:39
Subject: Re: equal() perf tweak

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group