From: Volkan YAZICI <yazicivo@ttnet.net.tr>
To: pgsql-general@postgresql.org
Subject: Re: intarray internals
Date: Mon, 8 May 2006 22:38:02 +0300
Message-ID: <20060508193802.GA211@alamut> (raw)
In-Reply-To: <20060505214601.GA208@alamut>
References: <20060505214601.GA208@alamut>
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.
Attachments:intarray_same.patch.0 (text/plain, 2.3K) download
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);
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: yazicivo@ttnet.net.tr, pgsql-general@postgresql.org
Subject: Re: intarray internals
In-Reply-To: <20060508193802.GA211@alamut>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox