[squeak-dev] The Trunk: Collections-ul.546.mcz

commits at source.squeak.org commits at source.squeak.org
Tue Dec 10 18:37:36 UTC 2013


Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.546.mcz

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

Name: Collections-ul.546
Author: ul
Time: 10 December 2013, 7:14:34.339 pm
UUID: 6fa6992c-8f61-47fa-aedd-173df2cb89f0
Ancestors: Collections-fbs.545

Scalable LRUCache. Migration code is in the postscript.

=============== Diff against Collections-fbs.545 ===============

Item was changed:
  Object subclass: #LRUCache
+ 	instanceVariableNames: 'map head calls hits size factory values'
- 	instanceVariableNames: 'size factory calls hits values'
  	classVariableNames: ''
  	poolDictionaries: ''
  	category: 'Collections-Cache'!
  
+ !LRUCache commentStamp: 'ul 11/23/2013 22:20' prior: 0!
+ I'm a cache of values, given a key I return a Value from the cache or from the factory.
+ 
+ I use map (a Dictionary) to find the corresponding value to the given key. I store the values in nodes, which are arrays of size 4. Together with head the nodes form a circular doubly-linked list with a head element.
+ The first element of a list node is the next list node, the second element is the previous list node. The third element (if exists) is the key, the fourth (if exists) is the value for the given key.
+ The nodes in the list are ordered by access time. The first node is the most recently accessed, the last one is the least recently accessed.!
- !LRUCache commentStamp: '<historical>' prior: 0!
- I'm a cache of values, given a key I return a Value from the cache or from the factory!

Item was changed:
  ----- Method: LRUCache>>at: (in category 'accessing') -----
  at: aKey 
  	"answer the object for aKey, if not present in the cache creates it"
+ 
  	| element keyHash |
+ 	self isMigrated ifTrue: [
+ 		calls := calls + 1.
+ 		^map
+ 			at: aKey
+ 			ifPresent: [ :node |
+ 				hits := hits + 1.
+ 				self 
+ 					unlink: node;
+ 					moveToFirst: node.
+ 				node at: 4 ]
+ 			ifAbsent: [
+ 				| node |
+ 				map size = size
+ 					ifTrue: [ 
+ 						node := head at: 2.
+ 						self unlink: node ]
+ 					ifFalse: [
+ 						node := Array new: 4 ].
+ 				self moveToFirst: node.
+ 				map at: aKey put: node.
+ 				node 
+ 					at: 3 put: aKey;
+ 					at: 4 put: (factory value: aKey) ] ].
  	calls := calls + 1.
  	keyHash := aKey hash.
  	1
  		to: size
  		do: [:index | 
  			element := values at: index.
  			(keyHash
  						= (element at: 2)
  					and: [aKey
  							= (element at: 1)])
  				ifTrue: ["Found!!"
  					hits := hits + 1.
  					values
  						replaceFrom: 2
  						to: index
  						with: (values first: index - 1).
  					values at: 1 put: element.
  					^ element at: 3]].
  	"Not found!!"
  	element := {aKey. keyHash. factory value: aKey}.
  	values
  		replaceFrom: 2
  		to: size
  		with: values allButLast.
  	values at: 1 put: element.
  	^ element at: 3!

Item was changed:
  ----- Method: LRUCache>>initializeSize:factory: (in category 'initialization') -----
+ initializeSize: anInteger factory: aBlock 
- initializeSize: aNumber factory: aBlock 
  	"initialize the receiver's size and factory"
+ 	
+ 	anInteger strictlyPositive ifFalse: [ self error: 'Size must be at least 1' ].
+ 	size := anInteger.
+ 	head := Array new: 2.
+ 	head 
+ 		at: 1 put: head;
+ 		at: 2 put: head.
+ 	map := PluggableDictionary integerDictionary.
- 	size := aNumber.
- 	values := Array new: aNumber withAll: {nil. nil. nil}.
  	factory := aBlock.
  	calls := 0.
  	hits := 0!

Item was added:
+ ----- Method: LRUCache>>isMigrated (in category 'migration') -----
+ isMigrated
+ 
+ 	^map notNil!

Item was added:
+ ----- Method: LRUCache>>migrate (in category 'migration') -----
+ migrate
+ 
+ 	self isMigrated ifTrue: [ ^self ].
+ 	head := Array new: 2.
+ 	head 
+ 		at: 1 put: head;
+ 		at: 2 put: head.
+ 	map := PluggableDictionary integerDictionary.
+ 	values reverseDo: [ :each |
+ 		| node |
+ 		node := { nil. nil. each first. each third }.
+ 		map at: each first put: node.
+ 		self moveToFirst: node ].
+ 	values := nil
+ 		!

Item was added:
+ ----- Method: LRUCache>>moveToFirst: (in category 'private') -----
+ moveToFirst: node
+ 	"Move node after head in the doubly-linked list. If the node is linked, it must be unlinked first."
+ 
+ 	| next |
+ 	next := head at: 1.
+ 	node
+ 		at: 1 put: next;
+ 		at: 2 put: head.
+ 	next at: 2 put: node.
+ 	head at: 1 put: node!

Item was added:
+ ----- Method: LRUCache>>unlink: (in category 'private') -----
+ unlink: node
+ 	"Unlink the node from the doubly-linked list represented by head."
+ 
+ 	| next previous |
+ 	next := node at: 1.
+ 	previous := node at: 2.
+ 	next at: 2 put: previous.
+ 	previous at: 1 put: next!

Item was changed:
+ (PackageInfo named: 'Collections') postscript: 'LRUCache allInstancesDo: #migrate'!
- (PackageInfo named: 'Collections') postscript: 'WeakRegistry allInstancesDo: [ :each | each installFinalizer ]'!



More information about the Squeak-dev mailing list