Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #81966 > unrolled thread

faster "CRC"- / "FNV"-hashing

Started byBonita Montero <Bonita.Montero@gmail.com>
First post2021-10-10 18:51 +0200
Last post2021-10-11 05:41 +0000
Articles 20 on this page of 31 — 7 participants

Back to article view | Back to comp.lang.c++

Contents

  faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-10 18:51 +0200
    Re: faster "CRC"- / "FNV"-hashing "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-10-10 12:36 -0700
      Re: faster "CRC"- / "FNV"-hashing scott@slp53.sl.home (Scott Lurndal) - 2021-10-10 22:51 +0000
        Re: faster "CRC"- / "FNV"-hashing "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-10-12 13:47 -0700
      Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 08:09 +0200
    Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 05:23 +0000
      Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 08:15 +0200
        Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 06:29 +0000
          Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 08:34 +0200
      Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 08:27 +0200
        Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 06:32 +0000
          Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 08:33 +0200
            Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 07:46 +0000
              Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 10:53 +0200
                Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 09:11 +0000
                  Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 11:18 +0200
                    Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 10:42 +0000
                      Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 13:03 +0200
                        Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 11:12 +0000
                          Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 13:44 +0200
                    Re: faster "CRC"- / "FNV"-hashing Bo Persson <bo@bo-persson.se> - 2021-10-11 13:58 +0200
                      Re: faster "CRC"- / "FNV"-hashing David Brown <david.brown@hesbynett.no> - 2021-10-11 14:23 +0200
                        Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 12:56 +0000
                          Re: faster "CRC"- / "FNV"-hashing Bonita Montero <Bonita.Montero@gmail.com> - 2021-10-11 15:55 +0200
                            Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 16:55 +0000
                              Re: faster "CRC"- / "FNV"-hashing RadicalRabbit@theburrow.co.uk - 2021-10-12 09:06 +0000
                                Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-12 11:01 +0000
                                  Re: faster "CRC"- / "FNV"-hashing RadicalRabbit@theburrow.co.uk - 2021-10-12 14:49 +0000
                          Re: faster "CRC"- / "FNV"-hashing David Brown <david.brown@hesbynett.no> - 2021-10-11 17:19 +0200
                            Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 16:57 +0000
    Re: faster "CRC"- / "FNV"-hashing Branimir Maksimovic <branimir.maksimovic@icloud.com> - 2021-10-11 05:41 +0000

Page 1 of 2  [1] 2  Next page →

#81966 — faster "CRC"- / "FNV"-hashing

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-10 18:51 +0200
Subjectfaster "CRC"- / "FNV"-hashing
Message-ID<sjv5nb$7sp$1@dont-email.me>
I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
the same results, and don't provide the opportunity for error-correction
for CRC, but which have the same equal distribution and are much more
performant on modern OoO-CPUS. How did I do that ?

These are the results on my Linux Ryzen 7 1800X:

fnv streamed 32: : 0.964425 GB/s
fnv blocked 32:  : 1.96624 GB/s 104%
fnv streamed 64: : 0.939418 GB/s
fnv blocked 64:  : 3.11791 GB/s 232%
crc64:           : 0.478093 GB/s
crc64 blocked:   : 2.39144 GB/s 400%

[toc] | [next] | [standalone]

#81968

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-10-10 12:36 -0700
Message-ID<sjvfb7$8o2$1@gioia.aioe.org>
In reply to#81966
On 10/10/2021 9:51 AM, Bonita Montero wrote:
> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
> the same results, and don't provide the opportunity for error-correction
> for CRC, but which have the same equal distribution and are much more
> performant on modern OoO-CPUS. How did I do that ?

I don't know.


> These are the results on my Linux Ryzen 7 1800X:
> 
> fnv streamed 32: : 0.964425 GB/s
> fnv blocked 32:  : 1.96624 GB/s 104%
> fnv streamed 64: : 0.939418 GB/s
> fnv blocked 64:  : 3.11791 GB/s 232%
> crc64:           : 0.478093 GB/s
> crc64 blocked:   : 2.39144 GB/s 400%
> 

