[Pharo-project] dictionary value is an array?
Hi nicolas If I remember you proposed fixes to have dictionary values -> array? Is it correct? I was wondering why? Because a set makes more sense to me since - the order of the elements in values is not useful (because they come from a dict) - the occurrences not really either - we cannot add to the results so we should create another collection May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that. Stef
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since     - the order of the elements in values is not useful (because they come from a dict)     - the occurrences not really either     - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly. Historically, they were a Bag and a Set because they were unordered. But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag. So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys. The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers. Nicolas
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since     - the order of the elements in values is not useful (because they come from a dict)     - the occurrences not really either     - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since     - the order of the elements in values is not useful (because they come from a dict)     - the occurrences not really either     - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
I agree. removing from another one's collection is not that well behaved ! It's putting expectations higher than necessary. I see this as a sort of optimization breaking encapsulation... I want to come with a better optimization. Unfortunately, historical uses will be found here and there, #keys being a well-known case. We have to put pressure on maintainers... Who ever takes this path shall be ready to sell the idea, and prove that gains > costs. A team modifying kernel in uncompatible manner (and we have to, or just stick to Squeak 3.7) shall provide support for a smooth transiiton. Sometimes I feel it would be convenient to inquire a code base larger than just an image, so that we can emit proposals and sell the idea rather than just waiting for complaints passively.... Nicolas
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary. For example, DictionaryKeys would be a subclass of Collection, behave like a Set and be implemented along ... Dictionary>>keys ^ DictionaryKeys on: self DictionaryKeys>>do: aBlock dictionary keysDo: aBlock DictionaryKeys>>includes: anObject ^ dictionary includesKey: anObject DictionaryKeys>>species ^ Set I bet that this would not only result in a major performance improvement, but also greatly reduce memory consumption. Furthermore it would solve the problem that #keys suddenly has totally different performance characteristics as we decide to return an Array instead of a Set. For example, it wouldn't matter anymore if you wrote aDictionary includesKey: #foo or aDictionary keys includes: #foo I see only obvious problem for such an approach and this is when the dictionary changes and the keys are stored somewhere. Some users might not expect the keys to change too. Cheers, Lukas -- Lukas Renggli http://www.lukas-renggli.ch
2009/10/31 Lukas Renggli <renggli@gmail.com>:
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary.
For example, DictionaryKeys would be a subclass of Collection, behave like a Set and be implemented along ...
  Dictionary>>keys     ^ DictionaryKeys on: self
  DictionaryKeys>>do: aBlock     dictionary keysDo: aBlock
  DictionaryKeys>>includes: anObject     ^ dictionary includesKey: anObject
  DictionaryKeys>>species     ^ Set
I bet that this would not only result in a major performance improvement, but also greatly reduce memory consumption. Furthermore it would solve the problem that #keys suddenly has totally different performance characteristics as we decide to return an Array instead of a Set. For example, it wouldn't matter anymore if you wrote
  aDictionary includesKey: #foo
or
  aDictionary keys includes: #foo
