The Inbox: Collections-ul.913.mcz

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

The Inbox: Collections-ul.913.mcz

commits-2
Levente Uzonyi uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-ul.913.mcz

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

Name: Collections-ul.913
Author: ul
Time: 28 September 2020, 1:19:09.686632 am
UUID: 03eb89d7-ea1f-4116-99eb-0181542610f7
Ancestors: Collections-eem.912

HashedCollection changes:
- make #capacity return the actual capacity of the collection instead of the size of the internal array. This change is obviously not backwards compatible.
- introduce #arraySize to return the size of the internal array
- improve the performance of #isEmpty when tally is 0

OrderedDictionary changes;
- make it a subclass of PluggableDictionary. This lets one create e.g. an ordered identity dictionary without creating a subclass with duplicated behavior
- simplify #initialize and #growTo: now that #capacity is accurate

=============== Diff against Collections-eem.912 ===============

Item was added:
+ ----- Method: HashedCollection>>arraySize (in category 'accessing') -----
+ arraySize
+ "Answer the size of the internal array of the receiver."
+
+ ^array size!

Item was changed:
  ----- Method: HashedCollection>>capacity (in category 'accessing') -----
  capacity
+ "Answer the current capacity of the receiver - aka the number of elements the receiver can hold without growing."
- "Answer the current capacity of the receiver."
 
+ ^ array size * 3 // 4!
- ^ array size!

Item was changed:
  ----- Method: HashedCollection>>isEmpty (in category 'testing') -----
  isEmpty
  "For non-weak collections, we can use the tally to speed up the empty check. For weak collections, we must use the traditional way because the tally is unreliable. Also see #size vs. #slowSize."
 
+ tally = 0 ifTrue: [ ^true ].
+ ^array class isWeak and: [ super isEmpty ]!
- ^ array class isWeak
- ifFalse: [ tally = 0 ]
- ifTrue: [ super isEmpty ]!

Item was changed:
  ----- Method: HashedCollection>>removeAll (in category 'removing') -----
  removeAll
  "remove all elements from this collection.
  Preserve the capacity"
 
+ self initialize: self arraySize!
- self initialize: self capacity!

Item was changed:
+ PluggableDictionary subclass: #OrderedDictionary
- Dictionary subclass: #OrderedDictionary
  instanceVariableNames: 'order'
  classVariableNames: ''
  poolDictionaries: ''
  category: 'Collections-Sequenceable'!
 
  !OrderedDictionary commentStamp: 'mt 1/16/2015 10:42' prior: 0!
  I am an ordered dictionary. I have an additional index (called 'order') to keep track of the insertion order of my associations.
 
  The read access is not affected by the additional index.
 
  The index is updated in O(1) [time] when inserting new keys. For present keys, that insertion involves actions in O(n) to move the respective element to the end of the order.
 
  The growth operation compacts the index and takes O(n) additional time.
 
  NOTE: This is still no instance of SequenceableCollection. Having this, some protocols are missing and may require working on #associations, which is an Array and thus sequenceable.!

Item was changed:
  ----- Method: OrderedDictionary>>growTo: (in category 'private') -----
  growTo: anInteger
 
- | oldOrder |
  super growTo: anInteger.
+ order := order grownBy: self capacity - order size!
- oldOrder := order.
- "Grow only to 75%. See #atNewIndex:put: in HashedCollection."
- order := self class arrayType new: anInteger + 1 * 3 // 4.
- order
- replaceFrom: 1
- to: tally
- with: oldOrder
- startingAt: 1!

Item was changed:
  ----- Method: OrderedDictionary>>initialize: (in category 'private') -----
  initialize: n
 
  super initialize: n.
+ order := self class arrayType new: self capacity!
- order := self class arrayType new: n + 1 * 3 // 4!


Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ul.913.mcz

marcel.taeumel
Hi Levente.

It looks like #arraySize is "private" or at least "tests only", right? I understand that you need a better accessor in tests regarding that growth behavior. Well, you could just add #arraySize via meta-programming to the test case where you need it. Hmm... 

So, +1 for fixing #capacity. Not sure about #arraySize though ... :-)

Best,
Marcel

Am 28.09.2020 01:22:39 schrieb [hidden email] <[hidden email]>:

Levente Uzonyi uploaded a new version of Collections to project The Inbox:
http://source.squeak.org/inbox/Collections-ul.913.mcz

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

