Message-ID: <791d98f474e518387d09eb390b8a12f265d130cc.camel@j-davis.com>
Subject: Re: Improve eviction algorithm in ReorderBuffer
From: Jeff Davis <pgsql@j-davis.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Cc: Amit Kapila <amit.kapila16@gmail.com>, vignesh C <vignesh21@gmail.com>,
 Peter Smith <smithpb2250@gmail.com>, Tomas Vondra
 <tomas.vondra@enterprisedb.com>, "Hayato Kuroda (Fujitsu)"
 <kuroda.hayato@fujitsu.com>, Shubham Khanna <khannashubham1197@gmail.com>,
 Dilip Kumar <dilipbalaut@gmail.com>, PostgreSQL Hackers
 <pgsql-hackers@lists.postgresql.org>
Date: Tue, 09 Apr 2024 11:04:49 -0700
In-Reply-To: 
 <CAD21AoAtR2A4f1-JFUE9KRkiPqMRvxS+3W=ZR7FpuXm8VSVASQ@mail.gmail.com>
References: 
	<CAD21AoAfKTgrBrLq96GcTv9d6k97zaQcDM-rxfKEt4GSe0qnaQ@mail.gmail.com>
	 <CAD21AoAkzQkEV8JVNonWbJNqCegpC5h8XsRfNbNjzDgAqj8uEA@mail.gmail.com>
	 <CAA4eK1+m=hfCSB0MWGTODM5Dj=P6Mzns3vQPKrTxp6ccVWgL2g@mail.gmail.com>
	 <CAD21AoBP5NcD3R6fJiX8QurH+Dhh2j_Ee1Ohc+b1XvSfvj6mnA@mail.gmail.com>
	 <CAA4eK1JqbW57NxFcp2weapDRMhN9+_HjLXq7W12UYUWcWfm_sg@mail.gmail.com>
	 <CAD21AoDffo37RC-eUuyHJKVEr017V2YYDLyn1xF_00ofptWbkg@mail.gmail.com>
	 <CAHv8RjJbd-EVs=YJLL6=XAA0ETbK-r8Zm5subP0CAuafOMbj1A@mail.gmail.com>
	 <CAD21AoBTgU=ZmJSoysZ+pokuGUEtFMU_4QvOaZCo2Gs7UKdORg@mail.gmail.com>
	 <CAD21AoA7L2Vwn3=3wMQxGrkisHfB7XK8wjh9x-rD7Q7Vms16LA@mail.gmail.com>
	 <TYCPR01MB120770098C895866564E29C24F5442@TYCPR01MB12077.jpnprd01.prod.outlook.com>
	 <CAD21AoDhuybyryVkmVkgPY8uVrjGLYchL8EY8-rBm1hbZJpwLw@mail.gmail.com>
	 <CALDaNm3NbbMpg_zo3wniJTFMsC4a6aCzOy6KsEhnhQgcsbaukA@mail.gmail.com>
	 <23e03725-8c77-431d-9f53-51709260ffeb@enterprisedb.com>
	 <CAD21AoDKMMRMEWAyL_nBpzJwktKyWLSmao_2uOA+_CrrB77bnw@mail.gmail.com>
	 <787cd90b-48ff-4c4a-a63e-a2b3f494385d@enterprisedb.com>
	 <CAD21AoAPkLQ9C5SA8ngPzegyq1C36+hGX78FwduvM6kOyfVU9A@mail.gmail.com>
	 <CAA4eK1+2zRU4+NAoUAiYYW1peGrE3JjSx9SrqeTGM=8r=0-UoA@mail.gmail.com>
	 <CALDaNm0-fSZdo=fVpSBfO+4_c+8HGuzWxZFZhpRPhjpPc5pifA@mail.gmail.com>
	 <CAD21AoBYjJmz7q_=Z+eXJgm0FScyu3_iGFshPAvnq78B2KL3qQ@mail.gmail.com>
	 <CAHut+PvZ12UDr1v7PX2CAEq1jo2rqWgB3gT9PRpQdboydAGTNQ@mail.gmail.com>
	 <CAD21AoAmj_gQt3LadRO5YrUr109AHBnbMh4Qt4cx7Wv3UwYJTA@mail.gmail.com>
	 <CAD21AoCY=x_XaNTOKae9bT-V5Fr2kY=6zUSSug3=Np_Ybue9VA@mail.gmail.com>
	 <CALDaNm14V8KHrxvqoOXd786Dkae-DFR4TDq1sj18SXCYUdDGzw@mail.gmail.com>
	 <CAD21AoDomWEkepxa8uE6s2eSoiB+gjtt51zx3Cnz6oLV_51U2Q@mail.gmail.com>
	 <CAA4eK1JTbEX-PcGwSni=W3J=viq4-BeRp1cmQAscJw0xxMAskQ@mail.gmail.com>
	 <CAD21AoA6=+tL=btB_s9N+cZK7tKz1W=PQyNq72nzjUcdyE+wZw@mail.gmail.com>
	 <CAD21AoC51TL6k+PFXyWEie-MVo7dqCHmPzTqfUaUueyx9OfLyw@mail.gmail.com>
	 <12747c15811d94efcc5cda72d6b35c80d7bf3443.camel@j-davis.com>
	 <fa89b6963899a05931f905dc7b1597e55b8204f5.camel@j-davis.com>
	 <CAD21AoAd7ZUz1SVKc+WNqNcTJdBZOBUeV_iExyzqk8WLyoNy1A@mail.gmail.com>
	 <f13d88915e7e197ccb78968a825d1c021f62c8ce.camel@j-davis.com>
	 <CAD21AoCfP++VF+12Za7SV_vQpRpFbe+Kf_LQsRPAw_pJj0YS3Q@mail.gmail.com>
	 <cecac19e0fb5739d4fd955000d19d88d060924d4.camel@j-davis.com>
	 <CAD21AoAtR2A4f1-JFUE9KRkiPqMRvxS+3W=ZR7FpuXm8VSVASQ@mail.gmail.com>
