sinval synchronization considered harmful

Robert Haas wrote:

SIGetDataEntries(). I believe we need to bite the bullet and
rewrite this using a lock-free algorithm, using memory barriers on
processors with weak memory ordering.

[32 processors; 80 clients]

On unpatched master

tps = 132518.586371 (including connections establishing)
tps = 130968.749747 (including connections establishing)
tps = 132574.338942 (including connections establishing)

With the lazy vxid locks patch

tps = 119215.958372 (including connections establishing)
tps = 113056.859871 (including connections establishing)
tps = 160562.770998 (including connections establishing)

gets rid of SInvalReadLock and instead gives each backend its own
spinlock.

tps = 167392.042393 (including connections establishing)
tps = 171336.145020 (including connections establishing)
tps = 170500.529303 (including connections establishing)

SIGetDataEntries() can pretty easily be made lock-free.

tps = 203256.701227 (including connections establishing)
tps = 190637.957571 (including connections establishing)
tps = 190228.617178 (including connections establishing)

Thoughts? Comments? Ideas?

Very impressive! Those numbers definitely justify some #ifdef code
to provide alternatives for weak memory ordering machines versus
others. With the number of CPUs climbing as it is, this is very
important work!

-Kevin

On Thu, Jul 21, 2011 at 12:16 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:

Very impressive!  Those numbers definitely justify some #ifdef code
to provide alternatives for weak memory ordering machines versus
others.  With the number of CPUs climbing as it is, this is very
important work!

Thanks. I'm not thinking so much about #ifdef (although that could
work, too) as I am about providing some primitives to allow this sort
of code-writing to be done in a somewhat less ad-hoc fashion. It
seems like there are basically two categories of machines we need to
worry about.

1. Machines with strong memory ordering. On this category of machines
(which include x86), the CPU basically does not perform loads or
stores out of order. On some of these machines, it is apparently
possible for there to be some ordering of stores relative to loads,
but if the program stores two values or loads two values, those
operations will performed in the same order they appear in the
program. The main thing you need to make your code work reliably on
these machines is a primitive that keeps the compiler from reordering
your code during optimization. On x86, certain categories of exotic
instructions do require

2. Machines with weak memory ordering. On this category of machines
(which includes PowerPC, Dec Alpha, and maybe some others), the CPU
reorders memory accesses arbitrarily unless you explicitly issue
instructions that enforce synchronization. You still need to keep the
compiler from moving things around, too. Alpha is particularly
pernicious, because something like a->b can fetch the pointed-to value
before loading the pointer itself. This is otherwise known as "we
have basically no cache coherency circuits on this chip at all". On
these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

So you can imagine a primitive that is defined to be a compiler
barrier on machines with strong memory ordering, and as a memory
fencing instruction on machines with weak memory ordering.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

... On these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

Right, and the reason that a spinlock fixes it is that we have memory
barrier instructions built into the spinlock code sequences on machines
where it matters.

To get to the point where we could do the sort of optimization Robert
is talking about, someone will have to build suitable primitives for
all the platforms we support. In the cases where we use gcc ASM in
s_lock.h, it shouldn't be too hard to pull out the barrier
instruction(s) ... but on platforms where we rely on OS-supplied
functions, some research is going to be needed.

regards, tom lane

On Thu, Jul 21, 2011 at 2:50 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

... On these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

Right, and the reason that a spinlock fixes it is that we have memory
barrier instructions built into the spinlock code sequences on machines
where it matters.

To get to the point where we could do the sort of optimization Robert
is talking about, someone will have to build suitable primitives for
all the platforms we support.  In the cases where we use gcc ASM in
s_lock.h, it shouldn't be too hard to pull out the barrier
instruction(s) ... but on platforms where we rely on OS-supplied
functions, some research is going to be needed.

Yeah, although falling back to SpinLockAcquire() and SpinLockRelease()
on a backend-private slock_t should work anywhere that PostgreSQL
works at all[1]This was a suggestion from Noah Misch. I wasn't quite convinced when he initially made it, but having studied the issue a lot more, I now am. The CPU doesn't know how many processes have the memory mapped into their address space.. That will probably be slower than a memory fence
instruction and certainly slower than a compiler barrier, but the
point is that - right now - we're doing it the slow way everywhere.

I think the real challenge is going to be testing. If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.
Getting it to work on x86 is not the hard part.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

[1]: This was a suggestion from Noah Misch. I wasn't quite convinced when he initially made it, but having studied the issue a lot more, I now am. The CPU doesn't know how many processes have the memory mapped into their address space.
when he initially made it, but having studied the issue a lot more, I
now am. The CPU doesn't know how many processes have the memory
mapped into their address space.

On Thu, Jul 21, 2011 at 8:15 PM, Robert Haas <robertmhaas@gmail.com> wrote:

I think the real challenge is going to be testing.  If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.
Getting it to work on x86 is not the hard part.

I believe there's a PPC box in our storage facility in NJ that we
might be able to dig out for you. There's also a couple in our India
office. Let me know if they'd be of help.

--
Dave Page
Blog: http://pgsnake.blogspot.com
Twitter: @pgsnake

EnterpriseDB UK: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 21, 2011 at 3:22 PM, Dave Page <dpage@pgadmin.org> wrote:

On Thu, Jul 21, 2011 at 8:15 PM, Robert Haas <robertmhaas@gmail.com> wrote:

I think the real challenge is going to be testing.  If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.
Getting it to work on x86 is not the hard part.

I believe there's a PPC box in our storage facility in NJ that we
might be able to dig out for you. There's also a couple in our India
office. Let me know if they'd be of help.

Yes!

More processors is better, of course, but having anything at all to
test on would be an improvement.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 21, 2011 at 8:25 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Thu, Jul 21, 2011 at 3:22 PM, Dave Page <dpage@pgadmin.org> wrote:

On Thu, Jul 21, 2011 at 8:15 PM, Robert Haas <robertmhaas@gmail.com> wrote:

I think the real challenge is going to be testing.  If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.
Getting it to work on x86 is not the hard part.

I believe there's a PPC box in our storage facility in NJ that we
might be able to dig out for you. There's also a couple in our India
office. Let me know if they'd be of help.

Yes!

More processors is better, of course, but having anything at all to
test on would be an improvement.

OK, will check with India first, as it'll be easier for them to deploy.

--
Dave Page
Blog: http://pgsnake.blogspot.com
Twitter: @pgsnake

EnterpriseDB UK: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

I think the real challenge is going to be testing. If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.

There are multi-CPU PPCen in the buildfarm, or at least there were last
time I broke the sinval code ;-). Note that testing on a single-core
PPC will prove nothing.

regards, tom lane

On Thu, Jul 21, 2011 at 3:53 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

I think the real challenge is going to be testing.  If anyone has a
machine with weak memory ordering they can give me access to, that
would be really helpful for flushing the bugs out of this stuff.

There are multi-CPU PPCen in the buildfarm, or at least there were last
time I broke the sinval code ;-).  Note that testing on a single-core
PPC will prove nothing.

Yeah, I was just thinking about that.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

For the last week or so, in between various other tasks, I've been
trying to understand why performance drops off when you run pgbench -n
-S -c $CLIENTS -j $CLIENTS -T $A_FEW_MINUTES at very high client
counts. The answer, in a word, is SIGetDataEntries(). I believe we
need to bite the bullet and rewrite this using a lock-free algorithm,
using memory barriers on processors with weak memory ordering.
Perhaps there is another way to do it, but nothing I've tried has
really worked so far, and I've tried quite a few things. Here's the
data.

On unpatched master, performance scales pretty much linearly out to 32
clients. As you add more clients, it drops off:

[80 clients]
tps = 132518.586371 (including connections establishing)
tps = 130968.749747 (including connections establishing)
tps = 132574.338942 (including connections establishing)

[80 clients, with lazy vxid locks and sinval-unlocked]
tps = 203256.701227 (including connections establishing)
tps = 190637.957571 (including connections establishing)
tps = 190228.617178 (including connections establishing)

Nice numbers. The sinval-unlocked.patch implementation looks like it's taking a
sound direction.

In
http://archives.postgresql.org/message-id/CA+TgmobbxMh_9zjudheSWO6m8sBMb5hdZt+3ChCLuv5eztv8Ug@mail.gmail.com,
you quoted 210k TPS when you stubbed out AcceptInvalidationMessages(). Is it
correct to conclude that AcceptInvalidationMessages() still reduces the
transaction rate by 5-10% with this stack of patches?

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Jul 21, 2011 at 4:54 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

For the last week or so, in between various other tasks, I've been
trying to understand why performance drops off when you run pgbench -n
-S -c $CLIENTS -j $CLIENTS -T $A_FEW_MINUTES at very high client
counts.  The answer, in a word, is SIGetDataEntries().  I believe we
need to bite the bullet and rewrite this using a lock-free algorithm,
using memory barriers on processors with weak memory ordering.
Perhaps there is another way to do it, but nothing I've tried has
really worked so far, and I've tried quite a few things.  Here's the
data.

On unpatched master, performance scales pretty much linearly out to 32
clients.  As you add more clients, it drops off:

[80 clients]
tps = 132518.586371 (including connections establishing)
tps = 130968.749747 (including connections establishing)
tps = 132574.338942 (including connections establishing)

[80 clients, with lazy vxid locks and sinval-unlocked]
tps = 203256.701227 (including connections establishing)
tps = 190637.957571 (including connections establishing)
tps = 190228.617178 (including connections establishing)

