Cryptographic Primitives

On Sun, 08 Oct 2006 00:35:19 +0200, Andreas Raab wrote:
:) Mathieu: hurry up, potential users are waiting for sensible performance  
comparisions :) Are there already benchmarks available for exhibiting the  
slowdown experienced with instance variables accessed from BlockClosures?

/Klaus

> Cheers,
>    - Andreas
>
>

Klaus D. Witzel wrote:
> On Sun, 08 Oct 2006 00:35:19 +0200, Andreas Raab wrote:
>> Not sure about this. There are issues with our current contexts, BIG
>> issues. So big that I'd very seriously consider accepting a slowdown
>> in exchange to fixing these problems.
>
> :) Mathieu: hurry up, potential users are waiting for sensible
> performance comparisions :) Are there already benchmarks available for
> exhibiting the slowdown experienced with instance variables accessed
> from BlockClosures?

I actually did a serious evaluation of the new compiler for the last
Croquet release. It failed the tests, primarily on the issue of error
messages. A compiler whose only complaint is "Token not expected" is
simply unusable no matter what else might be great about it.

Cheers,
   - Andreas

Mathieu skrev: You can also subscribe to the SqueakSource rss feed and see when
packages are updated.
Thats how I see f.x.  Exupery has been updated :-)
Karl

> You can also subscribe to the SqueakSource rss feed and see when
> packages are updated.
> Thats how I see f.x.  Exupery has been updated :-)

Or http://planetmisc.squeak.org 's, to watch all public repos at once.

Klaus,

I noticed in the comment (thanks for pointing out the BlockClosure class
btw) it mentioned recompiling the whole image using the BlockClosure class
instead of the BlockContext.  Has this been tried?  Any guess what the speed
hit would be?

On Sun, 08 Oct 2006 08:46:11 +0200, J J wrote:
> Klaus,
>
> I noticed in the comment (thanks for pointing out the BlockClosure class  
> btw) it mentioned recompiling the whole image using the BlockClosure  
> class instead of the BlockContext.  Has this been tried?  Any guess what  
> the speed hit would be?

Not easy to predict. Here are areas that I've investigated:

1] instVar access; time(bytecode) versus: time(#instVarAt); assumption:  
time(VM,tempVar access) = time(VM,instVar access)

[|required|required]bench '1.88744451109778e6 per second.'

[|required|thisContext instVarAt:1]bench '1.37969322947873e6 per second.'

Cost increase: > 30%

2] # of blocks affected by instVar access; depends on what your image  
currently runs

BlockContext allInstances inject: 0 into: [:accum :each | each  
hasInstVarRef ifTrue: [accum + 1] ifFalse: [accum]]

=> 113

3] list of blocks with instVar access (see report below); ignore duplicate  
entries; seems that nothing much in the list looks time critical (except  
that the performance of the compiler, which is part of the list, for me  
counts as time critical ;-)

4] but the new music will play for those blocks which cannot be inlined by  
the new compiler, and figures in terms of before/after are not easy to  
obtain; except for a static cost analysis.

