The Inbox: Collections-cmm.873.mcz

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

The Inbox: Collections-cmm.873.mcz

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

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

Name: Collections-cmm.873
Author: cmm
Time: 21 January 2020, 11:54:25.478956 pm
UUID: 3ec60cd4-3b16-4cf7-98bf-bc85acaa4192
Ancestors: Collections-ul.871

Let #new: *always* be a performance-improving choice over #new, when the correct size is known.

=============== Diff against Collections-ul.871 ===============

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).
  Assume that there are goodPrimes greater than 100000."
 
  | highIndex midIndex lowIndex prime |
- lowerLimit <= 7 ifTrue: [
- lowerLimit <= 3 ifTrue: [ ^3 ].
- lowerLimit <= 5 ifTrue: [ ^5 ].
- ^7 ].
  GoodPrimes ifNil: [ "migration only"
  self initializeGoodPrimes ].
  lowerLimit < 2500 ifTrue: [
  "Use linear search when the limit is small. The boundary is based on measurements."
  highIndex := 4. "skip 3 5 and 7"
  [ (GoodPrimes at: highIndex) < lowerLimit ] whileTrue: [
  highIndex := highIndex + 1 ].
  ^GoodPrimes at: highIndex ].
  lowerLimit < 100000
  ifTrue: [
  "Use exponential search when the limit is not too large. The boundary is based on measurements."
  highIndex := 1.
  [ (GoodPrimes at: highIndex) < lowerLimit ] whileTrue: [
  highIndex := highIndex * 2 ].
  lowIndex := highIndex // 2 + 1. "highIndex // 2 was smaller than lowerLimit" ]
  ifFalse: [
  "Regular binary search."
  lowIndex := 1.
  highIndex := GoodPrimes size.
  "Check whether the largest prime would fit"
  (GoodPrimes at: highIndex) < lowerLimit ifTrue: [
  ^lowerLimit bitOr: 1 ]. ].
  [ highIndex - lowIndex <= 1 ] whileFalse: [
  midIndex := highIndex + lowIndex // 2.
  prime := GoodPrimes at: midIndex.
  lowerLimit < prime
  ifTrue: [ highIndex := midIndex ]
  ifFalse: [
  lowerLimit > prime
  ifTrue: [ lowIndex := midIndex ]
  ifFalse: [ ^prime ] ] ].
  (GoodPrimes at: lowIndex) >= lowerLimit ifTrue: [ ^GoodPrimes at: lowIndex ].
  ^GoodPrimes at: highIndex!

Item was changed:
  ----- Method: HashedCollection class>>new: (in category 'instance creation') -----
+ new: numberOfElements
+ "Create a Set large enough to hold numberOfElements without growing"
+ ^ self basicNew initialize:
+ (numberOfElements < 3
+ ifTrue: [ 3 ]
+ ifFalse:
+ [ numberOfElements < 4
+ ifTrue: [ 5 ]
+ ifFalse: [ self sizeFor: numberOfElements ] ])!
- new: nElements
- "Create a Set large enough to hold nElements without growing"
- ^ self basicNew initialize: (self sizeFor: nElements)!


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-cmm.873.mcz

Tobias Pape
-1

I still don't buy the rationale.
If a collection is _That_ small and you _require_ #new: to be faster than #new, use an Array and do things yourself.
Really, there's no need to make #new: complicated.


Best regards
        -Tobias

> On 22.01.2020, at 06:54, [hidden email] wrote:
>
> Chris Muller uploaded a new version of Collections to project The Inbox:
> http://source.squeak.org/inbox/Collections-cmm.873.mcz
>
> ==================== Summary ====================
>
> Name: Collections-cmm.873
> Author: cmm
> Time: 21 January 2020, 11:54:25.478956 pm
> UUID: 3ec60cd4-3b16-4cf7-98bf-bc85acaa4192
> Ancestors: Collections-ul.871
>
> Let #new: *always* be a performance-improving choice over #new, when the correct size is known.
>
> =============== Diff against Collections-ul.871 ===============
>
> 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).
>   Assume that there are goodPrimes greater than 100000."
>  
>   | highIndex midIndex lowIndex prime |
> - lowerLimit <= 7 ifTrue: [
> - lowerLimit <= 3 ifTrue: [ ^3 ].
> - lowerLimit <= 5 ifTrue: [ ^5 ].
> - ^7 ].
>   GoodPrimes ifNil: [ "migration only"
>   self initializeGoodPrimes ].
>   lowerLimit < 2500 ifTrue: [
>   "Use linear search when the limit is small. The boundary is based on measurements."
>   highIndex := 4. "skip 3 5 and 7"
>   [ (GoodPrimes at: highIndex) < lowerLimit ] whileTrue: [
>   highIndex := highIndex + 1 ].
>   ^GoodPrimes at: highIndex ].
>   lowerLimit < 100000
>   ifTrue: [
>   "Use exponential search when the limit is not too large. The boundary is based on measurements."
>   highIndex := 1.
>   [ (GoodPrimes at: highIndex) < lowerLimit ] whileTrue: [
>   highIndex := highIndex * 2 ].
>   lowIndex := highIndex // 2 + 1. "highIndex // 2 was smaller than lowerLimit" ]
>   ifFalse: [
>   "Regular binary search."
>   lowIndex := 1.
>   highIndex := GoodPrimes size.
>   "Check whether the largest prime would fit"
>   (GoodPrimes at: highIndex) < lowerLimit ifTrue: [
>   ^lowerLimit bitOr: 1 ]. ].
>   [ highIndex - lowIndex <= 1 ] whileFalse: [
>   midIndex := highIndex + lowIndex // 2.
>   prime := GoodPrimes at: midIndex.
>   lowerLimit < prime
>   ifTrue: [ highIndex := midIndex ]
>   ifFalse: [
>   lowerLimit > prime
>   ifTrue: [ lowIndex := midIndex ]
>   ifFalse: [ ^prime ] ] ].
>   (GoodPrimes at: lowIndex) >= lowerLimit ifTrue: [ ^GoodPrimes at: lowIndex ].
>   ^GoodPrimes at: highIndex!
>
> Item was changed:
>  ----- Method: HashedCollection class>>new: (in category 'instance creation') -----
> + new: numberOfElements
> + "Create a Set large enough to hold numberOfElements without growing"
> + ^ self basicNew initialize:
> + (numberOfElements < 3
> + ifTrue: [ 3 ]
> + ifFalse:
> + [ numberOfElements < 4
> + ifTrue: [ 5 ]
> + ifFalse: [ self sizeFor: numberOfElements ] ])!
> - new: nElements
> - "Create a Set large enough to hold nElements without growing"
> - ^ self basicNew initialize: (self sizeFor: nElements)!
>
>