Re: [PATCHES] WIP: rewrite numeric division
Gregory Stark <[EMAIL PROTECTED]> writes: > Where did we get the CVS-HEAD algorithm from anyways? IIRC it's from Smith's "FM" library cited in numeric.c, which is also where most of numeric.c's higher-order-function algorithms came from. It's good code but oriented to scientific computing, which means it thinks that a close approximation to the right answer is good enough. In hindsight, there are too many people out there who expect div and mod to be exact for us to go with that approach. > wikipedia lists a whole > bunch of multiplication algorithms -- none of which sound like this -- but > only two division algorithms, "school-book" which is O(n^2) and Newton's > Method which has complexity equal to the multiplication method used. Yeah, my proposed patch is schoolbook division. I don't think I'd trust Newton's method to give anything but a close approximation, which is what we have in HEAD already. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [PATCHES] WIP: rewrite numeric division
"Tom Lane" <[EMAIL PROTECTED]> writes: > The bad news is that it's significantly slower than the CVS-HEAD code; > it appears that for long inputs, div_var is something like 4X slower > than before, depending on platform. Where did we get the CVS-HEAD algorithm from anyways? wikipedia lists a whole bunch of multiplication algorithms -- none of which sound like this -- but only two division algorithms, "school-book" which is O(n^2) and Newton's Method which has complexity equal to the multiplication method used. I'm not sure I see how to apply Newton's Method and get such low complexity though. It seems to me like you would have to repeatedly multiply so you should get an additional factor in the complexity representing the number of iterations necessary. > Still this is a bit annoying. Anyone see a way to speed it up, or > have another approach? What order of complexity is this algorithm? It looks basically like O(n^2) school-book division or is there something more clever going on? -- Gregory Stark EnterpriseDB http://www.enterprisedb.com ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
[PATCHES] Updated version of Numeric508
See -hackers thread for discussion.
Updated version of num508, against current CVS HEAD.
--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com
Index: src/backend/utils/adt/numeric.c
===
RCS file: /projects/cvsroot/pgsql/src/backend/utils/adt/numeric.c,v
retrieving revision 1.105
diff -c -r1.105 numeric.c
*** src/backend/utils/adt/numeric.c 15 Jun 2007 20:56:50 - 1.105
--- src/backend/utils/adt/numeric.c 17 Jun 2007 20:30:43 -
***
*** 85,93
#define MUL_GUARD_DIGITS 2 /* these are measured in NBASE digits */
#define DIV_GUARD_DIGITS 4
! typedef int16 NumericDigit;
#endif
/* --
* The value represented by a NumericVar is determined by the sign, weight,
--- 85,113
#define MUL_GUARD_DIGITS 2 /* these are measured in NBASE digits */
#define DIV_GUARD_DIGITS 4
! typedef uint16 NumericDigit;
#endif
+ /* -
+ * The storage format for NUMERIC is
+ *
+ * numeric header
+ * int32 varlen is the standard variable length header
+ * weight 8 bits in int8 so +/-127; -128 is reserved for NUMERIC_NAN
+ * scale 9 bits
+ * first 8 bits in uint8
+ * 9th bit is the high order bit of first digit
+ * signis the second highest bit of first digit
+ *
+ * numeric digits
+ * an array of NumericDigits, each element storing NBASE
+ * digits. All trailing and leading zeros are not stored,
+ * apart from when the value is Zero AND the scale > 255
+ * in which case we store a single zero digit, with the
+ * sign set to NUMERIC_POS so the actual stored value
+ * is equal to NUMERIC_DSCALE9_1
+ *--
+ */
/* --
* The value represented by a NumericVar is determined by the sign, weight,
***
*** 131,138
typedef struct NumericVar
{
int ndigits; /* # of digits in digits[] - can be 0! */
! int weight; /* weight of first digit */
! int sign; /* NUMERIC_POS, NUMERIC_NEG, or NUMERIC_NAN */
int dscale; /* display scale */
NumericDigit *buf; /* start of palloc'd space for digits[] */
NumericDigit *digits; /* base-NBASE digits */
--- 151,158
typedef struct NumericVar
{
int ndigits; /* # of digits in digits[] - can be 0! */
! int weight; /* weight of first digit, or NUMERIC_NAN */
! int sign; /* NUMERIC_POS, NUMERIC_NEG */
int dscale; /* display scale */
NumericDigit *buf; /* start of palloc'd space for digits[] */
NumericDigit *digits; /* base-NBASE digits */
***
*** 200,206
{2, 0, NUMERIC_POS, 1, NULL, const_one_point_one_data};
static NumericVar const_nan =
! {0, 0, NUMERIC_NAN, 0, NULL, NULL};
#if DEC_DIGITS == 4
static const int round_powers[4] = {0, 1000, 100, 10};
--- 220,226
{2, 0, NUMERIC_POS, 1, NULL, const_one_point_one_data};
static NumericVar const_nan =
! {0, NUMERIC_NAN, 0, 0, NULL, NULL};
#if DEC_DIGITS == 4
static const int round_powers[4] = {0, 1000, 100, 10};
***
*** 381,386
--- 401,412
*
* External format is a sequence of int16's:
* ndigits, weight, sign, dscale, NumericDigits.
+ *
+ * Note that the internal format is now different to the external format
+ * for the representation of NaN. In the external format, a value of
+ * NUMERIC_NAN_EXTERNAL in the sign field indicates NaN, which is converted
+ * into a NUMERIC_NAN in the weight field for the internal storage format and
+ * var formats. Sending data reverses this.
*/
Datum
numeric_recv(PG_FUNCTION_ARGS)
***
*** 407,426
alloc_var(&value, len);
value.weight = (int16) pq_getmsgint(buf, sizeof(int16));
value.sign = (uint16) pq_getmsgint(buf, sizeof(uint16));
if (!(value.sign == NUMERIC_POS ||
value.sign == NUMERIC_NEG ||
! value.sign == NUMERIC_NAN))
ereport(ERROR,
(errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
errmsg("invalid sign in external \"numeric\" value")));
value.dscale = (uint16) pq_getmsgint(buf, sizeof(uint16));
for (i = 0; i < len; i++)
{
NumericDigit d = pq_getmsgint(buf, sizeof(NumericDigit));
! if (d < 0 || d >= NBASE)
ereport(ERROR,
(errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
errmsg("invalid digit in external \"numeric\" value")));
--- 433,469
alloc_var(&value, len);
value.weight = (int16) pq_getmsgint(buf, sizeof(int16));
+ if (!(value.weight > NUMERIC_NAN ||
+ value.weight < NUMERIC_WEIGHT_MAX))
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
+ errmsg("invalid weight in external \"numeric\" value")));
+
value.sign = (uint16) pq_getmsgint(buf, sizeof(uint16));
if (!(value.sign == NUMERIC_POS ||
value.sign == NUMERIC_NEG ||
! value.sign == NUMERIC_NAN_EXTERNAL))
ereport(ERROR,
Re: [PATCHES] Remove comment about tab-complete.c
On Mon, Jun 18, 2007 at 10:02:21AM +0100, Simon Riggs wrote: > Remove line from guc.c > > 6. Add it to src/bin/psql/tab-complete.c, if it's a USERSET option. > > No longer required for parameters. Wow, a simple enough patch that I could "review" it in no time :-) Thanks, applied. //Magnus ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
[PATCHES] Remove comment about tab-complete.c
Remove line from guc.c 6. Add it to src/bin/psql/tab-complete.c, if it's a USERSET option. No longer required for parameters. -- Simon Riggs EnterpriseDB http://www.enterprisedb.com Index: src/backend/utils/misc/guc.c === RCS file: /projects/cvsroot/pgsql/src/backend/utils/misc/guc.c,v retrieving revision 1.397 diff -c -r1.397 guc.c *** src/backend/utils/misc/guc.c 13 Jun 2007 21:24:56 - 1.397 --- src/backend/utils/misc/guc.c 18 Jun 2007 09:01:32 - *** *** 417,427 * 5. Add it to src/backend/utils/misc/postgresql.conf.sample, if * appropriate * ! * 6. Add it to src/bin/psql/tab-complete.c, if it's a USERSET option. * ! * 7. Don't forget to document the option. ! * ! * 8. If it's a new GUC_LIST option you must edit pg_dumpall.c to ensure * it is not single quoted at dump time. */ --- 417,425 * 5. Add it to src/backend/utils/misc/postgresql.conf.sample, if * appropriate * ! * 6. Don't forget to document the option. * ! * 7. If it's a new GUC_LIST option you must edit pg_dumpall.c to ensure * it is not single quoted at dump time. */ ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [PATCHES] Maintaining cluster order on insert
"Heikki Linnakangas" <[EMAIL PROTECTED]> writes: > The reason for switching to the new API instead of the amsuggestblock API is > CPU overhead. It avoids constructing the IndexTuple twice and descending the > tree twice. I wonder if it's possible to finesse this. Have the suggestblock function remember the last block it suggested and somehow recognize when it's given the same tuple to index. Keeping the block pinned would still be the sticky point though. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