Btw, if you can come up with a really fast SHA2 impl, I would be 
interested because of my experimental HMAC cipher. I have a C version:

https://groups.google.com/g/comp.lang.c/c/a53VxN8cwkY/m/XKl1-0a8DAAJ

https://pastebin.com/raw/feUnA3kP

Also, I put it up online using a rather inefficient, but working SHA2 
lib. I say inefficient because it does not provide an update method.

http://fractallife247.com/test/hmac_cipher/ver_0_0_0_1?ct_hmac_cipher=0422a78fffa58f349a486b3842d2eedfa87985658fb9f011153b896fb97b4b291224ddd327017e9fcdf4b3d8fd5dfde47ae8f23639044f7c5c73a1f0a891087814a139dfe44e47b4300cac921f736776ab7042fb09aae38f8780aa49e5cd128d141e2982d3aa4b288fceef939126c0a319da20b0cf219732504491eb14c691149f

[toc] | [prev] | [next] | [standalone]

#81970

Fromscott@slp53.sl.home (Scott Lurndal)
Date2021-10-10 22:51 +0000
Message-ID<Z7K8J.9824$7U3.6089@fx24.iad>
In reply to#81968
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:

>
>Btw, if you can come up with a really fast SHA2 impl, I would be 
>interested because of my experimental HMAC cipher. I have a C version:

https://en.wikipedia.org/wiki/Intel_SHA_extensions
https://developer.arm.com/documentation/100076/0100/a64-instruction-set-reference/a64-cryptographic-algorithms/a64-cryptographic-instructions?lang=en

[toc] | [prev] | [next] | [standalone]

#82000

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-10-12 13:47 -0700
Message-ID<sk4s9h$10k0$1@gioia.aioe.org>
In reply to#81970
On 10/10/2021 3:51 PM, Scott Lurndal wrote:
> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
> 
>>
>> Btw, if you can come up with a really fast SHA2 impl, I would be
>> interested because of my experimental HMAC cipher. I have a C version:
> 
> https://en.wikipedia.org/wiki/Intel_SHA_extensions
> https://developer.arm.com/documentation/100076/0100/a64-instruction-set-reference/a64-cryptographic-algorithms/a64-cryptographic-instructions?lang=en
> 

Nice! I failed to notice SHA-384. I like that hash for some reasons. 
However, I did notice SHA3, which means they should have it.

[toc] | [prev] | [next] | [standalone]

#81974

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 08:09 +0200
Message-ID<sk0kff$n1i$1@dont-email.me>
In reply to#81968
Am 10.10.2021 um 21:36 schrieb Chris M. Thomasson:
> On 10/10/2021 9:51 AM, Bonita Montero wrote:
>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>> the same results, and don't provide the opportunity for error-correction
>> for CRC, but which have the same equal distribution and are much more
>> performant on modern OoO-CPUS. How did I do that ?
> 
> I don't know.
> 
> 
>> These are the results on my Linux Ryzen 7 1800X:
>>
>> fnv streamed 32: : 0.964425 GB/s
>> fnv blocked 32:  : 1.96624 GB/s 104%
>> fnv streamed 64: : 0.939418 GB/s
>> fnv blocked 64:  : 3.11791 GB/s 232%
>> crc64:           : 0.478093 GB/s
>> crc64 blocked:   : 2.39144 GB/s 400%
>>
> 
> Btw, if you can come up with a really fast SHA2 impl, I would be 
> interested because of my experimental HMAC cipher. I have a C version:

SHA* is completely different and can't be improved how I did it.

[toc] | [prev] | [next] | [standalone]

