[Vm-dev] VM Maker: VMMaker.oscog-eem.711.mcz
commits at source.squeak.org
commits at source.squeak.org
Fri May 9 23:15:54 UTC 2014
Eliot Miranda uploaded a new version of VMMaker to project VM Maker:
http://source.squeak.org/VMMaker/VMMaker.oscog-eem.711.mcz
==================== Summary ====================
Name: VMMaker.oscog-eem.711
Author: eem
Time: 9 May 2014, 4:11:21.064 pm
UUID: a8207038-3c80-4bb7-919a-7018c5ac3528
Ancestors: VMMaker.oscog-eem.710
Revise pigCompact to maintain the doubly-linked free list
after sweepToCoallesceFreeSpaceForPigCompactFrom:.
This means pigCompact can now be repeated.
Repeat pigCompact 3 times, which appears to compact well.
This needs lots of profiling!!
=============== Diff against VMMaker.oscog-eem.710 ===============
Item was added:
+ ----- Method: Spur32BitMMLESimulator>>inSortedFreeListLink:to:given: (in category 'compaction') -----
+ inSortedFreeListLink: freeChunk to: nextFree given: prevFree
+ "thisContext sender selector = #sweepToCoallesceFreeSpaceForPigCompactFrom: ifTrue:
+ [| pit |
+ pit := [:label :thing|
+ coInterpreter print: label; space; printHex: thing.
+ (thing ~= 0 and: [self isFreeObject: thing]) ifTrue:
+ [coInterpreter print: ' (free) ']].
+ pit value: 'link ' value: freeChunk.
+ pit value: ' to ' value: nextFree.
+ pit value: ' from ' value: prevFree.
+ coInterpreter cr]."
+ "freeChunk = 16r10B0730 ifTrue:
+ [self halt]."
+ super inSortedFreeListLink: freeChunk to: nextFree given: prevFree!
Item was removed:
- ----- Method: SpurMemoryManager>>allOldSpaceEntitiesForCoalescingDo: (in category 'object enumeration') -----
- allOldSpaceEntitiesForCoalescingDo: aBlock
- <inline: true>
- | prevObj prevPrevObj objOop rawNumSlots rawNumSlotsAfter |
- prevPrevObj := prevObj := nil.
- objOop := self firstObject.
- [self assert: objOop \\ self allocationUnit = 0.
- self oop: objOop isLessThan: endOfMemory] whileTrue:
- [self assert: (self long64At: objOop) ~= 0.
- rawNumSlots := self rawNumSlotsOf: objOop.
- aBlock value: objOop.
- "If the number of slot changes coalescing changed an object from a single to a double header."
- rawNumSlotsAfter := self rawNumSlotsOf: objOop.
- (rawNumSlotsAfter ~= rawNumSlots
- and: [rawNumSlotsAfter = self numSlotsMask]) ifTrue:
- [objOop := objOop + self baseHeaderSize.
- self assert: (self objectAfter: prevObj limit: endOfMemory) = objOop].
- prevPrevObj := prevObj.
- prevObj := objOop.
- objOop := self objectAfter: objOop limit: endOfMemory].
- self touch: prevPrevObj.
- self touch: prevObj!
Item was added:
+ ----- Method: SpurMemoryManager>>allOldSpaceEntitiesForCoalescingFrom:do: (in category 'object enumeration') -----
+ allOldSpaceEntitiesForCoalescingFrom: firstObj do: aBlock
+ <inline: true>
+ | prevObj prevPrevObj objOop rawNumSlots rawNumSlotsAfter |
+ prevPrevObj := prevObj := nil.
+ objOop := firstObj.
+ [self assert: objOop \\ self allocationUnit = 0.
+ self oop: objOop isLessThan: endOfMemory] whileTrue:
+ [self assert: (self long64At: objOop) ~= 0.
+ rawNumSlots := self rawNumSlotsOf: objOop.
+ aBlock value: objOop.
+ "If the number of slot changes coalescing changed an object from a single to a double header.
+ In future have the block return the vaue. It should know when things change."
+ self flag: 'future work'.
+ rawNumSlotsAfter := self rawNumSlotsOf: objOop.
+ (rawNumSlotsAfter ~= rawNumSlots
+ and: [rawNumSlotsAfter = self numSlotsMask]) ifTrue:
+ [objOop := objOop + self baseHeaderSize.
+ self assert: (self objectAfter: prevObj limit: endOfMemory) = objOop].
+ prevPrevObj := prevObj.
+ prevObj := objOop.
+ objOop := self objectAfter: objOop limit: endOfMemory].
+ self touch: prevPrevObj.
+ self touch: prevObj!
Item was changed:
----- Method: SpurMemoryManager>>eliminateAndFreeForwardersForPigCompact (in category 'gc - global') -----
eliminateAndFreeForwardersForPigCompact
"As the final phase of global garbage collect, sweep the heap to follow
forwarders, then free forwarders, coalescing with free space as we go."
<inline: false>
| lowestForwarder |
self assert: (self isForwarded: nilObj) not.
self assert: (self isForwarded: falseObj) not.
self assert: (self isForwarded: trueObj) not.
self assert: (self isForwarded: self freeListsObj) not.
self assert: (self isForwarded: hiddenRootsObj) not.
self assert: (self isForwarded: classTableFirstPage) not.
self followSpecialObjectsOop.
self followForwardedObjStacks.
coInterpreter mapInterpreterOops.
scavenger followRememberedForwardersAndForgetFreeObjectsForPigCompact.
self unmarkSurvivingObjectsForPigCompact.
lowestForwarder := self sweepToFollowForwardersForPigCompact.
+ self sweepToCoallesceFreeSpaceForPigCompactFrom: lowestForwarder.
- self sweepToCoallesceFreeSpaceAndRebuildFreeListsForPigCompactFrom: lowestForwarder.
- self checkFreeSpace.
self assert: self numberOfForwarders = 0!
Item was changed:
----- Method: SpurMemoryManager>>freeUnmarkedObjectsAndSortAndCoalesceFreeSpaceForFitCompact (in category 'gc - global') -----
freeUnmarkedObjectsAndSortAndCoalesceFreeSpaceForFitCompact
"Sweep all of old space, freeing unmarked objects, coalescing free chunks, and sorting free space.
Small free chunks are sorted in address order on each small list head. Large free chunks
are sorted on the sortedFreeChunks list. Record as many of the highest objects as there
is room for in highestObjects, a circular buffer, for the use of exactFitCompact. Use
unused eden space for highestObjects. If highestObjects does not wrap, store 0
at highestObjects last. Record the lowest free object in firstFreeChunk. Let the
segmentManager mark which segments contain pinned objects via notePinned:."
| lastLargeFree lastHighest highestObjectsWraps sortedFreeChunks |
<inline: false>
<var: #lastHighest type: #usqInt>
self checkFreeSpace.
scavenger forgetUnmarkedRememberedObjects.
segmentManager prepareForGlobalSweep."for notePinned:"
"for sorting free space throw away the list heads, rebuilding them for small free chunks below."
self resetFreeListHeads.
highestObjects initializeStart: freeStart limit: scavenger eden limit.
lastHighest := highestObjects start - self wordSize. "a.k.a. freeStart - wordSize"
highestObjectsWraps := 0.
self assert: highestObjects limit - highestObjects start // self wordSize >= 1024.
firstFreeChunk := sortedFreeChunks := lastLargeFree := 0.
"Note that if we were truly striving for performance we could split the scan into
two phases, one up to the first free object and one after, which would remove
the need to test firstFreeChunk when filling highestObjects."
+ self allOldSpaceEntitiesForCoalescingFrom: self firstObject do:
- self allOldSpaceEntitiesForCoalescingDo:
[:o|
self assert: (firstFreeChunk = 0 or: [self isFreeObject: firstFreeChunk]).
(self isMarked: o)
ifTrue: "forwarders should have been followed in markAndTrace:"
[self assert: (self isForwarded: o) not.
self setIsMarkedOf: o to: false. "this will unmark bridges. undo the damage in notePinned:"
(self isPinned: o) ifTrue:
[segmentManager notePinned: o].
firstFreeChunk ~= 0 ifTrue:
[false "conceptually...: "
ifTrue: [highestObjects addLast: o]
ifFalse: "but we inline so we can use the local lastHighest"
[(lastHighest := lastHighest + self wordSize) >= highestObjects limit ifTrue:
[highestObjectsWraps := highestObjectsWraps + 1.
lastHighest := highestObjects start].
self longAt: lastHighest put: o]]]
ifFalse: "unmarked; two cases, an unreachable object or a free chunk."
[| here |
here := self coallesceFreeChunk: o.
(self isLargeFreeObject: here)
ifTrue:
[self setFree: here.
lastLargeFree = 0
ifTrue: [sortedFreeChunks := lastLargeFree := here]
ifFalse:
[self storePointer: self freeChunkNextAddressIndex
ofFreeChunk: lastLargeFree
withValue: here].
lastLargeFree := here]
ifFalse:
[self freeSmallObject: here].
firstFreeChunk = 0 ifTrue:
[self assert: (self isFreeObject: here).
firstFreeChunk := here]]].
highestObjects last: lastHighest.
highestObjectsWraps ~= 0 ifTrue:
[highestObjects first: (lastHighest + self wordSize >= highestObjects limit
ifTrue: [highestObjects start]
ifFalse: [lastHighest + self wordSize])].
lastLargeFree ~= 0 ifTrue:
[self storePointer: self freeChunkNextAddressIndex ofFreeChunk: lastLargeFree withValue: 0].
totalFreeOldSpace := self reverseSmallListHeads.
totalFreeOldSpace := totalFreeOldSpace + (self rebuildFreeTreeFrom: sortedFreeChunks).
self checkFreeSpace.
self touch: highestObjectsWraps!
Item was changed:
----- Method: SpurMemoryManager>>freeUnmarkedObjectsAndSortAndCoalesceFreeSpaceForPigCompact (in category 'gc - global') -----
freeUnmarkedObjectsAndSortAndCoalesceFreeSpaceForPigCompact
"Sweep all of old space, freeing unmarked objects, coalescing free chunks, and sorting free space.
Doubly-link the free chunks in address order through the freeChunkNextIndex field using the
xor trick to use only one field, see e.g.
The Art of Computer Programming, Vol 1, D.E. Knuth, 3rd Ed, Sec 2.2.4 `Circular Lists', exercise. 18
http://en.wikipedia.org/wiki/XOR_linked_list.
Record the lowest free object in firstFreeChunk and the highest in lastFreeChunk.
Let the segmentManager mark which segments contain pinned objects via notePinned:."
| prevPrevFree prevFree |
<inline: false>
self checkFreeSpace.
scavenger forgetUnmarkedRememberedObjects.
self doScavenge: MarkOnTenure.
segmentManager prepareForGlobalSweep."for notePinned:"
"throw away the list heads, including the tree."
self resetFreeListHeads.
firstFreeChunk := prevPrevFree := prevFree := 0.
+ self allOldSpaceEntitiesForCoalescingFrom: self firstObject do:
- self allOldSpaceEntitiesForCoalescingDo:
[:o|
self assert: (firstFreeChunk = 0 or: [self isFreeObject: firstFreeChunk]).
(self isMarked: o)
ifTrue: "forwarders should have been followed in markAndTrace:"
[self assert: (self isForwarded: o) not.
self setIsMarkedOf: o to: false. "this will unmark bridges. undo the damage in notePinned:"
(self isPinned: o) ifTrue:
[segmentManager notePinned: o]]
ifFalse: "unmarked; two cases, an unreachable object or a free chunk."
[| here |
self assert: (self isRemembered: o) not. "scavenger should have cleared this above"
here := self coallesceFreeChunk: o.
self setObjectFree: here.
self inSortedFreeListLink: prevFree to: here given: prevPrevFree.
prevPrevFree := prevFree.
prevFree := here]].
prevFree ~= firstFreeChunk ifTrue:
[self storePointer: self freeChunkNextIndex
ofFreeChunk: prevFree
withValue: prevPrevFree].
lastFreeChunk := prevFree.
self cCode: [] inSmalltalk: [self checkTraversableSortedFreeList]!
Item was changed:
----- Method: SpurMemoryManager>>globalGarbageCollect (in category 'gc - global') -----
globalGarbageCollect
self assert: self validObjStacks.
self assert: (self isEmptyObjStack: markStack).
self assert: (self isEmptyObjStack: weaklingStack).
self markObjects.
self expungeDuplicateAndUnmarkedClasses: true.
self nilUnmarkedWeaklingSlots.
self freeUnmarkedObjectsAndSortAndCoalesceFreeSpace.
"Mid-way the leak check must be more lenient. Unmarked classes will have been
expunged from the table, but unmarked instances will not yet have been reclaimed."
self runLeakCheckerForFullGC: true
excludeUnmarkedNewSpaceObjs: true
classIndicesShouldBeValid: true.
+ UseFitCompact
+ ifTrue:
+ [self compact.
+ self eliminateAndFreeForwarders]
+ ifFalse:
+ [1 to: 3 do:
+ [:i|
+ self pigCompact.
+ self eliminateAndFreeForwardersForPigCompact].
+ self rebuildFreeListsForPigCompact].
- "At least for pigCompact it is worth repeating these two phases to get better compaction,
- for example during snapshot. In which case the code needs to be reorganized to not
- rebuild the free list after compact, but instead just coallesce, and maintain the sorted free
- list until compaction has been repeated sufficiently (an experiment showed no improvement
- after 3 repetitions, but a useful gain of ~ 200k in a small image on the third iteration."
- self flag: 'future work'.
- self compact.
- self eliminateAndFreeForwarders.
self assert: self validObjStacks.
self assert: (self isEmptyObjStack: markStack).
self assert: (self isEmptyObjStack: weaklingStack).
self assert: self allObjectsUnmarked.
self runLeakCheckerForFullGC: true!
Item was added:
+ ----- Method: SpurMemoryManager>>rebuildFreeListsForPigCompact (in category 'compaction') -----
+ rebuildFreeListsForPigCompact
+ "Rebuild the free lists from the doubly-linked free list."
+ totalFreeOldSpace := 0.
+ self sortedFreeListDo:
+ [:freeObj| | start bytes |
+ bytes := (self bytesInObject: freeObj).
+ start := self startOfObject: freeObj.
+ self addFreeChunkWithBytes: bytes at: start]!
Item was added:
+ ----- Method: SpurMemoryManager>>sortedFreeListDo: (in category 'compaction') -----
+ sortedFreeListDo: aBlock
+ "Evaluate aBlock with ascending entries in the free list"
+ | free nextFree prevFree prevPrevFree |
+ <inline: true>
+ free := firstFreeChunk.
+ prevPrevFree := prevFree := 0.
+ [free ~= 0] whileTrue:
+ [nextFree := self nextInSortedFreeListLink: free given: prevFree.
+ self assert: (self isFreeObject: free).
+ self assert: (nextFree = 0 or: [nextFree > free and: [self isFreeObject: nextFree]]).
+ self assert: (prevFree = 0 or: [prevFree < free]).
+ aBlock value: free.
+ prevPrevFree := prevFree.
+ prevFree := free.
+ free := nextFree]!
Item was changed:
----- Method: SpurMemoryManager>>sortedFreeListPairwiseReverseDo: (in category 'compaction') -----
sortedFreeListPairwiseReverseDo: aBinaryBlock
"Evaluate aBinaryBlock with adjacent entries in the free list, from
high address to low address. The second argument is in fact the
start of the next free chunk, not the free chunk itself. Use
endOfMemory - bridgeSize as the second argument in the first evaluation."
| free nextFree prevFree prevPrevFree |
+ <inline: true>
free := lastFreeChunk.
prevPrevFree := prevFree := 0.
[free ~= 0] whileTrue:
[nextFree := self nextInSortedFreeListLink: free given: prevFree.
self assert: (free = 0 or: [self isFreeObject: free]).
self assert: (prevFree = 0 or: [prevFree > free]).
aBinaryBlock value: free value: (prevFree = 0
ifTrue: [endOfMemory - self bridgeSize]
ifFalse: [self startOfObject: prevFree]).
self assert: (prevFree = 0 or: [self isFreeObject: prevFree]).
self assert: (prevPrevFree = 0 or: [self isFreeObject: prevPrevFree]).
(self isFreeObject: free) ifFalse:
[free := self nextInSortedFreeListLink: prevFree given: prevPrevFree].
(nextFree = 0 or: [self isFreeObject: nextFree])
ifTrue:
[prevPrevFree := prevFree.
prevFree := free.
free := nextFree]
ifFalse:
[free := lastFreeChunk.
prevPrevFree := prevFree := 0.
[free > nextFree] whileTrue:
[nextFree := self nextInSortedFreeListLink: free given: prevFree.
self assert: (self isFreeObject: nextFree).
prevPrevFree := prevFree.
prevFree := free.
free := nextFree]]]!
Item was changed:
----- Method: SpurMemoryManager>>sweepToCoallesceFreeSpaceAndRebuildFreeListsForPigCompactFrom: (in category 'compaction') -----
sweepToCoallesceFreeSpaceAndRebuildFreeListsForPigCompactFrom: lowestForwarder
"Coallesce free chunks and forwarders and rebuild the free list."
| lowest firstFree firstFreeStart lastFree |
lowest := (lowestForwarder = 0 ifTrue: [endOfMemory] ifFalse: [lowestForwarder])
min: (firstFreeChunk = 0 ifTrue: [endOfMemory] ifFalse: [firstFreeChunk]).
firstFree := totalFreeOldSpace := 0.
+ self allOldSpaceEntitiesForCoalescingFrom: lowest do:
- self allOldSpaceEntitiesFrom: lowest do:
[:o|
((self isFreeObject: o) or: [self isForwarded: o])
ifTrue:
[firstFree = 0 ifTrue:
[firstFree := o.
firstFreeStart := self startOfObject: o].
lastFree := o]
ifFalse:
[firstFree ~= 0 ifTrue:
[| bytes |
bytes := (self addressAfter: lastFree) - firstFreeStart.
self addFreeChunkWithBytes: bytes at: firstFreeStart].
firstFree := 0]].
firstFree ~= 0 ifTrue:
[| bytes |
bytes := (self addressAfter: lastFree) - firstFreeStart.
self addFreeChunkWithBytes: bytes at: firstFreeStart].
firstFreeChunk := lastFreeChunk := 0!
Item was added:
+ ----- Method: SpurMemoryManager>>sweepToCoallesceFreeSpaceForPigCompactFrom: (in category 'compaction') -----
+ sweepToCoallesceFreeSpaceForPigCompactFrom: lowestForwarder
+ "Coallesce free chunks and forwarders, maintaining the doubly-linked free list."
+ | lowest firstOfFreeRun startOfFreeRun endOfFreeRun prevPrevFree prevFree |
+ lowest := (lowestForwarder = 0 ifTrue: [endOfMemory] ifFalse: [lowestForwarder])
+ min: (firstFreeChunk = 0 ifTrue: [endOfMemory] ifFalse: [firstFreeChunk]).
+ firstOfFreeRun := prevPrevFree := prevFree := 0.
+ self allOldSpaceEntitiesFrom: lowest do:
+ [:o|
+ ((self isFreeObject: o) or: [self isForwarded: o])
+ ifTrue:
+ [firstOfFreeRun = 0 ifTrue:
+ [self setObjectFree: o.
+ firstOfFreeRun := o.
+ startOfFreeRun := self startOfObject: o].
+ endOfFreeRun := o]
+ ifFalse:
+ [firstOfFreeRun ~= 0 ifTrue:
+ [| bytes |
+ bytes := (self addressAfter: endOfFreeRun) - startOfFreeRun.
+ firstOfFreeRun := self initFreeChunkWithBytes: bytes at: startOfFreeRun.
+ self inSortedFreeListLink: prevFree to: firstOfFreeRun given: prevPrevFree.
+ prevPrevFree := prevFree.
+ prevFree := firstOfFreeRun.
+ firstOfFreeRun := 0]]].
+ firstOfFreeRun ~= 0 ifTrue:
+ [| bytes |
+ bytes := (self addressAfter: endOfFreeRun) - startOfFreeRun.
+ firstOfFreeRun := self initFreeChunkWithBytes: bytes at: startOfFreeRun.
+ self inSortedFreeListLink: prevFree to: firstOfFreeRun given: prevPrevFree.
+ prevPrevFree := prevFree.
+ prevFree := firstOfFreeRun.
+ firstOfFreeRun := 0].
+ prevFree ~= firstFreeChunk ifTrue:
+ [self storePointer: self freeChunkNextIndex
+ ofFreeChunk: prevFree
+ withValue: prevPrevFree].
+ lastFreeChunk := prevFree.
+ self cCode: [] inSmalltalk: [self checkTraversableSortedFreeList]!
More information about the Vm-dev
mailing list