Date: Mon, 8 May 2006 22:38:02 +0300
From: Volkan YAZICI <yazicivo@ttnet.net.tr>
To: pgsql-general@postgresql.org
Subject: Re: intarray internals
Message-ID: <20060508193802.GA211@alamut>
References: <20060505214601.GA208@alamut>
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="u3/rZRmxL6MmkK24"
Content-Disposition: inline
In-Reply-To: <20060505214601.GA208@alamut>
User-Agent: Mutt/1.4.2.1i


--u3/rZRmxL6MmkK24
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi,

[I'm trying to share some of my thoughts about intarray contrib module.
If this is the wrong way to achieve this, please warn me. (Should I
first get in touch with Teodor Sigaev and Oleg Bartunov?)]

[6]
_int_same() in _int_op.c looks like making some redundant sorting and
not taking advantage of sorted arrays while comparing each other. Here's
the related code piece:

SORT(a);
SORT(b);
na = ARRNELEMS(a);
nb = ARRNELEMS(b);
da = ARRPTR(a);
db = ARRPTR(b);

result = FALSE;

if (na == nb)                                                                      
{   
    result = TRUE;
    for (n = 0; n < na; n++)
        if (da[n] != db[n])
        {
            result = FALSE;
            break;
        }
}

IMHO, SORT() macro should be called after "if (na == nb)" block. (SORT()
doesn't remove duplicates.) Also, in the inner block, while comparing
two arrays, we can take advantage of sorting of arrays. While current
behaviour is like

if (A[0] == B[0] && A[1] == B[1] && ...)

we can replace it with sth like

if (A[0] == B[0] && A[  N] == B[  N] &&
    A[1] == B[1] && A[N-1] == B[N-1] &&
    ...)

Attached patch tries to implement both behaviours mentioned above and
some minor hacking for arrays of 1,2 and 3 items.


Regards.

--u3/rZRmxL6MmkK24
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="intarray_same.patch.0"

Index: contrib/intarray/_int_op.c
===================================================================
RCS file: /projects/cvsroot/pgsql/contrib/intarray/_int_op.c,v
retrieving revision 1.4
diff -c -r1.4 _int_op.c
*** contrib/intarray/_int_op.c	19 Nov 2005 03:00:09 -0000	1.4
--- contrib/intarray/_int_op.c	8 May 2006 18:50:43 -0000
***************
*** 69,77 ****
  	ArrayType  *b = (ArrayType *) DatumGetPointer(PG_DETOAST_DATUM_COPY(PG_GETARG_DATUM(1)));
  	int			na,
  				nb;
- 	int			n;
- 	int		   *da,
- 			   *db;
  	bool		result;
  	bool		avoid;
  	bool		bvoid;
--- 69,74 ----
***************
*** 83,106 ****
  	if (avoid || bvoid)
  		return (avoid && bvoid) ? TRUE : FALSE;
  
- 	SORT(a);
- 	SORT(b);
  	na = ARRNELEMS(a);
  	nb = ARRNELEMS(b);
! 	da = ARRPTR(a);
! 	db = ARRPTR(b);
! 
  	result = FALSE;
  
  	if (na == nb)
  	{
! 		result = TRUE;
! 		for (n = 0; n < na; n++)
! 			if (da[n] != db[n])
! 			{
! 				result = FALSE;
  				break;
  			}
  	}
  
  	pfree(a);
--- 80,155 ----
  	if (avoid || bvoid)
  		return (avoid && bvoid) ? TRUE : FALSE;
  
  	na = ARRNELEMS(a);
  	nb = ARRNELEMS(b);
! 	
  	result = FALSE;
  
  	if (na == nb)
  	{
! 		int	*da;
! 		int *db;
! 		
! 		SORT(a);
! 		SORT(b);
! 		da = ARRPTR(a);
! 		db = ARRPTR(b);
! 
! 		switch (na)
! 		{
! 			/*
! 			 * Some little hack for small length arrays.
! 			 */
! 			case 1:
! 				result = (da[0] == db[0]) ? TRUE : FALSE;
  				break;
+ 
+ 			case 2:
+ 				result = (da[0] == db[0] &&
+ 						  da[1] == db[1]) ? TRUE : FALSE;
+ 				break;
+ 
+ 			case 3:
+ 				result = (da[0] == db[0] &&
+ 						  da[1] == db[1] &&
+ 						  da[2] == db[2]) ? TRUE : FALSE;
+ 				break;
+ 
+ 			/*
+ 			 * Instead of making a brute force comparison, trying to take
+ 			 * advantage of sorted arrays.
+ 			 */
+ 			default:
+ 			{
+ 				int head = 0;
+ 				int toe = na - 1;
+ 				
+ 				result = TRUE;
+ 				
+ 				/*
+ 				 * Don't bother with even length arrays. Consume their first
+ 				 * element and carry on as arrays' lengths are odd.
+ 				 */
+ 				if (na % 2 == 0)
+ 				{
+ 					result = (*da++ == *db++) ? TRUE : FALSE;
+ 					toe--;
+ 				}
+ 		
+ 				if (result == TRUE)
+ 					while (head <= toe)
+ 					{
+ 						if (da[head] != db[head] || da[toe] != db[toe])
+ 						{
+ 							result = FALSE;
+ 							break;
+ 						}
+ 		
+ 						head++;
+ 						toe--;
+ 					}
  			}
+ 		}
  	}
  
  	pfree(a);

--u3/rZRmxL6MmkK24--