Sorry for the late answer, this slipped somehow through ...
I think you might want to cc Andrew Morton <[email protected]>
to let this go via akpm's tree for misc changes, perhaps?
The work from my side went via Dave's net-next tree as it had some
follow-up SCTP work that depended on these below bits.
No objections from my side if you really want this to go through
<[email protected]>, though.
Anyway, some more comments inline:
On 05/30/2014 07:35 AM, George Spelvin wrote:
> There's no need for a full 32x32 matrix, when rows before the last are
> just shifted copies of the rows after them.
>
> There's still room for improvement (especially on X86 processors with
> CRC32 and PCLMUL instructions), but this is a large step in the
> right direction.
>
> The internal primitive is now called crc32_generic_shift and takes one
> less argument; the XOR with crc2 is done in inline wrappers.
>
> Signed-off-by: George Spelvin <[email protected]>
> ---
> This is the significant patch; there other two patches are minor
> cleanups that I did while in the area.
>
> Tested extensively in user-space (the "power" variable is identical
> to the last row of the current even/odd matrix in the previous code)
> and with CONFIG_CRC32_SELFTEST:
>
> [ 0.587152] crc32: CRC_LE_BITS = 64, CRC_BE BITS = 64
> [ 0.587186] crc32: self tests passed, processed 225944 bytes in 115727 nsec
> [ 0.587341] crc32c: CRC_LE_BITS = 64
> [ 0.587373] crc32c: self tests passed, processed 225944 bytes in 59505 nsec
> [ 0.596827] crc32_combine: 8373 self tests passed
> [ 0.606259] crc32c_combine: 8373 self tests passed
>
> Code shrunk; comments increased to match.
> Pulling 2x32x32 bits = 256 bytes off the stack is a nice bonus.
Looks good to me! Do you have any performance numbers to share?
Some very minor nit-picking:
> include/linux/crc32.h | 12 ++++-
> lib/crc32.c | 142 +++++++++++++++++++++++---------------------------
> 2 files changed, 76 insertions(+), 78 deletions(-)
>
> diff --git a/include/linux/crc32.h b/include/linux/crc32.h
> index 7d275c4f..bcb8e9d3 100644
> --- a/include/linux/crc32.h
> +++ b/include/linux/crc32.h
> @@ -29,7 +29,11 @@ extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len);
> * with the same initializer as crc1, and crc2 seed was 0. See
> * also crc32_combine_test().
> */
> -extern u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
> +u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;
Perhaps a newline here.
> +static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
> +{
> + return crc32_le_shift(crc1, len2) ^ crc2;
> +}
>
> extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len);
>
> @@ -51,7 +55,11 @@ extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len);
> * seeded with the same initializer as crc1, and crc2 seed
> * was 0. See also crc32c_combine_test().
> */
> -extern u32 __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2);
> +u32 __crc32c_le_shift(u32 crc, size_t len) __attribute_const__;
Ditto. Or, put both *_shift() helper signatures before the crc32_le_combine
kdoc comment.
> +static inline u32 __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
> +{
> + return __crc32c_le_shift(crc1, len2) ^ crc2;
> +}
>
> #define crc32(seed, data, length) crc32_le(seed, (unsigned char const *)(data), length)
>
> diff --git a/lib/crc32.c b/lib/crc32.c
> index 70f00ca5..a4a576f3 100644
...
>
> -u32 __pure __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
> +/**
> + * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
> + * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
> + * @len: The number of bytes. @crc is multiplied by x^(8*@len)
> + # @polynomial: The modulus used to reduce the result to 32 bits.
^^ seems this should have been a '*'
> + *
> + * It's possible to parallelize CRC computations by computing a CRC
> + * over separate ranges of a buffer, then summing them.
> + * This shifts the given CRC by 8*len bits (i.e. produces the same effect
> + * as appending len bytes of zero to the data), in time proportional
> + * to log(len).
> + */
> +static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
> + u32 polynomial)
u32 polynomial is not correctly aligned to the opening '(' from the previous line.
> {
> - return crc32_generic_combine(crc1, crc2, len2, CRC32C_POLY_LE);
> + u32 power = polynomial; /* CRC of x^32 */
> + int i;
> +
> + /* Shift up to 32 bits in the simple linear way */
...
The other two patches are fine, imho. Thanks George! :)
Thanks for the nitpicks!
> I think you might want to cc Andrew Morton <[email protected]>
> to let this go via akpm's tree for misc changes, perhaps?
I don't care, but akpm is fine by me. I'll send out a v2 after I resolve
one minor point with you; see below.
Once that's done, may I add a Reviewed-by: or Acked-by: line from you?
> Looks good to me! Do you have any performance numbers to share?
Actually, I didn't bother benchmarking it because the improvement was
so obvious, but here's a quick test showing a 35.5x performance gain.
Old New Delta
0: 83005684 2314192 (-80691492)
1: 82730196 2313836 (-80416360)
2: 82805636 2312736 (-80492900)
3: 82648160 2344304 (-80303856)
4: 82531928 2314940 (-80216988)
5: 82669440 2312976 (-80356464)
6: 82528792 2313984 (-80214808)
7: 82415116 2313796 (-80101320)
8: 82451620 2314000 (-80137620)
9: 82811052 2329708 (-80481344)
10: 82903344 2311120 (-80592224)
11: 82549032 2313540 (-80235492)
12: 82564660 2330260 (-80234400)
13: 82289788 2312972 (-79976816)
14: 82535828 2312036 (-80223792)
15: 82664040 2313284 (-80350756)
16: 82629476 2309744 (-80319732)
17: 82806812 2329628 (-80477184)
18: 82379284 2312876 (-80066408)
19: 82483400 2313004 (-80170396)
20: 82651232 2314244 (-80336988)
21: 82327508 2330456 (-79997052)
22: 82641324 2330664 (-80310660)
23: 82538192 2314024 (-80224168)
MIN: 82289788 2309744 (-79980044)
Here's the test loop. Although it's subject to compiler rearrangements,
I tried to charge the loop overhead to the new code.
static void
do_test(uint64_t times[2])
{
uint32_t crc0 = 1, crc1 = 1;
uint64_t t0, t1, sum0 = 0, sum1 = 0;
int i;
t1 = t0 = rdtsc();
for (i = 1024; i < 2048; i++) {
sum0 += t1;
crc0 = crc32_generic_shift(crc0, i, CRC32C_POLY_LE);
sum1 += rdtsc();
crc1 = crc32_generic_combine(crc1, 0, i, CRC32C_POLY_LE);
t1 = rdtsc();
}
times[0] = sum0 + t1 - sum1 - t0; // Old code
times[1] = sum1 - sum0; // New code
if (crc0 != crc1)
printf("Mismatch! %08x != %08x\n", crc0, crc1);
}
It's possible to do a bit better with more effort (exploiting
the precomputed CRC tables for modular reduction) but this fruit
was hanging *so* low I couldn't resist grabbing it.
>> -extern u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
>> +u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;
> Perhaps a newline here.
Question: where do you think a newline should go? It's not obvious
to me. My style has been to keep as much of a declaration on one line
as possible so "git grep <function> include" is as informative as possible.
>> -extern u32 __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2);
>> +u32 __crc32c_le_shift(u32 crc, size_t len) __attribute_const__;
> Ditto. Or, put both *_shift() helper signatures before the crc32_le_combine
> kdoc comment.
Um, same basic question. I agree that putting a declaration
between the kdoc and the function is strange, but that doesn't
seem to be what you're commenting in...
Now that I've gotten an ack, I'm happy to be more aggressive about
tweaking comments. I just wanted to focus the diff on the code changes.
>> +/**
>> + * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
>> + * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
>> + * @len: The number of bytes. @crc is multiplied by x^(8*@len)
>> + # @polynomial: The modulus used to reduce the result to 32 bits.
> ^^ seems this should have been a '*'
Yes, obviously. Thanks for catching that.
>> +static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
>> + u32 polynomial)
> u32 polynomial is not correctly aligned to the opening '(' from the previous line.
Thanks again.
On 06/04/2014 08:32 PM, George Spelvin wrote:
> Thanks for the nitpicks!
>
>> I think you might want to cc Andrew Morton <[email protected]>
>> to let this go via akpm's tree for misc changes, perhaps?
>
> I don't care, but akpm is fine by me. I'll send out a v2 after I resolve
> one minor point with you; see below.
>
> Once that's done, may I add a Reviewed-by: or Acked-by: line from you?
Yes, feel free to add my Reviewed-by tag and keep me in Cc.
>> Looks good to me! Do you have any performance numbers to share?
>
> Actually, I didn't bother benchmarking it because the improvement was
> so obvious, but here's a quick test showing a 35.5x performance gain.
That's great!
...
>>> -extern u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
>>> +u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;
>
>> Perhaps a newline here.
>
> Question: where do you think a newline should go? It's not obvious
> to me. My style has been to keep as much of a declaration on one line
> as possible so "git grep <function> include" is as informative as possible.
It's just nit, but since you've asked, end result like this:
--snip--
u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;
static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
{
return crc32_le_shift(crc1, len2) ^ crc2;
}
--snap--
> Now that I've gotten an ack, I'm happy to be more aggressive about
> tweaking comments. I just wanted to focus the diff on the code changes.
Sounds good, thanks!
>>> +/**
>>> + * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
>>> + * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
>>> + * @len: The number of bytes. @crc is multiplied by x^(8*@len)
>>> + # @polynomial: The modulus used to reduce the result to 32 bits.
>
>> ^^ seems this should have been a '*'
>
> Yes, obviously. Thanks for catching that.
>
>>> +static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
>>> + u32 polynomial)
>
>> u32 polynomial is not correctly aligned to the opening '(' from the previous line.
>
> Thanks again.
>>> Perhaps a newline here.
>> Question: where do you think a newline should go? It's not obvious
>> to me. My style has been to keep as much of a declaration on one line
>> as possible so "git grep <function> include" is as informative as possible.
> It's just nit, but since you've asked, end result like this:
>
> --snip--
> u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;
>
> static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
> {
> return crc32_le_shift(crc1, len2) ^ crc2;
> }
> --snap--
Ah, got it! I couldn't figure out where it would make sense to insert
a newline into the middle of one line, breaking it into two. Adding a
blank line makes sense, and makes your other comment make sense.
Good suggestion; I'll do it.