#81972

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 05:23 +0000
Message-ID<3TP8J.82248$tG6.21234@fx39.iad>
In reply to#81966
On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
> the same results, and don't provide the opportunity for error-correction
> for CRC, but which have the same equal distribution and are much more
> performant on modern OoO-CPUS. How did I do that ?
>
> These are the results on my Linux Ryzen 7 1800X:
>
> fnv streamed 32: : 0.964425 GB/s
> fnv blocked 32:  : 1.96624 GB/s 104%
> fnv streamed 64: : 0.939418 GB/s
> fnv blocked 64:  : 3.11791 GB/s 232%
> crc64:           : 0.478093 GB/s
> crc64 blocked:   : 2.39144 GB/s 400%
>
Proprietary?

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81975

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 08:15 +0200
Message-ID<sk0kqq$s7n$1@dont-email.me>
In reply to#81972
Am 11.10.2021 um 07:23 schrieb Branimir Maksimovic:
> On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>> the same results, and don't provide the opportunity for error-correction
>> for CRC, but which have the same equal distribution and are much more
>> performant on modern OoO-CPUS. How did I do that ?
>>
>> These are the results on my Linux Ryzen 7 1800X:
>>
>> fnv streamed 32: : 0.964425 GB/s
>> fnv blocked 32:  : 1.96624 GB/s 104%
>> fnv streamed 64: : 0.939418 GB/s
>> fnv blocked 64:  : 3.11791 GB/s 232%
>> crc64:           : 0.478093 GB/s
>> crc64 blocked:   : 2.39144 GB/s 400%
>>
> Proprietary?

Of course - but the same equal distribution.

[toc] | [prev] | [next] | [standalone]

#81977

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 06:29 +0000
Message-ID<PQQ8J.66923$6U3.41978@fx43.iad>
In reply to#81975
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 07:23 schrieb Branimir Maksimovic:
>> On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>>> the same results, and don't provide the opportunity for error-correction
>>> for CRC, but which have the same equal distribution and are much more
>>> performant on modern OoO-CPUS. How did I do that ?
>>>
>>> These are the results on my Linux Ryzen 7 1800X:
>>>
>>> fnv streamed 32: : 0.964425 GB/s
>>> fnv blocked 32:  : 1.96624 GB/s 104%
>>> fnv streamed 64: : 0.939418 GB/s
>>> fnv blocked 64:  : 3.11791 GB/s 232%
>>> crc64:           : 0.478093 GB/s
>>> crc64 blocked:   : 2.39144 GB/s 400%
>>>
>> Proprietary?
>
> Of course - but the same equal distribution.
>
Dunno, those hashing algos work much better if there is support
from hardware. But, of course faster, better :P

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81980

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 08:34 +0200
Message-ID<sk0luh$fvr$2@dont-email.me>
In reply to#81977
Am 11.10.2021 um 08:29 schrieb Branimir Maksimovic:
> On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Am 11.10.2021 um 07:23 schrieb Branimir Maksimovic:
>>> On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>>>> the same results, and don't provide the opportunity for error-correction
>>>> for CRC, but which have the same equal distribution and are much more
>>>> performant on modern OoO-CPUS. How did I do that ?
>>>>
>>>> These are the results on my Linux Ryzen 7 1800X:
>>>>
>>>> fnv streamed 32: : 0.964425 GB/s
>>>> fnv blocked 32:  : 1.96624 GB/s 104%
>>>> fnv streamed 64: : 0.939418 GB/s
>>>> fnv blocked 64:  : 3.11791 GB/s 232%
>>>> crc64:           : 0.478093 GB/s
>>>> crc64 blocked:   : 2.39144 GB/s 400%
>>>>
>>> Proprietary?
>>
>> Of course - but the same equal distribution.
>>
> Dunno, those hashing algos work much better if there is
> support from hardware. But, of course faster, better :P

There are only special SSE-instrucions for CRC32, but not for CRC64.

[toc] | [prev] | [next] | [standalone]

#81976

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 08:27 +0200
Message-ID<sk0lga$94q$1@dont-email.me>
In reply to#81972
Am 11.10.2021 um 07:23 schrieb Branimir Maksimovic:
> On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>> the same results, and don't provide the opportunity for error-correction
>> for CRC, but which have the same equal distribution and are much more
>> performant on modern OoO-CPUS. How did I do that ?
>>
>> These are the results on my Linux Ryzen 7 1800X:
>>
>> fnv streamed 32: : 0.964425 GB/s
>> fnv blocked 32:  : 1.96624 GB/s 104%
>> fnv streamed 64: : 0.939418 GB/s
>> fnv blocked 64:  : 3.11791 GB/s 232%
>> crc64:           : 0.478093 GB/s
>> crc64 blocked:   : 2.39144 GB/s 400%
>>
> Proprietary?

