At Tue, 2 Aug 2022 16:18:44 +0100, Simon Riggs <simon.riggs@enterprisedb.com> wrote in
> On Tue, 2 Aug 2022 at 12:32, Andrey Borodin <x4mmm@yandex-team.ru> wrote:
>
> > KnownAssignedXidsRemoveTree() only compress with probability 1/8, but it is still O(N*N).
>
> Currently it is O(NlogS), not quite as bad as O(N^2).
>
> Since each xid in the tree is always stored to the right, it should be
> possible to make that significantly better by starting each binary
> search from the next element, rather than the start of the array.
> Something like the attached might help, but we can probably make that
> cache conscious to improve things even more.
The original complaint is KnownAssignedXidsGetAndSetXmin can get very
slow for large max_connections. I'm not sure what was happening on the
KAXidsArray at the time precisely, but if the array starts with a
large number of invalid entries (I guess it is likely), and the
variable "start" were available to the function (that is, it were
placed in procArray), that strategy seems to work for this case. With
this strategy we can avoid compression if only the relatively narrow
range in the array is occupied.
regards.
--
Kyotaro Horiguchi
NTT Open Source Software Center