Nice numbers.  The sinval-unlocked.patch implementation looks like it's taking a
sound direction.

In
http://archives.postgresql.org/message-id/CA+TgmobbxMh_9zjudheSWO6m8sBMb5hdZt+3ChCLuv5eztv8Ug@mail.gmail.com,
you quoted 210k TPS when you stubbed out AcceptInvalidationMessages().  Is it
correct to conclude that AcceptInvalidationMessages() still reduces the
transaction rate by 5-10% with this stack of patches?

Good question - I have not tested.

One idea I just had... if we use a 64-bit counter for maxMsgNum, maybe
we could make AcceptInvalidationMessages() a macro, something like
this:

if (MyProcState->nextMsgNum != shmInvalState->maxMsgNum)
ReallyAcceptInvalidationMessages();

That ought to be extremely cheap and - if we use 64-bit counters for
the message-number counters - safe. You might object that the load of
maxMsgNum might migrate backward, but it can't possibly back up any
further than the preceding lock acquisition, since that's required to
be a full memory barrier on every architecture. And if we haven't
acquired a relevant lock, then a relevant sinval message could show up
an instance after we check regardless of the implementation.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Jul21, 2011, at 21:15 , Robert Haas wrote:

On Thu, Jul 21, 2011 at 2:50 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

... On these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

Right, and the reason that a spinlock fixes it is that we have memory
barrier instructions built into the spinlock code sequences on machines
where it matters.

To get to the point where we could do the sort of optimization Robert
is talking about, someone will have to build suitable primitives for
all the platforms we support. In the cases where we use gcc ASM in
s_lock.h, it shouldn't be too hard to pull out the barrier
instruction(s) ... but on platforms where we rely on OS-supplied
functions, some research is going to be needed.

Yeah, although falling back to SpinLockAcquire() and SpinLockRelease()
on a backend-private slock_t should work anywhere that PostgreSQL
works at all[1]. That will probably be slower than a memory fence
instruction and certainly slower than a compiler barrier, but the
point is that - right now - we're doing it the slow way everywhere.

As I discovered while playing with various lockless algorithms to
improve our LWLocks, spin locks aren't actually a replacement for
a (full) barrier.

Lock acquisition only really needs to guarantee that loads and stores
which come after the acquisition operation in program order (i.e., in
the instruction stream) aren't globally visible before that operation
completes. This kind of barrier behaviour is often fittingly called
"acquire barrier".

Similarly, a lock release operation only needs to guarantee that loads
and stores which occur before that operation in program order are
globally visible before the release operation completes. This, again,
is fittingly called "release barrier".

Now assume the following code fragment

global1 = 1;
SpinLockAcquire();
SpinLockRelease();
global2 = 1;

If SpinLockAcquire() has "acquire barrier" semantics, and SpinLockRelease()
has "release barrier" sematics, the it's possible for the store to global1
to be delayed until after SpinLockAcquire(), and similarly for the store
to global2 to be executed before SpinLockRelease() completes. In other
words, what happens is

SpinLockAcquire();
global1 = 1;
global2 = 1;
SpinLockRelease();

But once that can happens, there's no reason that it couldn't also be

SpinLockAcquire();
global2 = 1;
global1 = 1;
SpinLockRelease();

I didn't check if any of our spin lock implementations is actually affected
by this, but it doesn't seem wise to rely on them being full barriers, even
if it may be true today.

best regards,
Florian Pflug

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

Profiling this combination of patches reveals that there is still some
pretty ugly spinlock contention on sinval's msgNumLock. And it occurs
to me that on x86, we really don't need this lock ... or
SInvalReadLock ... or a per-backend mutex. The whole of
SIGetDataEntries() can pretty easily be made lock-free. The only real
changes that seem to be are needed are (1) to use a 64-bit counter, so
you never need to decrement

On second thought, won't this be inadequate on 32-bit systems, where updating
the 64-bit counter produces two stores? You must avoid reading it between those
stores.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Jul 21, 2011 at 02:31:15PM -0400, Robert Haas wrote:

1. Machines with strong memory ordering. On this category of machines
(which include x86), the CPU basically does not perform loads or
stores out of order. On some of these machines, it is apparently
possible for there to be some ordering of stores relative to loads,
but if the program stores two values or loads two values, those
operations will performed in the same order they appear in the
program.

This is all correct, but...

The main thing you need to make your code work reliably on
these machines is a primitive that keeps the compiler from reordering
your code during optimization.

If you're suggesting that hardware memory barriers aren't going to be
needed to implement lock-free code on x86, that isn't true. Because a
read can be reordered with respect to a write to a different memory
location, you can still have problems. So you do still need memory
barriers, just fewer of them.

Dekker's algorithm is the classic example: two threads each set a flag
and then check whether the other thread's flag is set. In any
sequential execution, at least one should see the other's flag set, but
on the x86 that doesn't always happen. One thread's read might be
reordered before its write.

2. Machines with weak memory ordering. On this category of machines
(which includes PowerPC, Dec Alpha, and maybe some others), the CPU
reorders memory accesses arbitrarily unless you explicitly issue
instructions that enforce synchronization. You still need to keep the
compiler from moving things around, too. Alpha is particularly
pernicious, because something like a->b can fetch the pointed-to value
before loading the pointer itself. This is otherwise known as "we
have basically no cache coherency circuits on this chip at all". On
these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

The Alpha is pretty much unique (thankfully!) in allowing dependent
reads to be reordered. That makes it even weaker than the typical
weak-ordering machine. Since reading a pointer and then dereferencing
it is a pretty reasonable thing to do regularly in RCU code, you
probably don't want to emit barriers in between on architectures where
it's not actually necessary. That argues for another operation that's
defined to be a barrier (mb) on the Alpha but a no-op elsewhere.
Certainly the Linux kernel found it useful to do so
(read_barrier_depends)

Alternatively, one might question how important it is to support the
Alpha these days...

Dan

--
Dan R. K. Ports MIT CSAIL http://drkp.net/

On Jul21, 2011, at 03:46 , Robert Haas wrote:

Profiling this combination of patches reveals that there is still some
pretty ugly spinlock contention on sinval's msgNumLock. And it occurs
to me that on x86, we really don't need this lock ... or
SInvalReadLock ... or a per-backend mutex. The whole of
SIGetDataEntries() can pretty easily be made lock-free. The only real
changes that seem to be are needed are (1) to use a 64-bit counter, so
you never need to decrement and (2) to recheck resetState after
reading the entries from the queue, to see if we got reset while we
were reading those entries. Since x86 guarantees that writes will
become visible in the order they are executed, we only need to make
sure that the compiler doesn't rearrange things. As long as we first
read the maxMsgNum and then read the messages, we can't read garbage.
As long as we read the messages before we check resetState, we will be
sure to notice if we got reset before we read all the messages (which
is the only way that we can have read garbage messages).

Sounds sensible. There're one additional hazard though - you'll also
need the reads to be atomic. x86 guarantees that for up to 32 (i386)
respectively 64 (x64) loads, but only for reads from properly aligned
addresses (4 bytes for 4-byte reads, 8 bytes for 8-byte reads).

I founds that out the hard way a few days ago, again while playing with
different LWLock implementations, when I botched my test setup and
the proc array entries ended up being miss-aligned. Boy, was it fun
to debug the random crashes caused by non-atomic pointer reads...

If we widen the counter to 64-bit, reading it atomically on x86 becomes
a bit of a challenge on i386, but is doable also. From what I remember,
there are two options. You can either use the 8-byte compare-and-exchange
operation, but it might be that only quite recent CPUs support that. The
other options seems to be to use floating-point instructions. I believe
the latter is what Intel's own Thread Building Blocks library does, but
I'd have to re-check to be sure. It might also be that, once you starting
using floating-point instructions, you find that you actually do need
fencing instructions even on x86. Dunno if the weaker ordering affects only
SIMD instructions or all floating point stuff...

best regards,
Florian Pflug

On Thu, Jul 21, 2011 at 6:22 PM, Florian Pflug <fgp@phlo.org> wrote:

On Jul21, 2011, at 21:15 , Robert Haas wrote:

On Thu, Jul 21, 2011 at 2:50 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

... On these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

Right, and the reason that a spinlock fixes it is that we have memory
barrier instructions built into the spinlock code sequences on machines
where it matters.

To get to the point where we could do the sort of optimization Robert
is talking about, someone will have to build suitable primitives for
all the platforms we support.  In the cases where we use gcc ASM in
s_lock.h, it shouldn't be too hard to pull out the barrier
instruction(s) ... but on platforms where we rely on OS-supplied
functions, some research is going to be needed.

Yeah, although falling back to SpinLockAcquire() and SpinLockRelease()
on a backend-private slock_t should work anywhere that PostgreSQL
works at all[1]. That will probably be slower than a memory fence
instruction and certainly slower than a compiler barrier, but the
point is that - right now - we're doing it the slow way everywhere.

As I discovered while playing with various lockless algorithms to
improve our LWLocks, spin locks aren't actually a replacement for
a (full) barrier.

Lock acquisition only really needs to guarantee that loads and stores
which come after the acquisition operation in program order (i.e., in
the instruction stream) aren't globally visible before that operation
completes. This kind of barrier behaviour is often fittingly called
"acquire barrier".

Similarly, a lock release operation only needs to guarantee that loads
and stores which occur before that operation in program order are
globally visible before the release operation completes. This, again,
is fittingly called "release barrier".