That's the improved "CRC64":

#include "crc64.h"

using namespace std;

uint64_t CRC64_ECMA182::operator ()( void const *p, size_t n, uint64_t 
startCrc ) const
{
	uint64_t crc = startCrc;
	uint8_t const *s   = (uint8_t *)p,
	              *end = s + n;
	size_t         t;
	for( ; s != end; ++s )
		t   = (size_t)(crc >> 56) ^ *s,
		crc = table.t[t] ^ (crc << 8);
	return crc;
}

uint64_t CRC64_ECMA182::blocked( void const *p, size_t n, uint64_t 
startCrc ) const
{
	auto crc64_8x8 = []( uint8_t const *s ) -> uint64_t
	{
		uint64_t crcs[8] =
		{
			table.t[s[ 0]],
			table.t[s[ 8]],
			table.t[s[16]],
			table.t[s[24]],
			table.t[s[32]],
			table.t[s[40]],
			table.t[s[48]],
			table.t[s[56]]
		};
		size_t t;
		uint8_t const *end = ++s + 7;
		do
			t = (size_t)(crcs[0] >> 56) ^ s[ 0],
			crcs[0] = table.t[t] ^ (crcs[0] << 8),
			t = (size_t)(crcs[1] >> 56) ^ s[ 8],
			crcs[1] = table.t[t] ^ (crcs[1] << 8),
			t = (size_t)(crcs[2] >> 56) ^ s[16],
			crcs[2] = table.t[t] ^ (crcs[2] << 8),
			t = (size_t)(crcs[3] >> 56) ^ s[24],
			crcs[3] = table.t[t] ^ (crcs[3] << 8),
			t = (size_t)(crcs[4] >> 56) ^ s[32],
			crcs[4] = table.t[t] ^ (crcs[4] << 8),
			t = (size_t)(crcs[5] >> 56) ^ s[40],
			crcs[5] = table.t[t] ^ (crcs[5] << 8),
			t = (size_t)(crcs[6] >> 56) ^ s[48],
			crcs[6] = table.t[t] ^ (crcs[6] << 8),
			t = (size_t)(crcs[7] >> 56) ^ s[56],
			crcs[7] = table.t[t] ^ (crcs[7] << 8);
		while( ++s != end );
		uint64_t crc = 0;
		for( size_t i = 0; i != 8; ++i )
			crc ^= crcs[i];
		return crc;
	};
	uint8_t const *s   = (uint8_t *)p;
	uint64_t       crc = startCrc;
	for( uint8_t const *end = s + (n & -64); s != end; s += 64 )
		crc ^= crc64_8x8( s );
	crc ^= (*this)( s, n % 64, 0 );
	return crc;
}

CRC64_ECMA182::crc64_table::crc64_table()
{
	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
	for( uint64_t i = 0; i != 256; ++i )
	{
		uint64_t crc = 0,
		         c   = i << 56;
		for( unsigned j = 0; j != 8; ++j )
			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc 
<< 1,
			c <<= 1;
		t[(size_t)i] = crc;
	}
}

CRC64_ECMA182::crc64_table CRC64_ECMA182::table;

Why does it run faster ?

[toc] | [prev] | [next] | [standalone]

