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]>
2024-07-01 13:11 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[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 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 ` Joel Jacobson <[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