Name: Collections-ul.913
Author: ul
Time: 28 September 2020, 1:19:09.686632 am
UUID: 03eb89d7-ea1f-4116-99eb-0181542610f7
Ancestors: Collections-eem.912

HashedCollection changes:
- make #capacity return the actual capacity of the collection instead of the size of the internal array. This change is obviously not backwards compatible.
- introduce #arraySize to return the size of the internal array
- improve the performance of #isEmpty when tally is 0

OrderedDictionary changes;
- make it a subclass of PluggableDictionary. This lets one create e.g. an ordered identity dictionary without creating a subclass with duplicated behavior
- simplify #initialize and #growTo: now that #capacity is accurate

=============== Diff against Collections-eem.912 ===============

Item was added:
+ ----- Method: HashedCollection>>arraySize (in category 'accessing') -----
+ arraySize
+ "Answer the size of the internal array of the receiver."
+
+ ^array size!

Item was changed:
----- Method: HashedCollection>>capacity (in category 'accessing') -----
capacity
+ "Answer the current capacity of the receiver - aka the number of elements the receiver can hold without growing."
- "Answer the current capacity of the receiver."

+ ^ array size * 3 // 4!
- ^ array size!

Item was changed:
----- Method: HashedCollection>>isEmpty (in category 'testing') -----
isEmpty
"For non-weak collections, we can use the tally to speed up the empty check. For weak collections, we must use the traditional way because the tally is unreliable. Also see #size vs. #slowSize."

+ tally = 0 ifTrue: [ ^true ].
+ ^array class isWeak and: [ super isEmpty ]!
- ^ array class isWeak
- ifFalse: [ tally = 0 ]
- ifTrue: [ super isEmpty ]!

Item was changed:
----- Method: HashedCollection>>removeAll (in category 'removing') -----
removeAll
"remove all elements from this collection.
Preserve the capacity"

+ self initialize: self arraySize!
- self initialize: self capacity!

Item was changed:
+ PluggableDictionary subclass: #OrderedDictionary
- Dictionary subclass: #OrderedDictionary
instanceVariableNames: 'order'
classVariableNames: ''
poolDictionaries: ''
category: 'Collections-Sequenceable'!

!OrderedDictionary commentStamp: 'mt 1/16/2015 10:42' prior: 0!
I am an ordered dictionary. I have an additional index (called 'order') to keep track of the insertion order of my associations.

The read access is not affected by the additional index.

The index is updated in O(1) [time] when inserting new keys. For present keys, that insertion involves actions in O(n) to move the respective element to the end of the order.

The growth operation compacts the index and takes O(n) additional time.

NOTE: This is still no instance of SequenceableCollection. Having this, some protocols are missing and may require working on #associations, which is an Array and thus sequenceable.!

Item was changed:
----- Method: OrderedDictionary>>growTo: (in category 'private') -----
growTo: anInteger

- | oldOrder |
super growTo: anInteger.
+ order := order grownBy: self capacity - order size!
- oldOrder := order.
- "Grow only to 75%. See #atNewIndex:put: in HashedCollection."
- order := self class arrayType new: anInteger + 1 * 3 // 4.
- order
- replaceFrom: 1
- to: tally
- with: oldOrder
- startingAt: 1!

Item was changed:
----- Method: OrderedDictionary>>initialize: (in category 'private') -----
initialize: n

super initialize: n.
+ order := self class arrayType new: self capacity!
- order := self class arrayType new: n + 1 * 3 // 4!




Reply | Threaded
Open this post in threaded view
|

Re: The Inbox: Collections-ul.913.mcz

Levente Uzonyi
Hi Marcel,

On Mon, 28 Sep 2020, Marcel Taeumel wrote:

> Hi Levente.
> It looks like #arraySize is "private" or at least "tests only", right? I understand that you need a better accessor in tests regarding that growth behavior. Well, you could just add #arraySize via meta-programming to the test
> case where you need it. Hmm... 

Not really. It's used by HashedCollection >> #removeAll, MethodDictionary
>> #compact, and MethodDictionary class >> #compactAllInstances. The
latter two are in Kernel, which I forgot to push to the Inbox.

But we can entirely avoid introducing the new selector by using the
existing private/tests-only #array selector, and send #size to the object
it returns.


Levente

