[Pharo-project] about keys returning a set
Nicolas I was discussing with lukas and we would be interested to get your changes to dictionary keys (Ihope that this icorrect since I'm dead) We would like to integrate your changes. Do you have a basis that we could work? Else we can just try in the image directly. Stef
Yes I can have a look. Otherwise, the changes are quite simple: 1) track senders of keys and sometimes senders of senders 2) identify those sending a message not understandable by an Array (add: remove: etc...), insert keys asSet in this case 3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!) 4) change code for keys Then eventually change some chains: keys asSortedCollection asArray -> keys asArray sort Nicolas 2009/12/3 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Nicolas
I was discussing with lukas and we would be interested to get your changes to dictionary keys (Ihope that this icorrect since I'm dead) We would like to integrate your changes. Do you have a basis that we could work? Else we can just try in the image directly.
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
tx On Dec 3, 2009, at 10:13 PM, Nicolas Cellier wrote:
Yes I can have a look. Otherwise, the changes are quite simple: 1) track senders of keys and sometimes senders of senders 2) identify those sending a message not understandable by an Array (add: remove: etc...), insert keys asSet in this case 3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!) 4) change code for keys
Then eventually change some chains: keys asSortedCollection asArray -> keys asArray sort
Nicolas
2009/12/3 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Nicolas
I was discussing with lukas and we would be interested to get your changes to dictionary keys (Ihope that this icorrect since I'm dead) We would like to integrate your changes. Do you have a basis that we could work? Else we can just try in the image directly.
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead. Cheers, Henry
I wonder if ever something along the following lines was considered? Dictionary>>keys "Answer a Set containing the receiver's keys." | result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation. The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set. Lukas 2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
Actually the code can be further optimized: Dictionary>>keys "Answer a Set containing the receiver's keys." | result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation. The system doesn't seem to break with this change :-) Lukas 2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result |     result := Set basicNew.     result setTally: tally array: (array collect: [ :each |         each isNil ifFalse: [ each key ] ]).     ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result container |     result := Set basicNew setTally: tally array: array copy.     container := result array.     1 to: container size do: [ :index |         (container at: index)             ifNotNil: [ :assoc | container at: index put: assoc key ] ].     ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
except that it breaking encapsulation. Thus i vote -1 for this kind of optimization :)
Lukas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result |     result := Set basicNew.     result setTally: tally array: (array collect: [ :each |         each isNil ifFalse: [ each key ] ]).     ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
On Dec 4, 2009, at 9:12 30AM, Igor Stasenko wrote:
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
except that it breaking encapsulation. Thus i vote -1 for this kind of optimization :)
You could also achieve the same performance by writing the method (returning an array) | result currentIX | result := Array new: tally. currentIX := 1. 1 to: array size do: [:ix | (array at: ix) ifNotNil: [:assoc | result at: currentIX put: assoc key. currentIX := currentIX +1]]. ^result Which is, unless you consider using at:put: and expecting an Array of size n to hold n elements, not breaking encapsulation. Though, the block creation overhead of using keysDo (which is the main reason for the performance difference seen between the two) should, if I've understood Eliot correctly, go away with a stack-based vm. While on the topic of the Set hierarchy, is it just me, or is the Keyed* versions a mistake? Giving a block that computes a key means the collection either needs to: - Know about what type of objects is put into it, in which case you break encapsulation. and it would likely be better to just implement hash/= for those types of objects. - Only use info available of Object, in which case you're not very likely to end up with much better hash functions than scaledIdentityHash anyways. Cheers, Henry
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result container |     result := Set basicNew setTally: tally array: array copy.     container := result array.     1 to: container size do: [ :index |         (container at: index)             ifNotNil: [ :assoc | container at: index put: assoc key ] ].     ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do: Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result |     result := Set basicNew.     result setTally: tally array: (array collect: [ :each |         each isNil ifFalse: [ each key ] ]).     ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
I would be curious to see the average length of dictionary keys (except Smalltalk) and see the performance penalty between set and array for the do: Stef
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do:
Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
I posted these numbers a while ago. In my image the average length of a Dictionary is 10, the average length of a Set is 1.2. Lukas 2009/12/4 Stéphane Ducasse <stephane.ducasse@inria.fr>:
I would be curious to see the average length of dictionary keys  (except Smalltalk) and see the performance penalty between set and array for the do:
Stef
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result container |     result := Set basicNew setTally: tally array: array copy.     container := result array.     1 to: container size do: [ :index |         (container at: index)             ifNotNil: [ :assoc | container at: index put: assoc key ] ].     ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do:
Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys     "Answer a Set containing the receiver's keys."
    | result |     result := Set basicNew.     result setTally: tally array: (array collect: [ :each |         each isNil ifFalse: [ each key ] ]).     ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
