At Tue, 2 Aug 2022 16:18:44 +0100, Simon Riggs <simon.ri...@enterprisedb.com> wrote in > On Tue, 2 Aug 2022 at 12:32, Andrey Borodin <x4...@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
