From: Martin Kalcher <martin.kalcher@aboutsource.net>
To: Thomas Munro <thomas.munro@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Proposal to introduce a shuffle function to intarray extension
Date: Sun, 17 Jul 2022 18:15:51 +0200
Message-ID: <5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net> (raw)
In-Reply-To: <CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net>
<CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com>
<b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net>
<4073858.1658027909@sss.pgh.pa.us>
<4077925.1658029046@sss.pgh.pa.us>
<CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com>
Am 17.07.22 um 08:00 schrieb Thomas Munro:
>> Actually ... is there a reason to bother with an intarray version
>> at all, rather than going straight for an in-core anyarray function?
>> It's not obvious to me that an int4-only version would have
>> major performance advantages.
>
> Yeah, that seems like a good direction. If there is a performance
> advantage to specialising, then perhaps we only have to specialise on
> size, not type. Perhaps there could be a general function that
> internally looks out for typbyval && typlen == 4, and dispatches to a
> specialised 4-byte, and likewise for 8, if it can, and that'd already
> be enough to cover int, bigint, float etc, without needing
> specialisations for each type.
I played around with the idea of an anyarray shuffle(). The hard part
was to deal with arrays with variable length elements, as they can not
be swapped easily in place. I solved it by creating an intermediate
array of references to the elements. I'll attach a patch with the proof
of concept. Unfortunatly it is already about 5 times slower than the
specialised version and i am not sure if it is worth going down that road.
Martin
Attachments:0001-introduce-array_shuffle.patch (text/x-patch, 3.4K) download
From 85cb90c79459132c4220b8d78586dffe6e590ba9 Mon Sep 17 00:00:00 2001
From: Martin Kalcher <martin.kalcher@aboutsource.net>
Date: Sun, 17 Jul 2022 18:06:04 +0200
Subject: [PATCH] introduce array_shuffle()
---
src/backend/utils/adt/arrayfuncs.c | 73 ++++++++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 3 ++
2 files changed, 76 insertions(+)
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.cindex fb167f226a..b6576ce178 100644--- a/src/backend/utils/adt/arrayfuncs.c+++ b/src/backend/utils/adt/arrayfuncs.c@@ -6872,3 +6872,76 @@ trim_array(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
++Datum+array_shuffle(PG_FUNCTION_ARGS)+{+ ArrayType *array,+ *result;+ char *adat,+ *rdat;+ int nitems,+ i;+ Oid elemtype;+ TypeCacheEntry typentry;+ struct { char *dat; size_t size; } *refs;++ array = PG_GETARG_ARRAYTYPE_P(0);++ if (ARR_HASNULL(array))+ ereport(ERROR,+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),+ errmsg("shuffling arrays with null elements is not supported")));++ if (ARR_NDIM(array) > 1)+ ereport(ERROR,+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),+ errmsg("shuffling of multidimensional arrays is not supported")));++ elemtype = ARR_ELEMTYPE(array);+ typentry = *lookup_type_cache(elemtype, 0);+ nitems = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));+ refs = palloc(nitems * (sizeof(char *) + sizeof(size_t)));+ adat = ARR_DATA_PTR(array);++ /*+ * To allow shuffling of arrays with variable length elements, we are going+ * to shuffle references to the elements, because swapping variable length+ * elements in an array is complicated. In a second step we will iterate the+ * shuffled references and copy the elements to the destination array.+ * We are using the "inside-out" variant of the Fisher-Yates algorithm to+ * produce a shuffled array of references: Append each reference than swap it+ * with a radomly-chosen refence.+ */+ for (i = 0; i < nitems; i++)+ {+ int j = random() % (i + 1);+ char *next = att_addlength_pointer(adat, typentry.typlen, adat);+ next = (char *) att_align_nominal(next, typentry.typalign);+ refs[i] = refs[j];+ refs[j].dat = adat;+ refs[j].size = next - adat;+ adat = next;+ }++ result = create_array_envelope(ARR_NDIM(array),+ ARR_DIMS(array),+ ARR_LBOUND(array),+ ARR_SIZE(array),+ ARR_ELEMTYPE(array),+ array->dataoffset);++ rdat = ARR_DATA_PTR(result);++ /* Collect all references and copy elements to the destination array */+ for (i = 0; i < nitems; i++)+ {+ memcpy(rdat, refs[i].dat, refs[i].size);+ rdat += refs[i].size;+ }++ pfree(refs);+ PG_FREE_IF_COPY(array, 0);++ PG_RETURN_ARRAYTYPE_P(result);+}diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.datindex 2e41f4d9e8..56aff551d3 100644--- a/src/include/catalog/pg_proc.dat+++ b/src/include/catalog/pg_proc.dat@@ -1681,6 +1681,9 @@
proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8',
proargtypes => 'internal oid internal int2 internal',
prosrc => 'arraycontjoinsel' },
+{ oid => '7777', descr => 'shuffle array',+ proname => 'array_shuffle', proisstrict => 'f', prorettype => 'anyarray',+ proargtypes => 'anyarray', prosrc => 'array_shuffle' },
{ oid => '764', descr => 'large object import',
proname => 'lo_import', provolatile => 'v', proparallel => 'u',
--
2.37.1
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 from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-general@postgresql.org
Cc: martin.kalcher@aboutsource.net, thomas.munro@gmail.com, tgl@sss.pgh.pa.us, pgsql-hackers@lists.postgresql.org
Subject: Re: Proposal to introduce a shuffle function to intarray extension
In-Reply-To: <5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com> <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net> <4073858.1658027909@sss.pgh.pa.us> <4077925.1658029046@sss.pgh.pa.us> <CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com> <5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net>
* 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