Using this script: (Dictionary allInstances inject: 0 into: [ :r :e | r + e size ]) / Dictionary allInstances size asFloat I get 14.23 in my image. Using this script: (Set allInstances inject: 0 into: [ :r :e | r + e size ]) / Set allInstances size asFloat I get 0.49 Cheers, Doru On 4 Dec 2009, at 11:49, Lukas Renggli wrote:
I posted these numbers a while ago.
In my image the average length of a Dictionary is 10, the average length of a Set is 1.2.
Lukas
2009/12/4 Stéphane Ducasse <stephane.ducasse@inria.fr>:
I would be curious to see the average length of dictionary keys (except Smalltalk) and see the performance penalty between set and array for the do:
Stef
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do:
Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- www.tudorgirba.com "No matter how many recipes we know, we still value a chef."
this is interesting to see that this is still a guess game. Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up. May be in the future when system will have a better knowledge of themselves we may end up having better tools...
I posted these numbers a while ago.
In my image the average length of a Dictionary is 10, the average length of a Set is 1.2.
Lukas
2009/12/4 Stéphane Ducasse <stephane.ducasse@inria.fr>:
I would be curious to see the average length of dictionary keys (except Smalltalk) and see the performance penalty between set and array for the do:
Stef
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do:
Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up.
Yeah, the iteration slowdown should be minimal of using Set vs. Array. What I think is more critical that you change the semantics of the returned data-structure. That could not only break clients, but also their expectations towards performance. I find interesting that most sets are almost empty. Lukas -- Lukas Renggli http://www.lukas-renggli.ch
I think this last assertion has to be tempered by another statistic: which is the relationship between iteration (a.k.a. uses of) and creation? -- Cesar Rabak Em 04/12/2009 09:48, Stéphane Ducasse <stephane.ducasse@inria.fr> escreveu: this is interesting to see that this is still a guess game. Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up. May be in the future when system will have a better knowledge of themselves we may end up having better tools...
See also http://code.google.com/p/pharo/issues/detail?id=1353 http://code.google.com/p/pharo/issues/detail?id=1542 I uploaded a SLICE that just add a few #asSet here and there. Quasi-neutral as long as keys are Set, but enabling a switch to Array for macro benchmarks purposes... May I also push http://code.google.com/p/pharo/issues/detail?id=1354 which is related but quite independent ? Nicolas 2009/12/4 <csrabak@bol.com.br>:
I think this last assertion has to be tempered by another statistic: which is the relationship between iteration (a.k.a. uses of) and creation?
-- Cesar Rabak
Em 04/12/2009 09:48, Stéphane Ducasse <stephane.ducasse@inria.fr> escreveu:
this is interesting to see that this is still a guess game. Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up. May be in the future when system will have a better knowledge of themselves we may end up having better tools...
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
See also
http://code.google.com/p/pharo/issues/detail?id=1353 in 11071 ;)
"This is issue1353 isn't it ? Lukas proposed to keep a Set, but optimize its creation (with extra knowledge that same key hash code is used in both Set and Dictionary which breaks a bit encapsulation) However, even if the Set is created fast in #keys, the overall effect depends on usage made of these keys. For example a Set then iterates slower than an Array for such code: self keys select: [:e | e beginsWith: 'test'] Otherwise, the second advantage of an Array is that keys and values both are arrays in sync, which might be a nice property..." yes I agree I prefer to have both arrays in sync it is more regular.
I uploaded a SLICE that just add a few #asSet here and there. Quasi-neutral as long as keys are Set, but enabling a switch to Array for macro benchmarks purposes...
May I also push http://code.google.com/p/pharo/issues/detail?id=1354 which is related but quite independent ?
Yes this is on my todo to integrate but I wanted people to discuss it before. "The problem of current definition of classVarNames is precisly that they are unordered. The order is not defined by user, it just depend on the hash codes of classVarNames modulo the size of classPool, unless we sort them. Please look at usage." I totally agree with you nicolas I hate that the classVar changes randomly their order. in 11071 :)
Nicolas
2009/12/4 <csrabak@bol.com.br>:
I think this last assertion has to be tempered by another statistic: which is the relationship between iteration (a.k.a. uses of) and creation?
-- Cesar Rabak
Em 04/12/2009 09:48, Stéphane Ducasse <stephane.ducasse@inria.fr> escreveu:
this is interesting to see that this is still a guess game. Even with these numbers I cannot evaluate what could be a slowdown/pseed up impact on the complete system. I imgain that the ietration slow down should be minimal and compensated by the creation speed up. May be in the future when system will have a better knowledge of themselves we may end up having better tools...
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Nicolas in 1354 you change whichClassDefinesClassVar: aString ^self whichSuperclassSatisfies: [:aClass | (aClass classVarNames collect: [:each | each asString]) includes: aString asString] why not returning #() instead of nil? whichClassDefinesClassVar: aString Symbol hasInterned: aString ifTrue: [ :aSymbol | ^self whichSuperclassSatisfies: [:aClass | aClass classVarNames anySatisfy: [:each | each = aSymbol]]]. ^nil I saw that you have second version but it did not change it. Then I saw that you often do ... array sort I imagine that this is because like that you keep the same semantics in client code. Now may be one of these days we could fix the class builder to inforce the order. Naively I was dreaming that classVar would be sorted once for all. Stef
Nicolas
in 1354 you change
whichClassDefinesClassVar: aString ^self whichSuperclassSatisfies: [:aClass | (aClass classVarNames collect: [:each | each asString]) includes: aString asString]
why not returning #() instead of nil?
whichClassDefinesClassVar: aString Symbol hasInterned: aString ifTrue: [ :aSymbol | ^self whichSuperclassSatisfies: [:aClass | aClass classVarNames anySatisfy: [:each | each = aSymbol]]]. ^nil
I saw that you have second version but it did not change it.
I did it in 11071 -> #()
Then I saw that you often do ... array sort
I imagine that this is because like that you keep the same semantics in client code. Now may be one of these days we could fix the class builder to inforce the order. Naively I was dreaming that classVar would be sorted once for all.
Stef
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
This merely shows there are no tests testing the keys method of an IdentityDictionary which contains objects for which hash != identityHash... Cheers, Henry On Dec 4, 2009, at 9:06 25AM, Lukas Renggli wrote:
keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
Never mind, didn't notice IdentityDictionary reimplements keys... :/ On Dec 4, 2009, at 10:10 46AM, Henrik Johansen wrote:
This merely shows there are no tests testing the keys method of an IdentityDictionary which contains objects for which hash != identityHash...
Cheers, Henry
On Dec 4, 2009, at 9:06 25AM, Lukas Renggli wrote:
keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
do you have an idea why people did not use it? Stef On Dec 4, 2009, at 8:58 AM, Lukas Renggli wrote:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Em 04/12/2009 05:58, Lukas Renggli < renggli@gmail.com > escreveu:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
Why not: | result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each ifNil: [ each key ] ]). ^ result A bit more OO ;-) Reading Andrés' book is making more aware of those subtleties :-D My .019999... - Cesar Rabak
Yeah, this was my first attempt, but this implementation is ways slower. The block activations with #collect: matters. My implemebtation only calls primitives or inlined constructs. Not nice to look at, but as fast as it can get. Lukas On Friday, December 4, 2009, <csrabak@bol.com.br> wrote:
Em 04/12/2009 05:58, Lukas Renggli < renggli@gmail.com > escreveu:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
Why not:
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each ifNil: [ each key ] ]). ^ result
A bit more OO ;-)
Reading Andrés' book is making more aware of those subtleties :-D
My .019999...
- Cesar Rabak
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
I see. . . this is an interesting observation (about the performance penalty) on the issues of going really OO. In retrospect I think (once the concerns about the possibility of changing the semantics of the returned object) this is the way to go. We really need to have a competitive (in terms of raw computing performance) system! Em 04/12/2009 16:46, Lukas Renggli < renggli@gmail.com > escreveu: Yeah, this was my first attempt, but this implementation is ways slower. The block activations with #collect: matters. My implemebtation only calls primitives or inlined constructs. Not nice to look at, but as fast as it can get. Lukas
I would really like to get the changes suggested by nicolas so if one of you want to support by sending code it would be cool. We are trying to close some fixed issues (besides working on our little research activities). Stef On Dec 4, 2009, at 8:29 AM, Henrik Sperre Johansen wrote:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
participants (8)
-
csrabak＠bol.com.br -
Henrik Johansen -
Henrik Sperre Johansen
-
Igor Stasenko -
Lukas Renggli -
Nicolas Cellier -
Stéphane Ducasse -
Tudor Girba