Message-ID: <12747c15811d94efcc5cda72d6b35c80d7bf3443.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>, Amit Kapila
	 <amit.kapila16@gmail.com>
Cc: 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: Wed, 03 Apr 2024 01:45:55 -0700
In-Reply-To: 
 <CAD21AoC51TL6k+PFXyWEie-MVo7dqCHmPzTqfUaUueyx9OfLyw@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>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
User-Agent: Evolution 3.44.4-0ubuntu2 
MIME-Version: 1.0
Archived-At: 
 <https://www.postgresql.org/message-id/12747c15811d94efcc5cda72d6b35c80d7bf3443.camel%40j-davis.com>
Precedence: bulk

On Mon, 2024-04-01 at 12:42 +0900, Masahiko Sawada wrote:
> While reviewing the patches, I realized the comment of
> binearyheap_allocate() should also be updated. So I've attached the
> new patches.

In sift_{up|down}, each loop iteration calls set_node(), and each call
to set_node does a hash lookup. I didn't measure it, but that feels
wasteful.

I don't even think you really need the hash table. The key to the hash
table is a pointer, so it's not really doing anything that couldn't be
done more efficiently by just following the pointer.

I suggest that you add a "heap_index" field to ReorderBufferTXN that
would point to the index into the heap's array (the same as
bh_nodeidx_entry.index in your patch). Each time an element moves
within the heap array, just follow the pointer to the ReorderBufferTXN
object and update the heap_index -- no hash lookup required.

That's not easy to do with the current binaryheap API. But a binary
heap is not a terribly complex structure, so you can just do an inline
implementation of it where sift_{up|down} know to update the heap_index
field of the ReorderBufferTXN.

Regards,
	Jeff Davis