[Cryptography Team] Reed Solomon Erasure Coding and Error Correction

[Robert Withers]

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
>