[Vm-dev] pluginizing Galois Fields
Robert Withers
robert.w.withers at gmail.com
Sat Dec 19 02:20:09 UTC 2015
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