Hey everyone,
I hope you all are well, having the time of your lives!
Would anyone wish to help me develop plugins to speedup ReedSolomon?
I am feeling the dopamine high from finally finishing (mostly) my Reed Solomon implementation, both Erasure Coding from Backblaze [1] and Error Correction from ZXing [2]. I got decoding working correctly, with dataMatrix256 and QRCode, including corruption repair, within t/2 errors.
It is VERY SLOOOW, way to slow to use yet. I am working on writing plugins for the hot spots, which are on the decode side: GFPoly evaluateAt (40.1%), Decoder runEuclideanAlgorithm(38.5%), Decoder findErrorLocations(12.6%) and Decoder find ErrorMagnitudes(2.3%). At the bottom, an exposition of performance profiling the GF FEC code.
It is written in Squeak, my favorite all-time language environment. I have used it for over 20 years. It is so beautiful! The rule of development is #GetItWorking, #GetItWorkingRight #GetItWorkingFast.
If you are interested in checking out the code, go to http://squeak.org and grab squeak. Once you have it running, right click for the World Menu and select open...Monticello Browser. Add a new repository of type HTTP and enter the Cryptography repository.
MCHttpRepository location: ' https://www.squeaksource.com/Cryptography ' user: 'squeak' password: 'squeak'
Open a Workspace (World Menu -> Workspace) & run this code (paste into Workspace, select it and right click do it.):
Installer ss project: 'Cryptography'; install: 'ProCrypto-1-1-1'; install: 'ProCryptoTests-1-1-1'.
Now you can open a Browser to look at the code (categories: CryptographyRSFEC & CryptographyRSFECTests) or open a TestRunner to test it (World Menu -> *).
[1] Backblze RS erasure code - https://stackoverflow.com/posts/67696209/timeline
I am feeling the dopamine high from finally finishing (mostly) my Reed Solomon implementation. I got decoding working correctly, with dataMatrix256 and QRCode, including corruption repair, within t/2 errors. It is VERY SLOOOW, way to slow to use yet. There are speedups possible in writing a plugin for the hot spots, which are on the decode side: GFPoly evaluateAt (40.1%), Decoder runEuclideanAlgorithm(38.5%), Decoder findErrorLocations(12.6%) and Decoder find ErrorMagnitudes(2.3%).
It is written in Squeak, my favorite all-time language environment. I have used it for over 20 years. It is so beautiful! The rule of development is #GetItWorking, #GetItWorkingRight #GetItWorkingFast.
If you are interested in checking out the code, go to http://squeak.org and grab squeak. Once you have it running, right click for the World Menu and select open...Monticello Browser. Add a new repository of type HTTP and enter the Cryptography repository.
MCHttpRepository location: ' https://www.squeaksource.com/Cryptography ' user: 'squeak' password: 'squeak'
Open a Workspace (World Menu -> Workspace) & run this code (paste into Workspace, select it and right click do it.):
Installer ss project: 'Cryptography'; install: 'ProCrypto-1-1-1'; install: 'ProCryptoTests-1-1-1'.
Now you can open a Browser to look at the code (categories: CryptographyRSFEC & CryptographyRSFECTests) or open a TestRunner to test it (World Menu -> *).
[1] Backblaze Open-sources Reed-Solomon Erasure Coding Source Code - https://www.backblaze.com/blog/reed-solomon/ [2] ZXing github -https://github.com/zxing/zxing/tree/master/core/src/main/java/com/google/zxi...
---
From the comment on CryptographyRSErrorCorrection-rww.12.mcz...
Fixed decoding. Some test pass green (DataMatrix & QRCodes) with encoding, decoding AND error correction all working. So the algorithms are working correctly. #GetItWorking, #GetItWorkingRight #GetItWorkingFast. AztecParam GF is still failing.
Do not allow values equal to the max 256. it passes tests but it is VERY SLOOOW. Profilie looks like, top tree branches, then summary. I may need to pluginize both GF and GFPoly. The costly methods are in decode, with GF Polynomial evaluation, the Euclidean Algorithm, the Chein's search (#findErrorLocations) and the Forney's formula (#findErrorMagnitudes). In the leaves, I can see that OrderedColection access is expensive.
Top tree branches: [| 93.7% {136540ms} RSFECDecoder>>decode:twoS: [| 40.1% {58370ms} RSFECGenericGFPoly>>evaluateAt: [| 38.5% {56167ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees: [| 12.6% {18331ms} RSFECDecoder>>findErrorLocations: [| 2.3% {3423ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations: [ 5.4% {7842ms} RSFECReedSolomonTest>>corrupt:howMany:random:max:
**Leaves** 44.7% {65149ms} OrderedCollection>>at: 12.8% {18619ms} SmallInteger(Number)>>positive 8.0% {11589ms} RSFECGenericGF>>addOrSubtract:by: 5.7% {8332ms} RSFECGenericGF>>multiply:by: 5.0% {7352ms} RSFECGenericGFPoly>>evaluateAt: 5.0% {7270ms} OrderedCollection>>at:put: 4.6% {6727ms} False>>| 1.7% {2537ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.4% {1996ms} OrderedCollection(SequenceableCollection)>>replaceFrom:to:with:startingAt: 1.3% {1851ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 1.1% {1562ms} LargePositiveInteger(Integer)>>bitShift:
**Memory** old -16,777,216 bytes young +15,072,816 bytes used -1,704,400 bytes free -15,072,816 bytes
**GCs** full 2 totalling 171 ms (0.12% uptime), avg 85.5 ms incr 4193 totalling 764 ms (0.5% uptime), avg 0.2 ms tenures 6,093 (avg 0 GCs/tenure) root table 0 overflows
--
Kindly, Robert
Whoops, I repeated myself. So sorry. The pertinent profiling for Error Correction is:
Do not allow values equal to the max 256. it passes tests but it is VERY SLOOOW. Profile looks like, top tree branches, then summary. I may need to pluginize both GF and GFPoly. The costly methods are in decode, with GF Polynomial evaluation, the Euclidean Algorithm, the Chein's search (#findErrorLocations) and the Forney's formula (#findErrorMagnitudes). In the leaves, I can see that OrderedColection access is expensive.
Top tree branches: [| 93.7% {136540ms} RSFECDecoder>>decode:twoS: [| 40.1% {58370ms} RSFECGenericGFPoly>>evaluateAt: [| 38.5% {56167ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees: [| 12.6% {18331ms} RSFECDecoder>>findErrorLocations: [| 2.3% {3423ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations: [ 5.4% {7842ms} RSFECReedSolomonTest>>corrupt:howMany:random:max:
**Leaves** 44.7% {65149ms} OrderedCollection>>at: 12.8% {18619ms} SmallInteger(Number)>>positive 8.0% {11589ms} RSFECGenericGF>>addOrSubtract:by: 5.7% {8332ms} RSFECGenericGF>>multiply:by: 5.0% {7352ms} RSFECGenericGFPoly>>evaluateAt: 5.0% {7270ms} OrderedCollection>>at:put: 4.6% {6727ms} False>>| 1.7% {2537ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.4% {1996ms} OrderedCollection(SequenceableCollection)>>replaceFrom:to:with:startingAt: 1.3% {1851ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 1.1% {1562ms} LargePositiveInteger(Integer)>>bitShift:
**Memory** old -16,777,216 bytes young +15,072,816 bytes used -1,704,400 bytes free -15,072,816 bytes
**GCs** full 2 totalling 171 ms (0.12% uptime), avg 85.5 ms incr 4193 totalling 764 ms (0.5% uptime), avg 0.2 ms tenures 6,093 (avg 0 GCs/tenure) root table 0 overflows
Kindly, Robert
Speedup work: I converted OrderedCollection use to Array use to improve #at: lookup and #at:put: set calls. Code is published to Cryptography. OrderedCollection has fallen off the leaves, from profiling. Plugin support is next...
**Leaves** 26.5% {29474ms} RSFECGenericGF>>addOrSubtract:by: 8.4% {9341ms} SmallInteger(Number)>>positive 7.3% {8067ms} False>>| 7.1% {7941ms} RSFECGenericGF>>multiply:by: 6.7% {7435ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 3.2% {3513ms} RSErasureGalois>>add:by: 3.1% {3500ms} SmallInteger>>digitAt: 3.1% {3481ms} RSErasureGalois>>tableMultiply:by: 2.9% {3263ms} RSFECGenericGFPoly>>evaluateAt: 2.8% {3130ms} SmallInteger(Integer)>>twosComplement 2.4% {2723ms} RSErasureGalois>>galoisMultiply:by: 2.1% {2350ms} SmallInteger>>digitLength 1.6% {1789ms} RSErasureGaloisTest(TestCase)>>assert:equals: 1.5% {1713ms} RSErasureGaloisTest(TestCase)>>assert:description: 1.5% {1699ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.5% {1674ms} Array(SequenceableCollection)>>do: 1.4% {1523ms} LargePositiveInteger(Integer)>>bitShift: 1.3% {1411ms} LargePositiveInteger class(Behavior)>>new: 1.1% {1269ms} SmallInteger(Integer)>>areAllBitsSet 1.1% {1218ms} SecureHashAlgorithm>>hashInteger:seed:
Kindly, Robert
On 5/26/21 1:52 PM, Robert Withers wrote:
Whoops, I repeated myself. So sorry. The pertinent profiling for Error Correction is:
Do not allow values equal to the max 256. it passes tests but it is VERY SLOOOW. Profile looks like, top tree branches, then summary. I may need to pluginize both GF and GFPoly. The costly methods are in decode, with GF Polynomial evaluation, the Euclidean Algorithm, the Chein's search (#findErrorLocations) and the Forney's formula (#findErrorMagnitudes). In the leaves, I can see that OrderedColection access is expensive.
Top tree branches: [| 93.7% {136540ms} RSFECDecoder>>decode:twoS: [| 40.1% {58370ms} RSFECGenericGFPoly>>evaluateAt: [| 38.5% {56167ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees: [| 12.6% {18331ms} RSFECDecoder>>findErrorLocations: [| 2.3% {3423ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations: [ 5.4% {7842ms} RSFECReedSolomonTest>>corrupt:howMany:random:max:
**Leaves** 44.7% {65149ms} OrderedCollection>>at: 12.8% {18619ms} SmallInteger(Number)>>positive 8.0% {11589ms} RSFECGenericGF>>addOrSubtract:by: 5.7% {8332ms} RSFECGenericGF>>multiply:by: 5.0% {7352ms} RSFECGenericGFPoly>>evaluateAt: 5.0% {7270ms} OrderedCollection>>at:put: 4.6% {6727ms} False>>| 1.7% {2537ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.4% {1996ms} OrderedCollection(SequenceableCollection)>>replaceFrom:to:with:startingAt: 1.3% {1851ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 1.1% {1562ms} LargePositiveInteger(Integer)>>bitShift:
**Memory** old -16,777,216 bytes young +15,072,816 bytes used -1,704,400 bytes free -15,072,816 bytes
**GCs** full 2 totalling 171 ms (0.12% uptime), avg 85.5 ms incr 4193 totalling 764 ms (0.5% uptime), avg 0.2 ms tenures 6,093 (avg 0 GCs/tenure) root table 0 overflows
Kindly, Robert
More versions published with more speedups. Using GF>>#maskValue: & GF>>normalizeIndex: methods, to provide separate solutions for in-image code and plugin code, with the differing index start. These could be easily pluginized, me thinks.
**Leaves** 26.4% {25447ms} RSFECGenericGF>>exp: 14.0% {13505ms} RSFECGenericGF>>maskValue: 12.1% {11689ms} RSFECGenericGF>>addOrSubtract:by: 11.5% {11073ms} RSFECGenericGF>>log: 9.6% {9306ms} RSFECGenericGF>>normalizeIndex: 6.9% {6617ms} RSFECGenericGF>>multiply:by: 3.4% {3247ms} RSFECGenericGFPoly>>evaluateAt: 1.8% {1764ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 1.8% {1698ms} RSFECGenericGFPoly>>addOrSubtractPoly:
Kindly, Robert
On 5/26/21 3:54 PM, Robert Withers wrote:
Speedup work: I converted OrderedCollection use to Array use to improve #at: lookup and #at:put: set calls. Code is published to Cryptography. OrderedCollection has fallen off the leaves, from profiling. Plugin support is next...
**Leaves** 26.5% {29474ms} RSFECGenericGF>>addOrSubtract:by: 8.4% {9341ms} SmallInteger(Number)>>positive 7.3% {8067ms} False>>| 7.1% {7941ms} RSFECGenericGF>>multiply:by: 6.7% {7435ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 3.2% {3513ms} RSErasureGalois>>add:by: 3.1% {3500ms} SmallInteger>>digitAt: 3.1% {3481ms} RSErasureGalois>>tableMultiply:by: 2.9% {3263ms} RSFECGenericGFPoly>>evaluateAt: 2.8% {3130ms} SmallInteger(Integer)>>twosComplement 2.4% {2723ms} RSErasureGalois>>galoisMultiply:by: 2.1% {2350ms} SmallInteger>>digitLength 1.6% {1789ms} RSErasureGaloisTest(TestCase)>>assert:equals: 1.5% {1713ms} RSErasureGaloisTest(TestCase)>>assert:description: 1.5% {1699ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.5% {1674ms} Array(SequenceableCollection)>>do: 1.4% {1523ms} LargePositiveInteger(Integer)>>bitShift: 1.3% {1411ms} LargePositiveInteger class(Behavior)>>new: 1.1% {1269ms} SmallInteger(Integer)>>areAllBitsSet 1.1% {1218ms} SecureHashAlgorithm>>hashInteger:seed:
Kindly, Robert
On 5/26/21 1:52 PM, Robert Withers wrote:
Whoops, I repeated myself. So sorry. The pertinent profiling for Error Correction is:
Do not allow values equal to the max 256. it passes tests but it is VERY SLOOOW. Profile looks like, top tree branches, then summary. I may need to pluginize both GF and GFPoly. The costly methods are in decode, with GF Polynomial evaluation, the Euclidean Algorithm, the Chein's search (#findErrorLocations) and the Forney's formula (#findErrorMagnitudes). In the leaves, I can see that OrderedColection access is expensive.
Top tree branches: [| 93.7% {136540ms} RSFECDecoder>>decode:twoS: [| 40.1% {58370ms} RSFECGenericGFPoly>>evaluateAt: [| 38.5% {56167ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees: [| 12.6% {18331ms} RSFECDecoder>>findErrorLocations: [| 2.3% {3423ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations: [ 5.4% {7842ms} RSFECReedSolomonTest>>corrupt:howMany:random:max:
**Leaves** 44.7% {65149ms} OrderedCollection>>at: 12.8% {18619ms} SmallInteger(Number)>>positive 8.0% {11589ms} RSFECGenericGF>>addOrSubtract:by: 5.7% {8332ms} RSFECGenericGF>>multiply:by: 5.0% {7352ms} RSFECGenericGFPoly>>evaluateAt: 5.0% {7270ms} OrderedCollection>>at:put: 4.6% {6727ms} False>>| 1.7% {2537ms} RSFECGenericGFPoly>>addOrSubtractPoly: 1.4% {1996ms} OrderedCollection(SequenceableCollection)>>replaceFrom:to:with:startingAt: 1.3% {1851ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: 1.1% {1562ms} LargePositiveInteger(Integer)>>bitShift:
**Memory** old -16,777,216 bytes young +15,072,816 bytes used -1,704,400 bytes free -15,072,816 bytes
**GCs** full 2 totalling 171 ms (0.12% uptime), avg 85.5 ms incr 4193 totalling 764 ms (0.5% uptime), avg 0.2 ms tenures 6,093 (avg 0 GCs/tenure) root table 0 overflows
Kindly, Robert
cryptography@lists.squeakfoundation.org
-
Robert Withers