[squeak-dev] The Inbox: Collections-cmm.870.mcz
commits at source.squeak.org
commits at source.squeak.org
Sat Jan 4 22:09:02 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: 4 January 2020, 4:08:57.317384 pm
UUID: c4bf7594-c44e-4d02-9956-2b727d2eb75b
Ancestors: Collections-fn.869, Collections-ul.867
Tweak ul.867 so that:
Dictionary new: 3
is not 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>>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
|