Re: [PATCH v3 net-next] net: Implement fast csum_partial for x86_64

David Laight wrote:

I'd need convincing that unrolling the loop like that gives any significant gain.
You have a dependency chain on the carry flag so have delays between the 'adcq'
instructions (these may be more significant than the memory reads from l1 cache).

If the carry chain is a bottleneck, on Broadwell+ (feature flag
X86_FEATURE_ADX), there are the ADCX and ADOX instructions, which use
separate flag bits for their carry chains and so can be interleaved.

I don't have such a machine to test on, but if someone who does
would like to do a little benchmarking, that would be an interesting
data point.

Unfortunately, that means yet another version of the main loop,
but if there's a significant benefit...

From: George Spelvin [mailto:linux@horizon.com]

Sent: 08 February 2016 20:13
David Laight wrote:

quoted

I'd need convincing that unrolling the loop like that gives any significant gain.
You have a dependency chain on the carry flag so have delays between the 'adcq'
instructions (these may be more significant than the memory reads from l1 cache).

If the carry chain is a bottleneck, on Broadwell+ (feature flag
X86_FEATURE_ADX), there are the ADCX and ADOX instructions, which use
separate flag bits for their carry chains and so can be interleaved.

I don't have such a machine to test on, but if someone who does
would like to do a little benchmarking, that would be an interesting
data point.

Unfortunately, that means yet another version of the main loop,
but if there's a significant benefit...

Well, the only part actually worth writing in assembler is the 'adc' loop.
So run-time substitution of separate versions (as is done for memcpy())
wouldn't be hard.

Since adcx and adox must execute in parallel I clearly need to re-remember
how dependencies against the flags register work. I'm sure I remember
issues with 'false dependencies' against the flags.

However you still need a loop construct that doesn't modify 'o' or 'c'.
Using leal, jcxz, jmp might work.
(Unless broadwell actually has a fast 'loop' instruction.)

(I've not got a suitable test cpu.)

	David

David Laight wrote:

Since adcx and adox must execute in parallel I clearly need to re-remember
how dependencies against the flags register work. I'm sure I remember
issues with 'false dependencies' against the flags.

The issue is with flags register bits that are *not* modified by
an instruction.  If the register is treated as a monolithic entity,
then the previous values of those bits must be considered an *input*
to the instruction, forcing serialization.

The first step in avoiding this problem is to consider the rarely-modified
bits (interrupt, direction, trap, etc.) to be a separate logical register
from the arithmetic flags (carry, overflow, zero, sign, aux carry and parity)
which are updated by almost every instruction.

An arithmetic instruction overwrites the arithmetic flags (so it's only
a WAW dependency which can be broken by renaming) and doesn't touch the
status flags (so no dependency).

However, on x86 even the arithmetic flags aren't updated consistently.
The biggest offender are the (very common!) INC/DEC instructions,
which update all of the arithmetic flags *except* the carry flag.

Thus, the carry flag is also renamed separately on every superscalar
x86 implementation I've ever heard of.

The bit test instructions (BT, BTC, BTR, BTS) also affect *only*
the carry flag, leaving other flags unmodified.  This is also
handled properly by renaming the carry flag separately.


Here's a brief summary chart of flags updated by common instructions:
http://www.logix.cz/michal/doc/i386/app-c.htm
and the full list with all the corner cases:
http://www.logix.cz/michal/doc/i386/app-b.htm

The other two flags that can be worth separating are the overflow
and zero flags.

The rotate instructions modify *only* the carry and overflow flags.
While overflow is undefined for multi-bit rotates (and thus leaving it
unmodified is a valid implementation), it's defined for single-bit rotates,
so must be written.

There are several less common instructions, notably BSF, BSR, CMPXCHG8B,
and a bunch of 80286 segment instructions that nobody cares about,
which retort the result of a test in the zero flag and are defined to
not affect the other flags.


So an aggressive x86 implementation breaks the flags register into five
separately renamed registers:
- CF (carry)
- OF (overflow)
- ZF (zero)
- SF, AF, PF (sign, aux carry, and parity)
- DF, IF, TF, IOPL, etc.

Anyway, I'm sure that when Intel defined ADCX and ADOX they felt that
it was reasonable to commit to always renaming CF and OF separately.

However you still need a loop construct that doesn't modify 'o' or 'c'.
Using leal, jcxz, jmp might work.
(Unless broadwell actually has a fast 'loop' instruction.)

According to Agner Fog (http://agner.org/optimize/instruction_tables.pdf),
JCXZ is reasonably fast (2 uops) on almost all 64-bit CPUs, right back
to K8 and Merom.  The one exception is Precott.  JCXZ and LOOP are 4
uops on those processors.  But 64 bit in general sucked on Precott,
so how much do we care?

AMD:	LOOP is slow (7 uops) on K8, K10, Bobcat and Jaguar.
	JCXZ is acceptable on all of them.
	LOOP and JCXZ are 1 uop on Bulldozer, Piledriver and Steamroller.
Intel:	LOOP is slow (7+ uops) on all processors up to and including Skylake.
	JCXZ is 2 upos on everything from P6 to Skylake exacpt for:
	- Prescott (JCXZ & loop both 4 uops)
	- 1st gen Atom (JCXZ 3 uops, LOOP 8 uops)
	I can't find any that it's fast on.

From: George Spelvin

Sent: 10 February 2016 00:54
To: David Laight; linux-kernel@vger.kernel.org; linux@horizon.com; netdev@vger.kernel.org;
David Laight wrote:

quoted

Since adcx and adox must execute in parallel I clearly need to re-remember
how dependencies against the flags register work. I'm sure I remember
issues with 'false dependencies' against the flags.

The issue is with flags register bits that are *not* modified by
an instruction.  If the register is treated as a monolithic entity,
then the previous values of those bits must be considered an *input*
to the instruction, forcing serialization.

The first step in avoiding this problem is to consider the rarely-modified
bits (interrupt, direction, trap, etc.) to be a separate logical register
from the arithmetic flags (carry, overflow, zero, sign, aux carry and parity)
which are updated by almost every instruction.

An arithmetic instruction overwrites the arithmetic flags (so it's only
a WAW dependency which can be broken by renaming) and doesn't touch the
status flags (so no dependency).

However, on x86 even the arithmetic flags aren't updated consistently.
The biggest offender are the (very common!) INC/DEC instructions,
which update all of the arithmetic flags *except* the carry flag.

Thus, the carry flag is also renamed separately on every superscalar
x86 implementation I've ever heard of.

Ah, that is the little fact I'd forgotten.
...

Anyway, I'm sure that when Intel defined ADCX and ADOX they felt that
it was reasonable to commit to always renaming CF and OF separately.

Separate renaming allows:
1) The value to tested without waiting for pending updates to complete.
   Useful for IE and DIR.
2) Instructions that modify almost all the flags to execute without
   waiting for a previous instruction to complete.
   So separating 'carry' allows inc/dec to execute without waiting
   for previous arithmetic to complete.

