headers
Andreas Raab | 1 Dec 02:45
Picon
Picon

Re: Hash changes

Thanks. Now I see what's happening. The problem is that adding objects 
without scaled hash to a "regular" Dictionary creates hugely 
disproportional collision chain(s) as soon as we get north of 4096 
objects. At this point all the possible entries that any new object 
could have by default are already taken and since we use a linear 
collision chain they combine into one gigantonormeous (hope I spelled 
that correctly :-) collision chain.

That explains the difference - for larger number of elements we end up 
(with your changes) with an average length of the collision chain being 
(dict size // 4096) for both adding and accessing where without the 
scale we end up with a collision chain of (dict size) length (for 
adding) and (dict size // 2) for accessing elements once all possible 
initial slots are filled up and spill over.

(and we should probably add a comment explaining the issue)

Cheers,
   - Andreas

Levente Uzonyi wrote:
> On Mon, 30 Nov 2009, Andreas Raab wrote:
> 
>>> | test array |
>>> Transcript open; cr.
>>> test := Dictionary new.
>>
>> "There used to be an old issue with growth of Sets that were initially
>> sized with goodSizeFor: 3. Try working around it by starting at 5."
>> test := Dictionary new: 5.
(Continue reading)

Permalink | Reply | 2 comments |
headers
commits | 1 Dec 04:32
Favicon

The Trunk: ST80-dtl.73.mcz

David T. Lewis uploaded a new version of ST80 to project The Trunk:
http://source.squeak.org/trunk/ST80-dtl.73.mcz

==================== Summary ====================

Name: ST80-dtl.73
Author: dtl
Time: 30 November 2009, 11:28:51 am
UUID: 3fba2d46-02e6-43ff-b0d0-d5c1398604a6
Ancestors: ST80-dtl.72

Better progress display handling and rudimentary MVC implementations for
  Project>>loadFromServer:
  Project>>storeOnServerWithProgressInfo:
  Project>>storeOnServerWithProgressInfoOn:

=============== Diff against ST80-dtl.72 ===============

Item was added:
+ ----- Method: MVCProject>>do:withProgressInfoOn:label: (in category 'utilities') -----
+ do: aBlock withProgressInfoOn: aMorphOrNil label: aString
+ 	"Evaluate aBlock with a labeled progress bar. Use a simple progress
+ 	bar set to 50% progress. In Morphic, progress is displayed with a
+ 	ComplexProgressIndicator."
+ 
+ 	aString
+ 		displayProgressAt: Sensor cursorPoint
+ 		from: 0 to: 2
+ 		during: [:bar |  bar value: 1.
+ 				aBlock value]
(Continue reading)

Permalink | Reply | 0 comments |
headers
commits | 1 Dec 04:36
Favicon

The Trunk: Morphic-dtl.259.mcz

David T. Lewis uploaded a new version of Morphic to project The Trunk:
http://source.squeak.org/trunk/Morphic-dtl.259.mcz

==================== Summary ====================

Name: Morphic-dtl.259
Author: dtl
Time: 30 November 2009, 11:30:24 am
UUID: 48904b07-454e-4225-8681-5583dc4c124f
Ancestors: Morphic-dtl.258

Better progress display handling and rudimentary MVC implementations for
  Project>>loadFromServer:
  Project>>storeOnServerWithProgressInfo:
  Project>>storeOnServerWithProgressInfoOn:

=============== Diff against Morphic-dtl.258 ===============

Item was added:
+ ----- Method: MorphicProject>>do:withProgressInfoOn:label: (in category 'utilities') -----
+ do: aBlock withProgressInfoOn: aMorphOrNil label: aString
+ 	"Evaluate aBlock with a labeled progress bar"
+ 
+ 	ComplexProgressIndicator new 
+ 		targetMorph: aMorphOrNil;
+ 		historyCategory: aString;
+ 		withProgressDo: aBlock
+ !

Item was removed:
(Continue reading)

Permalink | Reply | 0 comments |
headers
commits | 1 Dec 04:39
Favicon

The Trunk: System-dtl.185.mcz

David T. Lewis uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-dtl.185.mcz

==================== Summary ====================

Name: System-dtl.185
Author: dtl
Time: 30 November 2009, 11:33:29 am
UUID: a7bc8a25-1b42-4de8-b16d-df3161022216
Ancestors: System-dtl.184

Better progress display handling and rudimentary MVC implementations for
  Project>>loadFromServer:
  Project>>storeOnServerWithProgressInfo:
  Project>>storeOnServerWithProgressInfoOn:

=============== Diff against System-dtl.184 ===============

Item was changed:
  ----- Method: Project>>loadFromServer: (in category 'file in/out') -----
  loadFromServer: newerAutomatically
  	"If a newer version of me is on the server, load it."
+ 	| pair resp server |
+ 	self assureIntegerVersion.

+ 	self isCurrentProject ifTrue: ["exit, then do the command"
+ 		^ self armsLengthCommand: #loadFromServer withDescription: 'Loading' translated
+ 	].
+ 	server := self tryToFindAServerWithMe ifNil: [^ nil].
+ 	pair := self class mostRecent: self name onServer: server.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Levente Uzonyi | 1 Dec 05:21
Picon
Picon
Favicon

Re: Re: Hash changes

On Tue, 1 Dec 2009, Levente Uzonyi wrote:

> On Mon, 30 Nov 2009, Levente Uzonyi wrote:
>> 
>> (I'm about to upload 2 more packages because the inlining trick used in the 
>> implementation doesn't work with SmallIntegers (LargeIntegers can be 
>> created while calculating the hash) and the enhancement for WeakSet growing 
>> is missing)
>
> Two packages are not sufficent, so I'll update some of the exisiting mczs.
>

The new versions are in the inbox. The load order is:
Collections-ul.217 "Initialization"
Kernel-ul.312 "Object >> #hash"
Kernel-ul.313
Kernel-ul.314
Collections-ul.228 "IdentityDictionary"
Collections-ul.229
Collections-ul.230 "KeyedIdentitySet"
Collections-ul.231
Collections-ul.232 "WeakIdentityKeyDictionary"
Collections-ul.233
Collections-ul.234 "IdentitySet"
Collections-ul.235
System-ul.185 "SystemDictionary"
System-ul.186
System-ul.187
Collections-ul.236 "Cleanup"
Collections-ul.237
(Continue reading)

Permalink | Reply | 5 comments |
headers
Andreas Raab | 1 Dec 05:32
Picon
Picon

Re: Hash changes

Levente Uzonyi wrote:
> The new versions are in the inbox. The load order is:

Thanks, I'll give it a shot. Folks, if you read this please abstain from 
posting or updating while I'm in the process of integrating these 
changes. I'll post an all clear message when I'm done. (plus: brace for 
a flurry of commit messages and knock on wood that the server doesn't 
die on the last commit ;-)

Cheers,
   - Andreas

> Collections-ul.217 "Initialization"
> Kernel-ul.312 "Object >> #hash"
> Kernel-ul.313
> Kernel-ul.314
> Collections-ul.228 "IdentityDictionary"
> Collections-ul.229
> Collections-ul.230 "KeyedIdentitySet"
> Collections-ul.231
> Collections-ul.232 "WeakIdentityKeyDictionary"
> Collections-ul.233
> Collections-ul.234 "IdentitySet"
> Collections-ul.235
> System-ul.185 "SystemDictionary"
> System-ul.186
> System-ul.187
> Collections-ul.236 "Cleanup"
> Collections-ul.237
>
(Continue reading)

Permalink | Reply | 4 comments |
headers
commits | 1 Dec 05:38
Favicon

The Trunk: Collections-ul.217.mcz

Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.217.mcz

==================== Summary ====================

Name: Collections-ul.217
Author: ul
Time: 30 November 2009, 4:47:54 am
UUID: a67f6177-4f3f-bd41-af32-c1881c7f0e20
Ancestors: Collections-ul.216

Replace sends of #scanForEmptySlotFor: with #scanFor:. This enables atomic changes of the hash implementation.

=============== Diff against Collections-dtl.214 ===============

Item was added:
+ ----- Method: CollectionRehashingUtility>>rehashAllSets (in category 'private - rehashing') -----
+ rehashAllSets
+ 
+ 	HashedCollection rehashAll!

Item was added:
+ ----- Method: CollectionRehashingUtility class>>rehashBecause: (in category 'rehashing') -----
+ rehashBecause: aSymbol
+ 
+ 	self new rehashBecause: aSymbol!

Item was changed:
  ----- Method: KeyedSet>>noCheckNoGrowFillFrom: (in category 'private') -----
  noCheckNoGrowFillFrom: anArray
(Continue reading)

Permalink | Reply | 0 comments |
headers
commits | 1 Dec 05:41
Favicon

The Trunk: Kernel-ul.312.mcz

Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.312.mcz

==================== Summary ====================

Name: Kernel-ul.312
Author: ul
Time: 1 December 2009, 4:19:45 am
UUID: 5b9007f4-b0f3-1e42-bf32-5a0efbeaae0f
Ancestors: Kernel-nice.307

Added #scaledIdentityHash.
Part 1 of updating Object >> hash.

=============== Diff against Kernel-nice.307 ===============

Item was added:
+ ----- Method: SmallInteger>>scaledIdentityHash (in category 'comparing') -----
+ scaledIdentityHash
+ 	"For identityHash values returned by primitive 75, answer
+ 	such values times 2^18.  Otherwise, match the existing
+ 	identityHash implementation"
+ 	
+ 	^self!

Item was added:
+ ----- Method: ProtoObject>>scaledIdentityHash (in category 'comparing') -----
+ scaledIdentityHash
+ 	"For identityHash values returned by primitive 75, answer
+ 	such values times 2^18.  Otherwise, match the existing
(Continue reading)

Permalink | Reply | 0 comments |
headers
commits | 1 Dec 05:43
Favicon

The Trunk: Kernel-ul.313.mcz

Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.313.mcz

==================== Summary ====================

Name: Kernel-ul.313
Author: ul
Time: 1 December 2009, 4:22:35 am
UUID: 46ec2793-b46f-fa4c-9149-63e980f5625f
Ancestors: Kernel-ul.312

Part 2 of updating Object >> #hash.

=============== Diff against Kernel-ul.312 ===============

Item was changed:
  ----- Method: Object>>hash (in category 'comparing') -----
  hash
  	"Answer a SmallInteger whose value is related to the receiver's identity.
  	May be overridden, and should be overridden in any classes that define = "

- 	CollectionRehashingUtility quickRehashBecause: #objectHashChanged.
  	^self scaledIdentityHash!
Permalink | Reply | 0 comments |
headers
commits | 1 Dec 05:45
Favicon

The Trunk: Kernel-ul.314.mcz

Andreas Raab uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-ul.314.mcz

==================== Summary ====================

Name: Kernel-ul.314
Author: ul
Time: 1 December 2009, 4:23:11 am
UUID: e293d76b-d182-a44c-b21f-1819da8fa9ec
Ancestors: Kernel-ul.313

Removed preamble.

=============== Diff against Kernel-ul.313 ===============
Permalink | Reply | 0 comments |

Gmane