Now assume the following code fragment

global1 = 1;
SpinLockAcquire();
SpinLockRelease();
global2 = 1;

If SpinLockAcquire() has "acquire barrier" semantics, and SpinLockRelease()
has "release barrier" sematics, the it's possible for the store to global1
to be delayed until after SpinLockAcquire(), and similarly for the store
to global2 to be executed before SpinLockRelease() completes. In other
words, what happens is

SpinLockAcquire();
global1 = 1;
global2 = 1;
SpinLockRelease();

But once that can happens, there's no reason that it couldn't also be

SpinLockAcquire();
global2 = 1;
global1 = 1;
SpinLockRelease();

I didn't check if any of our spin lock implementations is actually affected
by this, but it doesn't seem wise to rely on them being full barriers, even
if it may be true today.

Hmm. I'm not worried about that. AFAIK, only IA64 has such an
implementation, and our existing spinlock implementation doesn't use
it. If we were to add something like that in the future, we'd
presumably know that we were doing it, and would add the appropriate
memory barrier primitive at the same time.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 21, 2011 at 6:44 PM, Dan Ports <drkp@csail.mit.edu> wrote:

If you're suggesting that hardware memory barriers aren't going to be
needed to implement lock-free code on x86, that isn't true. Because a
read can be reordered with respect to a write to a different memory
location, you can still have problems. So you do still need memory
barriers, just fewer of them.

Dekker's algorithm is the classic example: two threads each set a flag
and then check whether the other thread's flag is set. In any
sequential execution, at least one should see the other's flag set, but
on the x86 that doesn't always happen. One thread's read might be
reordered before its write.

In the case of sinval, what we need to do for SIGetDataEntries() is,
approximately, a bunch of loads, followed by a store to one of the
locations we loaded (which no one else can have written meanwhile).
So I think that's OK.

In SIInsertDataEntries(), what we need to do is, approximately, take a
lwlock, load from a location which can only be written while holding
the lwlock, do a bunch of stores, ending with a store to that first
location, and release the lwlock. I think that's OK, too.

2. Machines with weak memory ordering.  On this category of machines
(which includes PowerPC, Dec Alpha, and maybe some others), the CPU
reorders memory accesses arbitrarily unless you explicitly issue
instructions that enforce synchronization.  You still need to keep the
compiler from moving things around, too.  Alpha is particularly
pernicious, because something like a->b can fetch the pointed-to value
before loading the pointer itself.  This is otherwise known as "we
have basically no cache coherency circuits on this chip at all".  On
these machines, you need to issue an explicit memory barrier
instruction at each sequence point, or just acquire and release a
spinlock.

The Alpha is pretty much unique (thankfully!) in allowing dependent
reads to be reordered. That makes it even weaker than the typical
weak-ordering machine. Since reading a pointer and then dereferencing
it is a pretty reasonable thing to do regularly in RCU code, you
probably don't want to emit barriers in between on architectures where
it's not actually necessary. That argues for another operation that's
defined to be a barrier (mb) on the Alpha but a no-op elsewhere.
Certainly the Linux kernel found it useful to do so
(read_barrier_depends)

Alternatively, one might question how important it is to support the
Alpha these days...

Well, currently, we do, so we probably don't want to drop support for
that without some careful thought. I searched the archive and found
someone trying to compile 8.3.something on Alpha just a few years ago,
so it's apparently not totally dead yet.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 21, 2011 at 6:43 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

Profiling this combination of patches reveals that there is still some
pretty ugly spinlock contention on sinval's msgNumLock.  And it occurs
to me that on x86, we really don't need this lock ... or
SInvalReadLock ... or a per-backend mutex.  The whole of
SIGetDataEntries() can pretty easily be made lock-free.  The only real
changes that seem to be are needed are (1) to use a 64-bit counter, so
you never need to decrement

On second thought, won't this be inadequate on 32-bit systems, where updating
the 64-bit counter produces two stores?  You must avoid reading it between those
stores.

Now that is a potentially big problem.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jul 21, 2011 at 6:43 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

SIGetDataEntries() can pretty easily be made lock-free. The only real
changes that seem to be are needed are (1) to use a 64-bit counter, so
you never need to decrement

On second thought, won't this be inadequate on 32-bit systems, where updating
the 64-bit counter produces two stores? You must avoid reading it between those stores.

Now that is a potentially big problem.

Could we do something similar to the xxid hacks? That is, we have a lot
of counters that should be fairly close to each other, so we store only
the low-order 32 bits of each notional value, and separately maintain a
common high-order word. You probably would need some additional
overhead each time the high-order word bumps, but that's reasonably
infrequent.

regards, tom lane

On Thu, Jul 21, 2011 at 9:19 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Thu, Jul 21, 2011 at 6:43 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Wed, Jul 20, 2011 at 09:46:33PM -0400, Robert Haas wrote:

SIGetDataEntries() can pretty easily be made lock-free.  The only real
changes that seem to be are needed are (1) to use a 64-bit counter, so
you never need to decrement

On second thought, won't this be inadequate on 32-bit systems, where updating
the 64-bit counter produces two stores?  You must avoid reading it between those stores.

Now that is a potentially big problem.

Could we do something similar to the xxid hacks?  That is, we have a lot
of counters that should be fairly close to each other, so we store only
the low-order 32 bits of each notional value, and separately maintain a
common high-order word.  You probably would need some additional
overhead each time the high-order word bumps, but that's reasonably
infrequent.

Well, the trouble is figuring out what the shape of that additional
overhead needs to look like. I think I have a simpler idea, though:
before acquiring any locks, just have SIGetDataEntries() do this:

+       if (stateP->nextMsgNum == segP->maxMsgNum && !stateP->resetState)
+               return 0;

Patch (with comment explaining why I think this is OK) attached. If
the message numbers happen to be equal only because the counter has
wrapped, then stateP->resetState will be true, so we'll still realize
we need to do some work.

Test results, with the lazy vxid patch plus this patch, at 8 clients:

tps = 34028.144439 (including connections establishing)
tps = 34079.085935 (including connections establishing)
tps = 34125.295938 (including connections establishing)

And at 32 clients:

tps = 185521.605364 (including connections establishing)
tps = 188250.700451 (including connections establishing)
tps = 186077.847215 (including connections establishing)

And at 80 clients:

tps = 188568.886569 (including connections establishing)
tps = 191035.971512 (including connections establishing)
tps = 189363.019377 (including connections establishing)

Not quite as good as the unlocked version, but better than the
per-backend mutex, and a whole lot simpler.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 21, 2011 at 11:37:27PM -0400, Robert Haas wrote:

I think I have a simpler idea, though:
before acquiring any locks, just have SIGetDataEntries() do this:

+       if (stateP->nextMsgNum == segP->maxMsgNum && !stateP->resetState)
+               return 0;

Patch (with comment explaining why I think this is OK) attached. If
the message numbers happen to be equal only because the counter has
wrapped, then stateP->resetState will be true, so we'll still realize
we need to do some work.

This is attractive, and I don't see any problems with it. (In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match. Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

+1 for doing this and moving on.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Fri, Jul 22, 2011 at 3:28 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Thu, Jul 21, 2011 at 11:37:27PM -0400, Robert Haas wrote:

I think I have a simpler idea, though:
before acquiring any locks, just have SIGetDataEntries() do this:

+       if (stateP->nextMsgNum == segP->maxMsgNum && !stateP->resetState)
+               return 0;

Patch (with comment explaining why I think this is OK) attached.  If
the message numbers happen to be equal only because the counter has
wrapped, then stateP->resetState will be true, so we'll still realize
we need to do some work.

This is attractive, and I don't see any problems with it.  (In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match.  Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

It's actually 262,144 times as long - see MSGNUMWRAPAROUND.

It would be pretty easy to eliminate even the theoretical possibility
of a race by getting rid of resetState altogether and using nextMsgNum
= -1 to mean that. Maybe I should go ahead and do that.

+1 for doing this and moving on.

