Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers, - Andreas
Strange since we did not even introduce the changes of andrew on associations.... I will look at that.
Stef
On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
The other method in the same change set broke finalization in 3.9, BTW.
Daniel
stéphane ducasse wrote:
Strange since we did not even introduce the changes of andrew on associations.... I will look at that.
Stef
On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
Daniel
which cs?
Stef
The other method in the same change set broke finalization in 3.9, BTW.
Daniel
stéphane ducasse wrote:
Strange since we did not even introduce the changes of andrew on associations.... I will look at that. Stef On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
The offending method (Dictionary>>at:put:) has two versions, the most recent by cmm. Then I open the MC browser, select Collections package, press history, and start moving back through time. Collections-md.18 discusses a change by Chris Muller (initials fit).
Close history, go back to MC Browser, open the 39a repository, choose the offending version, open its history. Choose the version before it, 17, get a menu, and then a diff between 17 and 18. See offending methods.
Daniel
stéphane ducasse wrote:
Daniel
which cs?
Stef
The other method in the same change set broke finalization in 3.9, BTW.
Daniel
stéphane ducasse wrote:
Strange since we did not even introduce the changes of andrew on associations.... I will look at that. Stef On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
Note that while that is the correct answer in a way (that's the change set in the image that has that change), it is not what Stef really wanted because it doesn't give him traceability to where that change got in.
Its interesting that that code got into the wrong changeset. I don't know if that's a big deal, or we should just get used to using the MC related tools for this kind of thing.
Daniel
danil osipchuk wrote:
Seems to be in Collections-md.20 (method versions browser -> menu "find original cs")
Daniel
which cs?
Stef
agreed, thank you, Daniel
Note that while that is the correct answer in a way (that's the change set in the image that has that change), it is not what Stef really wanted because it doesn't give him traceability to where that change got in.
Its interesting that that code got into the wrong changeset. I don't know if that's a big deal, or we should just get used to using the MC related tools for this kind of thing.
Daniel
danil osipchuk wrote:
Seems to be in Collections-md.20 (method versions browser -> menu "find original cs")
Daniel
which cs?
Stef
do you know who is cmm?
because he is not registered on squeakmap (I think that we should set up a policy and tool support so that any code accepted in the image is identified and its license too...seems like a task for SqF).
On 18 sept. 05, at 10:57, Daniel Vainsencher wrote:
Note that while that is the correct answer in a way (that's the change set in the image that has that change), it is not what Stef really wanted because it doesn't give him traceability to where that change got in.
Its interesting that that code got into the wrong changeset. I don't know if that's a big deal, or we should just get used to using the MC related tools for this kind of thing.
Daniel
danil osipchuk wrote:
Seems to be in Collections-md.20 (method versions browser -> menu "find original cs")
Daniel
which cs?
Stef
On 18 sept. 05, at 10:49, danil osipchuk wrote:
Seems to be in Collections-md.20 (method versions browser -> menu "find original cs")
Where can I get this menu?
I looked in the dual change sorter and lot of places....:)
Now what I want to identify if this change is not related to other and that by going back to the previous behavior we do not introduce other bugs.
Stef
Daniel
which cs?
Stef
Ok here is the reason
Name: Collections-md.18 Author: md Time: 7 August 2005, 3:26:12 pm UUID: 2d15dd50-ce8c-43d6-9f4e-4bd108c2af7d Ancestors: Collections-md.17
Change Set: WeakKeyDictionaryNilsFix Date: 5 December 2004 Author: Chris Muller
fixes this bug
Subject: [BUG] WeakKeyDictionary>>keysAndValuesDo: Author: Chris Muller Date Posted: 8 June 2004 Archive ID: 22746 Comments: The following code demonstrates that keysAndValuesDo: will evaluate nil keys that have been gc'd.
| d | d _ WeakIdentityKeyDictionary new at: 'hello' copy put: nil; yourself. Smalltalk garbageCollectMost. d keysAndValuesDo: [ : k : v | k ifNil: [ self halt ] ]
I consider this a bug because it contradicts the notion that nil cannot be a key in a Dictionary. Incidentally, keysDo: passes the test.
Dictionary>>at: key put: anObject "Set the value at key to be anObject. If key is not found, create a new entry for key and set is value to anObject. Answer anObject."
| index assoc | key ifNil: [ self error: 'Dictionaries cannot meaningfully key by nil.' ]. index _ self findElementOrNil: key. assoc _ array at: index. assoc ifNil: [self atNewIndex: index put: (Association key: key value: anObject)] ifNotNil: [assoc value: anObject]. ^ anObject
WeakKeyDictionary>>associationsDo: aBlock "Evaluate aBlock for each of the receiver's elements (key/value associations)."
super associationsDo: [ : eachAssoc | | eachKey | eachKey _ eachAssoc key. "reference to ensure no GC" eachKey ifNotNil: [ aBlock value: eachAssoc ] ]
I checked in VW nil is not a valid key for a dictionary
|d| d := Dictionary new. d at: nil put: #none.
Boum
at: key put: anObject "Set the value at key to be anObject. If key is not found, create a new entry for key and set is value to anObject. Answer anObject."
| index element | key == nil ifTrue: [^self subscriptBoundsErrorFor: #at:put: index: nil value: anObject]. index := self findKeyOrNil: key. element := self basicAt: index. element == nil ifTrue: [self atNewIndex: index put: (self createKey: key value: anObject)] ifFalse: [element value: anObject]. ^anObject
Stef
On 18 sept. 05, at 09:33, stéphane ducasse wrote:
Strange since we did not even introduce the changes of andrew on associations.... I will look at that.
Stef
On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
On 18 sept. 05, at 08:48, Andreas Raab wrote:
Hi -
Trying out some stuff, I noticed that
dd := Dictionary new. dd at: nil put: #none.
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Andreas why are you saying that with that kind of implication. Now you can get mad about changes, this is perfectly comprehensible but try to be nicer, your kind of anger does not help us.
I do not know why the behavior changed. I'm adding a test to cover this exact semantics point. Now as I say in my previous email nil is not allowed in Visualworks, I do not have dolphin at hand.
I checked the ansi standard for what it is good at:
p, 168 5.7.2.5 Message: at: key put: newElement Synopsis Store newElement at key in the receiver. Answer newElement. Definition: <abstractDictionary> If lookup succeeds for key, then newElement replaces the element previously stored at key. Otherwise, the newElement is stored at the new key. In either case, subsequent successful lookups for key will answer newElement. Answer newElement.
The result is undefined if the key is nil.
This clearly indicates that different smalltalks where doing different assumptions.
Now if this was possible in 3.8 I think that this is better to keep it like that. You see I can even be constructiv and positive.
So now let us find the guilty cs.
Stef
Could somebody please explain to me why we no longer allow a perfectly good key in dictionaries?
Cheers,
- Andreas
-----Message d'origine----- De : squeak-dev-bounces@lists.squeakfoundation.org [mailto:squeak-dev-bounces@lists.squeakfoundation.org] De la part de stéphane ducasse Envoyé : dimanche 18 septembre 2005 10:30 À : The general-purpose Squeak developers list Objet : Re: Dictionaries broken in 3.9a
[..]
Now as I say in my previous email nil is not allowed in Visualworks, I do not have dolphin at hand.
I tried in Dolphin Smalltalk Professional 5.1.4 :
12:21:24, dimanche 18 septembre 2005: 'key cannot be nil' Dictionary(Object)>>error: Dictionary>>at:put: [..]
Joseph
Hi All,
I am new to Squeak, and haven't done anything with it yet but I have been reading the news group to catch up on what is going on with Squeak.
I tried in Dolphin Smalltalk Professional 5.1.4 :
12:21:24, dimanche 18 septembre 2005: 'key cannot be nil' Dictionary(Object)>>error: Dictionary>>at:put: [..]
In VAST (IBM's VisualAge for Smalltalk) a LookupTable can not have a nil key but a Dictionary can. Dictionaries contain Associations and they have no problem with a nil key so I guess Dictionaries don't have a problem either. In past versions of VAST (before 5.5.2) LookupTables could have a nil key but that changed.
Lou ----------------------------------------------------------- Louis LaBrunda Keystone Software Corp. SkypeMe callto://PhotonDemon mailto:Lou@Keystone-Software.com http://www.Keystone-Software.com
stéphane ducasse wrote:
will raise an error in 3.9a saying that "Dictionaries cannot meaningfully key by nil". That makes no sense. Dictionaries can perfectly contain nil keys, they always have and they always will.
Andreas why are you saying that with that kind of implication. Now you can get mad about changes, this is perfectly comprehensible but try to be nicer, your kind of anger does not help us.
Actually, I'm not mad (at least not at the author) and the above should really be read with a big "sigh" upfront. It is likely that the author was inspired by the error message from Set (notice the similarity between "Sets cannot meaningfully contain nil as an element" and "Dictionaries cannot meaningfully key by nil") probably assuming that because Dictionaries are Sets of sorts the same invariant would hold.
However, in Set there is an an ambiguity between a free slot in a set and a slot containing nil[*] but in dictionaries we store associations and therefore we can distinguish between an empty slot and a slot keyed by nil. And therefore, *sigh*, Dictionaries have always contained nil keys and they always will :-)
[*] Which would be easy enough to fix if someone really cared.
Now as I say in my previous email nil is not allowed in Visualworks, I do not have dolphin at hand.
That's hillarious! In particular considering that VW allows nil in sets...
Cheers, - Andreas
Andreas.
Ok I understand. Next time put sigh..... Now I try to understand the relation will the WeakDictionary fix presented in my previous email.
Actually, I'm not mad (at least not at the author) and the above should really be read with a big "sigh" upfront. It is likely that the author was inspired by the error message from Set (notice the similarity between "Sets cannot meaningfully contain nil as an element" and "Dictionaries cannot meaningfully key by nil") probably assuming that because Dictionaries are Sets of sorts the same invariant would hold.
However, in Set there is an an ambiguity between a free slot in a set and a slot containing nil[*] but in dictionaries we store associations and therefore we can distinguish between an empty slot and a slot keyed by nil. And therefore, *sigh*, Dictionaries have always contained nil keys and they always will :-)
[*] Which would be easy enough to fix if someone really cared.
Now as I say in my previous email nil is not allowed in Visualworks,
That's hillarious! In particular considering that VW allows nil in sets...
But this is like that. Certainly result of an evolution or not breaking client code process. By the way you should have a look at HashTable on Squeaksource because the implementation of Dictionary there is much better in terms of collision strategy.
Stef
On 9/18/05, stéphane ducasse ducasse@iam.unibe.ch wrote:
By the way you should have a look at HashTable on Squeaksource because the implementation of Dictionary there is much better in terms of collision strategy.
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash. However, it doesn't seem to work yet as a drop-in replacement for Dictionary/IdentityDictionary in all cases. I'm right now scratching my head over why, in an old version of OmniBase, I consistently get a deadlock when using IdentityHashTable to map objects to IDs, but it works fine using either ODBIdentityDictionary or the standard Squeak IdentityDictionary.
Avi
On Sep 18, 2005, at 6:54 PM, Avi Bryant wrote:
However, it doesn't seem to work yet as a drop-in replacement for Dictionary/IdentityDictionary in all cases. I'm right now scratching my head over why, in an old version of OmniBase, I consistently get a deadlock when using IdentityHashTable to map objects to IDs, but it works fine using either ODBIdentityDictionary or the standard Squeak IdentityDictionary.
Aha. For what it's worth, the problem here was that HashTable was written under Squeak >= 3.7, and so was expecting #new to automatically #initialize - which means it was broken under 3.6, where I was trying to use it (ah, legacy apps...).
Avi
Thanks for testing it. Because it needs testing :) But I was blasted by the flatness of the curve Stef
On 9/18/05, stéphane ducasse ducasse@iam.unibe.ch wrote:
By the way you should have a look at HashTable on Squeaksource because the implementation of Dictionary there is much better in terms of collision strategy.
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash. However, it doesn't seem to work yet as a drop-in replacement for Dictionary/IdentityDictionary in all cases. I'm right now scratching my head over why, in an old version of OmniBase, I consistently get a deadlock when using IdentityHashTable to map objects to IDs, but it works fine using either ODBIdentityDictionary or the standard Squeak IdentityDictionary.
Avi
"stéphane ducasse" ducasse@iam.unibe.ch wrote:
Thanks for testing it. Because it needs testing :)
Well, here are more results:
When I tried to load SqueakSource into an image that uses the ClosureCompiler I found that SqueakSource does not compile under the new compiler for a surprisingly simple reason: Our old compiler tolerates some syntax errors and the new compiler is very strict about syntax.
Specifically the new compiler does not allow a period after the end of the message header and it does not allow two periods in sequence.
In the SqueakSource package, the definition that stops compilation is SSHelp>>renderWhatIsOn:
In this method, a period follows the message header:
renderWhatIsOn: html. html heading: 'What is SqueakSource?' level: 2. <code that follow truncated>
We may have this problem in other code too and I think that we should check all our more important packages with the new compiler. After all, the removal of wrong periods is not that difficult, but we have to do it.
Greetings, Boris
Boris Gaertner wrote:
Specifically the new compiler does not allow a period after the end of the message header and it does not allow two periods in sequence.
That's bad. "Forgiving on input, strict on output" is generally a good rule to follow. The compiler should definitely accept the above when invoked non-interactively; whether it'll accept accept it for interactive input is another question (is this actually a "syntax error" by any measures?).
Cheers, - Andreas
Avi Bryant wrote:
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash.
But you are aware that the current behavior is the result of a very particular set initialization that is easily fixed, yes? Changing the initial set capacity from 3 to 5 will *dramatically* improve the behavior ;-)
Besides, I'd be much more interested in a hashtable/dictionary implementation that preserves ordering (e.g., if an element is added before another it will be enumerated before the other) to preserve consistency in a replicated computation. I'll definitely need to look into this so if anyone has an implementation I'm all ears...
Cheers, - Andreas
On 19 sept. 05, at 09:26, Andreas Raab wrote:
Avi Bryant wrote:
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash.
But you are aware that the current behavior is the result of a very particular set initialization that is easily fixed, yes? Changing the initial set capacity from 3 to 5 will *dramatically* improve the behavior ;-)
So send a fix so that we change the default.
Now what I understood is that the degeneration is bad in the current implementation, since collisions generates more chance that other collision will occur. So on large dicts this is dramatic.
Besides, I'd be much more interested in a hashtable/dictionary implementation that preserves ordering (e.g., if an element is added before another it will be enumerated before the other) to preserve consistency in a replicated computation. I'll definitely need to look into this so if anyone has an implementation I'm all ears...
Does the default one preserve ordering? Not that nothing prevent us to have two kind of dictionary with specific behavior.
Stef
Cheers,
- Andreas
Am 19.09.2005 um 09:26 schrieb Andreas Raab:
Avi Bryant wrote:
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash.
But you are aware that the current behavior is the result of a very particular set initialization that is easily fixed, yes? Changing the initial set capacity from 3 to 5 will *dramatically* improve the behavior ;-)
The problem Phillippe solved is another: He made hash collisions cheaper. In Squeak, we have only 4096 different hash values, so if a collection get larger, collisions will occur. Now the current implementation has a very simple, but expensive collision resolving: It just takes the next free slot and puts the value there. When searching, it takes the slot calculated by the hash, looks if the entry really is there, if not, it will do a linear search starting at the calculated position.
The problem now is that this means that solving one collission will make another slot a collision, too. So dictionaries degenerate to a linear search quite fast, even if the hash is nicely distributed and spread correctly.
Phillipe uses a linked list for the solving collisions: If there is a collision, the slot will contain the head of a linked list. So if we have a nicely equally distributed hash in a 40.000 element dictionary, this will lead to 4096 10- element linked lists, accessible via the hash. In this case we just need to do a linear seach the 10-element linked list, which still is quite fast. And even if the hash value or spread is not perfect, this we make sure that we don't destroy other slots with each collision.
Marcus
"Marcus" == Marcus Denker denker@iam.unibe.ch writes:
Marcus> Phillipe uses a linked list for the solving collisions: If Marcus> there is a collision, the slot will contain the head of a Marcus> linked list.
Yup, he implemented what is called an "open hash table" while the previous implementation was using a "closed hash table".
Closed hash tables are typically used on systems where dynamic allocation is expensive or when values all use the same size (pointers for examples). In my experience, open hash tables are much more suitable to general purpose dictionaries than closed hash tables.
Sam
Am 19.09.2005 um 09:26 schrieb Andreas Raab:
Besides, I'd be much more interested in a hashtable/dictionary implementation that preserves ordering (e.g., if an element is added before another it will be enumerated before the other) to preserve consistency in a replicated computation. I'll definitely need to look into this so if anyone has an implementation I'm all ears...
Skiplists are a kind of blend between OrderedCollection and Dictionary: You have a defined ordering (like in OrderedCollection, that is, your objects would need to implement #<, or you can provide a sortBlock), and are free-access like dictionaries. And the best, they are quite efficient.
There is an enhanced implementation on Mantis:
http://bugs.impara.de/view.php?id=1555
" A skiplist is a sorted data structure that allows one to search for any element in o(log n) time.
It also allows one to enumerate forward to the next element. Basically, its a tree-like algorithm, except it doesn't use trees.
The implementation here is similar to a Dictionary, in that it indexes (a subclass of) Associations. Thus, you can do foo at: key put: value You can also search for a key, if the key does not exist, it will report the first key greater than the search, or nil. "
So if your events have an ordering (a timestamp), then this should be worth a look.
Marcus
It is a suggestion from a guy who often puts bad names to classes, but 'HashTable' sounds like a too internal representation dependent name.
Can we come up with something based on its external behavior? (like BlahBlahMap to make Java people happy?^^;)
-- Yoshiki
At Sun, 18 Sep 2005 18:54:57 -0700, Avi Bryant wrote:
On 9/18/05, stéphane ducasse ducasse@iam.unibe.ch wrote:
By the way you should have a look at HashTable on Squeaksource because the implementation of Dictionary there is much better in terms of collision strategy.
Seconded. It uses quite a bit more memory than a standard Dictionary, but the performance appears to be impressively flat while growing to very large sizes, even when using the anemic #identityHash. However, it doesn't seem to work yet as a drop-in replacement for Dictionary/IdentityDictionary in all cases. I'm right now scratching my head over why, in an old version of OmniBase, I consistently get a deadlock when using IdentityHashTable to map objects to IDs, but it works fine using either ODBIdentityDictionary or the standard Squeak IdentityDictionary.
Avi
Can we come up with something based on its external behavior? (like BlahBlahMap to make Java people happy?^^;)
Oh well, there is actually a Hashtable in Java http://java.sun.com/j2se/1.5.0/docs/api/java/util/Hashtable.html
Yeah, I could name it HashMap (like Java) HashDictionary or HTDictionary (and add HT to all classnames) or whatever. I'm open for suggestions but I don't have the impression that making Java users happy or feel at home as any priority around here ;)
Am 19.09.2005 um 21:31 schrieb Yoshiki Ohshima:
It is a suggestion from a guy who often puts bad names to classes, but 'HashTable' sounds like a too internal representation dependent name.
Can we come up with something based on its external behavior? (like BlahBlahMap to make Java people happy?^^;)
What about "Dictionary" ;-)
Marcus
Marcus,
It is a suggestion from a guy who often puts bad names to classes, but 'HashTable' sounds like a too internal representation dependent name.
Can we come up with something based on its external behavior? (like BlahBlahMap to make Java people happy?^^;)
What about "Dictionary" ;-)
That was exactly my ideal preference, if we live in the ideal world^^;
-- Yoshiki
Hello Andreas,
AR> That's hillarious! In particular considering that VW allows nil in AR> sets...
The expressions
Set with: nil
and
Set new add: nil; yourself
answer an empty set in VW 7.2.1. Has this changed in VW 7.3.x?
I don't know about VW but sets are often implemented (VAST) with nils as empty place holders as a memory allocation efficiency but the nils are not considered part of the set or the count of items in the set. So:
Set with: nil
and
Set new add: nil; yourself
might create valid sets but I expect they are empty.
Lou
On Sun, 18 Sep 2005 14:47:48 -0500, Andres Valloud sqrmax@optonline.net wrote:
Hello Andreas,
AR> That's hillarious! In particular considering that VW allows nil in AR> sets...
The expressions
Set with: nil
and
Set new add: nil; yourself
answer an empty set in VW 7.2.1. Has this changed in VW 7.3.x?
----------------------------------------------------------- Louis LaBrunda Keystone Software Corp. SkypeMe callto://PhotonDemon mailto:Lou@Keystone-Software.com http://www.Keystone-Software.com
squeak-dev@lists.squeakfoundation.org
-
Andreas Raab -
Andres Valloud -
Avi Bryant -
Boris Gaertner -
Daniel Vainsencher -
danil osipchuk -
Joseph Frippiat -
Louis LaBrunda -
Marcus Denker -
Philippe Marschall -
Samuel Tardieu -
stéphane ducasse -
Yoshiki Ohshima