Content-Type: multipart/mixed; boundary="=-hFgQDeb/a/gmTv/l2TCo"
User-Agent: Evolution 3.44.4-0ubuntu2 
MIME-Version: 1.0
Archived-At: 
 <https://www.postgresql.org/message-id/791d98f474e518387d09eb390b8a12f265d130cc.camel%40j-davis.com>
Precedence: bulk

--=-hFgQDeb/a/gmTv/l2TCo
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Fri, 2024-04-05 at 16:58 +0900, Masahiko Sawada wrote:
> > I have some further comments and I believe changes are required for
> > v17.

I also noticed that the simplehash is declared in binaryheap.h with
"SH_SCOPE extern", which seems wrong. Attached is a rough patch to
bring the declarations into binaryheap.c.

Note that the attached patch uses "SH_SCOPE static", which makes sense
to me in this case, but causes a bunch of warnings in gcc. I will post
separately about silencing that warning, but for now you can either
use:

   SH_SCOPE static inline

which is probably fine, but will encourage the compiler to inline more
code, when not all callers even use the hash table. Alternatively, you
can do:

   SH_SCOPE static pg_attribute_unused()

which looks a bit wrong to me, but seems to silence the warnings, and
lets the compiler decide whether or not to inline.

Also probably needs comment updates, etc.

Regards,
	Jeff Davis


--=-hFgQDeb/a/gmTv/l2TCo
Content-Disposition: attachment;
	filename*0=v1-0001-binaryheap-move-hash-table-out-of-header-into-bin.pat;
	filename*1=ch
Content-Type: text/x-patch;
	name="v1-0001-binaryheap-move-hash-table-out-of-header-into-bin.patch";
	charset="UTF-8"
Content-Transfer-Encoding: base64