#81978

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 06:32 +0000
Message-ID<WTQ8J.225542$T_8.141095@fx48.iad>
In reply to#81976
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 07:23 schrieb Branimir Maksimovic:
>> On 2021-10-10, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> I derived two hash-algorithms from FNV32/64 and CRC64 that don't yield
>>> the same results, and don't provide the opportunity for error-correction
>>> for CRC, but which have the same equal distribution and are much more
>>> performant on modern OoO-CPUS. How did I do that ?
>>>
>>> These are the results on my Linux Ryzen 7 1800X:
>>>
>>> fnv streamed 32: : 0.964425 GB/s
>>> fnv blocked 32:  : 1.96624 GB/s 104%
>>> fnv streamed 64: : 0.939418 GB/s
>>> fnv blocked 64:  : 3.11791 GB/s 232%
>>> crc64:           : 0.478093 GB/s
>>> crc64 blocked:   : 2.39144 GB/s 400%
>>>
>> Proprietary?
>
> That's the improved "CRC64":
>
> #include "crc64.h"
>
> using namespace std;
>
> uint64_t CRC64_ECMA182::operator ()( void const *p, size_t n, uint64_t 
> startCrc ) const
> {
> 	uint64_t crc = startCrc;
> 	uint8_t const *s   = (uint8_t *)p,
> 	              *end = s + n;
> 	size_t         t;
> 	for( ; s != end; ++s )
> 		t   = (size_t)(crc >> 56) ^ *s,
> 		crc = table.t[t] ^ (crc << 8);
> 	return crc;
> }
>
> uint64_t CRC64_ECMA182::blocked( void const *p, size_t n, uint64_t 
> startCrc ) const
> {
> 	auto crc64_8x8 = []( uint8_t const *s ) -> uint64_t
> 	{
> 		uint64_t crcs[8] =
> 		{
> 			table.t[s[ 0]],
> 			table.t[s[ 8]],
> 			table.t[s[16]],
> 			table.t[s[24]],
> 			table.t[s[32]],
> 			table.t[s[40]],
> 			table.t[s[48]],
> 			table.t[s[56]]
> 		};
> 		size_t t;
> 		uint8_t const *end = ++s + 7;
> 		do
> 			t = (size_t)(crcs[0] >> 56) ^ s[ 0],
> 			crcs[0] = table.t[t] ^ (crcs[0] << 8),
> 			t = (size_t)(crcs[1] >> 56) ^ s[ 8],
> 			crcs[1] = table.t[t] ^ (crcs[1] << 8),
> 			t = (size_t)(crcs[2] >> 56) ^ s[16],
> 			crcs[2] = table.t[t] ^ (crcs[2] << 8),
> 			t = (size_t)(crcs[3] >> 56) ^ s[24],
> 			crcs[3] = table.t[t] ^ (crcs[3] << 8),
> 			t = (size_t)(crcs[4] >> 56) ^ s[32],
> 			crcs[4] = table.t[t] ^ (crcs[4] << 8),
> 			t = (size_t)(crcs[5] >> 56) ^ s[40],
> 			crcs[5] = table.t[t] ^ (crcs[5] << 8),
> 			t = (size_t)(crcs[6] >> 56) ^ s[48],
> 			crcs[6] = table.t[t] ^ (crcs[6] << 8),
> 			t = (size_t)(crcs[7] >> 56) ^ s[56],
> 			crcs[7] = table.t[t] ^ (crcs[7] << 8);
> 		while( ++s != end );
> 		uint64_t crc = 0;
> 		for( size_t i = 0; i != 8; ++i )
> 			crc ^= crcs[i];
> 		return crc;
> 	};
> 	uint8_t const *s   = (uint8_t *)p;
> 	uint64_t       crc = startCrc;
> 	for( uint8_t const *end = s + (n & -64); s != end; s += 64 )
> 		crc ^= crc64_8x8( s );
> 	crc ^= (*this)( s, n % 64, 0 );
> 	return crc;
> }
>
> CRC64_ECMA182::crc64_table::crc64_table()
> {
> 	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
> 	for( uint64_t i = 0; i != 256; ++i )
> 	{
> 		uint64_t crc = 0,
> 		         c   = i << 56;
> 		for( unsigned j = 0; j != 8; ++j )
> 			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc 
><< 1,
> 			c <<= 1;
> 		t[(size_t)i] = crc;
> 	}
> }
>
> CRC64_ECMA182::crc64_table CRC64_ECMA182::table;
>
> Why does it run faster ?
Dunno, haven't have need to calculate crc64 yet :P
Better to generate table, don't waste time on generation :P


