Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oDDPI-0004Sd-Th for pgsql-hackers@arkaria.postgresql.org; Sun, 17 Jul 2022 23:10:37 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1oDDPH-0008Dj-GG for pgsql-hackers@arkaria.postgresql.org; Sun, 17 Jul 2022 23:10:35 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oDDMG-0002em-Mn for pgsql-hackers@lists.postgresql.org; Sun, 17 Jul 2022 23:07:28 +0000 Received: from mout-b-110.mailbox.org ([2001:67c:2050:102:465::110]) by magus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oDDME-0004RE-Ju for pgsql-hackers@lists.postgresql.org; Sun, 17 Jul 2022 23:07:28 +0000 Received: from smtp202.mailbox.org (smtp202.mailbox.org [IPv6:2001:67c:2050:b231:465::202]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-b-110.mailbox.org (Postfix) with ESMTPS id 4LmLMw0dBTz9sQk; Mon, 18 Jul 2022 01:07:24 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aboutsource.net; s=MBO0001; t=1658099244; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=k1YNAoXegfljh/GijYuyABtn8jCln2fhA3RSG1J5FMQ=; b=0yTOHOvKTrkjaIlDEa7f6U6j57zjRbzqTzuMmtnEUVoQEEEZift1JnKkIRJpOAkVBF5uYy P+T4G4kRSvC7BvqKyDEj+JgIBqnDQzmMpAvms5/6Ni4NFFC4s2BlmE2OZjGAsJIVur6832 HxTQ7apAq+q0/Eyr94m3OKs5r57pHYoWfQP8F755L4V5vhnbb3jlfDALtP9oyg4kkJLHhv syC3aQ6CdLtUVlcPiFWh2WksK0vORKlGmiIZS2lhRF1ZvR90v3aV/oP2e53Hs2DW4jG6IT Klyc78sTEKusUvKEi268Wi+oKaT86pMunMFhnA/P/Zz6cIA7OLstuz7Voo/LNg== Content-Type: multipart/mixed; boundary="------------ehXxvYxGsBqOWF8Yi9z0PZEd" Message-ID: <3c8e5531-aa1b-0d85-115c-540dc2a16b24@aboutsource.net> Date: Mon, 18 Jul 2022 01:07:22 +0200 MIME-Version: 1.0 Subject: Re: Proposal to introduce a shuffle function to intarray extension Content-Language: de-DE To: Thomas Munro Cc: Tom Lane , PostgreSQL Hackers References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <4073858.1658027909@sss.pgh.pa.us> <4077925.1658029046@sss.pgh.pa.us> <5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net> From: Martin Kalcher In-Reply-To: X-Rspamd-Queue-Id: 4LmLMw0dBTz9sQk List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------ehXxvYxGsBqOWF8Yi9z0PZEd Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Am 18.07.22 um 00:37 schrieb Thomas Munro: > Seems OK for a worst case. It must still be a lot faster than doing > it in SQL. Now I wonder what the exact requirements would be to > dispatch to a faster version that would handle int4. I haven't > studied this in detail but perhaps to dispatch to a fast shuffle for > objects of size X, the requirement would be something like typlen == X > && align_bytes <= typlen && typlen % align_bytes == 0, where > align_bytes is typalign converted to ALIGNOF_{CHAR,SHORT,INT,DOUBLE}? > Or in English, 'the data consists of densely packed objects of fixed > size X, no padding'. Or perhaps you can work out the padded size and > use that, to catch a few more types. Then you call > array_shuffle_{2,4,8}() as appropriate, which should be as fast as > your original int[] proposal, but work also for float, date, ...? > > About your experimental patch, I haven't reviewed it properly or tried > it but I wonder if uint32 dat_offset, uint32 size (= half size > elements) would be enough due to limitations on varlenas. I made another experimental patch with fast tracks for typelen4 and typelen8. alignments are not yet considered. --------------ehXxvYxGsBqOWF8Yi9z0PZEd Content-Type: text/x-patch; charset=UTF-8; name="0001-introduce-array_shuffle.patch" Content-Disposition: attachment; filename="0001-introduce-array_shuffle.patch" Content-Transfer-Encoding: base64 RnJvbSAzNzI2OTU5OGExZGFjZTk5YzkwNTk1MTRlMGZkY2I5MGI5MjQwZWQzIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBNYXJ0aW4gS2FsY2hlciA8bWFydGluLmthbGNoZXJA YWJvdXRzb3VyY2UubmV0PgpEYXRlOiBTdW4sIDE3IEp1bCAyMDIyIDE4OjA2OjA0ICswMjAw ClN1YmplY3Q6IFtQQVRDSF0gaW50cm9kdWNlIGFycmF5X3NodWZmbGUoKQoKLS0tCiBzcmMv YmFja2VuZC91dGlscy9hZHQvYXJyYXlmdW5jcy5jIHwgMTc4ICsrKysrKysrKysrKysrKysr KysrKysrKysrKysrCiBzcmMvaW5jbHVkZS9jYXRhbG9nL3BnX3Byb2MuZGF0ICAgIHwgICAz ICsKIDIgZmlsZXMgY2hhbmdlZCwgMTgxIGluc2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9z cmMvYmFja2VuZC91dGlscy9hZHQvYXJyYXlmdW5jcy5jIGIvc3JjL2JhY2tlbmQvdXRpbHMv YWR0L2FycmF5ZnVuY3MuYwppbmRleCBmYjE2N2YyMjZhLi45MTljYjJiZmQ2IDEwMDY0NAot LS0gYS9zcmMvYmFja2VuZC91dGlscy9hZHQvYXJyYXlmdW5jcy5jCisrKyBiL3NyYy9iYWNr ZW5kL3V0aWxzL2FkdC9hcnJheWZ1bmNzLmMKQEAgLTY4NzIsMyArNjg3MiwxODEgQEAgdHJp bV9hcnJheShQR19GVU5DVElPTl9BUkdTKQogCiAJUEdfUkVUVVJOX0RBVFVNKHJlc3VsdCk7 CiB9CisKK3N0YXRpYyBBcnJheVR5cGUgKgorYXJyYXlfc2h1ZmZsZV80KEFycmF5VHlwZSAq YXJyYXkpCit7CisJQXJyYXlUeXBlCSpyZXN1bHQ7CisJaW50MzIJCSphZGF0LAorCQkJCSpy ZGF0OworCWludAkJCWksCisJCQkJaiwKKwkJCQluaXRlbXM7CisKKwlyZXN1bHQgPSBjcmVh dGVfYXJyYXlfZW52ZWxvcGUoQVJSX05ESU0oYXJyYXkpLAorCQkJCQkJCQkgICBBUlJfRElN UyhhcnJheSksCisJCQkJCQkJCSAgIEFSUl9MQk9VTkQoYXJyYXkpLAorCQkJCQkJCQkgICBB UlJfU0laRShhcnJheSksCisJCQkJCQkJCSAgIEFSUl9FTEVNVFlQRShhcnJheSksCisJCQkJ CQkJCSAgIGFycmF5LT5kYXRhb2Zmc2V0KTsKKworCWFkYXQgPSAoaW50MzIgKikgQVJSX0RB VEFfUFRSKGFycmF5KTsKKwlyZGF0ID0gKGludDMyICopIEFSUl9EQVRBX1BUUihyZXN1bHQp OworCW5pdGVtcyA9IEFSUl9ESU1TKGFycmF5KVswXTsKKworCWZvciAoaSA9IDA7IGkgPCBu aXRlbXM7IGkrKykKKwl7CisJCWogPSByYW5kb20oKSAlIChpICsgMSk7CisJCXJkYXRbaV0g PSByZGF0W2pdOworCQlyZGF0W2pdID0gYWRhdFtpXTsKKwl9CisJcmV0dXJuIHJlc3VsdDsK K30KKworc3RhdGljIEFycmF5VHlwZSAqCithcnJheV9zaHVmZmxlXzgoQXJyYXlUeXBlICph cnJheSkKK3sKKwlBcnJheVR5cGUJKnJlc3VsdDsKKwlpbnQ2NAkJKmFkYXQsCisJCQkJKnJk YXQ7CisJaW50CQkJaSwKKwkJCQlqLAorCQkJCW5pdGVtczsKKworCXJlc3VsdCA9IGNyZWF0 ZV9hcnJheV9lbnZlbG9wZShBUlJfTkRJTShhcnJheSksCisJCQkJCQkJCSAgIEFSUl9ESU1T KGFycmF5KSwKKwkJCQkJCQkJICAgQVJSX0xCT1VORChhcnJheSksCisJCQkJCQkJCSAgIEFS Ul9TSVpFKGFycmF5KSwKKwkJCQkJCQkJICAgQVJSX0VMRU1UWVBFKGFycmF5KSwKKwkJCQkJ CQkJICAgYXJyYXktPmRhdGFvZmZzZXQpOworCisJYWRhdCA9IChpbnQ2NCAqKSBBUlJfREFU QV9QVFIoYXJyYXkpOworCXJkYXQgPSAoaW50NjQgKikgQVJSX0RBVEFfUFRSKHJlc3VsdCk7 CisJbml0ZW1zID0gQVJSX0RJTVMoYXJyYXkpWzBdOworCisJZm9yIChpID0gMDsgaSA8IG5p dGVtczsgaSsrKQorCXsKKwkJaiA9IHJhbmRvbSgpICUgKGkgKyAxKTsKKwkJcmRhdFtpXSA9 IHJkYXRbal07CisJCXJkYXRbal0gPSBhZGF0W2ldOworCX0KKwlyZXR1cm4gcmVzdWx0Owor fQorCitzdGF0aWMgQXJyYXlUeXBlICoKK2FycmF5X3NodWZmbGVfZ2VuZXJpYyhBcnJheVR5 cGUgKmFycmF5LAorCQkJCQkgIGludDE2IGVsbWxlbiwgYm9vbCBlbG1ieXZhbCwgY2hhciBl bG1hbGlnbikKK3sKKwlBcnJheVR5cGUJKnJlc3VsdDsKKwljaGFyCQkqYWRhdCwKKwkJCQkq cmRhdDsKKwlpbnQgCQlpLAorCQkJCW5kaW0sCisJCQkJKmRpbXMsCisJCQkJbml0ZW1zLAor CQkJCW5lbG1zX3Blcl9pdGVtOworCisJc3RydWN0IHsKKwkJY2hhciAqZGF0OworCQlzaXpl X3Qgc2l6ZTsKKwl9ICpyZWZzOworCisJbmRpbSA9IEFSUl9ORElNKGFycmF5KTsKKwlkaW1z ID0gQVJSX0RJTVMoYXJyYXkpOworCisJbmVsbXNfcGVyX2l0ZW0gPSAxOworCisJZm9yIChp ID0gMTsgaSA8IG5kaW07IGkrKykKKwkJbmVsbXNfcGVyX2l0ZW0gKj0gZGltc1tpXTsKKwor CW5pdGVtcyA9IGRpbXNbMF07CisKKwlyZWZzID0gcGFsbG9jKG5pdGVtcyAqIChzaXplb2Yo Y2hhciAqKSArIHNpemVvZihzaXplX3QpKSk7CisJYWRhdCA9IEFSUl9EQVRBX1BUUihhcnJh eSk7CisKKwkvKgorCSAqIFRvIGFsbG93IHNodWZmbGluZyBvZiBhcnJheXMgd2l0aCB2YXJp YWJsZSBsZW5ndGggZWxlbWVudHMsIHdlIGFyZSBnb2luZworCSAqIHRvIHNodWZmbGUgcmVm ZXJlbmNlcyB0byB0aGUgZWxlbWVudHMsIGJlY2F1c2Ugc3dhcHBpbmcgdmFyaWFibGUgbGVu Z3RoCisJICogZWxlbWVudHMgaW4gYW4gYXJyYXkgaXMgY29tcGxpY2F0ZWQuIEluIGEgc2Vj b25kIHN0ZXAgd2Ugd2lsbCBpdGVyYXRlIHRoZQorCSAqIHNodWZmbGVkIHJlZmVyZW5jZXMg YW5kIGNvcHkgdGhlIGVsZW1lbnRzIHRvIHRoZSBkZXN0aW5hdGlvbiBhcnJheS4KKwkgKiBX ZSBhcmUgdXNpbmcgdGhlICJpbnNpZGUtb3V0IiB2YXJpYW50IG9mIHRoZSBGaXNoZXItWWF0 ZXMgYWxnb3JpdGhtIHRvCisJICogcHJvZHVjZSBhIHNodWZmbGVkIGFycmF5IG9mIHJlZmVy ZW5jZXM6IEFwcGVuZCBlYWNoIHJlZmVyZW5jZSB0aGFuIHN3YXAgaXQKKwkgKiB3aXRoIGEg cmFkb21seS1jaG9zZW4gcmVmZW5jZS4KKwkgKi8KKwlmb3IgKGkgPSAwOyBpIDwgbml0ZW1z OyBpKyspCisJeworCQljaGFyICpuZXh0ID0gYXJyYXlfc2VlayhhZGF0LCAwLCBOVUxMLCBu ZWxtc19wZXJfaXRlbSwKKwkJCQkJCQkgICAgZWxtbGVuLCBlbG1ieXZhbCwgZWxtYWxpZ24p OworCQlpbnQgaiA9IHJhbmRvbSgpICUgKGkgKyAxKTsKKwkJcmVmc1tpXSA9IHJlZnNbal07 CisJCXJlZnNbal0uZGF0ID0gYWRhdDsKKwkJcmVmc1tqXS5zaXplID0gbmV4dCAtIGFkYXQ7 CisJCWFkYXQgPSBuZXh0OworCX0KKworCXJlc3VsdCA9IGNyZWF0ZV9hcnJheV9lbnZlbG9w ZShBUlJfTkRJTShhcnJheSksCisJCQkJCQkJCSAgIEFSUl9ESU1TKGFycmF5KSwKKwkJCQkJ CQkJICAgQVJSX0xCT1VORChhcnJheSksCisJCQkJCQkJCSAgIEFSUl9TSVpFKGFycmF5KSwK KwkJCQkJCQkJICAgQVJSX0VMRU1UWVBFKGFycmF5KSwKKwkJCQkJCQkJICAgYXJyYXktPmRh dGFvZmZzZXQpOworCisJcmRhdCA9IEFSUl9EQVRBX1BUUihyZXN1bHQpOworCisJLyogQ29s bGVjdCBhbGwgcmVmZXJlbmNlcyBhbmQgY29weSBlbGVtZW50cyB0byB0aGUgZGVzdGluYXRp b24gYXJyYXkgKi8KKwlmb3IgKGkgPSAwOyBpIDwgbml0ZW1zOyBpKyspCisJeworCQltZW1j cHkocmRhdCwgcmVmc1tpXS5kYXQsIHJlZnNbaV0uc2l6ZSk7CisJCXJkYXQgKz0gcmVmc1tp XS5zaXplOworCX0KKworCXBmcmVlKHJlZnMpOworCisJcmV0dXJuIHJlc3VsdDsKK30KKwor RGF0dW0KK2FycmF5X3NodWZmbGUoUEdfRlVOQ1RJT05fQVJHUykKK3sKKwlBcnJheVR5cGUJ CSphcnJheSwKKwkJCQkJKnJlc3VsdDsKKwlpbnQxNgkJCWVsbWxlbjsKKwlib29sCQkJZWxt Ynl2YWw7CisJY2hhcgkJCWVsbWFsaWduOworCU9pZCAgICAgICAgICAgICBlbG10eXA7CisJ VHlwZUNhY2hlRW50cnkJKnR5cGVudHJ5OworCisJYXJyYXkgPSBQR19HRVRBUkdfQVJSQVlU WVBFX1AoMCk7CisKKwlpZiAoQVJSX0hBU05VTEwoYXJyYXkpKQorCQllcmVwb3J0KEVSUk9S LAorCQkJCShlcnJjb2RlKEVSUkNPREVfRkVBVFVSRV9OT1RfU1VQUE9SVEVEKSwKKwkJCQkg ZXJybXNnKCJzaHVmZmxpbmcgYXJyYXlzIHdpdGggbnVsbCBlbGVtZW50cyBpcyBub3Qgc3Vw cG9ydGVkIikpKTsKKworCWlmIChBUlJfTkRJTShhcnJheSkgPCAxIHx8IEFSUl9ESU1TKGFy cmF5KVswXSA8IDIpCisJCVBHX1JFVFVSTl9BUlJBWVRZUEVfUChhcnJheSk7CisKKwllbG10 eXAgPSBBUlJfRUxFTVRZUEUoYXJyYXkpOworCisJdHlwZW50cnkgPSAoVHlwZUNhY2hlRW50 cnkgKikgZmNpbmZvLT5mbGluZm8tPmZuX2V4dHJhOworCisJaWYgKHR5cGVudHJ5ID09IE5V TEwgfHwgdHlwZW50cnktPnR5cGVfaWQgIT0gZWxtdHlwKQorCXsKKwkJdHlwZW50cnkgPSBs b29rdXBfdHlwZV9jYWNoZShlbG10eXAsIDApOworCQlmY2luZm8tPmZsaW5mby0+Zm5fZXh0 cmEgPSAodm9pZCAqKSB0eXBlbnRyeTsKKwl9CisJZWxtbGVuID0gdHlwZW50cnktPnR5cGxl bjsKKwllbG1ieXZhbCA9IHR5cGVudHJ5LT50eXBieXZhbDsKKwllbG1hbGlnbiA9IHR5cGVu dHJ5LT50eXBhbGlnbjsKKworCWlmIChBUlJfTkRJTShhcnJheSkgPT0gMSAmJiBlbG1sZW4g PT0gNCkKKwkJcmVzdWx0ID0gYXJyYXlfc2h1ZmZsZV80KGFycmF5KTsKKwllbHNlIGlmIChB UlJfTkRJTShhcnJheSkgPT0gMSAmJiBlbG1sZW4gPT0gOCkKKwkJcmVzdWx0ID0gYXJyYXlf c2h1ZmZsZV84KGFycmF5KTsKKwllbHNlCisJCXJlc3VsdCA9IGFycmF5X3NodWZmbGVfZ2Vu ZXJpYyhhcnJheSwgZWxtbGVuLCBlbG1ieXZhbCwgZWxtYWxpZ24pOworCisJUEdfRlJFRV9J Rl9DT1BZKGFycmF5LCAwKTsKKworCVBHX1JFVFVSTl9BUlJBWVRZUEVfUChyZXN1bHQpOwor fQpkaWZmIC0tZ2l0IGEvc3JjL2luY2x1ZGUvY2F0YWxvZy9wZ19wcm9jLmRhdCBiL3NyYy9p bmNsdWRlL2NhdGFsb2cvcGdfcHJvYy5kYXQKaW5kZXggMmU0MWY0ZDllOC4uNTZhZmY1NTFk MyAxMDA2NDQKLS0tIGEvc3JjL2luY2x1ZGUvY2F0YWxvZy9wZ19wcm9jLmRhdAorKysgYi9z cmMvaW5jbHVkZS9jYXRhbG9nL3BnX3Byb2MuZGF0CkBAIC0xNjgxLDYgKzE2ODEsOSBAQAog ICBwcm9uYW1lID0+ICdhcnJheWNvbnRqb2luc2VsJywgcHJvdm9sYXRpbGUgPT4gJ3MnLCBw cm9yZXR0eXBlID0+ICdmbG9hdDgnLAogICBwcm9hcmd0eXBlcyA9PiAnaW50ZXJuYWwgb2lk IGludGVybmFsIGludDIgaW50ZXJuYWwnLAogICBwcm9zcmMgPT4gJ2FycmF5Y29udGpvaW5z ZWwnIH0sCit7IG9pZCA9PiAnNzc3NycsIGRlc2NyID0+ICdzaHVmZmxlIGFycmF5JywKKyAg cHJvbmFtZSA9PiAnYXJyYXlfc2h1ZmZsZScsIHByb2lzc3RyaWN0ID0+ICdmJywgcHJvcmV0 dHlwZSA9PiAnYW55YXJyYXknLAorICBwcm9hcmd0eXBlcyA9PiAnYW55YXJyYXknLCBwcm9z cmMgPT4gJ2FycmF5X3NodWZmbGUnIH0sCiAKIHsgb2lkID0+ICc3NjQnLCBkZXNjciA9PiAn bGFyZ2Ugb2JqZWN0IGltcG9ydCcsCiAgIHByb25hbWUgPT4gJ2xvX2ltcG9ydCcsIHByb3Zv bGF0aWxlID0+ICd2JywgcHJvcGFyYWxsZWwgPT4gJ3UnLAotLSAKMi4zNy4xCgo= --------------ehXxvYxGsBqOWF8Yi9z0PZEd--