RnJvbSAwOGRjZjIxNjQ2ZTRkZWQyMmIxMGZkMGVkNTM2ZDNiYmY2ZmMxMzI4IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBKZWZmIERhdmlzIDxqZWZmQGotZGF2aXMuY29tPgpEYXRlOiBU
dWUsIDkgQXByIDIwMjQgMTA6NDU6MDAgLTA3MDAKU3ViamVjdDogW1BBVENIIHYxXSBiaW5hcnlo
ZWFwOiBtb3ZlIGhhc2ggdGFibGUgb3V0IG9mIGhlYWRlciBpbnRvCiBiaW5hcnloZWFwLmMuCgpD
b21taXQgYjg0MDUwODY0NCBkZWNsYXJlZCB0aGUgaW50ZXJuYWwgaGFzaCB0YWJsZSBpbiB0aGUg
aGVhZGVyIHdpdGgKc2NvcGUgImV4dGVybiIsIHdoaWNoIHdhcyB1bm5lY2Vzc2FyeS4KLS0tCiBz
cmMvY29tbW9uL2JpbmFyeWhlYXAuYyAgICAgIHwgMTUgKysrKysrKysrKysrKystCiBzcmMvaW5j
bHVkZS9saWIvYmluYXJ5aGVhcC5oIHwgMjUgKy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQogMiBm
aWxlcyBjaGFuZ2VkLCAxNSBpbnNlcnRpb25zKCspLCAyNSBkZWxldGlvbnMoLSkKCmRpZmYgLS1n
aXQgYS9zcmMvY29tbW9uL2JpbmFyeWhlYXAuYyBiL3NyYy9jb21tb24vYmluYXJ5aGVhcC5jCmlu
ZGV4IGMyMGVkNTBhY2MuLjI1MDFkYWQ2ZjIgMTAwNjQ0Ci0tLSBhL3NyYy9jb21tb24vYmluYXJ5
aGVhcC5jCisrKyBiL3NyYy9jb21tb24vYmluYXJ5aGVhcC5jCkBAIC0yNSw2ICsyNSwxOCBAQAog
I2luY2x1ZGUgImNvbW1vbi9oYXNoZm4uaCIKICNpbmNsdWRlICJsaWIvYmluYXJ5aGVhcC5oIgog
CisvKgorICogU3RydWN0IGZvciBhIGhhc2ggdGFibGUgZWxlbWVudCB0byBzdG9yZSB0aGUgbm9k
ZSdzIGluZGV4IGluIHRoZSBiaF9ub2RlcworICogYXJyYXkuCisgKi8KK3R5cGVkZWYgc3RydWN0
IGJoX25vZGVpZHhfZW50cnkKK3sKKwliaF9ub2RlX3R5cGUga2V5OworCWludAkJCWluZGV4OwkJ
CS8qIGVudHJ5J3MgaW5kZXggd2l0aGluIHRoZSBub2RlIGFycmF5ICovCisJY2hhcgkJc3RhdHVz
OwkJCS8qIGhhc2ggc3RhdHVzICovCisJdWludDMyCQloYXNoOwkJCS8qIGhhc2ggdmFsdWVzIChj
YWNoZWQpICovCit9IGJoX25vZGVpZHhfZW50cnk7CisKIC8qCiAgKiBEZWZpbmUgcGFyYW1ldGVy
cyBmb3IgaGFzaCB0YWJsZSBjb2RlIGdlbmVyYXRpb24uIFRoZSBpbnRlcmZhY2UgaXMgKmFsc28q
CiAgKiBkZWNsYXJlZCBpbiBiaW5hcnloZWFwLmggKHRvIGdlbmVyYXRlIHRoZSB0eXBlcywgd2hp
Y2ggYXJlIGV4dGVybmFsbHkKQEAgLTM3LDEyICs0OSwxMyBAQAogI2RlZmluZSBTSF9IQVNIX0tF
WSh0Yiwga2V5KSBcCiAJaGFzaF9ieXRlcygoY29uc3QgdW5zaWduZWQgY2hhciAqKSAma2V5LCBz
aXplb2YoYmhfbm9kZV90eXBlKSkKICNkZWZpbmUgU0hfRVFVQUwodGIsIGEsIGIpIChtZW1jbXAo
JmEsICZiLCBzaXplb2YoYmhfbm9kZV90eXBlKSkgPT0gMCkKLSNkZWZpbmUgU0hfU0NPUEUgZXh0
ZXJuCisjZGVmaW5lIFNIX1NDT1BFIHN0YXRpYwogI2lmZGVmIEZST05URU5ECiAjZGVmaW5lIFNI
X1JBV19BTExPQ0FUT1IgcGdfbWFsbG9jMAogI2VuZGlmCiAjZGVmaW5lIFNIX1NUT1JFX0hBU0gK
ICNkZWZpbmUgU0hfR0VUX0hBU0godGIsIGEpIGEtPmhhc2gKKyNkZWZpbmUgU0hfREVDTEFSRQog
I2RlZmluZSBTSF9ERUZJTkUKICNpbmNsdWRlICJsaWIvc2ltcGxlaGFzaC5oIgogCmRpZmYgLS1n
aXQgYS9zcmMvaW5jbHVkZS9saWIvYmluYXJ5aGVhcC5oIGIvc3JjL2luY2x1ZGUvbGliL2JpbmFy
eWhlYXAuaAppbmRleCA0YzFhMWJiMjc0Li44YjQ3MTMyZmMzIDEwMDY0NAotLS0gYS9zcmMvaW5j
bHVkZS9saWIvYmluYXJ5aGVhcC5oCisrKyBiL3NyYy9pbmNsdWRlL2xpYi9iaW5hcnloZWFwLmgK
QEAgLTI5LDI5ICsyOSw2IEBAIHR5cGVkZWYgRGF0dW0gYmhfbm9kZV90eXBlOwogICovCiB0eXBl
ZGVmIGludCAoKmJpbmFyeWhlYXBfY29tcGFyYXRvcikgKGJoX25vZGVfdHlwZSBhLCBiaF9ub2Rl
X3R5cGUgYiwgdm9pZCAqYXJnKTsKIAotLyoKLSAqIFN0cnVjdCBmb3IgYSBoYXNoIHRhYmxlIGVs
ZW1lbnQgdG8gc3RvcmUgdGhlIG5vZGUncyBpbmRleCBpbiB0aGUgYmhfbm9kZXMKLSAqIGFycmF5
LgotICovCi10eXBlZGVmIHN0cnVjdCBiaF9ub2RlaWR4X2VudHJ5Ci17Ci0JYmhfbm9kZV90eXBl
IGtleTsKLQlpbnQJCQlpbmRleDsJCQkvKiBlbnRyeSdzIGluZGV4IHdpdGhpbiB0aGUgbm9kZSBh
cnJheSAqLwotCWNoYXIJCXN0YXR1czsJCQkvKiBoYXNoIHN0YXR1cyAqLwotCXVpbnQzMgkJaGFz
aDsJCQkvKiBoYXNoIHZhbHVlcyAoY2FjaGVkKSAqLwotfSBiaF9ub2RlaWR4X2VudHJ5OwotCi0v
KiBEZWZpbmUgcGFyYW1ldGVycyBuZWNlc3NhcnkgdG8gZ2VuZXJhdGUgdGhlIGhhc2ggdGFibGUg
aW50ZXJmYWNlLiAqLwotI2RlZmluZSBTSF9QUkVGSVggYmhfbm9kZWlkeAotI2RlZmluZSBTSF9F
TEVNRU5UX1RZUEUgYmhfbm9kZWlkeF9lbnRyeQotI2RlZmluZSBTSF9LRVlfVFlQRSBiaF9ub2Rl
X3R5cGUKLSNkZWZpbmUgU0hfU0NPUEUgZXh0ZXJuCi0jaWZkZWYgRlJPTlRFTkQKLSNkZWZpbmUg
U0hfUkFXX0FMTE9DQVRPUiBwZ19tYWxsb2MwCi0jZW5kaWYKLSNkZWZpbmUgU0hfREVDTEFSRQot
I2luY2x1ZGUgImxpYi9zaW1wbGVoYXNoLmgiCi0KIC8qCiAgKiBiaW5hcnloZWFwCiAgKgpAQCAt
NzYsNyArNTMsNyBAQCB0eXBlZGVmIHN0cnVjdCBiaW5hcnloZWFwCiAJICogbm9kZSdzIGluZGV4
IGluIGJoX25vZGVzLiBUaGlzIGVuYWJsZXMgdGhlIGNhbGxlciB0byBwZXJmb3JtCiAJICogYmlu
YXJ5aGVhcF9yZW1vdmVfbm9kZV9wdHIoKSwgYmluYXJ5aGVhcF91cGRhdGVfdXAvZG93biBpbiBP
KGxvZyBuKS4KIAkgKi8KLQliaF9ub2RlaWR4X2hhc2ggKmJoX25vZGVpZHg7CisJc3RydWN0IGJo
X25vZGVpZHhfaGFzaCAqYmhfbm9kZWlkeDsKIH0gYmluYXJ5aGVhcDsKIAogZXh0ZXJuIGJpbmFy
eWhlYXAgKmJpbmFyeWhlYXBfYWxsb2NhdGUoaW50IG51bV9ub2RlcywKLS0gCjIuMzQuMQoK


--=-hFgQDeb/a/gmTv/l2TCo--