public inbox for [email protected]help / color / mirror / Atom feed
[PATCH] implement trim_array 3+ messages / 3 participants [nested] [flat]
* [PATCH] implement trim_array @ 2021-02-16 17:38 Vik Fearing <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Vik Fearing @ 2021-02-16 17:38 UTC (permalink / raw) --- doc/src/sgml/func.sgml | 18 ++++++++++++ src/backend/catalog/sql_features.txt | 2 +- src/backend/utils/adt/arrayfuncs.c | 42 ++++++++++++++++++++++++++++ src/include/catalog/pg_proc.dat | 5 ++++ src/test/regress/expected/arrays.out | 23 +++++++++++++++ src/test/regress/sql/arrays.sql | 19 +++++++++++++ 6 files changed, 108 insertions(+), 1 deletion(-) diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml index 08f08322ca..2aac87cf8d 100644 --- a/doc/src/sgml/func.sgml +++ b/doc/src/sgml/func.sgml @@ -17909,6 +17909,24 @@ SELECT NULLIF(value, '(none)') ... </para></entry> </row> + <row> + <entry role="func_table_entry"><para role="func_signature"> + <indexterm> + <primary>trim_array</primary> + </indexterm> + <function>trim_array</function> ( <parameter>array</parameter> <type>anyarray</type>, <parameter>n</parameter> <type>integer</type> ) + <returnvalue>anyarray</returnvalue> + </para> + <para> + Trims an array by removing the last <parameter>n</parameter> elements. + If the array is multidimensional, only the first dimension is trimmed. + </para> + <para> + <literal>trim_array(ARRAY[1,2,3,4,5,6], 2)</literal> + <returnvalue>{1,2,3,4}</returnvalue> + </para></entry> + </row> + <row> <entry role="func_table_entry"><para role="func_signature"> <indexterm> diff --git a/src/backend/catalog/sql_features.txt b/src/backend/catalog/sql_features.txt index ab0895ce3c..32eed988ab 100644 --- a/src/backend/catalog/sql_features.txt +++ b/src/backend/catalog/sql_features.txt @@ -398,7 +398,7 @@ S301 Enhanced UNNEST YES S401 Distinct types based on array types NO S402 Distinct types based on distinct types NO S403 ARRAY_MAX_CARDINALITY NO -S404 TRIM_ARRAY NO +S404 TRIM_ARRAY YES T011 Timestamp in Information Schema NO T021 BINARY and VARBINARY data types NO T022 Advanced support for BINARY and VARBINARY data types NO diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c index f7012cc5d9..d38a99f0b0 100644 --- a/src/backend/utils/adt/arrayfuncs.c +++ b/src/backend/utils/adt/arrayfuncs.c @@ -6631,3 +6631,45 @@ width_bucket_array_variable(Datum operand, return left; } + +/* + * Trim the right N elements from an array by calculating an appropriate slice. + * Only the first dimension is trimmed. + */ +Datum +trim_array(PG_FUNCTION_ARGS) +{ + ArrayType *v = PG_GETARG_ARRAYTYPE_P(0); + int n = PG_GETARG_INT32(1); + int array_length = ARR_DIMS(v)[0]; + int16 elmlen; + bool elmbyval; + char elmalign; + int lower[MAXDIM]; + int upper[MAXDIM]; + bool lowerProvided[MAXDIM]; + bool upperProvided[MAXDIM]; + Datum result; + + /* Throw an error if out of bounds */ + if (n < 0 || n > array_length) + ereport(ERROR, + (errcode(ERRCODE_ARRAY_ELEMENT_ERROR), + errmsg("number of elements to trim must be between 0 and %d", array_length))); + + /* Set all the bounds as unprovided except the first upper bound */ + memset(lowerProvided, 0, sizeof(lowerProvided)); + memset(upperProvided, 0, sizeof(upperProvided)); + upper[0] = ARR_LBOUND(v)[0] + array_length - n - 1; + upperProvided[0] = true; + + /* Fetch the needed information about the element type */ + get_typlenbyvalalign(ARR_ELEMTYPE(v), &elmlen, &elmbyval, &elmalign); + + /* Get the slice */ + result = array_get_slice(PointerGetDatum(v), 1, + upper, lower, upperProvided, lowerProvided, + -1, elmlen, elmbyval, elmalign); + + PG_RETURN_DATUM(result); +} diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index 1487710d59..8ab911238d 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -1674,6 +1674,11 @@ proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8', proargtypes => 'internal oid internal int2 internal', prosrc => 'arraycontjoinsel' }, +{ oid => '8819', + descr => 'trim an array down to n elements', + proname => 'trim_array', proisstrict => 't', provolatile => 'i', + prorettype => 'anyarray', proargtypes => 'anyarray int4', + prosrc => 'trim_array' }, { oid => '764', descr => 'large object import', proname => 'lo_import', provolatile => 'v', proparallel => 'u', diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out index 8bc7721e7d..fd3e4bfc49 100644 --- a/src/test/regress/expected/arrays.out +++ b/src/test/regress/expected/arrays.out @@ -2399,3 +2399,26 @@ SELECT width_bucket(5, ARRAY[3, 4, NULL]); ERROR: thresholds array must not contain NULLs SELECT width_bucket(5, ARRAY[ARRAY[1, 2], ARRAY[3, 4]]); ERROR: thresholds must be one-dimensional array +-- trim_array +CREATE TABLE trim_array_test (arr integer[]); +INSERT INTO trim_array_test +VALUES ('[-15:-10]={1,2,3,4,5,6}'), + ('{1,2,3,4,5,6}'), + ('[10:15]={1,2,3,4,5,6}'), + ('{{1,10},{2,20},{3,30},{4,40},{5,50},{6,60}}'); +SELECT arr, trim_array(arr, 2) +FROM trim_array_test +ORDER BY arr; + arr | trim_array +---------------------------------------------+------------------------------- + [-15:-10]={1,2,3,4,5,6} | {1,2,3,4} + {1,2,3,4,5,6} | {1,2,3,4} + [10:15]={1,2,3,4,5,6} | {1,2,3,4} + {{1,10},{2,20},{3,30},{4,40},{5,50},{6,60}} | {{1,10},{2,20},{3,30},{4,40}} +(4 rows) + +DROP TABLE trim_array_test; +VALUES (trim_array(ARRAY[1, 2, 3], -1)); -- fail +ERROR: number of elements to trim must be between 0 and 3 +VALUES (trim_array(ARRAY[1, 2, 3], 10)); -- fail +ERROR: number of elements to trim must be between 0 and 3 diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql index c40619a8d5..551cf5c5c9 100644 --- a/src/test/regress/sql/arrays.sql +++ b/src/test/regress/sql/arrays.sql @@ -722,3 +722,22 @@ SELECT width_bucket(5, '{}'); SELECT width_bucket('5'::text, ARRAY[3, 4]::integer[]); SELECT width_bucket(5, ARRAY[3, 4, NULL]); SELECT width_bucket(5, ARRAY[ARRAY[1, 2], ARRAY[3, 4]]); + + +-- trim_array + +CREATE TABLE trim_array_test (arr integer[]); +INSERT INTO trim_array_test +VALUES ('[-15:-10]={1,2,3,4,5,6}'), + ('{1,2,3,4,5,6}'), + ('[10:15]={1,2,3,4,5,6}'), + ('{{1,10},{2,20},{3,30},{4,40},{5,50},{6,60}}'); + +SELECT arr, trim_array(arr, 2) +FROM trim_array_test +ORDER BY arr; + +DROP TABLE trim_array_test; + +VALUES (trim_array(ARRAY[1, 2, 3], -1)); -- fail +VALUES (trim_array(ARRAY[1, 2, 3], 10)); -- fail -- 2.25.1 --------------CD3F9594D6239C85433F5ED4-- ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-01 12:25 Dagfinn Ilmari Mannsåker <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Dagfinn Ilmari Mannsåker @ 2024-07-01 12:25 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: pgsql-hackers "Joel Jacobson" <[email protected]> writes: > Hello hackers, > > Attached patch introduces an optimization of mul_var() in numeric.c, > targeting cases where the multiplicands consist of only one or two > base-NBASE digits. Such small multiplicands can fit into an int64 and > thus be computed directly, resulting in a significant performance > improvement, between 26% - 34% benchmarked on Intel Core i9-14900K. > > This optimization is similar to commit d1b307eef2, that also targeted > one and two base-NBASE digit operands, but optimized div_var(). div_var() also has an optimisation for 3- and 4-digit operands under HAVE_INT128 (added in commit 0aa38db56bf), would that make sense in mul_var() too? > Regards, > Joel - ilmari ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-01 13:11 Joel Jacobson <[email protected]> parent: Dagfinn Ilmari Mannsåker <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Joel Jacobson @ 2024-07-01 13:11 UTC (permalink / raw) To: Dagfinn Ilmari Mannsåker <[email protected]>; +Cc: pgsql-hackers On Mon, Jul 1, 2024, at 14:25, Dagfinn Ilmari Mannsåker wrote: > div_var() also has an optimisation for 3- and 4-digit operands under > HAVE_INT128 (added in commit 0aa38db56bf), would that make sense in > mul_var() too? I considered it, but it only gives a marginal speed-up on Intel Core i9-14900K, and is actually slower on Apple M3 Max. Not really sure why. Maybe the code I tried can be optimized further: ``` #ifdef HAVE_INT128 /* * If var1 and var2 are up to four digits, their product will fit in * an int128 can be computed directly, which is significantly faster. */ if (var2ndigits <= 4) { int128 product = 0; switch (var1ndigits) { case 1: product = var1digits[0]; break; case 2: product = var1digits[0] * NBASE + var1digits[1]; break; case 3: product = ((int128) var1digits[0] * NBASE + var1digits[1]) * NBASE + var1digits[2]; break; case 4: product = (((int128) var1digits[0] * NBASE + var1digits[1]) * NBASE + var1digits[2]) * NBASE + var1digits[3]; break; } switch (var2ndigits) { case 1: product *= var2digits[0]; break; case 2: product *= var2digits[0] * NBASE + var2digits[1]; break; case 3: product = ((int128) var2digits[0] * NBASE + var2digits[1]) * NBASE + var2digits[2]; break; case 4: product = (((int128) var2digits[0] * NBASE + var2digits[1]) * NBASE + var2digits[2]) * NBASE + var2digits[3]; break; } alloc_var(result, res_ndigits); res_digits = result->digits; for (i = res_ndigits - 1; i >= 0; i--) { res_digits[i] = product % NBASE; product /= NBASE; } Assert(product == 0); /* * Finally, round the result to the requested precision. */ result->weight = res_weight; result->sign = res_sign; /* Round to target rscale (and set result->dscale) */ round_var(result, rscale); /* Strip leading and trailing zeroes */ strip_var(result); return; } #endif ``` Benchmark 1, testing 2 ndigits * 2 ndigits: SELECT timeit.pretty_time(total_time_a / 1e6 / executions,3) AS execution_time_a, timeit.pretty_time(total_time_b / 1e6 / executions,3) AS execution_time_b, total_time_a::numeric/total_time_b AS performance_ratio FROM timeit.cmp( 'numeric_mul', 'numeric_mul_patched', input_values := ARRAY[ '11112222', '33334444' ], min_time := 1000000, timeout := '10 s' ); Apple M3 Max: execution_time_a | execution_time_b | performance_ratio ------------------+------------------+-------------------- 32.2 ns | 20.5 ns | 1.5700112246809388 (1 row) Intel Core i9-14900K: execution_time_a | execution_time_b | performance_ratio ------------------+------------------+-------------------- 30.2 ns | 21.4 ns | 1.4113042510107371 (1 row) So 57% and 41% faster. Benchmark 2, testing 4 ndigits * 4 ndigits: SELECT timeit.pretty_time(total_time_a / 1e6 / executions,3) AS execution_time_a, timeit.pretty_time(total_time_b / 1e6 / executions,3) AS execution_time_b, total_time_a::numeric/total_time_b AS performance_ratio FROM timeit.cmp( 'numeric_mul', 'numeric_mul_patched', input_values := ARRAY[ '1111222233334444', '5555666677778888' ], min_time := 1000000, timeout := '10 s' ); Apple M3 Max: execution_time_a | execution_time_b | performance_ratio ------------------+------------------+------------------------ 41.9 ns | 51.3 ns | 0.81733655797170943614 (1 row) Intel Core i9-14900K: execution_time_a | execution_time_b | performance_ratio ------------------+------------------+-------------------- 40 ns | 38 ns | 1.0515610914706320 (1 row) So 18% slower on Apple M3 Max and just 5% faster on Intel Core i9-14900K. /Joel ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-07-01 13:11 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-02-16 17:38 [PATCH] implement trim_array Vik Fearing <[email protected]> 2024-07-01 12:25 Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Dagfinn Ilmari Mannsåker <[email protected]> 2024-07-01 13:11 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox