MIME-Version: 1.0
References: 
 <CA+hUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse+HG0Yig@mail.gmail.com>
 <0F9ECBA9-1DF2-4C38-BB58-B17EEE6C7B3A@yesql.se>
 <CA+hUKGJhOtjQH+wjCodtJzHAFCAPYyt6Qm9E1mUoJph42qo1hg@mail.gmail.com>
 <20210311185847.zwb2rf3n4wzelkba@alap3.anarazel.de>
 <CA+hUKGLqmksGRKQRF6qkih6jV_d9qVrrk4wh5F_EgTXyRGeCyw@mail.gmail.com>
 <CA+hUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg@mail.gmail.com>
 <CALNJ-vRSvudAbdY-DChFv8C0-dJYD3FamX4FpW9A2xivKuB83A@mail.gmail.com>
 <CA+hUKGKWR3_-sqTE8BSrSy0kp0WJeKQ1ffyYxEKuykA7vmG9uQ@mail.gmail.com>
 <CA+hUKGLAfouP-rUpik45Z_KPM5+oxrX_564bLfiZPX4f25MYbA@mail.gmail.com>
 <CAFBsxsFSTSrrhAyFQo6Kz4vP40iXyvUdvzU0LvHa4LVyK-eDfA@mail.gmail.com>
 <CA+hUKG+-Nx4CfutUsgG-x7qfzmV-VHtcdD_kyRksE4t7CWYN3w@mail.gmail.com>
 <CA+hUKGLSaWnz4gznDp6aMhi4dzzUBJZEUACo6QAOC28JjvhxBg@mail.gmail.com>
 <CA+hUKGLPommgNw-SVwUGkw1YmTDwmJ5vSKO0kFnZfbRHtNFW5w@mail.gmail.com>
 <CAFBsxsFVG8-Q-98C__N=brinC6pAFs7kGjAZj5LO77M8VmTn-Q@mail.gmail.com>
In-Reply-To: 
 <CAFBsxsFVG8-Q-98C__N=brinC6pAFs7kGjAZj5LO77M8VmTn-Q@mail.gmail.com>
From: John Naylor <john.naylor@enterprisedb.com>
Date: Thu, 1 Jul 2021 12:39:32 -0400
Message-ID: 
 <CAFBsxsG_c24CHKA3cWrOP1HynWGLOkLb8hyZfsD9db5g-ZPagA@mail.gmail.com>
Subject: Re: A qsort template
To: Thomas Munro <thomas.munro@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Content-Type: multipart/mixed; boundary="000000000000759c3a05c6127c47"
Archived-At: 
 <https://www.postgresql.org/message-id/CAFBsxsG_c24CHKA3cWrOP1HynWGLOkLb8hyZfsD9db5g-ZPagA%40mail.gmail.com>
Precedence: bulk

--000000000000759c3a05c6127c47
Content-Type: multipart/alternative; boundary="000000000000759c3805c6127c45"

--000000000000759c3805c6127c45
Content-Type: text/plain; charset="UTF-8"

I wrote:

> One of the points of the talk I linked to is "if doing the sensible thing
makes things worse, try something silly instead".

For item pointers, it made sense to try doing math to reduce the number of
branches. That made things worse, so let's try the opposite: Increase the
number of branches so we do less math. In the attached patch (applies on
top of your 0012 and a .txt to avoid confusing the CF bot), I test a new
comparator with this approach, and also try a wider range of thresholds.
The thresholds don't seem to make any noticeable difference with this data
type, but the new comparator (cmp=ids below) gives a nice speedup in this
test:

# SELECT test_sort_itemptr();
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=0,
time=4.964657
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=1,
time=5.185384
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=2,
time=5.058179
NOTICE:  order=random, threshold=7, cmp=std, test=0, time=2.810627
NOTICE:  order=random, threshold=7, cmp=std, test=1, time=2.804940
NOTICE:  order=random, threshold=7, cmp=std, test=2, time=2.800677
NOTICE:  order=random, threshold=7, cmp=ids, test=0, time=1.692711
NOTICE:  order=random, threshold=7, cmp=ids, test=1, time=1.694546
NOTICE:  order=random, threshold=7, cmp=ids, test=2, time=1.692839
NOTICE:  order=random, threshold=12, cmp=std, test=0, time=2.687033
NOTICE:  order=random, threshold=12, cmp=std, test=1, time=2.681974
NOTICE:  order=random, threshold=12, cmp=std, test=2, time=2.687833
NOTICE:  order=random, threshold=12, cmp=ids, test=0, time=1.666418
NOTICE:  order=random, threshold=12, cmp=ids, test=1, time=1.666188
NOTICE:  order=random, threshold=12, cmp=ids, test=2, time=1.664176
NOTICE:  order=random, threshold=16, cmp=std, test=0, time=2.574147
NOTICE:  order=random, threshold=16, cmp=std, test=1, time=2.579981
NOTICE:  order=random, threshold=16, cmp=std, test=2, time=2.572861
NOTICE:  order=random, threshold=16, cmp=ids, test=0, time=1.699432
NOTICE:  order=random, threshold=16, cmp=ids, test=1, time=1.703075
NOTICE:  order=random, threshold=16, cmp=ids, test=2, time=1.697173
NOTICE:  order=random, threshold=32, cmp=std, test=0, time=2.750040
NOTICE:  order=random, threshold=32, cmp=std, test=1, time=2.744138
NOTICE:  order=random, threshold=32, cmp=std, test=2, time=2.748026
NOTICE:  order=random, threshold=32, cmp=ids, test=0, time=1.677414
NOTICE:  order=random, threshold=32, cmp=ids, test=1, time=1.683792
NOTICE:  order=random, threshold=32, cmp=ids, test=2, time=1.701309
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=0,
time=2.543837
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=1,
time=2.290497
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=2,
time=2.262956
NOTICE:  order=increasing, threshold=7, cmp=std, test=0, time=1.033052
NOTICE:  order=increasing, threshold=7, cmp=std, test=1, time=1.032079
NOTICE:  order=increasing, threshold=7, cmp=std, test=2, time=1.041836
NOTICE:  order=increasing, threshold=7, cmp=ids, test=0, time=0.367355
NOTICE:  order=increasing, threshold=7, cmp=ids, test=1, time=0.367428
NOTICE:  order=increasing, threshold=7, cmp=ids, test=2, time=0.367384
NOTICE:  order=increasing, threshold=12, cmp=std, test=0, time=1.004991
NOTICE:  order=increasing, threshold=12, cmp=std, test=1, time=1.008045
NOTICE:  order=increasing, threshold=12, cmp=std, test=2, time=1.010778
NOTICE:  order=increasing, threshold=12, cmp=ids, test=0, time=0.370944
NOTICE:  order=increasing, threshold=12, cmp=ids, test=1, time=0.368669
NOTICE:  order=increasing, threshold=12, cmp=ids, test=2, time=0.370100
NOTICE:  order=increasing, threshold=16, cmp=std, test=0, time=1.023682
NOTICE:  order=increasing, threshold=16, cmp=std, test=1, time=1.025805
NOTICE:  order=increasing, threshold=16, cmp=std, test=2, time=1.022005
NOTICE:  order=increasing, threshold=16, cmp=ids, test=0, time=0.365398
NOTICE:  order=increasing, threshold=16, cmp=ids, test=1, time=0.365586
NOTICE:  order=increasing, threshold=16, cmp=ids, test=2, time=0.364807
NOTICE:  order=increasing, threshold=32, cmp=std, test=0, time=0.950780
NOTICE:  order=increasing, threshold=32, cmp=std, test=1, time=0.949920
NOTICE:  order=increasing, threshold=32, cmp=std, test=2, time=0.953239
NOTICE:  order=increasing, threshold=32, cmp=ids, test=0, time=0.367866
NOTICE:  order=increasing, threshold=32, cmp=ids, test=1, time=0.372179
NOTICE:  order=increasing, threshold=32, cmp=ids, test=2, time=0.371115
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=0,
time=2.317475
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=1,
time=2.323446
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=2,
time=2.326714
NOTICE:  order=decreasing, threshold=7, cmp=std, test=0, time=1.022270
NOTICE:  order=decreasing, threshold=7, cmp=std, test=1, time=1.015133
NOTICE:  order=decreasing, threshold=7, cmp=std, test=2, time=1.016367
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=0, time=0.386884
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=1, time=0.388397
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=2, time=0.386328
NOTICE:  order=decreasing, threshold=12, cmp=std, test=0, time=0.993594
NOTICE:  order=decreasing, threshold=12, cmp=std, test=1, time=0.995031
NOTICE:  order=decreasing, threshold=12, cmp=std, test=2, time=0.995320
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=0, time=0.391243
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=1, time=0.391938
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=2, time=0.392478
NOTICE:  order=decreasing, threshold=16, cmp=std, test=0, time=1.006240
NOTICE:  order=decreasing, threshold=16, cmp=std, test=1, time=1.009817
NOTICE:  order=decreasing, threshold=16, cmp=std, test=2, time=1.010281
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=0, time=0.386388
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=1, time=0.385801
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=2, time=0.384484
NOTICE:  order=decreasing, threshold=32, cmp=std, test=0, time=0.959647
NOTICE:  order=decreasing, threshold=32, cmp=std, test=1, time=0.958833
NOTICE:  order=decreasing, threshold=32, cmp=std, test=2, time=0.960234
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=0, time=0.403014
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=1, time=0.393329
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=2, time=0.395659

--
John Naylor
EDB: http://www.enterprisedb.com

--000000000000759c3805c6127c45
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I wrote:<br><br>&gt; One of the points of the talk I linke=
d to is &quot;if doing the sensible thing makes things worse, try something=
 silly instead&quot;.<br><br>For item pointers, it made sense to try doing =
math to reduce the number of branches. That made things worse, so let&#39;s=
 try the opposite: Increase the number of branches so we do less math. In t=
he attached patch (applies on top of your 0012 and a .txt to avoid confusin=
g the CF bot), I test a new comparator with this approach, and also try a w=
ider range of thresholds. The thresholds don&#39;t seem to make any noticea=
ble difference with this data type, but the new comparator (cmp=3Dids below=
) gives a nice speedup in this test:<br><br># SELECT test_sort_itemptr();<b=
r>NOTICE: =C2=A0[traditional qsort] order=3Drandom, threshold=3D7, cmp=3D32=
, test=3D0, time=3D4.964657<br>NOTICE: =C2=A0[traditional qsort] order=3Dra=
ndom, threshold=3D7, cmp=3D32, test=3D1, time=3D5.185384<br>NOTICE: =C2=A0[=
traditional qsort] order=3Drandom, threshold=3D7, cmp=3D32, test=3D2, time=
=3D5.058179<br>NOTICE: =C2=A0order=3Drandom, threshold=3D7, cmp=3Dstd, test=
=3D0, time=3D2.810627<br>NOTICE: =C2=A0order=3Drandom, threshold=3D7, cmp=
=3Dstd, test=3D1, time=3D2.804940<br>NOTICE: =C2=A0order=3Drandom, threshol=
d=3D7, cmp=3Dstd, test=3D2, time=3D2.800677<br>NOTICE: =C2=A0order=3Drandom=
, threshold=3D7, cmp=3Dids, test=3D0, time=3D1.692711<br>NOTICE: =C2=A0orde=
r=3Drandom, threshold=3D7, cmp=3Dids, test=3D1, time=3D1.694546<br>NOTICE: =
=C2=A0order=3Drandom, threshold=3D7, cmp=3Dids, test=3D2, time=3D1.692839<b=
r>NOTICE: =C2=A0order=3Drandom, threshold=3D12, cmp=3Dstd, test=3D0, time=
=3D2.687033<br>NOTICE: =C2=A0order=3Drandom, threshold=3D12, cmp=3Dstd, tes=
t=3D1, time=3D2.681974<br>NOTICE: =C2=A0order=3Drandom, threshold=3D12, cmp=
=3Dstd, test=3D2, time=3D2.687833<br>NOTICE: =C2=A0order=3Drandom, threshol=
d=3D12, cmp=3Dids, test=3D0, time=3D1.666418<br>NOTICE: =C2=A0order=3Drando=
m, threshold=3D12, cmp=3Dids, test=3D1, time=3D1.666188<br>NOTICE: =C2=A0or=
der=3Drandom, threshold=3D12, cmp=3Dids, test=3D2, time=3D1.664176<br>NOTIC=
E: =C2=A0order=3Drandom, threshold=3D16, cmp=3Dstd, test=3D0, time=3D2.5741=
47<br>NOTICE: =C2=A0order=3Drandom, threshold=3D16, cmp=3Dstd, test=3D1, ti=
me=3D2.579981<br>NOTICE: =C2=A0order=3Drandom, threshold=3D16, cmp=3Dstd, t=
est=3D2, time=3D2.572861<br>NOTICE: =C2=A0order=3Drandom, threshold=3D16, c=
mp=3Dids, test=3D0, time=3D1.699432<br>NOTICE: =C2=A0order=3Drandom, thresh=
old=3D16, cmp=3Dids, test=3D1, time=3D1.703075<br>NOTICE: =C2=A0order=3Dran=
dom, threshold=3D16, cmp=3Dids, test=3D2, time=3D1.697173<br>NOTICE: =C2=A0=
order=3Drandom, threshold=3D32, cmp=3Dstd, test=3D0, time=3D2.750040<br>NOT=
ICE: =C2=A0order=3Drandom, threshold=3D32, cmp=3Dstd, test=3D1, time=3D2.74=
4138<br>NOTICE: =C2=A0order=3Drandom, threshold=3D32, cmp=3Dstd, test=3D2, =
time=3D2.748026<br>NOTICE: =C2=A0order=3Drandom, threshold=3D32, cmp=3Dids,=
 test=3D0, time=3D1.677414<br>NOTICE: =C2=A0order=3Drandom, threshold=3D32,=
 cmp=3Dids, test=3D1, time=3D1.683792<br>NOTICE: =C2=A0order=3Drandom, thre=
shold=3D32, cmp=3Dids, test=3D2, time=3D1.701309<br>NOTICE: =C2=A0[traditio=
nal qsort] order=3Dincreasing, threshold=3D7, cmp=3D32, test=3D0, time=3D2.=
543837<br>NOTICE: =C2=A0[traditional qsort] order=3Dincreasing, threshold=
=3D7, cmp=3D32, test=3D1, time=3D2.290497<br>NOTICE: =C2=A0[traditional qso=
rt] order=3Dincreasing, threshold=3D7, cmp=3D32, test=3D2, time=3D2.262956<=
br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D7, cmp=3Dstd, test=3D0, ti=
me=3D1.033052<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D7, cmp=3Dstd=
, test=3D1, time=3D1.032079<br>NOTICE: =C2=A0order=3Dincreasing, threshold=
=3D7, cmp=3Dstd, test=3D2, time=3D1.041836<br>NOTICE: =C2=A0order=3Dincreas=
ing, threshold=3D7, cmp=3Dids, test=3D0, time=3D0.367355<br>NOTICE: =C2=A0o=
rder=3Dincreasing, threshold=3D7, cmp=3Dids, test=3D1, time=3D0.367428<br>N=
OTICE: =C2=A0order=3Dincreasing, threshold=3D7, cmp=3Dids, test=3D2, time=
=3D0.367384<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D12, cmp=3Dstd,=
 test=3D0, time=3D1.004991<br>NOTICE: =C2=A0order=3Dincreasing, threshold=
=3D12, cmp=3Dstd, test=3D1, time=3D1.008045<br>NOTICE: =C2=A0order=3Dincrea=
sing, threshold=3D12, cmp=3Dstd, test=3D2, time=3D1.010778<br>NOTICE: =C2=
=A0order=3Dincreasing, threshold=3D12, cmp=3Dids, test=3D0, time=3D0.370944=
<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D12, cmp=3Dids, test=3D1, =
time=3D0.368669<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D12, cmp=3D=
ids, test=3D2, time=3D0.370100<br>NOTICE: =C2=A0order=3Dincreasing, thresho=
ld=3D16, cmp=3Dstd, test=3D0, time=3D1.023682<br>NOTICE: =C2=A0order=3Dincr=
easing, threshold=3D16, cmp=3Dstd, test=3D1, time=3D1.025805<br>NOTICE: =C2=
=A0order=3Dincreasing, threshold=3D16, cmp=3Dstd, test=3D2, time=3D1.022005=
<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D16, cmp=3Dids, test=3D0, =
time=3D0.365398<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D16, cmp=3D=
ids, test=3D1, time=3D0.365586<br>NOTICE: =C2=A0order=3Dincreasing, thresho=
ld=3D16, cmp=3Dids, test=3D2, time=3D0.364807<br>NOTICE: =C2=A0order=3Dincr=
easing, threshold=3D32, cmp=3Dstd, test=3D0, time=3D0.950780<br>NOTICE: =C2=
=A0order=3Dincreasing, threshold=3D32, cmp=3Dstd, test=3D1, time=3D0.949920=
<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D32, cmp=3Dstd, test=3D2, =
time=3D0.953239<br>NOTICE: =C2=A0order=3Dincreasing, threshold=3D32, cmp=3D=
ids, test=3D0, time=3D0.367866<br>NOTICE: =C2=A0order=3Dincreasing, thresho=
ld=3D32, cmp=3Dids, test=3D1, time=3D0.372179<br>NOTICE: =C2=A0order=3Dincr=
easing, threshold=3D32, cmp=3Dids, test=3D2, time=3D0.371115<br>NOTICE: =C2=
=A0[traditional qsort] order=3Ddecreasing, threshold=3D7, cmp=3D32, test=3D=
0, time=3D2.317475<br>NOTICE: =C2=A0[traditional qsort] order=3Ddecreasing,=
 threshold=3D7, cmp=3D32, test=3D1, time=3D2.323446<br>NOTICE: =C2=A0[tradi=
tional qsort] order=3Ddecreasing, threshold=3D7, cmp=3D32, test=3D2, time=
=3D2.326714<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D7, cmp=3Dstd, =
test=3D0, time=3D1.022270<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D=
7, cmp=3Dstd, test=3D1, time=3D1.015133<br>NOTICE: =C2=A0order=3Ddecreasing=
, threshold=3D7, cmp=3Dstd, test=3D2, time=3D1.016367<br>NOTICE: =C2=A0orde=
r=3Ddecreasing, threshold=3D7, cmp=3Dids, test=3D0, time=3D0.386884<br>NOTI=
CE: =C2=A0order=3Ddecreasing, threshold=3D7, cmp=3Dids, test=3D1, time=3D0.=
388397<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D7, cmp=3Dids, test=
=3D2, time=3D0.386328<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D12, =
cmp=3Dstd, test=3D0, time=3D0.993594<br>NOTICE: =C2=A0order=3Ddecreasing, t=
hreshold=3D12, cmp=3Dstd, test=3D1, time=3D0.995031<br>NOTICE: =C2=A0order=
=3Ddecreasing, threshold=3D12, cmp=3Dstd, test=3D2, time=3D0.995320<br>NOTI=
CE: =C2=A0order=3Ddecreasing, threshold=3D12, cmp=3Dids, test=3D0, time=3D0=
.391243<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D12, cmp=3Dids, tes=
t=3D1, time=3D0.391938<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D12,=
 cmp=3Dids, test=3D2, time=3D0.392478<br>NOTICE: =C2=A0order=3Ddecreasing, =
threshold=3D16, cmp=3Dstd, test=3D0, time=3D1.006240<br>NOTICE: =C2=A0order=
=3Ddecreasing, threshold=3D16, cmp=3Dstd, test=3D1, time=3D1.009817<br>NOTI=
CE: =C2=A0order=3Ddecreasing, threshold=3D16, cmp=3Dstd, test=3D2, time=3D1=
.010281<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D16, cmp=3Dids, tes=
t=3D0, time=3D0.386388<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D16,=
 cmp=3Dids, test=3D1, time=3D0.385801<br>NOTICE: =C2=A0order=3Ddecreasing, =
threshold=3D16, cmp=3Dids, test=3D2, time=3D0.384484<br>NOTICE: =C2=A0order=
=3Ddecreasing, threshold=3D32, cmp=3Dstd, test=3D0, time=3D0.959647<br>NOTI=
CE: =C2=A0order=3Ddecreasing, threshold=3D32, cmp=3Dstd, test=3D1, time=3D0=
.958833<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D32, cmp=3Dstd, tes=
t=3D2, time=3D0.960234<br>NOTICE: =C2=A0order=3Ddecreasing, threshold=3D32,=
 cmp=3Dids, test=3D0, time=3D0.403014<br>NOTICE: =C2=A0order=3Ddecreasing, =
threshold=3D32, cmp=3Dids, test=3D1, time=3D0.393329<br>NOTICE: =C2=A0order=
=3Ddecreasing, threshold=3D32, cmp=3Dids, test=3D2, time=3D0.395659<br><br>=
--<br>John Naylor<br>EDB: <a href=3D"http://www.enterprisedb.com">http://ww=
w.enterprisedb.com</a></div>

--000000000000759c3805c6127c45--

--000000000000759c3a05c6127c47
Content-Type: application/octet-stream; name="itemptr-cmp-blockids.patch"
Content-Disposition: attachment; filename="itemptr-cmp-blockids.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_kql4qvjz0>
X-Attachment-Id: f_kql4qvjz0

ZGlmZiAtLWdpdCBhL3NyYy90ZXN0L21vZHVsZXMvdGVzdF9zb3J0X3BlcmYvbWFrZS1pdGVtcHRy
LXRlc3RzLnNoIGIvc3JjL3Rlc3QvbW9kdWxlcy90ZXN0X3NvcnRfcGVyZi9tYWtlLWl0ZW1wdHIt
dGVzdHMuc2gKaW5kZXggOTE1MWVhNzAzZi4uZmQwMDQ4ZWJhMyAxMDA3NTUKLS0tIGEvc3JjL3Rl
c3QvbW9kdWxlcy90ZXN0X3NvcnRfcGVyZi9tYWtlLWl0ZW1wdHItdGVzdHMuc2gKKysrIGIvc3Jj
L3Rlc3QvbW9kdWxlcy90ZXN0X3NvcnRfcGVyZi9tYWtlLWl0ZW1wdHItdGVzdHMuc2gKQEAgLTEs
NyArMSw3IEBACiAjIS9iaW4vc2gKIAogIyBkaWZmZXJlbnQgdmFsdWVzIHRvIHRlc3QgZm9yIGlu
c2VydGlvbiBzb3J0cwotVEhSRVNIT0xEUz0iNyA4IDkgMTAgMTEgMTIgMTMiCitUSFJFU0hPTERT
PSI3IDEyIDE2IDMyIgogCiAjIGFtb3VudCBvZiBkYXRhIHRvIHNvcnQsIGluIG1lZ2FieXRlcwog
TUVNT1JZPTEyOApAQCAtMTgsMTAgKzE4LDkgQEAgZm9yIHRocmVzaG9sZCBpbiAkVEhSRVNIT0xE
UyA7IGRvCiAgIGVjaG8gIiNkZWZpbmUgU1RfREVGSU5FIgogICBlY2hvICIjaW5jbHVkZSBcImxp
Yi9zb3J0X3RlbXBsYXRlLmhcIiIKICAgZWNobwotICBlY2hvICIjZGVmaW5lIFNUX1NPUlQgc29y
dDY0XyR7dGhyZXNob2xkfV9pdGVtcHRyIgorICBlY2hvICIjZGVmaW5lIFNUX1NPUlQgc29ydF9p
ZHNfJHt0aHJlc2hvbGR9X2l0ZW1wdHIiCiAgIGVjaG8gIiNkZWZpbmUgU1RfRUxFTUVOVF9UWVBF
IEl0ZW1Qb2ludGVyRGF0YSIKLSAgZWNobyAiI2RlZmluZSBTVF9DT01QQVJFKGEsIGIpIChpdGVt
cHRyX2VuY29kZShhKSAtIGl0ZW1wdHJfZW5jb2RlKGIpKSIKLSAgZWNobyAiI2RlZmluZSBTVF9D
T01QQVJFX1JFVF9UWVBFIGludDY0IgorICBlY2hvICIjZGVmaW5lIFNUX0NPTVBBUkUoYSwgYikg
aXRlbXB0cl9jb21wYXJhdG9yX2Jsb2NraWRzKGEsIGIpIgogICBlY2hvICIjZGVmaW5lIFNUX1ND
T1BFIHN0YXRpYyIKICAgZWNobyAiI2RlZmluZSBTVF9TT1JUX1NNQUxMX1RIUkVTSE9MRCAkdGhy
ZXNob2xkIgogICBlY2hvICIjZGVmaW5lIFNUX0NIRUNLX0ZPUl9JTlRFUlJVUFRTIgpAQCAtNzYs
NyArNzUsNyBAQCBmb3Igb3JkZXIgaW4gcmFuZG9tIGluY3JlYXNpbmcgZGVjcmVhc2luZyA7IGRv
CiAgICAgZWNobyAiICAgICAgICBzb3J0XyR7dGhyZXNob2xkfV9pdGVtcHRyKHNvcnRlZCwgbm9i
amVjdHMpOyIKICAgICBlY2hvICIgICAgICAgIElOU1RSX1RJTUVfU0VUX0NVUlJFTlQoZW5kX3Rp
bWUpOyIKICAgICBlY2hvICIgICAgICAgIElOU1RSX1RJTUVfU1VCVFJBQ1QoZW5kX3RpbWUsIHN0
YXJ0X3RpbWUpOyIKLSAgICBlY2hvICIgICAgICAgIGVsb2coTk9USUNFLCBcIm9yZGVyPSRvcmRl
ciwgdGhyZXNob2xkPSR0aHJlc2hvbGQsIGNtcD0zMiwgdGVzdD0lZCwgdGltZT0lZlwiLCBpLCBJ
TlNUUl9USU1FX0dFVF9ET1VCTEUoZW5kX3RpbWUpKTsiCisgICAgZWNobyAiICAgICAgICBlbG9n
KE5PVElDRSwgXCJvcmRlcj0kb3JkZXIsIHRocmVzaG9sZD0kdGhyZXNob2xkLCBjbXA9c3RkLCB0
ZXN0PSVkLCB0aW1lPSVmXCIsIGksIElOU1RSX1RJTUVfR0VUX0RPVUJMRShlbmRfdGltZSkpOyIK
ICAgICBlY2hvICIgICAgfSIKICAgICBlY2hvICIgICAgZm9yIChpbnQgaSA9IDA7IGkgPCAzOyAr
K2kpIgogICAgIGVjaG8gIiAgICB7IgpAQCAtODQsMTAgKzgzLDEwIEBAIGZvciBvcmRlciBpbiBy
YW5kb20gaW5jcmVhc2luZyBkZWNyZWFzaW5nIDsgZG8KICAgICBlY2hvICIgICAgICAgIG1lbWNw
eShzb3J0ZWQsIHVuc29ydGVkLCBzaXplb2Yoc29ydGVkWzBdKSAqIG5vYmplY3RzKTsiCiAgICAg
ZWNobyAiICAgICAgICBJTlNUUl9USU1FX1NFVF9DVVJSRU5UKHN0YXJ0X3RpbWUpOyIKICAgICBl
Y2hvICIgICAgICAgIG1lbWNweShzb3J0ZWQsIHVuc29ydGVkLCBzaXplb2Yoc29ydGVkWzBdKSAq
IG5vYmplY3RzKTsiCi0gICAgZWNobyAiICAgICAgICBzb3J0NjRfJHt0aHJlc2hvbGR9X2l0ZW1w
dHIoc29ydGVkLCBub2JqZWN0cyk7IgorICAgIGVjaG8gIiAgICAgICAgc29ydF9pZHNfJHt0aHJl
c2hvbGR9X2l0ZW1wdHIoc29ydGVkLCBub2JqZWN0cyk7IgogICAgIGVjaG8gIiAgICAgICAgSU5T
VFJfVElNRV9TRVRfQ1VSUkVOVChlbmRfdGltZSk7IgogICAgIGVjaG8gIiAgICAgICAgSU5TVFJf
VElNRV9TVUJUUkFDVChlbmRfdGltZSwgc3RhcnRfdGltZSk7IgotICAgIGVjaG8gIiAgICAgICAg
ZWxvZyhOT1RJQ0UsIFwib3JkZXI9JG9yZGVyLCB0aHJlc2hvbGQ9JHRocmVzaG9sZCwgY21wPTY0
LCB0ZXN0PSVkLCB0aW1lPSVmXCIsIGksIElOU1RSX1RJTUVfR0VUX0RPVUJMRShlbmRfdGltZSkp
OyIKKyAgICBlY2hvICIgICAgICAgIGVsb2coTk9USUNFLCBcIm9yZGVyPSRvcmRlciwgdGhyZXNo
b2xkPSR0aHJlc2hvbGQsIGNtcD1pZHMsIHRlc3Q9JWQsIHRpbWU9JWZcIiwgaSwgSU5TVFJfVElN
RV9HRVRfRE9VQkxFKGVuZF90aW1lKSk7IgogICAgIGVjaG8gIiAgICB9IgogICBkb25lCiBkb25l
CmRpZmYgLS1naXQgYS9zcmMvdGVzdC9tb2R1bGVzL3Rlc3Rfc29ydF9wZXJmL3Rlc3Rfc29ydF9w
ZXJmLmMgYi9zcmMvdGVzdC9tb2R1bGVzL3Rlc3Rfc29ydF9wZXJmL3Rlc3Rfc29ydF9wZXJmLmMK
aW5kZXggMDVhMTA5MjRmMy4uMWViYWY0MTMyOSAxMDA2NDQKLS0tIGEvc3JjL3Rlc3QvbW9kdWxl
cy90ZXN0X3NvcnRfcGVyZi90ZXN0X3NvcnRfcGVyZi5jCisrKyBiL3NyYy90ZXN0L21vZHVsZXMv
dGVzdF9zb3J0X3BlcmYvdGVzdF9zb3J0X3BlcmYuYwpAQCAtOCw2ICs4LDQ0IEBACiAKICNpbmNs
dWRlIDxzdGRsaWIuaD4KIAorLyoKKyAqIEl0ZW1Qb2ludGVyR2V0QmxvY2tJZEhpTm9DaGVjawor
ICoJCVJldHVybnMgdGhlIGhpZ2ggc2hvcnQgb2YgYSBkaXNrIGl0ZW0gcG9pbnRlciBibG9ja2lk
LgorICovCisjZGVmaW5lIEl0ZW1Qb2ludGVyR2V0QmxvY2tJZEhpTm9DaGVjayhwb2ludGVyKSBc
CisoIFwKKwkocG9pbnRlciktPmlwX2Jsa2lkLmJpX2hpIFwKKykKKworLyoKKyAqIEl0ZW1Qb2lu
dGVyR2V0QmxvY2tJZEhpCisgKgkJQXMgYWJvdmUsIGJ1dCB2ZXJpZmllcyB0aGF0IHRoZSBpdGVt
IHBvaW50ZXIgbG9va3MgdmFsaWQuCisgKi8KKyNkZWZpbmUgSXRlbVBvaW50ZXJHZXRCbG9ja0lk
SGkocG9pbnRlcikgXAorKCBcCisJQXNzZXJ0TWFjcm8oSXRlbVBvaW50ZXJJc1ZhbGlkKHBvaW50
ZXIpKSwgXAorCUl0ZW1Qb2ludGVyR2V0QmxvY2tJZEhpTm9DaGVjayhwb2ludGVyKSBcCispCisK
Ky8qCisgKiBJdGVtUG9pbnRlckdldEJsb2NrSWRMb05vQ2hlY2sKKyAqCQlSZXR1cm5zIHRoZSBs
b3cgc2hvcnQgb2YgYSBkaXNrIGl0ZW0gcG9pbnRlciBibG9ja2lkLgorICovCisjZGVmaW5lIEl0
ZW1Qb2ludGVyR2V0QmxvY2tJZExvTm9DaGVjayhwb2ludGVyKSBcCisoIFwKKwkocG9pbnRlcikt
PmlwX2Jsa2lkLmJpX2xvIFwKKykKKworLyoKKyAqIEl0ZW1Qb2ludGVyR2V0QmxvY2tJZExvCisg
KgkJQXMgYWJvdmUsIGJ1dCB2ZXJpZmllcyB0aGF0IHRoZSBpdGVtIHBvaW50ZXIgbG9va3MgdmFs
aWQuCisgKi8KKyNkZWZpbmUgSXRlbVBvaW50ZXJHZXRCbG9ja0lkTG8ocG9pbnRlcikgXAorKCBc
CisJQXNzZXJ0TWFjcm8oSXRlbVBvaW50ZXJJc1ZhbGlkKHBvaW50ZXIpKSwgXAorCUl0ZW1Qb2lu
dGVyR2V0QmxvY2tJZEhpTm9DaGVjayhwb2ludGVyKSBcCispCisKIHN0YXRpYyBpbnQKIGl0ZW1w
dHJfY29tcGFyYXRvcihjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKQogewpAQCAtMjksNiAr
NjcsMzggQEAgaXRlbXB0cl9jb21wYXJhdG9yKGNvbnN0IHZvaWQgKmEsIGNvbnN0IHZvaWQgKmIp
CiAJcmV0dXJuIDA7CiB9CiAKK3N0YXRpYyBpbnQKK2l0ZW1wdHJfY29tcGFyYXRvcl9ibG9ja2lk
cyhjb25zdCB2b2lkICphLCBjb25zdCB2b2lkICpiKQoreworCWNvbnN0IEl0ZW1Qb2ludGVyRGF0
YSAqaXBhID0gKGNvbnN0IEl0ZW1Qb2ludGVyRGF0YSAqKSBhOworCWNvbnN0IEl0ZW1Qb2ludGVy
RGF0YSAqaXBiID0gKGNvbnN0IEl0ZW1Qb2ludGVyRGF0YSAqKSBiOworCisJdWludDE2IGJhX2hp
ID0gSXRlbVBvaW50ZXJHZXRCbG9ja0lkSGkoaXBhKTsKKwl1aW50MTYgYmJfaGkgPSBJdGVtUG9p
bnRlckdldEJsb2NrSWRIaShpcGIpOworCisJaWYgKGJhX2hpIDwgYmJfaGkpCisJCXJldHVybiAt
MTsKKwlpZiAoYmFfaGkgPiBiYl9oaSkKKwkJcmV0dXJuIDE7CisKKwl1aW50MTYgYmFfbG8gPSBJ
dGVtUG9pbnRlckdldEJsb2NrSWRMbyhpcGEpOworCXVpbnQxNiBiYl9sbyA9IEl0ZW1Qb2ludGVy
R2V0QmxvY2tJZExvKGlwYik7CisKKwlpZiAoYmFfbG8gPCBiYl9sbykKKwkJcmV0dXJuIC0xOwor
CWlmIChiYV9sbyA+IGJiX2xvKQorCQlyZXR1cm4gMTsKKworCU9mZnNldE51bWJlciBvYSA9IEl0
ZW1Qb2ludGVyR2V0T2Zmc2V0TnVtYmVyKGlwYSk7CisJT2Zmc2V0TnVtYmVyIG9iID0gSXRlbVBv
aW50ZXJHZXRPZmZzZXROdW1iZXIoaXBiKTsKKworCWlmIChvYSA8IG9iKQorCQlyZXR1cm4gLTE7
CisJaWYgKG9hID4gb2IpCisJCXJldHVybiAxOworCXJldHVybiAwOworfQorCiBQR19NT0RVTEVf
TUFHSUM7CiAKIC8qIGluY2x1ZGUgdGhlIGdlbmVyYXRlZCBjb2RlICovCg==
--000000000000759c3a05c6127c47--