Yeah, I think I'll go ahead and commit something along these lines if
no one objects. We can always fine-tune it more if needed (but it
probably isn't).

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Fri, Jul 22, 2011 at 03:54:03PM -0400, Robert Haas wrote:

On Fri, Jul 22, 2011 at 3:28 PM, Noah Misch <noah@2ndquadrant.com> wrote:

This is attractive, and I don't see any problems with it. �(In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match. �Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

It's actually 262,144 times as long - see MSGNUMWRAPAROUND.

Ah, so it is.

It would be pretty easy to eliminate even the theoretical possibility
of a race by getting rid of resetState altogether and using nextMsgNum
= -1 to mean that. Maybe I should go ahead and do that.

Seems like a nice simplification.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Jul 25, 2011 at 6:24 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Fri, Jul 22, 2011 at 03:54:03PM -0400, Robert Haas wrote:

On Fri, Jul 22, 2011 at 3:28 PM, Noah Misch <noah@2ndquadrant.com> wrote:

This is attractive, and I don't see any problems with it.  (In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match.  Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

It's actually 262,144 times as long - see MSGNUMWRAPAROUND.

Ah, so it is.

It would be pretty easy to eliminate even the theoretical possibility
of a race by getting rid of resetState altogether and using nextMsgNum
= -1 to mean that.  Maybe I should go ahead and do that.

Seems like a nice simplification.

On further reflection, I don't see that this helps: it just moves the
problem around. With resetState as a separate variable, nextMsgNum is
never changed by anyone other than the owner, so we can never have a
stale load. But if we overload nextMsgNum to also indicate whether
our state has been reset, then there's a race between when we load
nextMsgNum and when we load maxMsgNum (instead of code I posted
previously, which has a race between when we load resetState and when
we load maxMsgNum). Now, as you say, it seems really, really
difficult to hit that in practice, but I don't see a way of getting
rid of the theoretical possibility without either (1) a spinlock or
(2) a fence. (Of course, on x86, the fence could be optimized down to
a compiler barrier.) I guess the question is "should we worry about
that?".

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

On further reflection, I don't see that this helps: it just moves the
problem around. With resetState as a separate variable, nextMsgNum is
never changed by anyone other than the owner, so we can never have a
stale load. But if we overload nextMsgNum to also indicate whether
our state has been reset, then there's a race between when we load
nextMsgNum and when we load maxMsgNum (instead of code I posted
previously, which has a race between when we load resetState and when
we load maxMsgNum). Now, as you say, it seems really, really
difficult to hit that in practice, but I don't see a way of getting
rid of the theoretical possibility without either (1) a spinlock or
(2) a fence. (Of course, on x86, the fence could be optimized down to
a compiler barrier.) I guess the question is "should we worry about
that?".

Uh, yes. I've lost count of the number of times I've seen people hit
one-instruction-wide race condition windows, SIGSEGV crash based on
accessing only one byte past the valid data structure, etc etc.
The worst thing about this type of bug is that you can't reproduce the
failure when you try; doesn't mean your users won't see it.

regards, tom lane

Excerpts from Tom Lane's message of mar jul 26 13:43:08 -0400 2011:

Uh, yes. I've lost count of the number of times I've seen people hit
one-instruction-wide race condition windows, SIGSEGV crash based on
accessing only one byte past the valid data structure, etc etc.

I think you need a better locking protocol on that counter of yours.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Tue, Jul 26, 2011 at 6:36 PM, Robert Haas <robertmhaas@gmail.com> wrote:

Now, as you say, it seems really, really
difficult to hit that in practice, but I don't see a way of getting
rid of the theoretical possibility without either (1) a spinlock or
(2) a fence.  (Of course, on x86, the fence could be optimized down to
a compiler barrier.)  I guess the question is "should we worry about
that?".

Perhaps the answer lies in a different direction altogether?

Let me ask a few questions to stimulate a different solution

* Can we do this using an active technique (e.g. signals) rather than
a passive one (reading a counter?)

* Can we partition the sinval lock, so we have multiple copies? That
increases the task for those who trigger an invalidation, but will
relieve the pressure for most readers.

* Can we put the sinval info in a different place? e.g. inside each
lock partition.

* Why do we have a different mechanism for cache invalidation
internally (sinval) to the one we offer externally (LISTEN/NOTIFY)?
Why don't we have just one?

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Excerpts from Simon Riggs's message of mar jul 26 14:11:19 -0400 2011:

Let me ask a few questions to stimulate a different solution

* Can we do this using an active technique (e.g. signals) rather than
a passive one (reading a counter?)

Signals are already in use for special cases (queue is full), and I
think going through the kernel to achieve much more will lower
performance significantly.

* Can we partition the sinval lock, so we have multiple copies? That
increases the task for those who trigger an invalidation, but will
relieve the pressure for most readers.

Not sure there's a way to meaningfully partition the queue. In any
case, I think the problem being dealt with here is how to update the
read heads of the queue, not its contents.

* Can we put the sinval info in a different place? e.g. inside each
lock partition.

I don't think you can relate sinval messages to particular locks, which
would make this infeasible. I think this bit is directly related to the
point above.

* Why do we have a different mechanism for cache invalidation
internally (sinval) to the one we offer externally (LISTEN/NOTIFY)?
Why don't we have just one?

Performance. Not sure there are other reasons as well; but just this
one is significant enough.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Tue, Jul 26, 2011 at 7:24 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Excerpts from Simon Riggs's message of mar jul 26 14:11:19 -0400 2011:

Let me ask a few questions to stimulate a different solution

* Can we do this using an active technique (e.g. signals) rather than
a passive one (reading a counter?)

Signals are already in use for special cases (queue is full), and I
think going through the kernel to achieve much more will lower
performance significantly.

If there are no invalidations, there would be no signals. How would
zero signals decrease performance?

* Can we partition the sinval lock, so we have multiple copies? That
increases the task for those who trigger an invalidation, but will
relieve the pressure for most readers.

Not sure there's a way to meaningfully partition the queue.  In any
case, I think the problem being dealt with here is how to update the
read heads of the queue, not its contents.

I agree there's no meaningful way to partition the queue, but we can
store the information in more than one place to reduce the contention
of people requesting it.

Both those ideas are still on the table.

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Jul 26, 2011 at 2:56 PM, Simon Riggs <simon@2ndquadrant.com> wrote:

On Tue, Jul 26, 2011 at 7:24 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Excerpts from Simon Riggs's message of mar jul 26 14:11:19 -0400 2011:

Let me ask a few questions to stimulate a different solution

* Can we do this using an active technique (e.g. signals) rather than
a passive one (reading a counter?)

Signals are already in use for special cases (queue is full), and I
think going through the kernel to achieve much more will lower
performance significantly.

If there are no invalidations, there would be no signals. How would
zero signals decrease performance?

It wouldn't, although it might be bad in the case where there are lots
of temp tables being created and dropped. I think the biggest problem
with signals is that they don't provide any meaningful synchronization
guarantees. When you send somebody a signal, you don't really know
how long it's going to take for them to receive it.

* Can we partition the sinval lock, so we have multiple copies? That
increases the task for those who trigger an invalidation, but will
relieve the pressure for most readers.

Not sure there's a way to meaningfully partition the queue.  In any
case, I think the problem being dealt with here is how to update the
read heads of the queue, not its contents.

I agree there's no meaningful way to partition the queue, but we can
store the information in more than one place to reduce the contention
of people requesting it.

I thought about that. Basically, that saves you a factor of N in
contention on the read side (where N is the number of copies) and
costs you a factor of N on the write side (you have to update N
copies, taking a spinlock or lwlock for each). In the limit, you
could do one copy of the counter per backend.

I think, though, that a lock-free implementation using memory barriers
is going to end up being the only real solution. We might possibly
convince ourselves that we're OK with increasing the cost of
SIInsertDataEntries(), but any solution that involves replication the
data is still based on doing at least some locking. And I am pretty
well convinced that even one spinlock acquisition in
SIInsertDataEntries() is too many.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jul 26, 2011 at 8:11 PM, Robert Haas <robertmhaas@gmail.com> wrote:

It wouldn't, although it might be bad in the case where there are lots
of temp tables being created and dropped.

Do temp tables cause relcache invalidations?

That seems like something we'd want to change in itself.

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:

On Tue, Jul 26, 2011 at 7:24 PM, Alvaro Herrera
<alvherre@commandprompt.com> wrote:

Signals are already in use for special cases (queue is full), and I
think going through the kernel to achieve much more will lower
performance significantly.

If there are no invalidations, there would be no signals. How would
zero signals decrease performance?

But if there *is* an invalidation (which is not a negligible case),
it'd get significantly slower.

regards, tom lane

On Tue, Jul 26, 2011 at 8:11 PM, Robert Haas <robertmhaas@gmail.com> wrote:

* Can we partition the sinval lock, so we have multiple copies? That
increases the task for those who trigger an invalidation, but will
relieve the pressure for most readers.

Not sure there's a way to meaningfully partition the queue.  In any
case, I think the problem being dealt with here is how to update the
read heads of the queue, not its contents.

I agree there's no meaningful way to partition the queue, but we can
store the information in more than one place to reduce the contention
of people requesting it.

I thought about that.  Basically, that saves you a factor of N in
contention on the read side (where N is the number of copies) and
costs you a factor of N on the write side (you have to update N
copies, taking a spinlock or lwlock for each).  In the limit, you
could do one copy of the counter per backend.

I think, though, that a lock-free implementation using memory barriers
is going to end up being the only real solution.  We might possibly
convince ourselves that we're OK with increasing the cost of
SIInsertDataEntries(), but any solution that involves replication the
data is still based on doing at least some locking.  And I am pretty
well convinced that even one spinlock acquisition in
SIInsertDataEntries() is too many.

You might be right, but I think we have little knowledge of how some
memory barrier code you haven't written yet effects performance on
various architectures.

A spinlock per backend would cache very nicely, now you mention it. So
my money would be on the multiple copies.

It's not completely clear to me that updating N copies would be more
expensive. Accessing N low contention copies rather than 1
high-contention value might actually be a win.

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Noah Misch <noah@2ndQuadrant.com> writes:

On Thu, Jul 21, 2011 at 11:37:27PM -0400, Robert Haas wrote:

I think I have a simpler idea, though:
before acquiring any locks, just have SIGetDataEntries() do this:

+       if (stateP->nextMsgNum == segP->maxMsgNum && !stateP->resetState)
+               return 0;

Patch (with comment explaining why I think this is OK) attached. If
the message numbers happen to be equal only because the counter has
wrapped, then stateP->resetState will be true, so we'll still realize
we need to do some work.

This is attractive, and I don't see any problems with it. (In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match. Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

+1 for doing this and moving on.

After some further reflection I believe this patch actually is pretty
safe, although Noah's explanation of why seems a bit confused. The key
points are that (1) each of the reads is atomic, and (2) we should not
be able to see a value that is older than our last acquisition/release
of a shared memory lock. These being granted, we will make a decision
that is correct, or at least was correct as of some time after that last
lock action. As stated in the patch comments, we are not required to
promptly assimilate sinval actions on objects we don't hold any lock on,
so this seems sufficient. In essence, we are relying on an assumed
prior visit to the lock manager to provide memory access synchronization
for the sinval no-work-to-do test.

The case Noah speculates about above amounts to supposing that this
reasoning fails to hold for the resetState value, and I don't see why
that would be true. Even if the above scenario did manage to happen,
it would not mean that we missed the reset, just that we hadn't noticed
it *yet*. And by hypothesis, none of the as-yet-not-seen catalog
updates are a problem for us.

BTW, the patch really ought to add something to the comment around
line 100.

regards, tom lane

On Tue, Jul 26, 2011 at 03:40:32PM -0400, Tom Lane wrote:

Noah Misch <noah@2ndQuadrant.com> writes:

On Thu, Jul 21, 2011 at 11:37:27PM -0400, Robert Haas wrote:

I think I have a simpler idea, though:
before acquiring any locks, just have SIGetDataEntries() do this:

+       if (stateP->nextMsgNum == segP->maxMsgNum && !stateP->resetState)
+               return 0;

Patch (with comment explaining why I think this is OK) attached. If
the message numbers happen to be equal only because the counter has
wrapped, then stateP->resetState will be true, so we'll still realize
we need to do some work.

This is attractive, and I don't see any problems with it. (In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match. Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

+1 for doing this and moving on.

After some further reflection I believe this patch actually is pretty
safe, although Noah's explanation of why seems a bit confused. The key
points are that (1) each of the reads is atomic, and (2) we should not
be able to see a value that is older than our last acquisition/release
of a shared memory lock. These being granted, we will make a decision
that is correct, or at least was correct as of some time after that last
lock action. As stated in the patch comments, we are not required to
promptly assimilate sinval actions on objects we don't hold any lock on,
so this seems sufficient. In essence, we are relying on an assumed
prior visit to the lock manager to provide memory access synchronization
for the sinval no-work-to-do test.

The case Noah speculates about above amounts to supposing that this
reasoning fails to hold for the resetState value, and I don't see why
that would be true. Even if the above scenario did manage to happen,
it would not mean that we missed the reset, just that we hadn't noticed
it *yet*. And by hypothesis, none of the as-yet-not-seen catalog
updates are a problem for us.

Here's the way it can fail:

1. Backend enters SIGetDataEntries() with main memory bearing stateP->resetState
= false, stateP->nextMsgNum = 500, segP->maxMsgNum = 505. The CPU has those
latest stateP values in cache, but segP->maxMsgNum is *not* in cache.
2. Backend stalls for <long time>. Meanwhile, other backends issue
MSGNUMWRAPAROUND - 5 invalidation messages. Main memory bears
stateP->resetState = true, stateP->nextMsgNum = 500 - MSGNUMWRAPAROUND,
segP->maxMsgNum = 500.
3. Backend wakes up, uses its cached stateP values and reads segP->maxMsgNum =
500 from main memory. The patch's test finds no need to reset or process
invalidation messages.

That's the theoretical risk I wished to illustrate. Though this appears
possible on an abstract x86_64 system, I think it's unrealistic to suppose that
a dirty cache line could persist *throughout* the issuance of more than 10^9
invalidation messages on a concrete implementation.

A way to think about the problem is that our read of segP->maxMsgNum is too new.
If we had used a snapshot of values as of the most recent lock
acquisition/release, there would be no problem. It's the mix of a new-enough
stateP with an all-too-new segP that yields the anomaly.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Jul 26, 2011 at 01:36:26PM -0400, Robert Haas wrote:

On Mon, Jul 25, 2011 at 6:24 PM, Noah Misch <noah@2ndquadrant.com> wrote:

On Fri, Jul 22, 2011 at 03:54:03PM -0400, Robert Haas wrote:

On Fri, Jul 22, 2011 at 3:28 PM, Noah Misch <noah@2ndquadrant.com> wrote:

This is attractive, and I don't see any problems with it. �(In theory, you could
hit a case where the load of resetState gives an ancient "false" just as the
counters wrap to match. �Given that the wrap interval is 1000000x as long as the
reset interval, I'm not worried about problems on actual silicon.)

It's actually 262,144 times as long - see MSGNUMWRAPAROUND.

Ah, so it is.

It would be pretty easy to eliminate even the theoretical possibility
of a race by getting rid of resetState altogether and using nextMsgNum
= -1 to mean that. �Maybe I should go ahead and do that.

Seems like a nice simplification.

On further reflection, I don't see that this helps: it just moves the
problem around.

Alas, yes.

With resetState as a separate variable, nextMsgNum is
never changed by anyone other than the owner, so we can never have a
stale load.

It's also changed when SICleanupQueue() decides to wrap everyone. This could
probably be eliminated by using uint32 and letting overflow take care of wrap
implicitly, but ...

But if we overload nextMsgNum to also indicate whether
our state has been reset, then there's a race between when we load
nextMsgNum and when we load maxMsgNum (instead of code I posted
previously, which has a race between when we load resetState and when
we load maxMsgNum). Now, as you say, it seems really, really
difficult to hit that in practice, but I don't see a way of getting
rid of the theoretical possibility without either (1) a spinlock or
(2) a fence. (Of course, on x86, the fence could be optimized down to
a compiler barrier.)

No new ideas come to mind, here. We could migrate back toward your original
proposal of making the counter a non-wrapping uint64; Florian described some
nice techniques for doing atomic 64-bit reads on x86:

http://archives.postgresql.org/message-id/7C94C386-122F-4918-8624-A14352E8DBC5@phlo.org

I'm not personally acquainted with those approaches, but they sound promising.
Since the overlap between 32-bit installations and performance-sensitive
installations is all but gone, we could even just use a spinlock under 32-bit.

I guess the question is "should we worry about that?".

I'd lean toward "no". I share Tom's unease about writing off a race condition
as being too improbable, but this is quite exceptionally improbable. On the
other hand, some of the fixes don't look too invasive.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Noah Misch <noah@2ndQuadrant.com> writes:

On Tue, Jul 26, 2011 at 03:40:32PM -0400, Tom Lane wrote:

After some further reflection I believe this patch actually is pretty
safe, although Noah's explanation of why seems a bit confused.

Here's the way it can fail:

1. Backend enters SIGetDataEntries() with main memory bearing stateP->resetState
= false, stateP->nextMsgNum = 500, segP->maxMsgNum = 505. The CPU has those
latest stateP values in cache, but segP->maxMsgNum is *not* in cache.
2. Backend stalls for <long time>. Meanwhile, other backends issue
MSGNUMWRAPAROUND - 5 invalidation messages. Main memory bears
stateP->resetState = true, stateP->nextMsgNum = 500 - MSGNUMWRAPAROUND,
segP->maxMsgNum = 500.
3. Backend wakes up, uses its cached stateP values and reads segP->maxMsgNum =
500 from main memory. The patch's test finds no need to reset or process
invalidation messages.

[ squint... ] Hmm, you're right. The case where this would break
things is if (some of) the five unprocessed messages relate to some
object we've just locked. But the initial state you describe would be
valid right after obtaining such a lock.

That's the theoretical risk I wished to illustrate. Though this appears
possible on an abstract x86_64 system, I think it's unrealistic to suppose that
a dirty cache line could persist *throughout* the issuance of more than 10^9
invalidation messages on a concrete implementation.

Dirty cache line, maybe not, but what if the assembly code commands the
CPU to load those variables into CPU registers before doing the
comparison? If they're loaded with maxMsgNum coming in last (or at
least after resetState), I think you can have the problem without any
assumptions about cache line behavior at all. You just need the process
to lose the CPU at the right time.

