[HACKERS] notify duplicate elimination

2014-02-09 Thread Hardy Falk
I have prepared a patch to backends/commands/async,c to speed up
duplicate elimination. rdtsc timing results are sent back via ereport.



*** a/src/backend/commands/async.c
--- b/src/backend/commands/async.c
***
*** 326,337  typedef struct Notification
--- 326,353 
  {
  	char	   *channel;		/* channel name */
  	char	   *payload;		/* payload string (can be empty) */
+ 	uint32  hash ;			/* speed up search for duplicates */
+ struct Notification *left  ;
+ struct Notification *right ;
+ 
  } Notification;
  
  static List *pendingNotifies = NIL;		/* list of Notifications */
  
  static List *upperPendingNotifies = NIL;		/* list of upper-xact lists */
  
+ static Notification *treerootNotifies = NULL ; /* speed up search for duplicates */
+ #warning rdtsc just included for lack of a suitable reference
+ static uint64   rdtsc_total ;
+ static int  rdtsc_count ;
+ static inline uint64 rdtsc(void)
+ {
+ 	uint64  x;
+ 	__asm__ volatile (.byte 0x0f, 0x31 : =A (x));
+ 	return x;
+ }
+ 
+ 
  /*
   * State for inbound notifications consists of two flags: one saying whether
   * the signal handler is currently allowed to call ProcessIncomingNotify
***
*** 382,389  static void ProcessIncomingNotify(void);
  static void NotifyMyFrontEnd(const char *channel,
   const char *payload,
   int32 srcPid);
- static bool AsyncExistsPendingNotify(const char *channel, const char *payload);
  static void ClearPendingActionsAndNotifies(void);
  
  /*
   * We will work on the page range of 0..QUEUE_MAX_PAGE.
--- 398,408 
  static void NotifyMyFrontEnd(const char *channel,
   const char *payload,
   int32 srcPid);
  static void ClearPendingActionsAndNotifies(void);
+ static Notification **AsyncSearchPendingNotifies(const char *channel,
+ const char *payload,
+ uint32 *hash);
+ /* Does pendingNotifies include the given channel/payload? */
  
  /*
   * We will work on the page range of 0..QUEUE_MAX_PAGE.
***
*** 533,538  Async_Notify(const char *channel, const char *payload)
--- 552,560 
  {
  	Notification *n;
  	MemoryContext oldcontext;
+ 	Notification **nn ; 
+ 	uint64 t1,t2 ; 
+ 	uint32 hash ; 
  
  	if (Trace_notify)
  		elog(DEBUG1, Async_Notify(%s), channel);
***
*** 557,564  Async_Notify(const char *channel, const char *payload)
  	}
  
  	/* no point in making duplicate entries in the list ... */
! 	if (AsyncExistsPendingNotify(channel, payload))
! 		return;
  
  	/*
  	 * The notification list needs to live until end of transaction, so store
--- 579,592 
  	}
  
  	/* no point in making duplicate entries in the list ... */
! 	t1 = rdtsc() ;
! nn = AsyncSearchPendingNotifies(channel,payload,hash) ;
! t2 = rdtsc();
! rdtsc_total += t2-t1 ;
! rdtsc_count += 1 ;
! if ( !nn ) /* this was a duplicate entry */
! return ;
! 
  
  	/*
  	 * The notification list needs to live until end of transaction, so store
***
*** 566,584  Async_Notify(const char *channel, const char *payload)
  	 */
  	oldcontext = MemoryContextSwitchTo(CurTransactionContext);
  
! 	n = (Notification *) palloc(sizeof(Notification));
  	n-channel = pstrdup(channel);
  	if (payload)
  		n-payload = pstrdup(payload);
  	else
  		n-payload = ;
  
! 	/*
! 	 * We want to preserve the order so we need to append every notification.
! 	 * See comments at AsyncExistsPendingNotify().
  	 */
  	pendingNotifies = lappend(pendingNotifies, n);
- 
  	MemoryContextSwitchTo(oldcontext);
  }
  
--- 594,625 
  	 */
  	oldcontext = MemoryContextSwitchTo(CurTransactionContext);
  
! 	n = (Notification *) palloc(sizeof(*n));
  	n-channel = pstrdup(channel);
  	if (payload)
  		n-payload = pstrdup(payload);
  	else
  		n-payload = ;
+  
+ 	/* append to search tree */
+ 	n-left  = NULL ; 
+ 	n-right = NULL ; 
+ 	n-hash  = hash ; 
+ 	*nn = n ;
  
! 	/* We want to preserve the order so we need to append every notification. 
! 	 * As we are not checking our parents' lists, we can still get duplicates
! 	 * in combination with subtransactions, like in:
! 	 *
! 	 * begin;
! 	 * notify foo '1';
! 	 * savepoint foo;
! 	 * notify foo '1';
! 	 * commit;
! 	 *--
  	 */
+ 
  	pendingNotifies = lappend(pendingNotifies, n);
  	MemoryContextSwitchTo(oldcontext);
  }
  
***
*** 2149,2156  NotifyMyFrontEnd(const char *channel, const char *payload, int32 srcPid)
  		elog(INFO, NOTIFY for \%s\ payload \%s\, channel, payload);
  }
  
! /* Does pendingNotifies include the given channel/payload? */
! static bool
  AsyncExistsPendingNotify(const char *channel, const char *payload)
  {
  	ListCell   *p;
--- 2190,2314 
  		elog(INFO, NOTIFY for \%s\ payload \%s\, channel, payload);
  }
  
! 
! static inline uint32 murmurhash2( const char* key, uint32 seed )
! #warning yet another copy of murmurhash2
! #warning should we use murmurhash3 or one of the hash functions from 

[HACKERS] notify duplicate elimination performance

2014-02-08 Thread Hardy Falk
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

2014-02-08 Thread Hardy Falk
 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

2014-02-08 Thread Hardy Falk
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