digest-crc Speeding up C implementation

Switch from Sarwate's algorithm to byte-order free Slicing-by-16. Each table data file is generated by extconf.rb.

In addition, the inspection string, which was previously 10 bytes, is extended to 19 bytes. This is to check the slicing-by-16 loop, which processes in 16-byte units.

Jul 13 '23 14:07 dearblue

For information, here is a summary of the benchmark results. The environment is the same as https://github.com/postmodern/digest-crc/pull/41#issuecomment-1627216364.

CRC Models	main	slicing-by-8	slicing-by-16
Digest::CRC1#update	( 0.394643)	( 0.404651)	( 0.400259)
Digest::CRC5#update	( 0.015706)	( 0.004514)	( 0.003536)
Digest::CRC8#update	( 0.013652)	( 0.004703)	( 0.003673)
Digest::CRC8_1Wire#update	( 0.013575)	( 0.004455)	( 0.003519)
Digest::CRC15#update	( 0.020950)	( 0.004627)	( 0.003702)
Digest::CRC16#update	( 0.018752)	( 0.004552)	( 0.003753)
Digest::CRC16CCITT#update	( 0.019875)	( 0.004606)	( 0.003683)
Digest::CRC16DNP#update	( 0.016596)	( 0.004538)	( 0.003724)
Digest::CRC16Genibus#update	( 0.019800)	( 0.004601)	( 0.003699)
Digest::CRC16Modbus#update	( 0.018721)	( 0.004683)	( 0.003724)
Digest::CRC16QT#update	( 0.018728)	( 0.004732)	( 0.003727)
Digest::CRC16USB#update	( 0.018706)	( 0.004654)	( 0.003923)
Digest::CRC16X25#update	( 0.020320)	( 0.004558)	( 0.003866)
Digest::CRC16XModem#update	( 0.025078)	( 0.004610)	( 0.003897)
Digest::CRC16ZModem#update	( 0.022976)	( 0.004603)	( 0.003760)
Digest::CRC24#update	( 0.021261)	( 0.004867)	( 0.003787)
Digest::CRC32#update	( 0.017693)	( 0.004533)	( 0.003643)
Digest::CRC32BZip2#update	( 0.017650)	( 0.004801)	( 0.003785)
Digest::CRC32c#update	( 0.017690)	( 0.004551)	( 0.003679)
Digest::CRC32Jam#update	( 0.017696)	( 0.004685)	( 0.003636)
Digest::CRC32MPEG#update	( 0.017663)	( 0.004937)	( 0.003790)
Digest::CRC32POSIX#update	( 0.017704)	( 0.004839)	( 0.003791)
Digest::CRC32XFER#update	( 0.017731)	( 0.004858)	( 0.003827)
Digest::CRC64#update	( 0.017776)	( 0.004971)	( 0.004435)
Digest::CRC64Jones#update	( 0.017718)	( 0.004897)	( 0.004274)
Digest::CRC64XZ#update	( 0.017697)	( 0.004946)	( 0.004311)

Finally, FreeBSD uses clang, so if built with GCC 13, the results will be different. Only the CRC-32 results are excerpted.

% gmake -C ext/digest/crc CC=gcc13 'cflags=$(optflags) $(debugflags) $(warnflags)' 'warnflags=-Wall -Wextra -Wundef' clean all

gcc13 sarwate
Digest::CRC32#update          0.017745   0.000000   0.017745 (  0.017761)

gcc13 slicing-by-8
Digest::CRC32#update          0.003948   0.000000   0.003948 (  0.003921)

gcc13 slicing-by-16
Digest::CRC32#update          0.002824   0.000000   0.002824 (  0.002815)

Jul 13 '23 14:07 dearblue

Summary of changes:.

Dedicated functions for each CRC are now provided.
No longer provides generic functions.
The CRC-64 table is now 32 KiB, but I believe modern PC processors have L1 data caches of 64 KiB or more.
Extend spec check string to 19 bytes (also in commit message).

Tables are still generated at build time of the installation. As I wrote to https://github.com/postmodern/digest-crc/pull/42#discussion_r1265337971, including the tables in the repository will probably increase the GEM package size to around 400 KiB.

Jul 24 '23 13:07 dearblue

Table data is to be prepared in advance. However, ext/digest/gentable.rb will be kept for future extensions.

Also, I forgot to mention in the last change, "Slicing-by-16" is always used. This is because I don't know how to write a test that switches to "Slicing-by-8".

Aug 15 '23 05:08 dearblue