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.ciolli@2ndquadrant.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