-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81979

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 08:33 +0200
Message-ID<sk0lrs$fvr$1@dont-email.me>
In reply to#81978
Am 11.10.2021 um 08:32 schrieb Branimir Maksimovic:

>> CRC64_ECMA182::crc64_table::crc64_table()
>> {
>> 	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
>> 	for( uint64_t i = 0; i != 256; ++i )
>> 	{
>> 		uint64_t crc = 0,
>> 		         c   = i << 56;
>> 		for( unsigned j = 0; j != 8; ++j )
>> 			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc
>> << 1,
>> 			c <<= 1;
>> 		t[(size_t)i] = crc;
>> 	}
>> }
>>
>> CRC64_ECMA182::crc64_table CRC64_ECMA182::table;
>>
>> Why does it run faster ?
> Dunno, haven't have need to calculate crc64 yet :P
> Better to generate table, don't waste time on generation :P

Eeeh, I'm using also a table as you can see from above.

[toc] | [prev] | [next] | [standalone]

#81981

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 07:46 +0000
Message-ID<TZR8J.11209$yk1.5819@fx13.iad>
In reply to#81979
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 08:32 schrieb Branimir Maksimovic:
>
>>> CRC64_ECMA182::crc64_table::crc64_table()
>>> {
>>> 	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
>>> 	for( uint64_t i = 0; i != 256; ++i )
>>> 	{
>>> 		uint64_t crc = 0,
>>> 		         c   = i << 56;
>>> 		for( unsigned j = 0; j != 8; ++j )
>>> 			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc
>>> << 1,
>>> 			c <<= 1;
>>> 		t[(size_t)i] = crc;
>>> 	}
>>> }
>>>
>>> CRC64_ECMA182::crc64_table CRC64_ECMA182::table;
>>>
>>> Why does it run faster ?
>> Dunno, haven't have need to calculate crc64 yet :P
>> Better to generate table, don't waste time on generation :P
>
> Eeeh, I'm using also a table as you can see from above.
>
>
What do you think about following:
https://github.com/intel/isa-l/tree/master/crc

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81982

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 10:53 +0200
Message-ID<sk0u2a$ajc$1@dont-email.me>
In reply to#81981
Am 11.10.2021 um 09:46 schrieb Branimir Maksimovic:
> On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>> Am 11.10.2021 um 08:32 schrieb Branimir Maksimovic:
>>
>>>> CRC64_ECMA182::crc64_table::crc64_table()
>>>> {
>>>> 	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
>>>> 	for( uint64_t i = 0; i != 256; ++i )
>>>> 	{
>>>> 		uint64_t crc = 0,
>>>> 		         c   = i << 56;
>>>> 		for( unsigned j = 0; j != 8; ++j )
>>>> 			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc
>>>> << 1,
>>>> 			c <<= 1;
>>>> 		t[(size_t)i] = crc;
>>>> 	}
>>>> }
>>>>
>>>> CRC64_ECMA182::crc64_table CRC64_ECMA182::table;
>>>>
>>>> Why does it run faster ?
>>> Dunno, haven't have need to calculate crc64 yet :P
>>> Better to generate table, don't waste time on generation :P
>>
>> Eeeh, I'm using also a table as you can see from above.
>>
>>
> What do you think about following:
> https://github.com/intel/isa-l/tree/master/crc

I won't check this ASM-code. An I don't know why people use ASM.
C / C++ and intrinsics usually result in better code.

[toc] | [prev] | [next] | [standalone]

