[squeak-dev] The Inbox: Collections-cmm.870.mcz

commits at source.squeak.org commits at source.squeak.org
Sat Jan 4 01:59:24 UTC 2020


Chris Muller uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-cmm.870.mcz

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

Name: Collections-cmm.870
Author: cmm
Time: 3 January 2020, 7:59:19.257837 pm
UUID: b3e2efab-cf35-426d-9910-adab44aa4ed4
Ancestors: Collections-fn.869, Collections-ul.867

Building on Collections-ul.867, let "Dictionary new: anySize" _never_ be significantly slower than "Dictionary new".

=============== Diff against Collections-fn.869 ===============

Item was changed:
  ----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') -----
  goodPrimeAtLeast: lowerLimit
+ 	"Answer the smallest good prime >= lowerlimit.
+ 	If lowerLimit is larger than the largest known good prime, just make it odd.
+ 	Use linear search, and exponential search to speed up cases when lowerLimit is small (<2500 and <100000, respectively)."
- 	"Answer the next good prime >= lowerlimit.
- 	If lowerLimit is larger than the largest known good prime,
- 	just make it odd."
  	
+ 	| high mid low prime primes |
- 	| low mid high prime primes |
  	primes := self goodPrimes.
+ 	(primes at: primes size) < lowerLimit ifTrue: [
- 	high := primes size.
- 	lowerLimit > (primes at: high) ifTrue: [
  		^lowerLimit bitOr: 1 ].
+ 	lowerLimit < 2500 ifTrue: [
+ 		"Use linear search when the limit is small. The boundary is based on measurements."
+ 		high := 1.
+ 		[ 
+ 			(prime := primes at: high) >= lowerLimit ifTrue: [ ^prime ].
+ 			high := high + 1 ] repeat ].
+ 	lowerLimit < 100000 
+ 		ifTrue: [
+ 			"Use exponential search when the limit is not too large. The boundary is based on measurements."
+ 			high := 1.
+ 			[ (primes at: high) < lowerLimit ] whileTrue: [
+ 				high := high * 2 ].
+ 			low := high // 2 + 1. "high // 2 was smaller than lowerLimit" ]
+ 		ifFalse: [
+ 			"Regular binary search."
+ 			low := 1.
+ 			high := primes size ].
- 	low := 1.
  	[ high - low <= 1 ] whileFalse: [
  		mid := high + low // 2.
  		prime := primes at: mid.
  		lowerLimit < prime
  			ifTrue: [ high := mid ]
  			ifFalse: [
  				lowerLimit > prime
  					ifTrue: [ low := mid ]
  					ifFalse: [ ^prime ] ] ].
  	(primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
  	^primes at: high!

Item was changed:
  ----- Method: HashedCollection class>>sizeFor: (in category 'sizing') -----
  sizeFor: nElements
  	"Large enough prime (or odd if too large) size to hold nElements with some slop (see fullCheck)"
  	
+ 	nElements < 6 ifTrue: [ ^5 ].
- 	nElements < 4 ifTrue: [ ^5 ].
  	^self goodPrimeAtLeast: nElements + 1 * 4 // 3!

Item was changed:
  ----- Method: HashedCollection>>compact (in category 'private') -----
  compact
  	"Reduce the size of array so that the load factor will be ~75%."
  	
  	| newCapacity |
+ 	newCapacity := self class sizeFor: tally.
- 	newCapacity := self class goodPrimeAtLeast: tally * 4 // 3.
  	self growTo: newCapacity!



More information about the Squeak-dev mailing list