The latter should remove the dependency (both ways) between 'adc' and
'dec, jnz' in a checksum loop.

I can't see any obvious gain from separating out O or Z (even with
adcx and adox). You'd need some other instructions that don't set O (or Z)
but set some other useful flags.
(A decrement that only set Z for instance.)

quoted

However you still need a loop construct that doesn't modify 'o' or 'c'.
Using leal, jcxz, jmp might work.
(Unless broadwell actually has a fast 'loop' instruction.)

According to Agner Fog (http://agner.org/optimize/instruction_tables.pdf),
JCXZ is reasonably fast (2 uops) on almost all 64-bit CPUs, right back
to K8 and Merom.  The one exception is Precott.  JCXZ and LOOP are 4
uops on those processors.  But 64 bit in general sucked on Precott,
so how much do we care?

AMD:	LOOP is slow (7 uops) on K8, K10, Bobcat and Jaguar.
	JCXZ is acceptable on all of them.
	LOOP and JCXZ are 1 uop on Bulldozer, Piledriver and Steamroller.
Intel:	LOOP is slow (7+ uops) on all processors up to and including Skylake.
	JCXZ is 2 upos on everything from P6 to Skylake exacpt for:
	- Prescott (JCXZ & loop both 4 uops)
	- 1st gen Atom (JCXZ 3 uops, LOOP 8 uops)
	I can't find any that it's fast on.

While LOOP could be used on Bulldozer+ an equivalently fast loop
can be done with inc/dec and jnz.
So you only care about LOOP/JCXZ when ADOX is supported.

I think the fastest loop is:
10:	adc	%rax,0(%rdi,%rcx,8)
	inc	%rcx
	jnz	10b
but check if any cpu add an extra clock for the 'scaled' offset
(they might be faster if %rdi is incremented).
That loop looks like it will have no overhead on recent cpu.

	David

David Laight wrote:

Separate renaming allows:
1) The value to tested without waiting for pending updates to complete.
   Useful for IE and DIR.

I don't quite follow.  It allows the value to be tested without waiting
for pending updates *of other bits* to complete.

Obviusly, the update of the bit being tested has to complete!

I can't see any obvious gain from separating out O or Z (even with
adcx and adox). You'd need some other instructions that don't set O (or Z)
but set some other useful flags.
(A decrement that only set Z for instance.)

I tried to describe the advantages in the previous message.

The problems arise much less often than the INC/DEC pair, but there are
instructions whick write only the O and C flags, (ROL, ROR) and only
the Z flag (CMPXCHG).

The sign, aux carry, and parity flags are *always* updated as
a group, so they can be renamed as a group.

While LOOP could be used on Bulldozer+ an equivalently fast loop
can be done with inc/dec and jnz.
So you only care about LOOP/JCXZ when ADOX is supported.

I think the fastest loop is:
10:	adc	%rax,0(%rdi,%rcx,8)
	inc	%rcx
	jnz	10b
but check if any cpu add an extra clock for the 'scaled' offset
(they might be faster if %rdi is incremented).
That loop looks like it will have no overhead on recent cpu.

Well, it should execute at 1 instruction/cycle.  (No, a scaled offset
doesn't take extra time.)  To break that requires ADCX/ADOX:

10:	adcxq	0(%rdi,%rcx),%rax
	adoxq	8(%rdi,%rcx),%rdx
 	leaq	16(%rcx),%rcx
	jrcxz	11f
 	j	10b
11:

From: George Spelvin

Sent: 10 February 2016 14:44

...

quoted

I think the fastest loop is:
10:	adcq	0(%rdi,%rcx,8),%rax
	inc	%rcx
	jnz	10b
That loop looks like it will have no overhead on recent cpu.

Well, it should execute at 1 instruction/cycle.

I presume you do mean 1 adc/cycle.
If it doesn't unrolling once might help.

(No, a scaled offset doesn't take extra time.)

Maybe I'm remembering the 386 book.

To break that requires ADCX/ADOX:

10:	adcxq	0(%rdi,%rcx),%rax
	adoxq	8(%rdi,%rcx),%rdx
 	leaq	16(%rcx),%rcx
	jrcxz	11f
 	j	10b
11:

Getting 2 adc/cycle probably does require a little unrolling.
With luck the adcxq, adoxq and leaq will execute together.
The jrcxz is two clocks - so definitely needs a second adcoxq/adcxq pair.

Experiments would be needed to confirm guesses though.

	David