[Vm-dev] pluginizing Galois Fields

Robert Withers robert.w.withers at gmail.com
Sat Dec 19 02:33:30 UTC 2015


A little further thinking and looking. The ReedSolomon Decoder is 
absolutely using the euclidean algorithm to rebuild the data from the 
code. It is partially working, as sometimes it repairs errors and 
othertimes not. Keep mashing the run selected tests button to see this. 
I have seen all 3 GFs rebuild mutations in both the inner tests: the RS 
tests and the outer tests: FEC.

On 12/18/2015 09:20 PM, Robert Withers wrote:
> Here is a profile. The broken part uses GenericGF and GenericGFPoly, 
> so those can be optimized without the broken bits affecting it.
>
> Note that  70% of the time is inside of GenericGFPoly>>#divide:, but 
> addOrSubtract: is really the one.
>
>
> robert
>
>
>
> **Leaves**
> 21.4% {1084ms} OrderedCollection>>at:
> 11.7% {592ms} GenericGFPoly>>addOrSubtract:
> 11.7% {590ms} ProcessorScheduler class>>idleProcess
> 10.8% {548ms} GenericGF class>>addOrSubtract:coefficient:
> 5.7% {287ms} Array(SequenceableCollection)>>from:to:put:
> 5.5% {277ms} OrderedCollection>>at:put:
> 3.8% {194ms} GenericGF>>logarithm:
> 3.3% {167ms} [] DelayWaitTimeout>>wait
> 2.8% {144ms} GenericGF>>multiply:scalar:
> 2.6% {129ms} GenericGF>>exponent:
> 2.1% {107ms} Array(SequenceableCollection)>>atAllPut:
> 2.1% {104ms} SmallInteger(Integer)>><<
> 1.6% {81ms} GenericGF>>checkInit
> 1.5% {78ms} LargePositiveInteger>>bitAt:
> 1.2% {60ms} OrderedCollection>>size
> 1.1% {57ms} SmallInteger(Magnitude)>>min:
>
>
>
>
>  - 5056 tallies, 5056 msec.
>
> **Tree**
> --------------------------------
> Process: other processes
> --------------------------------
> 11.7% {590ms} [] ProcessorScheduler class>>startUp
>   |11.7% {590ms} ProcessorScheduler class>>idleProcess
> 6.1% {310ms} [] TransportEndpoint(ProtocolEndpoint)>>run
>   |6.1% {310ms} TransportEndpoint(ProtocolEndpoint)>>serverLoop
>   |  6.1% {310ms} BlockClosure>>ensure:
>   |    6.1% {310ms} [] TransportEndpoint(ProtocolEndpoint)>>serverLoop
>   |      6.1% {310ms} BlockClosure>>on:do:
>   |        6.1% {310ms} [[]] 
> TransportEndpoint(ProtocolEndpoint)>>serverLoop
>   |          6.1% {310ms} BlockClosure>>on:do:
>   |            6.1% {308ms} [[[]]] 
> TransportEndpoint(ProtocolEndpoint)>>serverLoop
>   |              5.9% {296ms} TransportEndpoint>>upcallFrame:
>   |                5.9% {296ms} 
> TransportEndpoint(ProtocolLayer)>>upcallFrame:
>   |                  5.9% {296ms} BinaryChunkProtocol>>upcallFrame:
>   |                    5.9% {296ms} BinaryChunkProtocol>>processChunk
>   |                      5.9% {296ms} OperationProtocol>>upcallFrame:
>   |                        5.9% {296ms} 
> OperationProtocol(StatefulProtocol)>>transitionEvent:with:
>   |                          5.9% {296ms} 
> ProtocolStateTransition>>transitionFor:with:
>   |                            5.9% {296ms} 
> OperationProtocol>>processStartupMsg:
>   |                              5.9% {296ms} 
> StartupProtocol(StatefulProtocol)>>transitionEvent:with:
>   |                                5.9% {296ms} 
> ProtocolStateTransition>>transitionFor:with:
>   |                                  2.3% {116ms} 
> StartupProtocol>>processGo:
>   |                                  2.3% {115ms} 
> StartupProtocol>>processReplyInfo:
>   |                                    |2.2% {113ms} 
> StartupProtocol>>dhParm
>   |                                    |  2.2% {113ms} 
> EncryptionSecrets>>dhParm
>   |                                    |    2.2% {113ms} 
> DiffieHellman>>sendMessage
>   |                                    |      1.3% {66ms} SecureRandom 
> class(RandomGenerator class)>>picker
>   |                                    |        1.3% {66ms} 
> SecureRandom class(RandomGenerator class)>>withGeneratedKey
>   |                                    |          1.3% {66ms} 
> SecureRandom class(RandomGenerator class)>>generateKey
>   |                                    |            1.3% {64ms} 
> ByteArray class(SequenceableCollection class)>>streamContents:
>   |                                    |              1.3% {64ms} 
> ByteArray class(SequenceableCollection class)>>new:streamContents:
>   |                                    |                1.3% {64ms} [] 
> SecureRandom class(RandomGenerator class)>>generateKey
>   |                                    |                  1.3% {64ms} 
> SecureRandom class(RandomGenerator class)>>unpredictableStringsDo:
>   |                                    |                    1.3% 
> {64ms} Time class>>millisecondsToRun:
>   |                                    |                      1.3% 
> {64ms} [] SecureRandom class(RandomGenerator 
> class)>>unpredictableStringsDo:
>   |                                  1.3% {65ms} 
> StartupProtocol>>processGoToo:
> 3.3% {165ms} [] UnixOSProcessAccessor>>grimReaperProcess
>   3.1% {155ms} Semaphore>>waitTimeoutMSecs:
>     3.1% {155ms} DelayWaitTimeout>>wait
>       3.1% {155ms} BlockClosure>>ensure:
>         3.1% {155ms} [] DelayWaitTimeout>>wait
> --------------------------------
> Process: (40s) 50028: nil
> --------------------------------
> 78.5% {3967ms} MessageTally class>>spyOn:reportOtherProcesses:
>   78.5% {3967ms} MessageTally>>spyEvery:on:
>     78.5% {3967ms} BlockClosure>>ensure:
>       78.5% {3967ms} [] TestRunner>>runProfiled
>         78.5% {3967ms} TestRunner>>runAll
>           78.5% {3967ms} TestRunner>>runSuite:
>             78.5% {3967ms} TestRunner>>basicRunSuite:do:
>               78.5% {3967ms} BlockClosure>>ensure:
>                 78.5% {3967ms} [] TestRunner>>basicRunSuite:do:
>                   78.5% {3967ms} 
> OrderedCollection(Collection)>>do:displayingProgress:every:
>                     78.5% {3967ms} 
> ByteString(String)>>displayProgressFrom:to:during:
>                       78.5% {3967ms} 
> ByteString(String)>>displayProgressAt:from:to:during:
>                         78.5% {3967ms} ProgressInitiationException 
> class>>display:at:from:to:during:
>                           78.5% {3967ms} 
> ProgressInitiationException>>display:at:from:to:during:
>                             78.5% {3967ms} 
> ProgressInitiationException(Exception)>>signal
>                               78.5% {3967ms} 
> MethodContext(ContextPart)>>handleSignal:
>                                 78.5% {3967ms} 
> UndefinedObject>>handleSignal:
>                                   78.5% {3967ms} 
> ProgressInitiationException>>defaultAction
>                                     78.5% {3967ms} 
> ProgressInitiationException(Exception)>>resume
>                                       78.5% {3967ms} 
> ProgressInitiationException>>defaultResumeValue
>                                         78.5% {3967ms} 
> MorphicUIManager>>displayProgress:at:from:to:during:
>                                           78.4% {3965ms} 
> BlockClosure>>ensure:
>                                             78.4% {3965ms} [] 
> MorphicUIManager>>displayProgress:at:from:to:during:
>                                               78.4% {3965ms} 
> BlockClosure>>on:do:
>                                                 78.4% {3965ms} [[]] 
> MorphicUIManager>>displayProgress:at:from:to:during:
>                                                   78.4% {3965ms} [] 
> OrderedCollection(Collection)>>do:displayingProgress:every:
>                                                     78.4% {3965ms} 
> OrderedCollection>>do:
>                                                       78.4% {3965ms} 
> [[]] OrderedCollection(Collection)>>do:displayingProgress:every:
>                                                         78.1% {3947ms} 
> [] TestRunner>>runSuite:
>                                                           78.1% 
> {3947ms} TestRunner>>runTest:
>                                                             78.0% 
> {3945ms} SecureSessionPerformanceTestCase(TestCase)>>run:
> 78.0% {3945ms} TestResult>>runCase:
> 78.0% {3945ms} BlockClosure>>on:do:
> 78.0% {3945ms} [] TestResult>>runCase:
> 78.0% {3945ms} BlockClosure>>on:do:
> 78.0% {3945ms} [[]] TestResult>>runCase:
> 78.0% {3945ms} SecureSessionPerformanceTestCase(TestCase)>>runCase
> 78.0% {3945ms} BlockClosure>>ensure:
> 77.4% {3912ms} [] SecureSessionPerformanceTestCase(TestCase)>>runCase
> 77.4% {3912ms} SecureSessionPerformanceTestCase(TestCase)>>timeout:after:
> 77.4% {3912ms} BlockClosure>>ensure:
> 77.4% {3912ms} [] 
> SecureSessionPerformanceTestCase(TestCase)>>timeout:after:
> 77.4% {3912ms} BlockClosure>>on:do:
> 77.4% {3912ms} [[]] SecureSessionPerformanceTestCase(TestCase)>>runCase
> 77.4% {3912ms} SecureSessionPerformanceTestCase(TestCase)>>performTest
> 77.4% {3912ms} SecureSessionPerformanceTestCase>>testPerformance1
> 77.2% {3902ms} SmallInteger(Integer)>>timesRepeat:
> 77.2% {3902ms} [] SecureSessionPerformanceTestCase>>testPerformance1
> 77.2% {3902ms} SecureSessionTerminal>>sendBytes:
> 77.2% {3902ms} SecureSessionTerminal>>downcallFrame:
> 77.2% {3902ms} SecureSessionTerminal(ProtocolLayer)>>downcallFrame:
> 77.2% {3902ms} FullDuplexProxy>>downcallFrame:
> 77.1% {3900ms} MACComputeAndLengthWriter>>writeFrame:handler:
> 77.1% {3898ms} [] FullDuplexProxy>>downcallFrame:
> 77.1% {3898ms} FullDuplexProxy(ProtocolLayer)>>downcallFrame:
> 77.1% {3898ms} FullDuplexProxy>>downcallFrame:
> 77.1% {3898ms} Encryptor>>writeFrame:handler:
> 76.4% {3864ms} [] FullDuplexProxy>>downcallFrame:
> 76.4% {3864ms} FullDuplexProxy(ProtocolLayer)>>downcallFrame:
> 76.4% {3864ms} FullDuplexProxy>>downcallFrame:
> 76.4% {3864ms} MACMessageWriter>>writeFrame:handler:
> 76.4% {3864ms} [] FullDuplexProxy>>downcallFrame:
> 76.4% {3864ms} FullDuplexProxy(ProtocolLayer)>>downcallFrame:
> 76.4% {3864ms} FullDuplexProxy>>downcallFrame:
> 76.4% {3864ms} FECEncoder>>writeFrame:handler:
> 76.4% {3862ms} FECEncoder>>encodeFrame:
> 76.4% {3862ms} GaloisField>>encode:
> 76.3% {3860ms} GaloisField>>encodeBlock:
> 76.2% {3851ms} ReedSolomonEncoder>>encode:
> 72.9% {3685ms} GenericGFPoly>>divide:
> |52.0% {2628ms} GenericGFPoly>>addOrSubtract:
> |  |17.4% {881ms} OrderedCollection>>at:
> |  |11.7% {592ms} primitives
> |  |10.7% {542ms} GenericGF class>>addOrSubtract:coefficient:
> |  |4.5% {225ms} OrderedCollection class>>new:withAll:
> |  |  |4.4% {223ms} Array class(ArrayedCollection class)>>new:withAll:
> |  |  |  4.3% {219ms} Array(SequenceableCollection)>>atAllPut:
> |  |  |    3.3% {166ms} Array(SequenceableCollection)>>from:to:put:
> |  |  |      |2.6% {133ms} primitives
> |  |  |    1.0% {53ms} primitives
> |  |4.3% {216ms} OrderedCollection>>at:put:
> |  |2.1% {105ms} GenericGFPoly class>>newOnGF:coefficients:
> |  |  1.7% {86ms} GenericGFPoly>>initializeOnGF:coefficients:
> |  |    1.3% {64ms} OrderedCollection>>copyFrom:to:
> |  |      1.2% {60ms} OrderedCollection>>postCopyFrom:to:
> |16.9% {852ms} GenericGFPoly>>multiply:monomial:
> |  |11.6% {589ms} GenericGF>>multiply:scalar:
> |  |  |7.0% {352ms} GenericGF>>logarithm:
> |  |  |  |3.6% {180ms} primitives
> |  |  |  |2.5% {127ms} OrderedCollection>>at:
> |  |  |2.5% {127ms} GenericGF>>exponent:
> |  |  |  |1.8% {93ms} primitives
> |  |  |1.9% {98ms} primitives
> |  |2.8% {142ms} OrderedCollection class>>new:withAll:
> |  |  |2.7% {136ms} Array class(ArrayedCollection class)>>new:withAll:
> |  |  |  2.7% {134ms} Array(SequenceableCollection)>>atAllPut:
> |  |  |    2.0% {102ms} Array(SequenceableCollection)>>from:to:put:
> |  |  |      1.8% {92ms} primitives
> |  |1.1% {55ms} OrderedCollection>>at:put:
> |2.1% {108ms} GenericGF>>buildMonomial:coefficient:
> |  1.9% {96ms} Array class(ArrayedCollection class)>>new:withAll:
> |    1.9% {96ms} Array(SequenceableCollection)>>atAllPut:
> |      1.5% {76ms} Array(SequenceableCollection)>>from:to:put:
> |        1.2% {62ms} primitives
> 2.8% {142ms} ReedSolomonEncoder>>buildGenerator:
> 2.8% {140ms} GenericGFPoly>>multiply:
> 2.2% {110ms} GenericGF>>multiply:scalar:
> 
> **Leaves**
> 21.4% {1084ms} OrderedCollection>>at:
> 11.7% {592ms} GenericGFPoly>>addOrSubtract:
> 11.7% {590ms} ProcessorScheduler class>>idleProcess
> 10.8% {548ms} GenericGF class>>addOrSubtract:coefficient:
> 5.7% {287ms} Array(SequenceableCollection)>>from:to:put:
> 5.5% {277ms} OrderedCollection>>at:put:
> 3.8% {194ms} GenericGF>>logarithm:
> 3.3% {167ms} [] DelayWaitTimeout>>wait
> 2.8% {144ms} GenericGF>>multiply:scalar:
> 2.6% {129ms} GenericGF>>exponent:
> 2.1% {107ms} Array(SequenceableCollection)>>atAllPut:
> 2.1% {104ms} SmallInteger(Integer)>><<
> 1.6% {81ms} GenericGF>>checkInit
> 1.5% {78ms} LargePositiveInteger>>bitAt:
> 1.2% {60ms} OrderedCollection>>size
> 1.1% {57ms} SmallInteger(Magnitude)>>min:
>
> **Memory**
>     old            +0 bytes
>     young        +1,005,072 bytes
>     used        +1,005,072 bytes
>     free        -1,005,072 bytes
>
> **GCs**
>     full            1 totalling 146 ms (2.89% uptime), avg 146 ms
>     incr            259 totalling 41 ms (0.8% uptime), avg 0.2 ms
>     tenures        3,681 (avg 0 GCs/tenure)
>     root table    0 overflows
>
>
> On 12/18/2015 08:59 PM, David T. Lewis wrote:
>>   On Fri, Dec 18, 2015 at 08:13:00PM -0500, Robert Withers wrote:
>>> On 12/18/2015 08:07 PM, David T. Lewis wrote:
>>>> If you are implementing your algorithm from scratch, then it would be
>>>> nice if it could be done in Smalltalk, because that means we can all
>>>> read it, play with it in the image, and write unit tests to 
>>>> validate and
>>>> document its behavior. We can figure out the translation to C 
>>>> afterwords,
>>>> once you have a good implementation in Smalltalk (and yes I will help
>>>> with that).
>>> I have a smalltalk implmentation that came from Google Java code and is
>>> fully implemented in squeak/pharo. I am intermittently fixing byte
>>> mutations in the payload, so it is working to a degree. Check out the
>>> classes GenericGF, GenericGFPoly and GaloisField to see the insides.
>>> FECEncoder and FECDecoder are calling the galoisField which builds a
>>> ReedSolomon Decoder. That last is where the error detection occurs.
>>>
>>> Thank you all very much for looking out!
>> I guess my suggestion would be that once you have a fairly good working
>> implementation that you are comfortable with from a functional point of
>> view, then let's look at which methods in that implementation would 
>> benefit
>> from being translated to primitives in C. It would be especially good if
>> you can run a profiler on your Smalltalk implementation and see where 
>> the
>> time is being spent. Those would be the things we would want to turn 
>> into
>> primitives. But first things first, let's get it working 100% (not "to a
>> degree") and then we can do the translation to primitives.
>>
>> Dave
>>
>

-- 
. .. .. ^,^ robert


More information about the Vm-dev mailing list