reedsolomon 0.0.1.2 → 0.0.2.0
raw patch · 9 files changed
+188/−116 lines, 9 filesdep −cpudep ~exceptionsdep ~mtl
Dependencies removed: cpu
Dependency ranges changed: exceptions, mtl
Files
- README.md +30/−9
- bench/Main.hs +12/−24
- cbits/configure +10/−10
- cbits/reedsolomon.h +12/−0
- cbits/reedsolomon_dispatch.c +72/−47
- examples/simple-bench.hs +3/−0
- reedsolomon.cabal +10/−4
- src/Data/ReedSolomon.lhs +30/−0
- test/Galois.lhs +9/−22
README.md view
@@ -23,18 +23,39 @@ Here are the throughput numbers with some different selections of data and parity shards. For reference each shard is 1MB random data, and 1 CPU core is used for encoding. -| Data | Parity | Parity | SSSE3 MB/s | AVX2 MB/s |-|------|--------|--------|------------|-----------|-| 5 | 2 | 40% | 3641,66 | 3987,24 |-| 10 | 2 | 20% | 3951,01 | 4444,44 |-| 10 | 4 | 40% | 1821,16 | 1927,90 |-| 50 | 20 | 40% | 398,09 | 431,78 |+<table>+ <thead>+ <tr>+ <th>Data</th>+ <th>Parity</th>+ <th>Parity</th>+ <th>SSSE3 MB/s</th>+ <th>AVX2 MB/s</th>+ </tr>+ </thead>+ <tbody>+ <tr><td>5</td><td>2</td><td>40%</td><td>3641,66</td><td>3987,24</td></tr>+ <tr><td>10</td><td>2</td><td>20%</td><td>3951,01</td><td>4444,44</td></tr>+ <tr><td>10</td><td>4</td><td>40%</td><td>1821,16</td><td>1927,90</td></tr>+ <tr><td>50</td><td>20</td><td>40%</td><td>398,09</td><td>431,78</td></tr>+ </tbody>+</table> Example of performance on Intel(R) Core(TM) i7-4600U CPU @ 3.30GHz - 2 physical cores, 4 logical cores (note: `/proc/cpuinfo` mentions 2.10GHz only). The example uses 10 blocks with 16MB data each and 4 parity blocks. -| Threads | SSSE3 MB/s | AVX2 MB/s | Speed |-|---------|------------|-----------|-------|-| 1 | 1551,89 | 1588,88 | 100% |+<table>+ <thead>+ <tr>+ <th>Threads</th>+ <th>SSSE3 MB/s</th>+ <th>AVX2 MB/s</th>+ <th>Speed</th>+ </tr>+ </thead>+ <tbody>+ <tr><td>1</td><td>1551,89</td><td>1588,88</td><td>100%</td></tr>+ </tbody>+</table> # Links * [Backblaze Open Sources Reed-Solomon Erasure Coding Source Code](https://www.backblaze.com/blog/reed-solomon/).
bench/Main.hs view
@@ -10,7 +10,6 @@ import Control.Monad.ST (ST) #ifdef SIMD-import Data.Bits ((.&.), shiftL) import Data.Maybe (catMaybes) #endif import Data.Word (Word8)@@ -19,13 +18,6 @@ import Foreign.C (CSize(..)) #endif -#ifdef SIMD-import System.Cpuid (cpuid)-# if RS_HAVE_AVX2-import System.Cpuid (cpuidWithIndex)-# endif-#endif- import Criterion.Main import qualified Data.Vector.Generic as V@@ -34,27 +26,23 @@ #ifdef SIMD import qualified Data.Vector.Generic.Sized as S+import Data.ReedSolomon (SIMDInstructions(..)) #endif+import qualified Data.ReedSolomon as RS import qualified Data.ReedSolomon.Galois.NoAsm as NoAsm #ifdef SIMD import qualified Data.ReedSolomon.Galois.Amd64 as Amd64 #endif main :: IO ()-#ifdef SIMD main = do- (_, _, ecx1, edx1) <- cpuid 1- let avx = ecx1 .&. (1 `shiftL` 28) /= 0- ssse3 = ecx1 .&. (1 `shiftL` 9) /= 0- sse2 = edx1 .&. (1 `shiftL` 26) /= 0- dependOn b c = if b then Just c else Nothing-# if RS_HAVE_AVX2- (_, ebx7, _, _) <- cpuidWithIndex 7 0- let avx2 = ebx7 .&. (1 `shiftL` 5) /= 0-# endif-#else-main =+ level <- RS.simdInstructions+ putStrLn $ "Native instructions: " ++ maybe "None" show level++#ifdef SIMD+ let dependOn l prop = maybe Nothing (\lvl -> if l <= lvl then Just prop else Nothing ) level #endif+ defaultMain [ bgroup "Galois/galMulSlice/1048576" [ bench "NoAsm" $ whnf (benchGalMulSlice NoAsm.galMulSlice 177) v1048576@@ -66,11 +54,11 @@ , bgroup "reedsolomon_gal_mul" $ catMaybes [ Just $ bench "Native" $ whnf (benchRGM c_reedsolomon_gal_mul) v1048576 #if RS_HAVE_AVX2- , dependOn avx2 $ bench "AVX2" $ whnf (benchRGM c_reedsolomon_gal_mul_avx2) v1048576+ , dependOn AVX2 $ bench "AVX2" $ whnf (benchRGM c_reedsolomon_gal_mul_avx2) v1048576 #endif- , dependOn avx $ bench "AVX" $ whnf (benchRGM c_reedsolomon_gal_mul_avx) v1048576- , dependOn ssse3 $ bench "SSSE3" $ whnf (benchRGM c_reedsolomon_gal_mul_ssse3) v1048576- , dependOn sse2 $ bench "SSE2" $ whnf (benchRGM c_reedsolomon_gal_mul_sse2) v1048576+ , dependOn AVX $ bench "AVX" $ whnf (benchRGM c_reedsolomon_gal_mul_avx) v1048576+ , dependOn SSSE3 $ bench "SSSE3" $ whnf (benchRGM c_reedsolomon_gal_mul_ssse3) v1048576+ , dependOn SSE2 $ bench "SSE2" $ whnf (benchRGM c_reedsolomon_gal_mul_sse2) v1048576 , Just $ bench "Generic" $ whnf (benchRGM c_reedsolomon_gal_mul_generic) v1048576 ] #endif
cbits/configure view
@@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles.-# Generated by GNU Autoconf 2.69 for reedsolomon 0.0.1.2.+# Generated by GNU Autoconf 2.69 for reedsolomon 0.0.2.0. # # Report bugs to <https://github.com/NicolasT/reedsolomon/issues>. #@@ -590,8 +590,8 @@ # Identity of this package. PACKAGE_NAME='reedsolomon' PACKAGE_TARNAME='reedsolomon'-PACKAGE_VERSION='0.0.1.2'-PACKAGE_STRING='reedsolomon 0.0.1.2'+PACKAGE_VERSION='0.0.2.0'+PACKAGE_STRING='reedsolomon 0.0.2.0' PACKAGE_BUGREPORT='https://github.com/NicolasT/reedsolomon/issues' PACKAGE_URL='https://github.com/NicolasT/reedsolomon' @@ -1316,7 +1316,7 @@ # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF-\`configure' configures reedsolomon 0.0.1.2 to adapt to many kinds of systems.+\`configure' configures reedsolomon 0.0.2.0 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1386,7 +1386,7 @@ if test -n "$ac_init_help"; then case $ac_init_help in- short | recursive ) echo "Configuration of reedsolomon 0.0.1.2:";;+ short | recursive ) echo "Configuration of reedsolomon 0.0.2.0:";; esac cat <<\_ACEOF @@ -1495,7 +1495,7 @@ test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF-reedsolomon configure 0.0.1.2+reedsolomon configure 0.0.2.0 generated by GNU Autoconf 2.69 Copyright (C) 2012 Free Software Foundation, Inc.@@ -1972,7 +1972,7 @@ This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by reedsolomon $as_me 0.0.1.2, which was+It was created by reedsolomon $as_me 0.0.2.0, which was generated by GNU Autoconf 2.69. Invocation command line was $ $0 $@@@ -2840,7 +2840,7 @@ # Define the identity of the package. PACKAGE='reedsolomon'- VERSION='0.0.1.2'+ VERSION='0.0.2.0' cat >>confdefs.h <<_ACEOF@@ -13290,7 +13290,7 @@ # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log="-This file was extended by reedsolomon $as_me 0.0.1.2, which was+This file was extended by reedsolomon $as_me 0.0.2.0, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES@@ -13357,7 +13357,7 @@ cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\-reedsolomon config.status 0.0.1.2+reedsolomon config.status 0.0.2.0 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\"
cbits/reedsolomon.h view
@@ -15,6 +15,8 @@ PROTO(reedsolomon_gal_mul_avx2); PROTO(reedsolomon_gal_mul_xor_avx2);+PROTO(reedsolomon_gal_mul_avx);+PROTO(reedsolomon_gal_mul_xor_avx); PROTO(reedsolomon_gal_mul_ssse3); PROTO(reedsolomon_gal_mul_xor_ssse3); PROTO(reedsolomon_gal_mul_sse2);@@ -24,3 +26,13 @@ PROTO(reedsolomon_gal_mul); PROTO(reedsolomon_gal_mul_xor);++typedef enum {+ REEDSOLOMON_CPU_GENERIC = 0,+ REEDSOLOMON_CPU_SSE2 = 1,+ REEDSOLOMON_CPU_SSSE3 = 2,+ REEDSOLOMON_CPU_AVX = 3,+ REEDSOLOMON_CPU_AVX2 = 4,+} reedsolomon_cpu_support;++reedsolomon_cpu_support reedsolomon_determine_cpu_support(void);
cbits/reedsolomon_dispatch.c view
@@ -38,57 +38,82 @@ return 1; } +struct cpuid_registers {+ unsigned int eax, ebx, ecx, edx;+};++reedsolomon_cpu_support reedsolomon_determine_cpu_support(void) {+ struct cpuid_registers cpuid1 = { 0, 0, 0, 0 };+ unsigned int rc1 = 0;+ reedsolomon_cpu_support result = REEDSOLOMON_CPU_GENERIC;++ rc1 = __get_cpuid(1, &cpuid1.eax, &cpuid1.ebx, &cpuid1.ecx, &cpuid1.edx);++ if(rc1 == 0) {+ result = REEDSOLOMON_CPU_GENERIC;+ }+ else { #if RS_HAVE_AVX2-# define IFUNC_AVX2(n, result) \- do { \- int avx2_rc = 0; \- struct { \- unsigned int eax, ebx, ecx, edx; \- } cpuid7 = { 0, 0, 0, 0 }; \- \- avx2_rc = __get_cpuid_count(7, 0, &cpuid7.eax, &cpuid7.ebx, &cpuid7.ecx, &cpuid7.edx); \- \- if(avx2_rc != 0 && (cpuid7.ebx & bit_AVX2) != 0) { \- LOG("reedsolomon: using " #n "_avx2"); \- result = n ## _avx2; \- } \- } while(0)+ struct cpuid_registers cpuid7 = { 0, 0, 0, 0 };+ unsigned int rc7 = 0;++ rc7 = __get_cpuid_count(7, 0, &cpuid7.eax, &cpuid7.ebx, &cpuid7.ecx, &cpuid7.edx);+ if(rc7 != 0 && (cpuid7.ebx & bit_AVX2) != 0) {+ result = REEDSOLOMON_CPU_AVX2;+ }+ else { #else-# define IFUNC_AVX2(n, result)+ if(1) { #endif+ if((cpuid1.ecx & bit_AVX) != 0) {+ result = REEDSOLOMON_CPU_AVX;+ }+ else if((cpuid1.ecx & bit_SSSE3) != 0) {+ result = REEDSOLOMON_CPU_SSSE3;+ }+ else if((cpuid1.edx & bit_SSE2) != 0) {+ result = REEDSOLOMON_CPU_SSE2;+ }+ else {+ result = REEDSOLOMON_CPU_GENERIC;+ }+ }+ } -#define IFUNC(n, proto) \- static proto n ## _ifunc(void) { \- struct { \- unsigned int eax, ebx, ecx, edx; \- } cpuid1 = { 0, 0, 0, 0 }; \- int rc = 0; \- proto func = NULL; \- \- rc = __get_cpuid(1, &cpuid1.eax, &cpuid1.ebx, &cpuid1.ecx, &cpuid1.edx); \- if(rc == 0) { \- LOG("reedsolomon: cpuid failed, using " #n "_generic"); \- func = n ## _generic; \- } \- else { \- IFUNC_AVX2(n, func); \- if(func == NULL) { \- if((cpuid1.ecx & bit_SSSE3) != 0) { \- LOG("reedsolomon: using " #n "_ssse3"); \- func = n ## _ssse3; \- } \- else if((cpuid1.edx & bit_SSE2) != 0) { \- LOG("reedsolomon: using " #n "_sse2"); \- func = n ## _sse2; \- } \- else { \- LOG("reedsolomon: using " #n "_generic"); \- func = n ## _generic; \- } \- } \- } \- \- return func; \+ return result;+}++#define CASE(n, lower, upper) \+ case REEDSOLOMON_CPU_ ## upper: { \+ LOG("reedsolomon: using " #n "_" #lower); \+ result = n ## _ ## lower; \+ } break++#if RS_HAVE_AVX2+# define MAYBE_AVX2(n) \+ CASE(n, avx2, AVX2)+#else+# define MAYBE_AVX2(n)+#endif++#define IFUNC(n, proto) \+ static proto n ## _ifunc(void) { \+ reedsolomon_cpu_support level = reedsolomon_determine_cpu_support(); \+ proto result = n ## _generic; \+ \+ switch(level) { \+ MAYBE_AVX2(n); \+ CASE(n, avx, AVX); \+ CASE(n, ssse3, SSSE3); \+ CASE(n, sse2, SSE2); \+ CASE(n, generic, GENERIC); \+ default: { \+ LOG("reedsolomon: using " #n "_generic"); \+ result = n ## _generic; \+ } \+ } \+ \+ return result; \ } typedef PROTO_RETURN(*gal_mul_proto)(PROTO_ARGS);
examples/simple-bench.hs view
@@ -45,6 +45,9 @@ let [dataShards, parityShards, dataSize] = fmap read args + instructionSet <- RS.simdInstructions+ printf "Using CPU instructions: %s\n" (maybe "None" show instructionSet)+ putStrLn "generating encoder..." encoder <- RS.new dataShards parityShards
reedsolomon.cabal view
@@ -1,5 +1,5 @@ Name: reedsolomon-Version: 0.0.1.2+Version: 0.0.2.0 Synopsis: Reed-Solomon Erasure Coding in Haskell Description: Please see README.md Homepage: http://github.com/NicolasT/reedsolomon@@ -190,7 +190,6 @@ , exceptions , bytestring , profunctors- , cpu >= 0.1 && < 0.2 , tasty >= 0.10 && < 0.12 , tasty-hunit > 0.9 && < 0.10 , tasty-quickcheck >= 0.8 && < 0.9@@ -215,14 +214,21 @@ Hs-Source-Dirs: bench , src Main-Is: Main.hs- Other-Modules: Data.ReedSolomon.Galois.GenTables+ Other-Modules: Data.ReedSolomon+ , Data.ReedSolomon.Galois+ , Data.ReedSolomon.Galois.GenTables , Data.ReedSolomon.Galois.NoAsm+ , Data.ReedSolomon.Matrix+ , Data.Vector.Generic.Compat+ , Data.Vector.Generic.Exceptions+ , Data.Vector.Generic.Lifted , Data.Vector.Generic.Sized Build-Depends: base+ , mtl , vector , loop , primitive- , cpu >= 0.1 && < 0.2+ , exceptions , criterion >= 1.1 && < 1.2 , reedsolomon Default-Language: Haskell2010
src/Data/ReedSolomon.lhs view
@@ -33,6 +33,9 @@ > -- * Exceptions > , ShardType(..) > , ValueError(..)+> -- * Determining runtime SIMD instruction support+> , SIMDInstructions(..)+> , simdInstructions > ) where > > import Prelude hiding (any)@@ -45,6 +48,10 @@ > import Data.Typeable (Typeable) > import Data.Word >+#if SIMD+> import Foreign.C (CInt(..))+#endif+> > import Control.Monad.Catch (MonadThrow, throwM) > > import qualified Data.Vector as V (Vector, MVector)@@ -841,3 +848,26 @@ > | V.length shards < rsDataShards r = throwM (InvalidNumberOfShards DataShard $ V.length shards) > | V.sum (V.map V.length shards) < outSize = throwM InvalidDataSize > | otherwise = return $ V.take outSize $ V.concat $ V.toList shards++> -- | Enumeration of SIMD instruction sets.+> data SIMDInstructions = Generic+> | SSE2+> | SSSE3+> | AVX+> | AVX2+> deriving (Show, Eq, Ord, Enum, Bounded)+>+> -- | Retrieve the SIMD instruction set used by 'native' Galois field operations.+> --+> -- Returns 'Nothing' when the library is compiled without SIMD support,+> -- otherwise 'Just' the runtime-determined SIMD instruction set used for+> -- optimized Galois field calculations.+> simdInstructions :: IO (Maybe SIMDInstructions)+> simdInstructions =+#if !SIMD+> return Nothing+#else+> (Just . toEnum . fromIntegral) `fmap` c_reedsolomon_determine_cpu_support+>+> foreign import ccall unsafe "reedsolomon_determine_cpu_support" c_reedsolomon_determine_cpu_support :: IO CInt+#endif
test/Galois.lhs view
@@ -12,7 +12,6 @@ > > import Control.Monad (foldM, void, when) #ifdef SIMD-> import Data.Bits ((.&.), shiftL) > import Data.Maybe (catMaybes) #endif > import Data.Word (Word8)@@ -28,13 +27,6 @@ > import qualified Data.Vector.Generic.Mutable as MV > import qualified Data.Vector.Storable as SV >-#ifdef SIMD-> import System.Cpuid (cpuid)-# if RS_HAVE_AVX2-> import System.Cpuid (cpuidWithIndex)-# endif-#endif-> > import Test.Tasty (TestTree, testGroup) > import Test.Tasty.HUnit (Assertion, (@?=), testCase) #ifdef SIMD@@ -47,6 +39,8 @@ > #ifdef SIMD > import qualified Data.Vector.Generic.Sized as S+> import qualified Data.ReedSolomon as RS+> import Data.ReedSolomon (SIMDInstructions(..)) #endif > import Data.ReedSolomon.Galois > import qualified Data.ReedSolomon.Galois.NoAsm as NoAsm@@ -412,14 +406,14 @@ > , testGroup "cbits" [ > testGroup "reedsolomon_gal_mul" $ catMaybes [ #if RS_HAVE_AVX2-> dependOn avx2 $ testProperty "native/avx2" $+> dependOn AVX2 $ testProperty "native/avx2" $ > reedsolomonGalMulEquivalence c_rgm c_rgm_avx2, #endif-> dependOn avx $ testProperty "native/avx" $+> dependOn AVX $ testProperty "native/avx" $ > reedsolomonGalMulEquivalence c_rgm c_rgm_avx-> , dependOn ssse3 $ testProperty "native/ssse3" $+> , dependOn SSSE3 $ testProperty "native/ssse3" $ > reedsolomonGalMulEquivalence c_rgm c_rgm_ssse3-> , dependOn sse2 $ testProperty "native/sse2" $+> , dependOn SSE2 $ testProperty "native/sse2" $ > reedsolomonGalMulEquivalence c_rgm c_rgm_sse2 > , Just $ testProperty "native/generic" $ > reedsolomonGalMulEquivalence c_rgm c_rgm_generic@@ -428,15 +422,8 @@ > ] #endif > ]-#ifdef SIMD+#if SIMD > where-> (_, _, ecx1, edx1) = unsafePerformIO $ cpuid 1-#if RS_HAVE_AVX2-> (_, ebx7, _, _) = unsafePerformIO $ cpuidWithIndex 7 0-> avx2 = ebx7 .&. (1 `shiftL` 5) /= 0-#endif-> avx = ecx1 .&. (1 `shiftL` 28) /= 0-> ssse3 = ecx1 .&. (1 `shiftL` 9) /= 0-> sse2 = edx1 .&. (1 `shiftL` 26) /= 0-> dependOn b c = if b then Just c else Nothing+> level = unsafePerformIO RS.simdInstructions+> dependOn l prop = maybe Nothing (\lvl -> if l <= lvl then Just prop else Nothing) level #endif