>
> So, +1 for fixing #capacity. Not sure about #arraySize though ... :-)
>
> Best,
> Marcel
>
>       Am 28.09.2020 01:22:39 schrieb [hidden email] <[hidden email]>:
>
>       Levente Uzonyi uploaded a new version of Collections to project The Inbox:
>       http://source.squeak.org/inbox/Collections-ul.913.mcz
>
>       ==================== Summary ====================
>
>       Name: Collections-ul.913
>       Author: ul
>       Time: 28 September 2020, 1:19:09.686632 am
>       UUID: 03eb89d7-ea1f-4116-99eb-0181542610f7
>       Ancestors: Collections-eem.912
>
>       HashedCollection changes:
>       - make #capacity return the actual capacity of the collection instead of the size of the internal array. This change is obviously not backwards compatible.
>       - introduce #arraySize to return the size of the internal array
>       - improve the performance of #isEmpty when tally is 0
>
>       OrderedDictionary changes;
>       - make it a subclass of PluggableDictionary. This lets one create e.g. an ordered identity dictionary without creating a subclass with duplicated behavior
>       - simplify #initialize and #growTo: now that #capacity is accurate
>
>       =============== Diff against Collections-eem.912 ===============
>
>       Item was added:
>       + ----- Method: HashedCollection>>arraySize (in category 'accessing') -----
>       + arraySize
>       + "Answer the size of the internal array of the receiver."
>       +
>       + ^array size!
>
>       Item was changed:
>       ----- Method: HashedCollection>>capacity (in category 'accessing') -----
>       capacity
>       + "Answer the current capacity of the receiver - aka the number of elements the receiver can hold without growing."
>       - "Answer the current capacity of the receiver."
>
>       + ^ array size * 3 // 4!
>       - ^ array size!
>
>       Item was changed:
>       ----- Method: HashedCollection>>isEmpty (in category 'testing') -----
>       isEmpty
>       "For non-weak collections, we can use the tally to speed up the empty check. For weak collections, we must use the traditional way because the tally is unreliable. Also see #size vs. #slowSize."
>
>       + tally = 0 ifTrue: [ ^true ].
>       + ^array class isWeak and: [ super isEmpty ]!
>       - ^ array class isWeak
>       - ifFalse: [ tally = 0 ]
>       - ifTrue: [ super isEmpty ]!
>
>       Item was changed:
>       ----- Method: HashedCollection>>removeAll (in category 'removing') -----
>       removeAll
>       "remove all elements from this collection.
>       Preserve the capacity"
>
>       + self initialize: self arraySize!
>       - self initialize: self capacity!
>
>       Item was changed:
>       + PluggableDictionary subclass: #OrderedDictionary
>       - Dictionary subclass: #OrderedDictionary
>       instanceVariableNames: 'order'
>       classVariableNames: ''
>       poolDictionaries: ''
>       category: 'Collections-Sequenceable'!
>
>       !OrderedDictionary commentStamp: 'mt 1/16/2015 10:42' prior: 0!
>       I am an ordered dictionary. I have an additional index (called 'order') to keep track of the insertion order of my associations.
>
>       The read access is not affected by the additional index.
>
>       The index is updated in O(1) [time] when inserting new keys. For present keys, that insertion involves actions in O(n) to move the respective element to the end of the order.
>
>       The growth operation compacts the index and takes O(n) additional time.
>
>       NOTE: This is still no instance of SequenceableCollection. Having this, some protocols are missing and may require working on #associations, which is an Array and thus sequenceable.!
>
>       Item was changed:
>       ----- Method: OrderedDictionary>>growTo: (in category 'private') -----
>       growTo: anInteger
>
>       - | oldOrder |
>       super growTo: anInteger.
>       + order := order grownBy: self capacity - order size!
>       - oldOrder := order.
>       - "Grow only to 75%. See #atNewIndex:put: in HashedCollection."
>       - order := self class arrayType new: anInteger + 1 * 3 // 4.
>       - order
>       - replaceFrom: 1
>       - to: tally
>       - with: oldOrder
>       - startingAt: 1!
>
>       Item was changed:
>       ----- Method: OrderedDictionary>>initialize: (in category 'private') -----
>       initialize: n
>
>       super initialize: n.
>       + order := self class arrayType new: self capacity!
>       - order := self class arrayType new: n + 1 * 3 // 4!
>
>
>
>