The Inbox: Collections-cmm.870.mcz

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!

you produce stale versions in the inbox, in this case Collections-cmm.869 if I remember correctly.

Hi Chris, hi all,

Chris, in your effort to omit intermediary or flawed versions from the ancestry, you produce stale versions in the inbox, in this case Collections-cmm.869 if I remember correctly.

How can we make sure that no Trunk committer (you are a Trunk committer Chris and can handle this yourself, but in general someone else might do it) will merge these versions that you wanted to omit?

If that happens, the ancestry will be "complete" again, which you wanted to avoid, and moreover it will look confusing (branches and merges instead of plain linear, actual history). I am still opposed to such omissions, but let's focus on the "if it happens, what then" part instead.

The omitted versions should be removed from the inbox, either by treating them or by withdrawing them (which is not directly possible at the moment, right?). How can we implement a reasonably reliable process with communication rules to handle such cases? Or is there already one that works? I don't think we can expect every treating Trunk committer to read through all the mails and ancillary threads to identify, or derive implicitly as in this case, which versions are stale.

Kind regards,
Jakob

Am Sa., 4. Jan. 2020 um 23:09 Uhr schrieb <[hidden email]>:

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!