[Vm-dev] Reed Solomon plugins & performance slow down

[Robert Withers]

Yes! Thanks so much! I made your suggested changes, every type to "char", including the #declareCVarsIn: changes to #var:type:array: and here are the results, with a 407% speedup, with and without RSFECPlugin. I dropped the RSErasure tests from the profiling.

If only I could pluginize #findErrorLocations: and #findErrorMagnitudes:errorLocations:. Perhaps #newField:coefficients:, as well. I do not think #decode:twoS: is pluginizable due to complex object instantiation. What are your thoughts? Can we squeeze it down further?

> WITH PLUGIN
>
> - 22437 tallies, 22876 msec.
>
> **Leaves**
> 28.8% {6577ms} RSFECDecoder>>decode:twoS:
> 12.7% {2904ms} RSFECGenericGFPoly class>>newField:coefficients:
> 9.2% {2095ms} RSFECDecoder>>findErrorLocations:
> 3.3% {766ms} RSFECGenericGFWithPlugin>>multiply:by:
> 1.8% {411ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations:
> 1.6% {363ms} RSFECGenericGFWithPlugin>>inverse:
> 1.2% {265ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees:

and...

> WITHOUT PLUGIN
>
> - 91190 tallies, 93245 msec.
>
> **Leaves**
> 26.0% {24256ms} RSFECGenericGF>>exp:
> 13.7% {12778ms} RSFECGenericGF>>maskValue:
> 12.8% {11945ms} RSFECGenericGF>>addOrSubtract:by:
> 10.8% {10094ms} RSFECGenericGF>>log:
> 9.2% {8615ms} RSFECGenericGF>>normalizeIndex:
> 7.4% {6873ms} RSFECGenericGF>>multiply:by:
> 3.8% {3513ms} RSFECGenericGFPoly>>evaluateAt:
> 2.2% {2079ms} RSFECGenericGFPoly>>addOrSubtractPoly:
> 2.2% {2040ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient:

---
Kindly,
Robert

On 6/2/21 10:40 AM, Levente Uzonyi wrote:

> Hi Robert,
>
> On Tue, 1 Jun 2021, Robert Withers wrote:
>
>> Hey ya, Levente,
>>
>> Woot!!! I was able to get all the primitives working with ByteArrays. Everything is passing green! (except for several GF fields: Aztec and Maxicode and QRCode) I think I will primitize one of the codingLoops on the RSErasure
>> side. Here are the numbers.  Take note of the tallies and time: 50 seconds versus 114 seconds. I updated the squeak wiki Cryptography page (
>> http://wiki.squeak.org/squeak/5776
>> ) with d/l links to the plugins. Here are those
>
> Brilliant. ByteArray is indeed the optimal choice there.
>
> Let me answer your question in your previous email here:
> AFAIK, on all the currently supported platforms and C compilers, unsigned
> int is 32-bits, so it matches WordArray in Squeak.
> DoubleWordArray is 64-bits, and in C that matches the type unsigned long long (on the currently supported platforms and compilers).
>
> I think you can shave off a few more seconds there by adding those
> <inline: #always> pragmas to the methods the primitive methods send
> either directly or indirectly.
>
> And, I think the logTable and expTable variables can be declared as
> constant as well as unsigned char arrays instead of unsigned int arrays.
> That might give more opportunities to the C compiler to optimize the code.
>
> I prefer to use #var:type:array: instead of #var:declareC: when possible.
> E.g.
>
>	cg
>		var: #logTable declareC: 'unsigned int logTable[256] = {
> 0, 0, 1, 240, 2, 225, 241, 53, 3, 38, 226, 133, 242, 43, 54, 210, 4, 195,
> 39, 114, 227, 106, 134, 28, 243, 140, 44, 23, 55, 118, 211, 234, 5, 219,
> 196, 96, 40, 222, 115, 103, 228, 78, 107, 125, 135, 8, 29, 162, 244, 186,
> 141, 180, 45, 99, 24, 49, 56, 13, 119, 153, 212, 199, 235, 91, 6, 76, 220,
> 217, 197, 11, 97, 184, 41, 36, 223, 253, 116, 138, 104, 193, 229, 86, 79,
> 171, 108, 165, 126, 145, 136, 34, 9, 74, 30, 32, 163, 84, 245, 173, 187,
> 204, 142, 81, 181, 190, 46, 88, 100, 159, 25, 231, 50, 207, 57, 147, 14,
> 67, 120, 128, 154, 248, 213, 167, 200, 63, 236, 110, 92, 176, 7, 161, 77,
> 124, 221, 102, 218, 95, 198, 90, 12, 152, 98, 48, 185, 179, 42, 209, 37,
> 132, 224, 52, 254, 239, 117, 233, 139, 22, 105, 27, 194, 113, 230, 206,
> 87, 158, 80, 189, 172, 203, 109, 175, 166, 62, 127, 247, 146, 66, 137,
> 192, 35, 252, 10, 183, 75, 216, 31, 83, 33, 73, 164, 144, 85, 170, 246,
> 65, 174, 61, 188, 202, 205, 157, 143, 169, 82, 72, 182, 215, 191, 251, 47,
> 178, 89, 151, 101, 94, 160, 123, 26, 112, 232, 21, 51, 238, 208, 131, 58,
> 69, 148, 18, 15, 16, 68, 17, 121, 149, 129, 19, 155, 59, 249, 70, 214,
> 250, 168, 71, 201, 156, 64, 60, 237, 130, 111, 20, 93, 122, 177, 150 }';
>
> could be written as
>
>	cg
>		var: #logTable
>		type: #'const unsigned char'
>		array:  #[0 0 1 240 2 225 241 53 3 38 226 133 242 43 54
> 210 4 195 39 114 227 106 134 28 243 140 44 23 55 118 211 234 5 219 196 96
> 40 222 115 103 228 78 107 125 135 8 29 162 244 186 141 180 45 99 24 49 56
> 13 119 153 212 199 235 91 6 76 220 217 197 11 97 184 41 36 223 253 116 138
> 104 193 229 86 79 171 108 165 126 145 136 34 9 74 30 32 163 84 245 173 187
> 204 142 81 181 190 46 88 100 159 25 231 50 207 57 147 14 67 120 128 154
> 248 213 167 200 63 236 110 92 176 7 161 77 124 221 102 218 95 198 90 12
> 152 98 48 185 179 42 209 37 132 224 52 254 239 117 233 139 22 105 27 194
> 113 230 206 87 158 80 189 172 203 109 175 166 62 127 247 146 66 137 192 35
> 252 10 183 75 216 31 83 33 73 164 144 85 170 246 65 174 61 188 202 205 157
> 143 169 82 72 182 215 191 251 47 178 89 151 101 94 160 123 26 112 232 21
> 51 238 208 131 58 69 148 18 15 16 68 17 121 149 129 19 155 59 249 70 214
> 250 168 71 201 156 64 60 237 130 111 20 93 122 177 150]
>
> Levente
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20210602/fbdfb636/attachment.html>