Re: ResourceOwner refactoring

On 21/01/2021 06:14, Michael Paquier wrote:
> On Thu, Jan 21, 2021 at 12:11:37AM +0200, Heikki Linnakangas wrote:
>> Summary: In the the worst scenario, the patched version is still 24% slower
>> than unpatched. But many other scenarios are now faster with the patch.
>
> Is there a reason explaining the sudden drop for numsnaps within the
> [10,60] range? The gap looks deeper with a low numkeep.

It's the switch from array to hash table. With the patch, the array
holds 8 entries. Without the patch, it's 64 entries. So you see a drop
around those points. I added more data points in that range to get a
better picture:

LIFO tests:
numkeep | numsnaps | unpatched | patched | ratio
---------+----------+-----------+---------+-------
0 | 1 | 32.8 | 32.9 | 1.00
0 | 2 | 31.6 | 32.8 | 1.04
0 | 4 | 32.7 | 32.0 | 0.98
0 | 6 | 34.1 | 33.9 | 0.99
0 | 8 | 35.1 | 32.4 | 0.92
0 | 10 | 34.0 | 37.1 | 1.09
0 | 15 | 33.1 | 35.9 | 1.08
0 | 20 | 33.0 | 38.8 | 1.18
0 | 25 | 32.9 | 42.3 | 1.29
0 | 30 | 32.9 | 40.5 | 1.23
0 | 35 | 33.1 | 39.9 | 1.21
0 | 40 | 33.0 | 39.0 | 1.18
0 | 45 | 35.3 | 41.1 | 1.16
0 | 50 | 33.0 | 40.8 | 1.24
0 | 55 | 32.8 | 40.6 | 1.24
0 | 58 | 33.0 | 41.5 | 1.26
0 | 60 | 33.1 | 41.6 | 1.26
0 | 62 | 32.8 | 41.7 | 1.27
0 | 64 | 46.8 | 40.9 | 0.87
0 | 66 | 47.0 | 42.5 | 0.90
0 | 68 | 47.1 | 41.8 | 0.89
0 | 70 | 47.8 | 41.7 | 0.87
(22 rows)

FIFO tests:
numkeep | numsnaps | unpatched | patched | ratio
---------+----------+-----------+---------+-------
0 | 1 | 32.3 | 32.1 | 0.99
0 | 2 | 33.4 | 31.6 | 0.95
0 | 4 | 34.0 | 31.4 | 0.92
0 | 6 | 35.4 | 33.2 | 0.94
0 | 8 | 34.8 | 31.9 | 0.92
0 | 10 | 35.4 | 40.2 | 1.14
0 | 15 | 35.4 | 40.3 | 1.14
0 | 20 | 35.6 | 43.8 | 1.23
0 | 25 | 35.4 | 42.4 | 1.20
0 | 30 | 36.0 | 43.3 | 1.20
0 | 35 | 36.4 | 45.1 | 1.24
0 | 40 | 36.9 | 46.6 | 1.26
0 | 45 | 37.7 | 45.3 | 1.20
0 | 50 | 37.2 | 43.9 | 1.18
0 | 55 | 38.4 | 46.8 | 1.22
0 | 58 | 37.6 | 45.0 | 1.20
0 | 60 | 37.7 | 46.6 | 1.24
0 | 62 | 38.4 | 46.5 | 1.21
0 | 64 | 48.7 | 47.6 | 0.98
0 | 66 | 48.2 | 45.8 | 0.95
0 | 68 | 48.5 | 47.5 | 0.98
0 | 70 | 48.4 | 47.3 | 0.98
(22 rows)

Let's recap the behavior:

Without patch
-------------

For each different kind of resource, there's an array that holds up to
64 entries. In ResourceOwnerForget(), the array is scanned linearly. If
the array fills up, we replace the array with a hash table. After
switching, all operations use the hash table.

With patch
----------

There is one array that holds up to 8 entries. It is shared by all
resources. In ResourceOwnerForget(), the array is always scanned.

If the array fills up, all the entries are moved to a hash table,
freeing up space in the array, and the new entry is added to the array.
So the array is used together with the hash table, like an LRU cache of
the most recently remembered entries.

Why this change? I was afraid that now that all different resources
share the same data structure, remembering e.g. a lot of locks at the
beginning of a transaction would cause the switch to the hash table,
making all subsequent remember/forget operations, like for buffer pins,
slower. That kind of interference seems bad. By continuing to use the
array for the recently-remembered entries, we avoid that problem. The
[numkeep, numsnaps] = [65, 70] test is in that regime, and the patched
version was significantly faster.

Because the array is now always scanned, I felt that it needs to be
small, to avoid wasting much time scanning for entries that have already
been moved to the hash table. That's why I made it just 8 entries.

Perhaps 8 entries is too small, after all? Linearly scanning an array is
very fast. To test that, I bumped up RESOWNER_ARRAY_SIZE to 64, and ran
the test again:

numkeep | numsnaps | lifo_time_ns | fifo_time_ns
---------+----------+--------------+--------------
0 | 1 | 35.4 | 31.5
0 | 2 | 32.3 | 32.3
0 | 4 | 32.8 | 31.0
0 | 6 | 34.5 | 33.7
0 | 8 | 33.9 | 32.7
0 | 10 | 33.7 | 33.0
0 | 15 | 34.8 | 33.1
0 | 20 | 35.0 | 32.6
0 | 25 | 36.9 | 33.0
0 | 30 | 38.7 | 33.2
0 | 35 | 39.9 | 34.5
0 | 40 | 40.8 | 35.5
0 | 45 | 42.6 | 36.4
0 | 50 | 44.9 | 37.8
0 | 55 | 45.4 | 38.5
0 | 58 | 47.7 | 39.6
0 | 60 | 45.9 | 40.2
0 | 62 | 47.6 | 40.9
0 | 64 | 51.4 | 41.2
0 | 66 | 38.2 | 39.8
0 | 68 | 39.7 | 40.3
0 | 70 | 38.1 | 40.9
(22 rows)

Here you can see that as numsnaps increases, the test becomes slower,
but then it becomes faster again at 64-66, when it switches to the hash
table. So 64 seems too much. 32 seems to be the sweet spot here, that's
where scanning the hash and scanning the array are about the same speed.

- Heikki