If we marked the pointers volatile, we could probably ensure that the
assembly code tests resetState last, but that's not sufficient to avoid
the stale-cache-line risk.

regards, tom lane

On Tue, Jul 26, 2011 at 05:05:15PM -0400, Tom Lane wrote:

Noah Misch <noah@2ndQuadrant.com> writes:

That's the theoretical risk I wished to illustrate. Though this appears
possible on an abstract x86_64 system, I think it's unrealistic to suppose that
a dirty cache line could persist *throughout* the issuance of more than 10^9
invalidation messages on a concrete implementation.

Dirty cache line, maybe not, but what if the assembly code commands the
CPU to load those variables into CPU registers before doing the
comparison? If they're loaded with maxMsgNum coming in last (or at
least after resetState), I think you can have the problem without any
assumptions about cache line behavior at all. You just need the process
to lose the CPU at the right time.

True. If the compiler places the resetState load first, you could hit the
anomaly by "merely" setting a breakpoint on the next instruction, waiting for
exactly MSGNUMWRAPAROUND messages to enqueue, and letting the backend continue.
I think, though, we should either plug that _and_ the cache incoherency case or
worry about neither.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Noah Misch <noah@2ndQuadrant.com> writes:

On Tue, Jul 26, 2011 at 05:05:15PM -0400, Tom Lane wrote:

Dirty cache line, maybe not, but what if the assembly code commands the
CPU to load those variables into CPU registers before doing the
comparison? If they're loaded with maxMsgNum coming in last (or at
least after resetState), I think you can have the problem without any
assumptions about cache line behavior at all. You just need the process
to lose the CPU at the right time.