Yes, the proxy/wrapper pattern can be an elegant and efficient solution (a good example is ublas from BOOST library). It depends how many time you will iterate the collection though. Iterating a Set is often +2x the cost of iterating an Array.
I see only obvious problem for such an approach and this is when the dictionary changes and the keys are stored somewhere. Some users might not expect the keys to change too.
Yes, an immutable proxy with copy on write behaviour is challenging to implement...
Cheers, Lukas
-- 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
Lukas Renggli wrote:
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary.
+1, I've had similar thoughts. I'd think DictionaryKeys would need to be a read-only collection. Otherwise, what would be the effect of DictionaryKeys>>add: on the underlying Dictionary? And even worse effects of trying to add to a DictionaryValues... Regards, -Martin
2009/10/31 Martin McClure <martin@hand2mouse.com>:
Lukas Renggli wrote:
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary.
+1, I've had similar thoughts.
I'd think DictionaryKeys would need to be a read-only collection. Otherwise, what would be the effect of DictionaryKeys>>add: on the underlying Dictionary? And even worse effects of trying to add to a DictionaryValues...
Yeah, i talked about this earlier in this topic. I think that given approach can be generalized to serve for multiple purposes. Imagine a proxy object, which takes a collection and block with two arguments: | dictKeys | dictKeys := CollectionFilter new collection: (Object methodDict) filter: [:coll :aBlock | coll keysDo: [:each | aBlock value: each ] ]. dictKeys asSet There are many ways how this proxy can be used. For instance, a #reject: and #select: , in parallel we could have #rejectedBy: and #selectedBy: which creating a filter proxy instead of creating new collection: CollectionFilter class>>collection: aCollection rejectedBy: rejectBlock ^ self new collection: aCollection filter: [:coll :aBlock | coll do: [:each | (rejectBlock value: each) ifFalse: [ aBlock value: each ] ]]
Regards,
-Martin
_______________________________________________ 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.
2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Martin McClure <martin@hand2mouse.com>:
Lukas Renggli wrote:
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary.
+1, I've had similar thoughts.
I'd think DictionaryKeys would need to be a read-only collection. Otherwise, what would be the effect of DictionaryKeys>>add: on the underlying Dictionary? And even worse effects of trying to add to a DictionaryValues...
Yeah, i talked about this earlier in this topic. I think that given approach can be generalized to serve for multiple purposes.
Imagine a proxy object, which takes a collection and block with two arguments:
| dictKeys | dictKeys := CollectionFilter new collection: (Object methodDict) filter: [:coll :aBlock | Â Â Â Â coll keysDo: [:each | aBlock value: each ] ]. dictKeys asSet
There are many ways how this proxy can be used. For instance, a #reject: and #select: , in parallel we could have #rejectedBy: and #selectedBy: which creating a filter proxy instead of creating new collection:
CollectionFilter class>>collection: aCollection rejectedBy: rejectBlock  ^ self new collection: aCollection filter: [:coll :aBlock |    coll do: [:each | (rejectBlock value: each) ifFalse: [ aBlock value: each ]  ]]
That also has been generalized to stream. See Nile or gnu smalltalk for example.
Regards,
-Martin
_______________________________________________ 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.
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Watch out, because code like this may or may not work: someDictionary keys do: [:each | each isNotInteresting ifTrue: [someDictionary removeKey: each]] Thus, I think keys should answer a new collection. If the intent is to iterate over the keys, then I'd send the message directly to the dictionary. Andres. Lukas Renggli wrote:
It always annoyed me that #keys and #values create a new collection object. Form an object-oriented stand-point of view, what would rather make sense is to return a collection that delegates to the dictionary.
For example, DictionaryKeys would be a subclass of Collection, behave like a Set and be implemented along ...
Dictionary>>keys ^ DictionaryKeys on: self
DictionaryKeys>>do: aBlock dictionary keysDo: aBlock
DictionaryKeys>>includes: anObject ^ dictionary includesKey: anObject
DictionaryKeys>>species ^ Set
I bet that this would not only result in a major performance improvement, but also greatly reduce memory consumption. Furthermore it would solve the problem that #keys suddenly has totally different performance characteristics as we decide to return an Array instead of a Set. For example, it wouldn't matter anymore if you wrote
aDictionary includesKey: #foo
or
aDictionary keys includes: #foo
I see only obvious problem for such an approach and this is when the dictionary changes and the keys are stored somewhere. Some users might not expect the keys to change too.
Cheers, Lukas
Hello all, FWIW, Dolphin "lookup tables" use parallel arrays for keys and values. OA's claim (I do not dispute it, I'm simply reporting what they said) is that the result is faster than a dictionary based on associations. Bill -----Original Message----- From: pharo-project-bounces@lists.gforge.inria.fr [mailto:pharo-project-bounces@lists.gforge.inria.fr] On Behalf Of Nicolas Cellier Sent: Saturday, October 31, 2009 9:23 AM To: Pharo-project@lists.gforge.inria.fr Subject: Re: [Pharo-project] dictionary value is an array? 2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since     - the order of the elements in values is not useful (because they come from a dict)     - the occurrences not really either     - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
I agree. removing from another one's collection is not that well behaved ! It's putting expectations higher than necessary. I see this as a sort of optimization breaking encapsulation... I want to come with a better optimization. Unfortunately, historical uses will be found here and there, #keys being a well-known case. We have to put pressure on maintainers... Who ever takes this path shall be ready to sell the idea, and prove that gains > costs. A team modifying kernel in uncompatible manner (and we have to, or just stick to Squeak 3.7) shall provide support for a smooth transiiton. Sometimes I feel it would be convenient to inquire a code base larger than just an image, so that we can emit proposals and sell the idea rather than just waiting for complaints passively.... Nicolas
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ 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
2009/10/31 Schwab,Wilhelm K <bschwab@anest.ufl.edu>:
Hello all,
FWIW, Dolphin "lookup tables" use parallel arrays for keys and values. Â OA's claim (I do not dispute it, I'm simply reporting what they said) is that the result is faster than a dictionary based on associations.
Bill
Squeak.MethodDictionary is an example of this pattern too
-----Original Message----- From: pharo-project-bounces@lists.gforge.inria.fr [mailto:pharo-project-bounces@lists.gforge.inria.fr] On Behalf Of Nicolas Cellier Sent: Saturday, October 31, 2009 9:23 AM To: Pharo-project@lists.gforge.inria.fr Subject: Re: [Pharo-project] dictionary value is an array?
2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since     - the order of the elements in values is not useful (because they come from a dict)     - the occurrences not really either     - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
I agree. removing from another one's collection is not that well behaved ! It's putting expectations higher than necessary.
I see this as a sort of optimization breaking encapsulation... I want to come with a better optimization. Unfortunately, historical uses will be found here and there, #keys being a well-known case. We have to put pressure on maintainers... Who ever takes this path shall be ready to sell the idea, and prove that gains > costs.
A team modifying kernel in uncompatible manner (and we have to, or just stick to Squeak 3.7) shall provide support for a smooth transiiton. Sometimes I feel it would be convenient to inquire a code base larger than just an image, so that we can emit proposals and sell the idea rather than just waiting for complaints passively....
Nicolas
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ 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
what is a parallel array?
2009/10/31 Schwab,Wilhelm K <bschwab@anest.ufl.edu>:
Hello all,
FWIW, Dolphin "lookup tables" use parallel arrays for keys and values. OA's claim (I do not dispute it, I'm simply reporting what they said) is that the result is faster than a dictionary based on associations.
Bill
Squeak.MethodDictionary is an example of this pattern too
-----Original Message----- From: pharo-project-bounces@lists.gforge.inria.fr [mailto:pharo- project-bounces@lists.gforge.inria.fr] On Behalf Of Nicolas Cellier Sent: Saturday, October 31, 2009 9:23 AM To: Pharo-project@lists.gforge.inria.fr Subject: Re: [Pharo-project] dictionary value is an array?
2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since - the order of the elements in values is not useful (because they come from a dict) - the occurrences not really either - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
I agree. removing from another one's collection is not that well behaved ! It's putting expectations higher than necessary.
I see this as a sort of optimization breaking encapsulation... I want to come with a better optimization. Unfortunately, historical uses will be found here and there, #keys being a well-known case. We have to put pressure on maintainers... Who ever takes this path shall be ready to sell the idea, and prove that gains > costs.
A team modifying kernel in uncompatible manner (and we have to, or just stick to Squeak 3.7) shall provide support for a smooth transiiton. Sometimes I feel it would be convenient to inquire a code base larger than just an image, so that we can emit proposals and sell the idea rather than just waiting for complaints passively....
Nicolas
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ 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
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
I got it after sending it :) On Oct 31, 2009, at 5:31 PM, Stéphane Ducasse wrote:
what is a parallel array?
2009/10/31 Schwab,Wilhelm K <bschwab@anest.ufl.edu>:
Hello all,
FWIW, Dolphin "lookup tables" use parallel arrays for keys and values. OA's claim (I do not dispute it, I'm simply reporting what they said) is that the result is faster than a dictionary based on associations.
Bill
Squeak.MethodDictionary is an example of this pattern too
-----Original Message----- From: pharo-project-bounces@lists.gforge.inria.fr [mailto:pharo- project-bounces@lists.gforge.inria.fr] On Behalf Of Nicolas Cellier Sent: Saturday, October 31, 2009 9:23 AM To: Pharo-project@lists.gforge.inria.fr Subject: Re: [Pharo-project] dictionary value is an array?
2009/10/31 Igor Stasenko <siguctua@gmail.com>:
2009/10/31 Nicolas Cellier <nicolas.cellier.aka.nice@gmail.com>:
2009/10/31 Stéphane Ducasse <stephane.ducasse@inria.fr>:
Hi nicolas
If I remember you proposed fixes to have dictionary values -> array? Is it correct?
I was wondering why? Because a set makes more sense to me since - the order of the elements in values is not useful (because they come from a dict) - the occurrences not really either - we cannot add to the results so we should create another collection
May be I'm totally wrong with the changes but I think that values should be set while keys an array. I would be interested in discussion on that.
Stef
Dictionary values is already an Array... I proposed to change keys accordingly.
Historically, they were a Bag and a Set because they were unordered.
But very few or no sender expect a behavior specific to a Bag or a Set. Most just do: select: collect: asArray asSortedCollection etc... That's where an Array outperforms a Set or a Bag.
So we are paying the price of a Set or a Bag almost for nothing... And that is why you can see a #fasterKeys.
The drawback is that a few senders will add: to or remove: from keys. My estimation is around 5%. Inside the image, no problem, it is easy to fix, just write (someDictionary keys asSet). But that put a load on package maintainers.
+1 Nicolas. Personally, i think that modifying a collection which not constructed by your own code is bad programming style, because you never know where this collection is came from and you can't be sure that there is no other users of it, which in own turn may modify it at any moment, while often you assuming that only you own the collection and don't expecting any modifications to it except in own code. So, IMO this approach is error prone, and you should never use #remove: or #add: with collections which constructed by separate package/layer, and instead, use #asSet, #asOrderedCollection and, of course #copy, before starting manipulating its elements.
I agree. removing from another one's collection is not that well behaved ! It's putting expectations higher than necessary.
I see this as a sort of optimization breaking encapsulation... I want to come with a better optimization. Unfortunately, historical uses will be found here and there, #keys being a well-known case. We have to put pressure on maintainers... Who ever takes this path shall be ready to sell the idea, and prove that gains > costs.
A team modifying kernel in uncompatible manner (and we have to, or just stick to Squeak 3.7) shall provide support for a smooth transiiton. Sometimes I feel it would be convenient to inquire a code base larger than just an image, so that we can emit proposals and sell the idea rather than just waiting for complaints passively....
Nicolas
Nicolas
_______________________________________________ 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
-- Best regards, Igor Stasenko AKA sig.
_______________________________________________ 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
_______________________________________________ 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
Schwab,Wilhelm K wrote:
Hello all,
FWIW, Dolphin "lookup tables" use parallel arrays for keys and values. OA's claim (I do not dispute it, I'm simply reporting what they said) is that the result is faster than a dictionary based on associations.
Parallel arrays should indeed be faster than Associations. The overhead at add: time of creating a new Association object is an appreciable fraction of the overall add: time. But lookups should be even faster with a single array that alternates keys and values, an approach I often use. Why is this faster? Modern RAM isn't really "random access"; accesses to locations in the CPU cache can be up to two orders of magnitude faster than accesses to locations in main memory. If the key and value are next to each other, they are often in the same cache line, so the number of reads from main memory is halved. Regards, -Martin
participants (7)
-
Andres Valloud -
Igor Stasenko -
Lukas Renggli -
Martin McClure -
Nicolas Cellier -
Schwab,Wilhelm K -
Stéphane Ducasse