| 1 |
Goals |
| 2 |
----- |
| 3 |
|
| 4 |
1. Performance. In distributed systems the data is CRC'ed |
| 5 |
on every breath in and out, and often multiple times. |
| 6 |
Having entire cluster spend 10% of all CPU computing |
| 7 |
CRCs is not something unheard of. |
| 8 |
|
| 9 |
2. Functionality. Computing CRC is not enough. Oftentimes, |
| 10 |
distributed systems need to perform various operations |
| 11 |
using known CRC values (concatenation, data replacement, |
| 12 |
etc.) without touching the actual data. |
| 13 |
|
| 14 |
3. Functionality verification: ability to catch even the most |
| 15 |
subtle bugs in CRC implementation. |
| 16 |
|
| 17 |
4. Performance benchmarking: ability to evaluate performance |
| 18 |
of known CRC algorithms and choose the right one for given |
| 19 |
architecture and/or compiler. |
| 20 |
|
| 21 |
5. Support most popular and most advanced CPUs [typically |
| 22 |
used in distributed environments]. That is, AMD64 and X86. |
| 23 |
|
| 24 |
6. Support most popular compilers used to compile code running |
| 25 |
in distributed environments. That is, Microsoft's CL, GCC, |
| 26 |
and Intel's ICL. |
| 27 |
|
| 28 |
7. Ability to easily (at run-time) create CRCs for arbitrary |
| 29 |
generating polynomials. Many complex projects have to deal |
| 30 |
with multiple CRC generating polynomials. Adding support |
| 31 |
yet another one should be 1-line change, not 2-week journey. |
| 32 |
|
| 33 |
|
| 34 |
Caveats |
| 35 |
------- |
| 36 |
|
| 37 |
1. Only little-endian CPUs are supported. Reason: all the |
| 38 |
optimizations makes sense only when CPU has multiple ALUs |
| 39 |
and may execute multiple instructions in parallel. I cannot |
| 40 |
easily recall big-endian CPUs like that (probably PPC and |
| 41 |
IBM's Z-series?) -- and, unless CPU is powerful enough, |
| 42 |
trivial byte-by-byte Sarwate algorithm is hard to beat. |
| 43 |
|
| 44 |
2. The only CPUs the code was tested are AMD64 and X86 family. |
| 45 |
I do not have access to Itanium. I tried to do my best to |
| 46 |
allow the code to work on Itanium as is, but I will not |
| 47 |
be very surprised if I overlooked something. |
| 48 |
|
| 49 |
|
| 50 |
How it all works |
| 51 |
---------------- |
| 52 |
|
| 53 |
Please read crc.pdf in "docs" directory -- it explains, slowly, |
| 54 |
step-by-step, how it all works, and provides small listings |
| 55 |
of respective algorithms that (hopefully, clearly) demonstrate |
| 56 |
how specific algorithm is implemented -- actual implementation |
| 57 |
is heavily optimized, a lot of loops are unrolled, and comments |
| 58 |
explain only the most subtle details of implementation. |
| 59 |
|
| 60 |
|
| 61 |
Usage |
| 62 |
----- |
| 63 |
|
| 64 |
"unittest.cc" is standalone unit test which perform extensive |
| 65 |
functionality validation and also tests performance of key scenarios. |
| 66 |
Please keep in mind that it takes almost a minute for GCC to compile |
| 67 |
it. Full performance test takes a couple of hours. |
| 68 |
|
| 69 |
"generic_crc.h" provides a set of implemenations of generic CRCs. |
| 70 |
"crc32c*" set of files implements CRC using Intel's CRC32 instruction. |
| 71 |
"multiword*" set of files implements specialized -- and heavily |
| 72 |
optimized -- versions of multiword CRC. |
| 73 |
|
| 74 |
However, including these files directly into your project may be |
| 75 |
a bad idea -- there is a lot of quite heavy-weight template code |
| 76 |
that you probably do not want to see included into every file that |
| 77 |
uses CRCs. |
| 78 |
|
| 79 |
Instead, use "interface.h" which hides all the details of the |
| 80 |
implementation. It declares on namespace, two types in that |
| 81 |
namespace, and brings in a couple of standard ANSI C headers. |
| 82 |
|
| 83 |
Another advantage of using "interface.h" is that actual |
| 84 |
implementation will pick the most efficient implementation |
| 85 |
of CRC for specific platform and compiler (applies to |
| 86 |
AMD64 and X86 platform and CL, ICL, and GCC compilers only). |
| 87 |
|
| 88 |
Please see "usage.cc" which provides an example how to use |
| 89 |
crcutil_interface::CRC class. |
| 90 |
|
| 91 |
|
| 92 |
Compiler optimization settings |
| 93 |
------------------------------ |
| 94 |
|
| 95 |
Recommended compiler flags: |
| 96 |
CL: -O2 -Wall |
| 97 |
ICL: -O3 -Wall -Qdiag-disable:181 -Qdiag-disable:185 -Qdiag-disable:442 -Qdiag-disable:vec |
| 98 |
GCC 4.5+: -O3 -Wall -msse2 -mcrc32 |
| 99 |
GCC 4.4-, AMD64: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1 |
| 100 |
GCC 4.4-, I386: -O3 -Wall -msse2 -DCRCUTIL_USE_MM_CRC32=1 -fomit-frame-pointer |
| 101 |
|
| 102 |
|
| 103 |
Compile-time constants |
| 104 |
---------------------- |
| 105 |
|
| 106 |
CRCUTIL_USE_ASM |
| 107 |
Allows the use of inline ASM for GCC on AMD64 and I386 platforms, |
| 108 |
32-bit Intel and Microsoft compilers on Windows. |
| 109 |
|
| 110 |
See multiword*.cc files. |
| 111 |
|
| 112 |
By default, turned on. |
| 113 |
|
| 114 |
|
| 115 |
HAVE_MMX |
| 116 |
MMX and respective intrinsics are available. When MMX is available, it |
| 117 |
will be used on I386 platform to speed up computation of up to 64-bit |
| 118 |
CRCs (1.3 CPU cycles/byte, see see *i386_mmx.cc files). |
| 119 |
|
| 120 |
By default, enabled on AMD64 and I386 platforms, disabled otherwise. |
| 121 |
|
| 122 |
|
| 123 |
HAVE_SSE |
| 124 |
By default, enabled on AMD64 and I386 platforms, disabled otherwise. |
| 125 |
|
| 126 |
|
| 127 |
HAVE_SSE2 |
| 128 |
By default, enabled on AMD64 and I386 platforms, disabled otherwise. |
| 129 |
|
| 130 |
Allows the use of SSE2 instructions to compute 128-bit CRCs efficiently |
| 131 |
(see uint128_sse2.h, multiword_128_64_gcc_amd64_sse2.cc). |
| 132 |
|
| 133 |
|
| 134 |
CRCUTIL_PREFETCH_WIDTH |
| 135 |
Prefetch width (default is 0 -- read platform.h to see why). |
| 136 |
|
| 137 |
When CRCUTIL_PREFETCH_WIDTH > 0 and HAVE_SSE, the code will try to |
| 138 |
prefetch CRCUTIL_PREFETCH_WIDTH bytes ahead. |
| 139 |
|
| 140 |
|
| 141 |
CRCUTIL_MIN_ALIGN_SIZE |
| 142 |
Align input pointer on word boundary when input length exceeds |
| 143 |
CRCUTIL_MIN_ALIGN_SIZE bytes and when CRC implementation will read |
| 144 |
input data by words. |
| 145 |
|
| 146 |
Non-AMD64/I386 do not allow misaligned reads, so default value of |
| 147 |
CRCUTIL_MIN_ALIGN_SIZE is 0. |
| 148 |
|
| 149 |
On AMD64 and I386 platforms, default value is 1KB. Even though AMD64 |
| 150 |
and I386 allow non-aligned reads, crossing cache line boundary is not |
| 151 |
free, and it makes sense to align large inputs first before processing |
| 152 |
them (see generic_crc.h for more details). |
| 153 |
|
| 154 |
|
| 155 |
CRCUTIL_USE_MM_CRC32 |
| 156 |
Allows the use SSE4.2 crc32 instruction when computing CRC32C (0.13 CPU |
| 157 |
cycles per byte, see crc32c_sse4* files). |
| 158 |
|
| 159 |
If set to false (i.e. 0), _mm_crc32_u*() intrinsics will be simulated |
| 160 |
(useful for debugging crc32_sse4 code on machines that do not support |
| 161 |
SSE 4.2). |
| 162 |
|
| 163 |
Hardware-assisted CRC32C is supported on AMD64 and I386 platforms only. |
| 164 |
|
| 165 |
By default, enabled for Windows and for "g++ -msse4". |
| 166 |
|
| 167 |
With GCC 4.5, it is possible to compile the code using "-msse2 -mcrc32 |
| 168 |
-DCRCUTIL_USE_MM_CRC32=1" flags. |
| 169 |
|
| 170 |
GCC 4.4 and earlier do not support "-mcrc32" flag, but it is still |
| 171 |
possible to use crc32c_sse4 code by compiling the code using "-msse2 |
| 172 |
-DCRCUTIL_USE_MM_CRC32=1" flags. In this case, inline asm code will be |
| 173 |
used (see crc32c_sse4_intrin.h). |
| 174 |
|
| 175 |
|
| 176 |
CRCUTIL_FORCE_ASM_CRC32C |
| 177 |
GCC 4.4 and earlier versions do not have -mcrc32 flag, so |
| 178 |
_mm_crc32_u64/32/8 intrinsics there are not available from standard |
| 179 |
headers. They are replaced by inline asm code (see |
| 180 |
crc32c_sse4_intrin.h). To test backward compatibility using GCC 4.5+, |
| 181 |
use "-Wall -O3 -msse2 --DCRCUTIL_USE_MM_CRC32=1 |
| 182 |
-DCRCUTIL_FORCE_ASM_CRC32C=1". |
| 183 |
|
| 184 |
|
| 185 |
[The end of the document] |