True. If the compiler places the resetState load first, you could hit the
anomaly by "merely" setting a breakpoint on the next instruction, waiting for
exactly MSGNUMWRAPAROUND messages to enqueue, and letting the backend continue.
I think, though, we should either plug that _and_ the cache incoherency case or
worry about neither.

How do you figure that? The poor-assembly-code-order risk is both a lot
easier to fix and a lot higher probability. Admittedly, it's still way
way down there, but you only need a precisely-timed sleep, not a
precisely-timed sleep *and* a cache line that somehow remained stale.

regards, tom lane

On Tue, Jul 26, 2011 at 3:34 PM, Simon Riggs <simon@2ndquadrant.com> wrote:

You might be right, but I think we have little knowledge of how some
memory barrier code you haven't written yet effects performance on
various architectures.

A spinlock per backend would cache very nicely, now you mention it. So
my money would be on the multiple copies.

Maybe so, but you can see from the numbers in my OP that the results
still leave something to be desired.

It's not completely clear to me that updating N copies would be more
expensive. Accessing N low contention copies rather than 1
high-contention value might actually be a win.

Yeah, I haven't tested that approach.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jul 26, 2011 at 3:25 PM, Simon Riggs <simon@2ndquadrant.com> wrote:

On Tue, Jul 26, 2011 at 8:11 PM, Robert Haas <robertmhaas@gmail.com> wrote:

It wouldn't, although it might be bad in the case where there are lots
of temp tables being created and dropped.

Do temp tables cause relcache invalidations?

That seems like something we'd want to change in itself.

I agree. Unfortunately, I think it's a non-trivial fix.

I've also been wondering if we could avoid taking an
AccessExclusiveLock on a newly created (temporary?) table. It seems
like no one should be able to see it until commit, at which point we'd
be releasing the lock anyway.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jul 26, 2011 at 4:38 PM, Noah Misch <noah@2ndquadrant.com> wrote:

No new ideas come to mind, here.

OK, I have a new idea. :-)

1. Add a new flag to each procState called something like "timeToPayAttention".
2. Each call to SIGetDataEntries() iterates over all the ProcStates
whose index is < lastBackend and sets stateP->timeToPayAttention =
TRUE for each.
3. At the beginning of SIGetDataEntries(), we do an unlocked if
(!stateP->timeToPayAttention) return 0.
4. Immediately following that if statement and before acquiring any
locks, we set stateP->timeToPayAttention = FALSE.

The LWLockRelease() in SIGetDataEntries() will be sufficient to force
all of the stateP->timeToPayAttention writes out to main memory, and
the read side is OK because we either just took a lock (which acted as
a fence) or else there's a race anyway. But unlike my previous
proposal, it doesn't involve *comparing* anything. We needn't worry
about whether we could read two different values that are through
great misfortune out of sync because we're only reading one value.

If, by chance, the value is set to true just after we set it to false,
that won't mess us up either: we'll still read all the messages after
acquiring the lock.

Now, there's some downside to this approach - it involves doing O(N)
work for each invalidation message we receive. But as long as it's
only O(N) stores and not O(N) lock acquisitions and releases, I think
that might be OK.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jul 26, 2011 at 06:04:16PM -0400, Tom Lane wrote:

Noah Misch <noah@2ndQuadrant.com> writes:

On Tue, Jul 26, 2011 at 05:05:15PM -0400, Tom Lane wrote:

Dirty cache line, maybe not, but what if the assembly code commands the
CPU to load those variables into CPU registers before doing the
comparison? If they're loaded with maxMsgNum coming in last (or at
least after resetState), I think you can have the problem without any
assumptions about cache line behavior at all. You just need the process
to lose the CPU at the right time.

True. If the compiler places the resetState load first, you could hit the
anomaly by "merely" setting a breakpoint on the next instruction, waiting for
exactly MSGNUMWRAPAROUND messages to enqueue, and letting the backend continue.
I think, though, we should either plug that _and_ the cache incoherency case or
worry about neither.

How do you figure that? The poor-assembly-code-order risk is both a lot
easier to fix and a lot higher probability. Admittedly, it's still way
way down there, but you only need a precisely-timed sleep, not a
precisely-timed sleep *and* a cache line that somehow remained stale.

I think both probabilities are too low to usefully distinguish. An sinval
wraparound takes a long time even in a deliberate test setup: almost 30 hours @
10k messages/sec. To get a backend to sleep that long, you'll probably need
something like SIGSTOP or a debugger attach. The sleep has to fall within the
space of no more than a few instructions. Then, you'd need to release the
process at the exact moment for it to observe wrapped equality. In other words,
you get one split-millisecond opportunity every 30 hours of process sleep time.
If your backends don't have multi-hour sleeps, it can't ever happen.

Even so, all the better if we settle on an approach that has neither hazard.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Jul 26, 2011 at 9:57 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Tue, Jul 26, 2011 at 4:38 PM, Noah Misch <noah@2ndquadrant.com> wrote:

No new ideas come to mind, here.

OK, I have a new idea.  :-)

1. Add a new flag to each procState called something like "timeToPayAttention".
2. Each call to SIGetDataEntries() iterates over all the ProcStates
whose index is < lastBackend and sets stateP->timeToPayAttention =
TRUE for each.
3. At the beginning of SIGetDataEntries(), we do an unlocked if
(!stateP->timeToPayAttention) return 0.
4. Immediately following that if statement and before acquiring any
locks, we set stateP->timeToPayAttention = FALSE.

The LWLockRelease() in SIGetDataEntries() will be sufficient to force
all of the stateP->timeToPayAttention writes out to main memory, and
the read side is OK because we either just took a lock (which acted as
a fence) or else there's a race anyway.  But unlike my previous
proposal, it doesn't involve *comparing* anything.  We needn't worry
about whether we could read two different values that are through
great misfortune out of sync because we're only reading one value.

If, by chance, the value is set to true just after we set it to false,
that won't mess us up either: we'll still read all the messages after
acquiring the lock.

There turned out to be a little bit of further subtlety to this, but
it seems to work. Patch attached.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

On Tue, Jul 26, 2011 at 9:57 PM, Robert Haas <robertmhaas@gmail.com> wrote:

1. Add a new flag to each procState called something like "timeToPayAttention".
2. Each call to SIGetDataEntries() iterates over all the ProcStates
whose index is < lastBackend and sets stateP->timeToPayAttention =
TRUE for each.
3. At the beginning of SIGetDataEntries(), we do an unlocked if
(!stateP->timeToPayAttention) return 0.
4. Immediately following that if statement and before acquiring any
locks, we set stateP->timeToPayAttention = FALSE.

There turned out to be a little bit of further subtlety to this, but
it seems to work. Patch attached.

And?

It didn't sound to me like this could possibly be a performance win,
but I await some numbers ...

regards, tom lane

Robert Haas <robertmhaas@gmail.com> wrote:

There turned out to be a little bit of further subtlety to this,
but it seems to work. Patch attached.

Stylistic question: Why is stateP->hasMessages set to false in one
place and FALSE and TRUE in others? It seems like it would be less
confusing to be consistent.

A quick count of the usage of both forms in the PostgreSQL source
codes shows the lowercase is used about 10 times more often:

kgrittn@kgrittn-desktop:~/git/postgresql/kgrittn$ find -name '*.h'
-or -name '*.c' | egrep -v '/tmp_check/' | xargs cat | egrep -c
'\b(FALSE|TRUE)\b'
1670

kgrittn@kgrittn-desktop:~/git/postgresql/kgrittn$ find -name '*.h'
-or -name '*.c' | egrep -v '/tmp_check/' | xargs cat | egrep -c
'\b(false|true)\b'
17349

-Kevin

On Wed, Jul 27, 2011 at 12:34 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

On Tue, Jul 26, 2011 at 9:57 PM, Robert Haas <robertmhaas@gmail.com> wrote:

1. Add a new flag to each procState called something like "timeToPayAttention".
2. Each call to SIGetDataEntries() iterates over all the ProcStates
whose index is < lastBackend and sets stateP->timeToPayAttention =
TRUE for each.
3. At the beginning of SIGetDataEntries(), we do an unlocked if
(!stateP->timeToPayAttention) return 0.
4. Immediately following that if statement and before acquiring any
locks, we set stateP->timeToPayAttention = FALSE.

There turned out to be a little bit of further subtlety to this, but
it seems to work.  Patch attached.

And?

It didn't sound to me like this could possibly be a performance win,
but I await some numbers ...

On master, with the patch, scale factor 100, pgbench -S -c $CLIENTS -j
$CLIENTS -T 300 results for different client counts, on a 32-core
machine with 128GB RAM, shared_buffers = 8GB:

01 tps = 4444.280459 (including connections establishing)
01 tps = 4438.365576 (including connections establishing)
01 tps = 4423.718466 (including connections establishing)
08 tps = 33187.827872 (including connections establishing)
08 tps = 33288.247330 (including connections establishing)
08 tps = 33304.307835 (including connections establishing)
32 tps = 178876.350559 (including connections establishing)
32 tps = 177293.082295 (including connections establishing)
32 tps = 175577.058885 (including connections establishing)
80 tps = 159202.449993 (including connections establishing)
80 tps = 151541.717088 (including connections establishing)
80 tps = 150454.658132 (including connections establishing)

Without the patch:

01 tps = 4447.660101 (including connections establishing)
01 tps = 4440.830713 (including connections establishing)
01 tps = 4411.610348 (including connections establishing)
08 tps = 33135.773476 (including connections establishing)
08 tps = 33365.387051 (including connections establishing)
08 tps = 33364.859705 (including connections establishing)
32 tps = 175834.280471 (including connections establishing)
32 tps = 176713.118271 (including connections establishing)
32 tps = 176830.687087 (including connections establishing)
80 tps = 135211.036587 (including connections establishing)
80 tps = 130642.264016 (including connections establishing)
80 tps = 133621.549513 (including connections establishing)

I'm fairly certain the results will be even more dramatic with the
lazy-vxid patch applied, since master still has to fight with the lock
manager on this workload. I haven't tested that yet, but there's not
much reason to suppose that the results will be dramatically different
from any of the other methods of reducing the sinval overhead that
I've benchmarked, many of which I've already posted about. See, for
example, the OP on this thread.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Jul 26, 2011 at 09:57:10PM -0400, Robert Haas wrote:

On Tue, Jul 26, 2011 at 4:38 PM, Noah Misch <noah@2ndquadrant.com> wrote:

No new ideas come to mind, here.

OK, I have a new idea. :-)

1. Add a new flag to each procState called something like "timeToPayAttention".
2. Each call to SIGetDataEntries() iterates over all the ProcStates
whose index is < lastBackend and sets stateP->timeToPayAttention =
TRUE for each.
3. At the beginning of SIGetDataEntries(), we do an unlocked if
(!stateP->timeToPayAttention) return 0.
4. Immediately following that if statement and before acquiring any
locks, we set stateP->timeToPayAttention = FALSE.

The LWLockRelease() in SIGetDataEntries() will be sufficient to force
all of the stateP->timeToPayAttention writes out to main memory, and
the read side is OK because we either just took a lock (which acted as
a fence) or else there's a race anyway. But unlike my previous
proposal, it doesn't involve *comparing* anything. We needn't worry
about whether we could read two different values that are through
great misfortune out of sync because we're only reading one value.

If, by chance, the value is set to true just after we set it to false,
that won't mess us up either: we'll still read all the messages after
acquiring the lock.

This approach would work if a spinlock release constrained the global stores
timeline. It makes a weaker guarantee: all stores preceding the lock release
in program order will precede it globally. Consequently, no processor will
observe the spinlock to be available without also observing all stores made by
the last holding processor before that processor released it. That guarantee
is not enough for this sequence of events:

Backend 0:
add a message for table "a"
store 5 => maxMsgNum
store true => timeToPayAttention
LWLockRelease(SInvalWriteLock)
<plenty of time passes>
Backend 2:
LOCK TABLE a;
load timeToPayAttention => true
Backend 1:
add a message for table "b"
store 6 => maxMsgNum
SpinLockRelease(&vsegP->msgnumLock);
store true => timeToPayAttention
Backend 2:
store false => timeToPayAttention
LWLockAcquire(SInvalReadLock, LW_SHARED)
load maxMsgNum => 5 [!]
Backend 1:
LWLockRelease(SInvalWriteLock);
Backend 2:
LOCK TABLE b;
load timeToPayAttention => false
<use b without processing updates>

The "SpinLockRelease(&vsegP->msgnumLock)" guarantees that any process
observing the backend 2 store of timeToPayAttention will also observe
maxMsgNum = 6. However, nothing constrains which timeToPayAttention store
will "win" in main memory. Backend 1 can observe neither update from backend
2, yet still have its store appear later than the backend 1 stores in the
global timeline.

Now, there's some downside to this approach - it involves doing O(N)
work for each invalidation message we receive. But as long as it's
only O(N) stores and not O(N) lock acquisitions and releases, I think
that might be OK.

I think a benchmark is in order, something like 900 idle connections and 80
connections running small transactions that create a few temporary tables. If
that shows no statistically significant regression, then we're probably fine
here. I'm not sure what result to expect, honestly.

What did you think of making the message number a uint64, removing wraparound
handling, and retaining SISeg.msgnumLock for 32-bit only? You could isolate the
variant logic in READ_MSGNUM and WRITE_MSGNUM macros.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Wed, Jul 27, 2011 at 12:55 PM, Noah Misch <noah@2ndquadrant.com> wrote:

This approach would work if a spinlock release constrained the global stores
timeline.  It makes a weaker guarantee: all stores preceding the lock release
in program order will precede it globally.  Consequently, no processor will
observe the spinlock to be available without also observing all stores made by
the last holding processor before that processor released it.  That guarantee
is not enough for this sequence of events:

Backend 0:
       add a message for table "a"
       store 5 => maxMsgNum
       store true => timeToPayAttention
       LWLockRelease(SInvalWriteLock)
<plenty of time passes>
Backend 2:
       LOCK TABLE a;
       load timeToPayAttention => true
Backend 1:
       add a message for table "b"
       store 6 => maxMsgNum
       SpinLockRelease(&vsegP->msgnumLock);
       store true => timeToPayAttention
Backend 2:
       store false => timeToPayAttention
       LWLockAcquire(SInvalReadLock, LW_SHARED)
       load maxMsgNum => 5 [!]

Eh, how can this possibly happen? You have to hold msgNumLock to to
set maxMsgNum and msgNumLock to read maxMsgNum. If that's not enough
to guarantee that we never read a stale value, what is?

I think a benchmark is in order, something like 900 idle connections and 80
connections running small transactions that create a few temporary tables.  If
that shows no statistically significant regression, then we're probably fine
here.  I'm not sure what result to expect, honestly.

That's setting the bar pretty high. I don't mind doing the
experiment, but I'm not sure that's the case we should be optimizing
for.

What did you think of making the message number a uint64, removing wraparound
handling, and retaining SISeg.msgnumLock for 32-bit only?  You could isolate the
variant logic in READ_MSGNUM and WRITE_MSGNUM macros.

Well, what you really need to know is whether the platform has 8-byte
atomic stores, which doesn't seem trivial to figure out, plus you need
a memory fence. If that's the only method of fixing this problem we
can agree on, I'm willing to work on it, but an
architecture-independent fix would be nicer.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Jul 27, 2011 at 01:30:47PM -0400, Robert Haas wrote:

On Wed, Jul 27, 2011 at 12:55 PM, Noah Misch <noah@2ndquadrant.com> wrote:

[wrong objection]

Eh, how can this possibly happen? You have to hold msgNumLock to to
set maxMsgNum and msgNumLock to read maxMsgNum. If that's not enough
to guarantee that we never read a stale value, what is?

Indeed, my analysis was all wrong.

I think a benchmark is in order, something like 900 idle connections and 80
connections running small transactions that create a few temporary tables. �If
that shows no statistically significant regression, then we're probably fine
here. �I'm not sure what result to expect, honestly.

That's setting the bar pretty high. I don't mind doing the
experiment, but I'm not sure that's the case we should be optimizing
for.

Granted. How about 32 clients running the temporary table transaction, no idle
connections? Given the meager benefit of this patch compared to your previous
version, it would be hard to justify a notable performance drop in return.

What did you think of making the message number a uint64, removing wraparound
handling, and retaining SISeg.msgnumLock for 32-bit only? �You could isolate the
variant logic in READ_MSGNUM and WRITE_MSGNUM macros.

Well, what you really need to know is whether the platform has 8-byte
atomic stores, which doesn't seem trivial to figure out, plus you need
a memory fence. If that's the only method of fixing this problem we
can agree on, I'm willing to work on it, but an
architecture-independent fix would be nicer.

Fair enough.

Thanks,
nm

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Wed, Jul 27, 2011 at 1:58 PM, Noah Misch <noah@2ndquadrant.com> wrote:

I think a benchmark is in order, something like 900 idle connections and 80
connections running small transactions that create a few temporary tables.  If
that shows no statistically significant regression, then we're probably fine
here.  I'm not sure what result to expect, honestly.

That's setting the bar pretty high.  I don't mind doing the
experiment, but I'm not sure that's the case we should be optimizing
for.

Granted.  How about 32 clients running the temporary table transaction, no idle
connections?  Given the meager benefit of this patch compared to your previous
version, it would be hard to justify a notable performance drop in return.

The reason the benefit is smaller is, I believe, because the previous
numbers were generated with the lazy vxid locks patch applied, and
these were generated against master. With the lock manager as a
bottleneck, the sinval stuff doesn't get hit quite as hard, so the
benefit is less. I can regenerate the numbers with the lazy vxid
patch applied; I suspect they'll be similar to what we saw before.
I'll also test out creating and dropping some tables.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Jul 27, 2011 at 2:29 PM, Robert Haas <robertmhaas@gmail.com> wrote:

The reason the benefit is smaller is, I believe, because the previous
numbers were generated with the lazy vxid locks patch applied, and
these were generated against master.  With the lock manager as a
bottleneck, the sinval stuff doesn't get hit quite as hard, so the
benefit is less.  I can regenerate the numbers with the lazy vxid
patch applied; I suspect they'll be similar to what we saw before.

Yep. Here's with both lazy-vxids and sinval-hasmessages;

01 tps = 4470.133776 (including connections establishing)
01 tps = 4471.450650 (including connections establishing)
01 tps = 4490.833194 (including connections establishing)
32 tps = 191416.960956 (including connections establishing)
32 tps = 190653.742400 (including connections establishing)
32 tps = 191832.231458 (including connections establishing)
80 tps = 189348.509378 (including connections establishing)
80 tps = 191080.641878 (including connections establishing)
80 tps = 191366.728275 (including connections establishing)

And with just lazy vxids:

