Thread: Compiler branch prediction hints (was: So, is COUNT(*) fast now?)

On Fri, Oct 28, 2011 at 20:58, Robert Haas <robertmhaas@gmail.com> wrote:
> I tried sprinkling a little branch-prediction magic on this code using
> GCC's __builtin_expect().  That initially seemed to help, but once I
> changed the BufferIsValid() test to !BufferIsInvalid() essentially all
> of the savings disappeared.

Sounds like mere chance that the compiler decided to lay it out in one
way or another. A different compiler version could pick a different
path.

I quite like the likely() and unlikely() macros used in Linux kernel;
much more readable than __builtin_expect and they might also be useful
for (usually redundant) error checks and asserts in hot code paths. It
looks like this:

#ifdef __GNUC__
# define unlikely(xpr) __builtin_expect(xpr, 0)
#else
# define unlikely(xpr) (xpr)
#endif

if (unlikely(blkno >= rel->rd_smgr->smgr_vm_nblocks))
{
/* unlikely branch here */
}

However, the wins are probably minor because most of the time,
adaptive CPU branch prediction will override that. Do you think this
would be a useful patch to attempt?

Regards,
Marti

On Tue, Nov 1, 2011 at 10:47 AM, Marti Raudsepp <marti@juffo.org> wrote:
> On Fri, Oct 28, 2011 at 20:58, Robert Haas <robertmhaas@gmail.com> wrote:
>> I tried sprinkling a little branch-prediction magic on this code using
>> GCC's __builtin_expect().  That initially seemed to help, but once I
>> changed the BufferIsValid() test to !BufferIsInvalid() essentially all
>> of the savings disappeared.
>
> Sounds like mere chance that the compiler decided to lay it out in one
> way or another. A different compiler version could pick a different
> path.
>
> I quite like the likely() and unlikely() macros used in Linux kernel;
> much more readable than __builtin_expect and they might also be useful
> for (usually redundant) error checks and asserts in hot code paths. It
> looks like this:
>
> #ifdef __GNUC__
> # define unlikely(xpr) __builtin_expect(xpr, 0)
> #else
> # define unlikely(xpr) (xpr)
> #endif
>
> if (unlikely(blkno >= rel->rd_smgr->smgr_vm_nblocks))
> {
> /* unlikely branch here */
> }
>
> However, the wins are probably minor because most of the time,
> adaptive CPU branch prediction will override that. Do you think this
> would be a useful patch to attempt?

Well, the obvious problem is that we might end up spending a lot of
work on something that doesn't actually improve performance, or even
makes it worse, if our guesses about what's likely and unlikely turn
out to be wrong.  If we can show cases where it reliably produces a
significant speedup, then I would think it would be worthwhile, but I
think we should probably start by looking at what's slow and see how
it can best be made faster rather than by looking specifically for
places to use likely() and unlikely().

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

On Tue, Nov 01, 2011 at 10:55:02AM -0400, Robert Haas wrote:
> Well, the obvious problem is that we might end up spending a lot of
> work on something that doesn't actually improve performance, or even
> makes it worse, if our guesses about what's likely and unlikely turn
> out to be wrong.  If we can show cases where it reliably produces a
> significant speedup, then I would think it would be worthwhile, but I
> think we should probably start by looking at what's slow and see how
> it can best be made faster rather than by looking specifically for
> places to use likely() and unlikely().

The biggest problem here is that (usually) the time is going in
branches other than the ones you're thinking of.

Something that might be interesting to try profile branch feedback in
GCC.  If you let the profiler see how often each branch was taken and
then feed this back into the compiler you get in principle the best
case result.  This would represent the possible best case scenario.  If
you can prove a measurable difference then you know it's worth
pursuing.  If there's no result, then you know that too...

Mind you, getting profile data with postgresql's multiprocess
architechture can be challenge.

Have a nice day,
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> He who writes carelessly confesses thereby at the very outset that he does
> not attach much importance to his own thoughts.  -- Arthur Schopenhauer

On Tue, Nov 1, 2011 at 9:55 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Tue, Nov 1, 2011 at 10:47 AM, Marti Raudsepp <marti@juffo.org> wrote:
>> On Fri, Oct 28, 2011 at 20:58, Robert Haas <robertmhaas@gmail.com> wrote:
>>> I tried sprinkling a little branch-prediction magic on this code using
>>> GCC's __builtin_expect().  That initially seemed to help, but once I
>>> changed the BufferIsValid() test to !BufferIsInvalid() essentially all
>>> of the savings disappeared.
>>
>> Sounds like mere chance that the compiler decided to lay it out in one
>> way or another. A different compiler version could pick a different
>> path.
>>
>> I quite like the likely() and unlikely() macros used in Linux kernel;
>> much more readable than __builtin_expect and they might also be useful
>> for (usually redundant) error checks and asserts in hot code paths. It
>> looks like this:
>>
>> #ifdef __GNUC__
>> # define unlikely(xpr) __builtin_expect(xpr, 0)
>> #else
>> # define unlikely(xpr) (xpr)
>> #endif
>>
>> if (unlikely(blkno >= rel->rd_smgr->smgr_vm_nblocks))
>> {
>> /* unlikely branch here */
>> }
>>
>> However, the wins are probably minor because most of the time,
>> adaptive CPU branch prediction will override that. Do you think this
>> would be a useful patch to attempt?
>
> Well, the obvious problem is that we might end up spending a lot of
> work on something that doesn't actually improve performance, or even
> makes it worse, if our guesses about what's likely and unlikely turn
> out to be wrong.  If we can show cases where it reliably produces a
> significant speedup, then I would think it would be worthwhile, but I
> think we should probably start by looking at what's slow and see how
> it can best be made faster rather than by looking specifically for
> places to use likely() and unlikely().

The first thing that jumps to mind is the hint bit checks in
HeapTupleSatisifiesMVCC().

merlin