For the latter, both the new block valuation messages  
(BlockClosure>>#value and friends) and the frequency of #createBlock:  
versus: #blockCopy: are relevant; the bytecode access of temps is  
invariant-again the assumption that time(VM,tempVar access) =  
time(VM,instVar access). This paragraph is preliminary; I have as yet not  
thought about the cost of the implementation of ClosureEnvironment and of  
BlockClosure's non-local returns.

/Klaus

-------------------

|coll| coll := OrderedCollection new.
BlockContext allInstancesDo: [:each | each hasInstVarRef ifTrue: [coll  
add: each]].
coll do:[:each | Transcript cr; show: each printString]

=>

[] in WorldState>>displayWorld:submorphs: {[worldDamageRects := self      
drawWorld: aWorld     submorphs: submorphs    ...]}
[] in MenuItemMorph>>invokeWithEvent: {[(selArgCount := selector numArgs)  
= 0   ifTrue: [target perform: selector] ...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in MenuItemMorph>>invokeWithEvent: {[(selArgCount := selector numArgs)  
= 0   ifTrue: [target perform: selector] ...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in SystemWindow(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in AlignmentMorph(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in MenuItemMorph>>invokeWithEvent: {[(selArgCount := selector numArgs)  
= 0   ifTrue: [target perform: selector] ...]}
[] in WorldState>>displayWorld:submorphs: {[worldDamageRects := self      
drawWorld: aWorld     submorphs: submorphs    ...]}
[] in CornerRounder>>tweakCornersOf:on:in:borderWidth:corners: {[:i |  
corner := corners at: i.  saveBits := underBits at: i.  saveBits   if...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in SystemWindow(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in SystemWindow(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in ImageMorph(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in MenuItemMorph>>invokeWithEvent: {[(selArgCount := selector numArgs)  
= 0   ifTrue: [target perform: selector] ...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in MessageSet>>selectedMessage {[:class :selector |  class   ifNil: [^  
'Class vanished'].  selector first is...]}
[] in Parser>>parse:class:noPattern:context:notifying:ifFail: {[:ex |  
repeatNeeded := (requestor isKindOf: TextMorphEditor) not.  myStream...]}
[] in MenuItemMorph>>invokeWithEvent: {[(selArgCount := selector numArgs)  
= 0   ifTrue: [target perform: selector] ...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in ScrollBar>>menuButtonMouseDown: {[:sel |  menuSelector := sel.  
model perform: sel with: event]}
[] in MenuMorph(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in SystemWindow(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in AlignmentMorph(Morph)>>fullBounds {[:ex |  fullBounds := bounds.  ex  
pass]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in Delay>>schedule {[beingWaitedOn := true.  resumptionTime := Time  
millisecondClockValue + dela...]}
[] in SharedQueue>>nextPut: {[writePosition > contentsArray size   ifTrue:  
[self makeRoomAtEnd].  content...]}
[] in SharedQueue>>nextPut: {[writePosition > contentsArray size   ifTrue:  
[self makeRoomAtEnd].  content...]}
[] in SharedQueue>>next {[readPosition = writePosition   ifTrue: [self  
error: 'Error in SharedQueue s...]}
[] in SharedQueue>>next {[readPosition = writePosition   ifTrue: [self  
error: 'Error in SharedQueue s...]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in Parser>>parse:class:noPattern:context:notifying:ifFail: {[:ex |  
repeatNeeded := (requestor isKindOf: TextMorphEditor) not.  myStream...]}
[] in Encoder>>init:context:notifying: {[:variable |  node := VariableNode  
new     name: variable     index: (n := n...]}
[] in Encoder>>lookupInPools:ifFound: {[:sym |  (class bindingOf: sym)    
ifNotNilDo: [:assoc |     assocBlock value...]}
[] in Parser(Scanner)>>xDigit {[Number readFrom: source]}
[] in Encoder>>lookupInPools:ifFound: {[:sym |  (class bindingOf: sym)    
ifNotNilDo: [:assoc |     assocBlock value...]}
[] in WeakSet>>growTo: {[:each | (each == flag    or: [each == nil])    
ifFalse: [self noCheckAdd: ea...]}
[] in Encoder>>lookupInPools:ifFound: {[:sym |  (class bindingOf: sym)    
ifNotNilDo: [:assoc |     assocBlock value...]}
[] in Parser(Scanner)>>xDigit {[Number readFrom: source]}
[] in MethodNode>>generateWith:using: {[:m |  method := m.  method  
properties: properties.  ^ method]}
[] in BlockNode>>sizeForValue: {[:arg | size := size     + (arg  
sizeForStorePop: encoder)]}
[] in Encoder>>tempNames {[:node | (node isMemberOf: MessageAsTempNode)    
ifTrue: [scopeTable keyAtVal...]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in WorldState>>displayWorld:submorphs: {[worldDamageRects := self      
drawWorld: aWorld     submorphs: submorphs    ...]}
[] in WorldState>>displayWorld:submorphs: {[worldDamageRects := self      
drawWorld: aWorld     submorphs: submorphs    ...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in Parser>>parse:class:noPattern:context:notifying:ifFail: {[:ex |  
repeatNeeded := (requestor isKindOf: TextMorphEditor) not.  myStream...]}
[] in TextMorphForEditView(TextMorph)>>keyStroke: {[editor readKeyboard]}
[] in Parser>>parse:class:noPattern:context:notifying:ifFail: {[:ex |  
repeatNeeded := (requestor isKindOf: TextMorphEditor) not.  myStream...]}
[] in EventSensor>>eventTickler {[delay wait.  delta := Time  
millisecondClockValue - lastEventPoll.  (delta <...]}
[] in Encoder>>lookupInPools:ifFound: {[:sym |  (class bindingOf: sym)    
ifNotNilDo: [:assoc |     assocBlock value...]}
[] in Parser>>removeUnusedTemps {[:temp | (UIManager default    
chooseFrom: #('yes' 'no' )    title: ((temp ,...]}
[] in MethodNode>>generateWith:using: {[:m |  method := m.  method  
properties: properties.  ^ method]}
[] in BlockNode>>sizeForValue: {[:arg | size := size     + (arg  
sizeForStorePop: encoder)]}
[] in BlockNode>>sizeForValue: {[:arg | size := size     + (arg  
sizeForStorePop: encoder)]}
[] in Encoder>>tempNames {[:node | (node isMemberOf: MessageAsTempNode)    
ifTrue: [scopeTable keyAtVal...]}

Klaus D. Witzel a écrit :
Sorry I had to sleep I didn't saw your email.
I don't really know if there are benchmarks available but the best way to ask them is to ask either
Marcus or in the NewCompiler mailing list.

        Math

2006/10/8, Klaus D. Witzel <[hidden email]>:
You can do some micro-benchmarks for closures vs. blocks. And they
don't look good. They also slow down cases where you don't need full
block clousres and what VW calls a clean block would do. Probably
primitive 189 was not added.

http://minnow.cc.gatech.edu/squeak/ClosureCompiler
http://lists.squeakfoundation.org/pipermail/squeak-dev/2003-April/056833.html

[(1 to: 1000000) do: [:i | i]] timeToRun
non-closure mode: 240 ms
closure mode: 1660 ms

Philippe

>
>

Thank you Mathieu and Phillipe for you pointers and example.

Just out of curiosity (and as input for writing accurate yes/no test cases  
:) let me ask what is expected by the community (apologies if this sounds  
like a silly question ;-) when is a closure a real one:

1] after #fixTemps (or equivalent)

2] after #blockCopy: (is this equivalent to 1?)

3] after #createBlock: (is this equivalent to 1? to 2?)

4] <put: your requirements: or thoughts: here>

Thank you for your time!

/Klaus

Klaus D. Witzel a écrit :
> Thank you Mathieu and Phillipe for you pointers and example.
>
> Just out of curiosity (and as input for writing accurate yes/no test
> cases :) let me ask what is expected by the community (apologies if this
> sounds like a silly question ;-) when is a closure a real one:
>
> 1] after #fixTemps (or equivalent)

no
>
> 2] after #blockCopy: (is this equivalent to 1?)

no and it's not equivalent to 1. In fact blockCopy create a BlockContext.
And a BlockContext is not a closure, it's more like MethodContext. See:
http://users.ipa.net/~dwighth/smalltalk/bluebook/bluebook_chapter27.html#Contexts27

>
> 3] after #createBlock: (is this equivalent to 1? to 2?)

Yes and in a way it can be equivalent to 1 plus 2.

>
> 4] <put: your requirements: or thoughts: here>
>
> Thank you for your time!
>
> /Klaus
>

Hi Mathieu,

on Sun, 08 Oct 2006 11:26:00 +0200, you wrote:
And *exactly after* the respective operation? Don't they have the same  
values represented by the same names?

> In fact blockCopy create a BlockContext.

Ah :)

> And a BlockContext is not a closure, it's more like MethodContext.

This is the question that I'm trying to address by using equivalency (not  
identity). A counter example for you: a block with a single argument which  
does *not* access anything else but the argument, always has equivalent  
state and behavior (in terms of what you put inside [:x|...]) and that is  
regardless of 1, 2 or 3.

> See:
> http://users.ipa.net/~dwighth/smalltalk/bluebook/bluebook_chapter27.html#Contexts27
>
>>
>> 3] after #createBlock: (is this equivalent to 1? to 2?)
>
> Yes and in a way it can be equivalent to 1 plus 2.

In what way, mind to elaborate a bit. Thank you.

/Klaus

Klaus D. Witzel a écrit :
Oh! yes I misinterpret your question. In away yes it's the same.

Yes and I think the best is to ask Marcus

Philippe Marschall writes:
 > You can do some micro-benchmarks for closures vs. blocks. And they
 > don't look good. They also slow down cases where you don't need full
 > block clousres and what VW calls a clean block would do. Probably
 > primitive 189 was not added.
 >
 > http://minnow.cc.gatech.edu/squeak/ClosureCompiler
 > http://lists.squeakfoundation.org/pipermail/squeak-dev/2003-April/056833.html
 >
 > [(1 to: 1000000) do: [:i | i]] timeToRun
 > non-closure mode: 240 ms
 > closure mode: 1660 ms

When the only problems are performance problems I'm happy to help
fix them. With an interpreter (no Exupery) only solution.

Bryce

Hi andreas

this is clear. I really understand. This is why we asked mathieu to  
work on that and propose this project as SummerTalk project.
This would be great to have real exception too not subclass of String  
like in the default compiler for syntax error. :)
Mathieu already fixed a lot of things in the new compiler related to  
pragmas parsing. Now he is focusing
on the error handling and may be after he will work on the decompiler  
code.
If people wants to help we need the decompiler also working well.
Mathieu also worked on fixing the way comments are attached in the  
tree (before this was kind of random).
Stef

On 8 oct. 06, at 01:03, Andreas Raab wrote:

I am not familiar enough with those calls to say 100%, but when I say "real
closures", what I mean are closures that can be returned from a function and
used without fear.  In other words, what other languages that have closures
do.

Now I relize the "return to home context" (i.e. ^) is not compatible with
this, but that's ok.  This ability is unique to smalltalk as far as I know
and treating it different would be fine (e.g. if a ^ is seen then turn the
block into the cheaper BlockContext since it can't be returned from a method
anyway).

Or for that matter if the speed problem is too hard to fix right now, then
maybe a simple change in the compiler to make a block into a BlockClosure if
it gets returned?  Obviously most of you know a lot more about this then me.
  Just throwing some things out there.

The problem is not non-local returns but block arguments/temps. Squeak
just makes method temps out of them.

Philippe

2006/10/8, J J <[hidden email]>:

Hi,

On 10/8/06, J J <[hidden email]> wrote:
I'm not sure whether I understand your correctly, but I think that the
problem in Squeak is something different (as Philippe already
mentioned). As for ^, it is *good* that it returns from the lexical
context of the block it occurs in.

Imagine what would happen in a setting like this:

SomeClass>>someMessage
    self someCondition ifTrue: [ ^10 ] ifFalse: [ ^20 ]

if ^ was defined to return from the dynamic scope. In that case, it
would return from #ifTrue:ifFalse: (or wherever the blocks would be
evaluated), instead of #someMessage, which is the intention. Crazy
behaviour. 8-)

Best,

Michael

Right, but it looks like we have, what I would call real closures in the
image, they just don't get used.  I was suggesting that perhaps if you see
something like:

MyClass>>myMethod

a := SomeClass new.

^ [ :b | b use: a ]

Then the compiler turns that into a real closure, since it obviously needs
to have that environment around after the method is gone.  And you don't
have to look inside the block at what it is doing.  If a block gets returned
from a method then that can only mean (I think) it's going to need a copy of
the context it was created in.

For methods that pass blocks downward (i.e. they call methods passing
blocks, but they will be around for the life of the block) then the current
blocks are probably ok, since the context the block was made in has to stay
around.

But then again, it's probably better to just do it right to begin with and
not worry about such complexity.  You all would know the answer to that
better then me.

Yes I know.  What I meant was: I think the presence of ^ means your block
can't be a complete closure.  I.e. you can't return it from a method and
invoke it later, since it might try to return to a place that no longer
exists.  I think the way ^ works is wonderful, but if the compiler sees one
in a block it can treat that block differently then if one wasn't present.  
That is: if copying free variables is so expensive, then it can be avoided
at least in the case that a ^ is present in the block.  You don't have to
copy the environment then because the block can't be passed upward anyway.

Did I make more sense this time or less? :)

Hi,

On 10/8/06, J J <[hidden email]> wrote:
> Did I make more sense this time or less? :)

more, thanks. :-)

Best,

Michael