01 tps = 4458.667013 (including connections establishing)
01 tps = 4526.922638 (including connections establishing)
01 tps = 4480.415099 (including connections establishing)
32 tps = 193273.434028 (including connections establishing)
32 tps = 190661.279391 (including connections establishing)
32 tps = 189526.560031 (including connections establishing)
80 tps = 150572.020250 (including connections establishing)
80 tps = 118643.970622 (including connections establishing)
80 tps = 119211.643930 (including connections establishing)

Same select-only, scale-factor-100 pgbench test, same 32 core machine,
as I've been using for my other recent tests.

I'll also test out creating and dropping some tables.

Still need to work on this one.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 28, 2011 at 10:05 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I'll also test out creating and dropping some tables.

Still need to work on this one.

And there results are in. I set up the following sophisticated test
script for pgbench:

CREATE TEMP TABLE foo (a int);
DROP TABLE foo;

And then did 5-minute test runs with varying numbers of clients on
Nate Boley's 32-core machine with (a) master, (b) master +
sinval-hasmessages, (c) master + lazy-vxid, and (d) master + lazy-vxid
+ sinval-hasmessages. I held my breath until the results started
popping out, then felt much better. In the table below, results with
L are with the lazy-vxid patch, S is with the sinval-hasmessages
patch, LS with both, and results with no letters are neither. The
numbers are the client count. Long story short, it seems that the
patch actually makes this test case faster at any client code, though
the improvement at 1 and 8 clients might be in the noise:

01L tps = 514.880290 (including connections establishing)
01L tps = 525.097199 (including connections establishing)
01L tps = 508.319588 (including connections establishing)
08L tps = 1834.259810 (including connections establishing)
08L tps = 1846.846089 (including connections establishing)
08L tps = 1841.402433 (including connections establishing)
32L tps = 1463.822936 (including connections establishing)
32L tps = 1481.169483 (including connections establishing)
32L tps = 1393.780335 (including connections establishing)
80L tps = 1192.768020 (including connections establishing)
80L tps = 1165.545010 (including connections establishing)
80L tps = 1169.776066 (including connections establishing)

01LS tps = 517.624068 (including connections establishing)
01LS tps = 524.507723 (including connections establishing)
01LS tps = 507.847622 (including connections establishing)
08LS tps = 1831.248178 (including connections establishing)
08LS tps = 1873.932133 (including connections establishing)
08LS tps = 1863.048113 (including connections establishing)
32LS tps = 1851.143407 (including connections establishing)
32LS tps = 1754.683356 (including connections establishing)
32LS tps = 1785.926527 (including connections establishing)
80LS tps = 1510.778084 (including connections establishing)
80LS tps = 1484.423486 (including connections establishing)
80LS tps = 1480.692051 (including connections establishing)

01 tps = 511.572832 (including connections establishing)
01 tps = 499.389527 (including connections establishing)
01 tps = 495.697080 (including connections establishing)
08 tps = 1832.762548 (including connections establishing)
08 tps = 1819.884564 (including connections establishing)
08 tps = 1835.608561 (including connections establishing)
32 tps = 1417.168790 (including connections establishing)
32 tps = 1447.478971 (including connections establishing)
32 tps = 1427.489879 (including connections establishing)
80 tps = 1154.272515 (including connections establishing)
80 tps = 1168.805881 (including connections establishing)
80 tps = 1173.971801 (including connections establishing)

01S tps = 519.860218 (including connections establishing)
01S tps = 510.759087 (including connections establishing)
01S tps = 517.159276 (including connections establishing)
08S tps = 1880.179600 (including connections establishing)
08S tps = 1829.693454 (including connections establishing)
08S tps = 1886.168401 (including connections establishing)
32S tps = 1809.950929 (including connections establishing)
32S tps = 1809.474070 (including connections establishing)
32S tps = 1798.620842 (including connections establishing)
80S tps = 1483.037788 (including connections establishing)
80S tps = 1481.059504 (including connections establishing)
80S tps = 1487.215748 (including connections establishing)

So, apparently, the extra work in SIInsertDataEntries() is more than
paid for by the speedup in SIGetDataEntries(). I'm guessing that at
high client counts you win because of reduced spinlock contention, and
at low client counts you still win a little bit because
SIGetDataEntries() is called multiple times per transaction, whereas
SIInsertDataEntries() is only called once. I could be all wet on the
reason, but at any rate the numbers look pretty good.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Thu, Jul 28, 2011 at 03:03:05PM -0400, Robert Haas wrote:

On Thu, Jul 28, 2011 at 10:05 AM, Robert Haas <robertmhaas@gmail.com> wrote:

I'll also test out creating and dropping some tables.

Still need to work on this one.

And there results are in. I set up the following sophisticated test
script for pgbench:

CREATE TEMP TABLE foo (a int);
DROP TABLE foo;

And then did 5-minute test runs with varying numbers of clients on
Nate Boley's 32-core machine with (a) master, (b) master +
sinval-hasmessages, (c) master + lazy-vxid, and (d) master + lazy-vxid
+ sinval-hasmessages.

The comparison I had in mind was (a) master + lazy-vxid + [1]http://archives.postgresql.org/message-id/CA+TgmoZc8Z_JTj44xvpWpXKQt2jGjB5YGCZ3T9u5-QZVdBmyCA@mail.gmail.comsinval-fastpath
vs. (b) master + lazy-vxid + [2]http://archives.postgresql.org/message-id/CA+TgmoZjo1bkP6eX=xOX3aHuPYbmJT9+PKW6qubQzN7sukK3Dg@mail.gmail.comsinval-hasmessages. The only claimed benefit of
[2]: http://archives.postgresql.org/message-id/CA+TgmoZjo1bkP6eX=xOX3aHuPYbmJT9+PKW6qubQzN7sukK3Dg@mail.gmail.com
[3]: http://archives.postgresql.org/message-id/20110727033537.GB18910@tornado.leadboat.com
performance we exchange for its benefit.

I did a bit of (relatively unrigorous) poking at this workload with oprofile,
and I never saw SIInsertDataEntries take more than 0.26% of CPU time. It's
perhaps too cheap relative to the workload's other costs to matter. That's good
enough for me.

[1]: http://archives.postgresql.org/message-id/CA+TgmoZc8Z_JTj44xvpWpXKQt2jGjB5YGCZ3T9u5-QZVdBmyCA@mail.gmail.com
[2]: http://archives.postgresql.org/message-id/CA+TgmoZjo1bkP6eX=xOX3aHuPYbmJT9+PKW6qubQzN7sukK3Dg@mail.gmail.com
[3]: http://archives.postgresql.org/message-id/20110727033537.GB18910@tornado.leadboat.com

80L tps = 1192.768020 (including connections establishing)
80L tps = 1165.545010 (including connections establishing)
80L tps = 1169.776066 (including connections establishing)

80LS tps = 1510.778084 (including connections establishing)
80LS tps = 1484.423486 (including connections establishing)
80LS tps = 1480.692051 (including connections establishing)

80 tps = 1154.272515 (including connections establishing)
80 tps = 1168.805881 (including connections establishing)
80 tps = 1173.971801 (including connections establishing)

80S tps = 1483.037788 (including connections establishing)
80S tps = 1481.059504 (including connections establishing)
80S tps = 1487.215748 (including connections establishing)

So, apparently, the extra work in SIInsertDataEntries() is more than
paid for by the speedup in SIGetDataEntries(). I'm guessing that at
high client counts you win because of reduced spinlock contention, and
at low client counts you still win a little bit because
SIGetDataEntries() is called multiple times per transaction, whereas
SIInsertDataEntries() is only called once. I could be all wet on the
reason, but at any rate the numbers look pretty good.

Interesting. I had hypothesized that at two clients per core, nearly every call
to SIGetDataEntries() would find work to do, making the patch a strict loss. A
bit of instrumented testing showed otherwise: at two clients per core,
sinval-hasmessages optimized away 93% of the calls. At fifty clients per core,
it still optimized away more than half of the calls.

--
Noah Misch http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Thu, Jul 28, 2011 at 11:05 PM, Noah Misch <noah@2ndquadrant.com> wrote:

The comparison I had in mind was (a) master + lazy-vxid + [1]sinval-fastpath
vs. (b) master + lazy-vxid + [2]sinval-hasmessages.  The only claimed benefit of
[2] over [1], as far as I can see, is invulnerability to the hazard described in
[3].  Before selecting [2] over [1], it would be instructive to know how much
performance we exchange for its benefit.

I did a bit of (relatively unrigorous) poking at this workload with oprofile,
and I never saw SIInsertDataEntries take more than 0.26% of CPU time.  It's
perhaps too cheap relative to the workload's other costs to matter.  That's good
enough for me.

Me, too. There's another possible benefit, though: in
sinval-fastpath, everybody's got to read maxMsgNum every time through;
whereas in sinval-hasmessages, everyone's reading their own flag. I'm
not sure how much it costs to have memory that gets read by multiple
readers rather than just a single reader, but I think I've seen some
things that indicate it might not always be free.

Interesting.  I had hypothesized that at two clients per core, nearly every call
to SIGetDataEntries() would find work to do, making the patch a strict loss.  A
bit of instrumented testing showed otherwise: at two clients per core,
sinval-hasmessages optimized away 93% of the calls.  At fifty clients per core,
it still optimized away more than half of the calls.

Wow. That's better than I expected. Great idea for a test, too.

Unless someone has another concern here, I think we've got this one nailed.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company