[HACKERS] notify duplicate elimination performance
I know that it is not a big problem for most users, but allowing a very
large number of notifications while using linear search is a bit dumb.
I can fix this with a very small modification to
struct Notification:
{
char *channel ;
char *payload ;
uint32 hash ;
struct Notification *left ;
struct Notification *right ;
}
AsyncExistsPendingNotify does an iterative binary tree search.
The tree is insert-only, there is no need for rebalancing, and the code
is quite simple.
Any comments?
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] notify duplicate elimination performance
Hi,
On 2014-02-08 18:56:41 +0100, Hardy Falk wrote:
I know that it is not a big problem for most users, but allowing a very
large number of notifications while using linear search is a bit dumb.
I can fix this with a very small modification to
struct Notification:
{
char *channel ;
char *payload ;
uint32 hash ;
struct Notification *left ;
struct Notification *right ;
}
AsyncExistsPendingNotify does an iterative binary tree search.
The tree is insert-only, there is no need for rebalancing, and the code
is quite simple.
Any comments?
Well, you didn't add any code, so it's hard to say... Simple ways of
doing what I think you describe will remove the queue's order. Do you
preserve the ordering guarantees?
Greetings,
Andres Freund
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] notify duplicate elimination performance
Well, you didn't add any code, so it's hard to say... Simple ways of
doing what I think you describe will remove the queue's order. Do you
preserve the ordering guarantees?
Greetings,
Andres Freund
Yes, the order is preserved.
I didn't remove the the original list code.
The tree is just an additional access path.
oldcontext = MemoryContextSwitchTo(CurTransactionContext);
n = (Notification *) palloc(sizeof(Notification));
n-channel = pstrdup(channel);
if (payload)
n-payload = pstrdup(payload);
else
n-payload = ;
n-hash = hash ;
n-left = NULL ;
n-right= NULL ;
*tt = n ;
tt is a Notification** obtained by the search.
static Notification **search(const char *channel, const char *payload )
{
Notification *t,**tt ;
uint32 hash ;
t = hashroot ;
tt = hashroot ;
hash = hashf(channel,691) ;
hash = hashf(payload,hash) ;
while ( t )
{
if ( hash t-hash )
{
tt = t-left ;
t = t-left ;
}
else if ( hash t-hash )
{
tt = t-right ;
t = t-right ;
}
else
{
if (0==strcmp(t-channel,channel)
0==strcmp(t-payload,payload))
{
return NULL
}
else
{
tt = t-left ;
t = t-left ;
}
}
}
return tt ;
}
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] notify duplicate elimination performance
Hi, On 2014-02-08 19:28:56 +0100, Hardy Falk wrote: Well, you didn't add any code, so it's hard to say... Simple ways of doing what I think you describe will remove the queue's order. Do you preserve the ordering guarantees? Greetings, Andres Freund Yes, the order is preserved. I didn't remove the the original list code. The tree is just an additional access path. How about actually attaching a patch? Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] notify duplicate elimination performance
Hardy Falk hardy.f...@blue-cable.de writes: Well, you didn't add any code, so it's hard to say... Simple ways of doing what I think you describe will remove the queue's order. Do you preserve the ordering guarantees? Yes, the order is preserved. I didn't remove the the original list code. The tree is just an additional access path. It seems likely that this approach would be a net loss for small numbers of notify events (which is surely the common case). Have you done any measurements of the performance tradeoff? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] notify duplicate elimination performance
Tom Lane schrieb:
Hardy Falk hardy.f...@blue-cable.de writes:
Well, you didn't add any code, so it's hard to say... Simple ways of
doing what I think you describe will remove the queue's order. Do you
preserve the ordering guarantees?
Yes, the order is preserved.
I didn't remove the the original list code.
The tree is just an additional access path.
It seems likely that this approach would be a net loss for small numbers
of notify events (which is surely the common case). Have you done any
measurements of the performance tradeoff?
regards, tom lane
I can easily keep the tail test. This avoids the hash computation in a
common case. The tree search compares only uint32 values, this should be
quite fast. Even a degenerate tree is no worse than the list. Im my
first tests I didn't use murmurhash, a select
pg_notify('alasys',format('Hello %s',x) from generate_series(1,100)
as x triggered this worst case. With murmurhash2 the average search
depth for 10^6 entries is 24.57.
I am about to prepare a patch, should I do some performance tests with
rtdsc first?
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
