Proposed fix for NOTIFY performance degradation

Hi,

while measuring NOTIFY execution time, I noticed a significant
performance drop.

Please find a patch attached, together with some tests; more details
are shown below.

Best regards,
Dr. Gianni Ciolli - 2ndQuadrant Italia
PostgreSQL Training, Services and Support
gianni(dot)ciolli(at)2ndquadrant(dot)it | www.2ndquadrant.it

---8<------8<------8<------8<------8<------8<------8<------8<------8<---

h1. The problem

We record pending notifications in a transaction-based list.
Notifications are recorded in the same order as they are issued.

Because of PostgreSQL's asynchronous notification semantics, we don't
need to record two identical notifications; we record a notification
only if there are no duplicates.

This is implemented by scanning the list and checking for duplicates.
The list is scanned backwards because the last element is easily
accessible, which is a sensible optimisation in the case of many
notifications which are identical to the previous one (scenario A).

However, scanning the list is quite expensive in the case of many
notifications which are not identical to the previous one (scenario B,
see Test 1 below when m > 1).

h1. Proposed solution

To check only the last element in that list, which is efficient in
both scenarios (see Test 2 below).

h1. Tests

"PostgreSQL HEAD" has been fetched as after commit #a0e8df52 (Wed Apr
20 22:49:37 2011 -0400).

Test 1 has been executed against PostgreSQL HEAD.

Test 2 has been executed against patched version of PostgreSQL HEAD.

In the tables below:

* "n" denotes the number of notifications issued in a single
transaction;

* "m" denotes the number of distinct channels used for these
notifications;

* "iter" is the number of times each transaction has been repeated (to
reduce the importance of occasional spikes);

* "avg_usec" denotes the average time in microseconds required by each
NOTIFY statement.

h2. Test 1 - PostgreSQL HEAD

n | m | iter | avg_usec
-------+-------+------+----------
10 | 1 | 10 | 43.730
100 | 1 | 10 | 37.630
1000 | 1 | 10 | 42.990
10000 | 1 | 10 | 36.225
10 | 10 | 10 | 43.960
100 | 100 | 10 | 46.537
1000 | 1000 | 10 | 126.115
10000 | 10000 | 10 | 906.501

h2. Test 2 - patched PostgreSQL

n | m | iter | avg_usec
-------+-------+------+----------
10 | 1 | 10 | 43.810
100 | 1 | 10 | 38.256
1000 | 1 | 10 | 36.950
10000 | 1 | 10 | 36.638
10 | 10 | 10 | 44.830
100 | 100 | 10 | 38.684
1000 | 1000 | 10 | 38.924
10000 | 10000 | 10 | 38.032