#81983

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 09:11 +0000
Message-ID<wdT8J.185287$o45.132180@fx46.iad>
In reply to#81982
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 09:46 schrieb Branimir Maksimovic:
>> On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
>>> Am 11.10.2021 um 08:32 schrieb Branimir Maksimovic:
>>>
>>>>> CRC64_ECMA182::crc64_table::crc64_table()
>>>>> {
>>>>> 	uint64_t const CRC64_ECMA182_POLY = 0x42F0E1EBA9EA3693u;
>>>>> 	for( uint64_t i = 0; i != 256; ++i )
>>>>> 	{
>>>>> 		uint64_t crc = 0,
>>>>> 		         c   = i << 56;
>>>>> 		for( unsigned j = 0; j != 8; ++j )
>>>>> 			crc = (int64_t)(crc ^ c) < 0 ? (crc << 1) ^ CRC64_ECMA182_POLY : crc
>>>>> << 1,
>>>>> 			c <<= 1;
>>>>> 		t[(size_t)i] = crc;
>>>>> 	}
>>>>> }
>>>>>
>>>>> CRC64_ECMA182::crc64_table CRC64_ECMA182::table;
>>>>>
>>>>> Why does it run faster ?
>>>> Dunno, haven't have need to calculate crc64 yet :P
>>>> Better to generate table, don't waste time on generation :P
>>>
>>> Eeeh, I'm using also a table as you can see from above.
>>>
>>>
>> What do you think about following:
>> https://github.com/intel/isa-l/tree/master/crc
>
> I won't check this ASM-code. An I don't know why people use ASM.
> C / C++ and intrinsics usually result in better code.
If you want to be hacker you have to program in ASM
(without debugger :) )
ASM code is most efficient always and works as tested without
surprises :P
C/C++ you can use after ypou master ASM :P
IMO :P

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81984

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 11:18 +0200
Message-ID<sk0vgf$6or$1@dont-email.me>
In reply to#81983
Am 11.10.2021 um 11:11 schrieb Branimir Maksimovic:

> ASM code is most efficient always and works as tested without
> surprises :P

ASM code can be faster in rare cases when you know everyting about
your OoO-CPU, but in most cases the compiler generates better code.
I've seen code from clang where you might think: there would be no
ASM-programmer that knows all of these optimization-tricks.

[toc] | [prev] | [next] | [standalone]

#81985

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 10:42 +0000
Message-ID<9yU8J.139676$F26.46001@fx44.iad>
In reply to#81984
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 11:11 schrieb Branimir Maksimovic:
>
>> ASM code is most efficient always and works as tested without
>> surprises :P
>
> ASM code can be faster in rare cases when you know everyting about
> your OoO-CPU, but in most cases the compiler generates better code.
> I've seen code from clang where you might think: there would be no
> ASM-programmer that knows all of these optimization-tricks.
Human always beats compiler, as you can always examine
compiler generated code, learn and bit it :
Also humans are better in algorithms :P
As major optimisation is *always algorithm* :P

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81986

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 13:03 +0200
Message-ID<sk15md$v4q$1@dont-email.me>
In reply to#81985
Am 11.10.2021 um 12:42 schrieb Branimir Maksimovic:

> Human always beats compiler, as you can always examine
> compiler generated code, learn and bit it :

Humans tend to write Asm that is readable. Compilers generate
Asm that's often not readbale for performance reasons.

[toc] | [prev] | [next] | [standalone]

#81987

FromBranimir Maksimovic <branimir.maksimovic@icloud.com>
Date2021-10-11 11:12 +0000
Message-ID<P_U8J.69383$fZ.5770@fx06.iad>
In reply to#81986
On 2021-10-11, Bonita Montero <Bonita.Montero@gmail.com> wrote:
> Am 11.10.2021 um 12:42 schrieb Branimir Maksimovic:
>
>> Human always beats compiler, as you can always examine
>> compiler generated code, learn and bit it :
>
> Humans tend to write Asm that is readable. Compilers generate
> Asm that's often not readbale for performance reasons.
Readable and compact, not bloated :P
Optimize in iterations :P

-- 

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

[toc] | [prev] | [next] | [standalone]

#81988

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-10-11 13:44 +0200
Message-ID<sk183i$han$1@dont-email.me>
In reply to#81987
> Readable and compact, not bloated :P

Inlining makes bloat - but is usually more performant.
Loop-unrolling of small loops makes bloat - but is usually
more performant.

> Optimize in iterations :P

Hand-written asm is usually slower because there are only a small
number of asm-writers that know all the optimizaztion-tricks that
compilers have learned for decades. F.e. the code of clang 12 is
meanwhile somewhat faster than that of gcc 11. I think in five
years absoutely no asm writer can beat a compiler.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web