Tom Braun uploaded a new version of VMMaker to project VM Maker: http://source.squeak.org/VMMaker/VMMaker.oscog.seperateMarking-WoC.3336.mcz
==================== Summary ====================
Name: VMMaker.oscog.seperateMarking-WoC.3336 Author: WoC Time: 12 July 2023, 6:56:42.867361 pm UUID: 44e397a4-6ef1-407c-b738-e9f6325feb1c Ancestors: VMMaker.oscog.seperateMarking-WoC.3335
add optimization for sweeping lilliputian chunks
=============== Diff against VMMaker.oscog.seperateMarking-WoC.3335 ===============
Item was changed: ----- Method: SpurIncrementalSweeper>>cautiousBulkFreeChunkFrom: (in category 'api - incremental') ----- cautiousBulkFreeChunkFrom: objOop "The old space entity before objOop is necessarily a marked object. Attempts to free as many bytes from objOop start as possible, looking ahead to free contiguous freechunks / unmarked objects" | bytes start next currentObj | self assert: (self canUseAsFreeSpace: objOop). start := manager startOfObject: objOop. currentObj := objOop. bytes := 0. [| objSize | sweptEntities := sweptEntities + 1. objSize := (manager bytesInBody: currentObj). bytes := bytes + objSize. (manager isRemembered: currentObj) ifTrue: [self assert: (manager isFreeObject: currentObj) not. scavenger forgetObject: currentObj].
(manager isFreeObject: currentObj) ifTrue: [ "we need to unlink chunks for concurrent sweeping. In the stop the world sweeper we can just reset the freeLists but here we need to keep them around so the mutator can still work between sweeping passes" self flag: #Todo. "we want to optimize for lilliputian chunks!! For now it is ok(ish) but we have to do something about it. At the moment I see 3 possibilities: - have the lilliputian list always sorted (O(n) insert in the worst case!!) - sort the lilliputian part before sweeping (O(n log n) at the start. but everytime before sweeping) - be cheeky and discard the lilliputian list (problem: the mutator has no access to the list + it can insert unsorted chunks (for the duration of sweeping we could let it use a second list and just append it after sweeping)" + (manager isLilliputianSize: objSize) - "(manager isLilliputianSize: objSize) ifTrue: [ | nextLilliputian | + lilliputianChunksToFree := lilliputianChunksToFree + 1. nextLilliputian := (manager fetchPointer: manager freeChunkNextIndex ofFreeChunk: currentObj). manager noCheckPush: nextLilliputian onObjStack: manager markStack] + ifFalse: [manager detachFreeObject: currentObj] + "manager detachFreeObject: currentObj" - ifFalse: [manager detachFreeObject: currentObj]" - manager detachFreeObject: currentObj "self assert: manager totalFreeOldSpace = manager totalFreeListBytes."].
next := manager objectStartingAt: start + bytes. currentsCycleSeenObjectCount := currentsCycleSeenObjectCount + 1. self assert: ((manager oop: next isLessThan: manager endOfMemory) or: [next = manager endOfMemory and: [(self canUseAsFreeSpace: next) not]]).
"should the next object not be usable as free space (because it is marked) abort the loop. Attention: briges at the end of segments are marked and therefore we leave the loop here. This is important as the newly created free space segment should not be bigger than there still is space left in the current segment" (self canUseAsFreeSpace: next) and: [coInterpreter ioUTCMicrosecondsNow - sStartTime < 5000]] whileTrue: [currentObj := next]. currentSegmentUnused := currentSegmentUnused + bytes. + ^ self interceptAddFreeChunkWithBytes: bytes at: start + "^ manager addFreeChunkWithBytes: bytes at: start"! - "^ self interceptAddFreeChunkWithBytes: bytes at: start" - ^ manager addFreeChunkWithBytes: bytes at: start!
Item was changed: ----- Method: SpurIncrementalSweeper>>cleanUpLilliputianChunks (in category 'as yet unclassified') ----- cleanUpLilliputianChunks
"- remove all lilliputian chunks in the range of this sweep - patch the lilliputian free list with the saved values on the MarkStack - append all newly created (or already existing but previously here removed) lilliputian chunks" self flag: #Todo. "it would be nicer if we appened lilliputian chunk lists instead of prepending. Not sure if it has any preformance impact" + - (manager isEmptyObjStack: manager markStack) not ifTrue: [ | node prev | node := manager freeLists at: 2. prev := 0. + [node ~= 0 or: [(manager isEmptyObjStack: manager markStack) not]] - [node ~= 0] whileTrue: [ + "we already found the end of the list, although we did not connect all links from the list in the swept area" + node = 0 + ifTrue: [node := (manager popObjStack: manager markStack). + manager noCheckPush: 0 onObjStack: manager markStack. + + "attach the element to the previous tail of the list" + manager setNextFreeChunkOf: prev withValue: node isLilliputianSize: true]. + + (node >= sweepingStart and: [node < currentSweepingEntity]) + ifTrue: [ "the node is in the swept area" - ifTrue: [ self assert: (manager sizeOfObjStack: manager markStack) > 0. node := (manager popObjStack: manager markStack).
+ "We popped the end of the list. As there are more links use them first" (node = 0 and: [(manager sizeOfObjStack: manager markStack) > 0]) ifTrue: [ node := (manager popObjStack: manager markStack). manager noCheckPush: 0 onObjStack: manager markStack]. manager totalFreeOldSpace: manager totalFreeOldSpace - manager lilliputianChunkSize. prev = 0 ifTrue: [manager freeLists at: 2 put: node] ifFalse: [manager setNextFreeChunkOf: prev withValue: node isLilliputianSize: true]] + ifFalse: [ + prev := node. - ifFalse: [prev := node. node := (manager fetchPointer: manager freeChunkNextIndex ofFreeChunk: node)]]]. + - self assert: (manager isEmptyObjStack: manager markStack). + (manager sizeOfObjStack: manager markStack) ~= 0 ifTrue: [manager debugger]. + lilliputianListEnd ~= 0 ifTrue: [ manager setNextFreeChunkOf: lilliputianListEnd withValue: (manager freeLists at: 2) isLilliputianSize: true. manager freeLists at: 2 put: lilliputianList. manager totalFreeOldSpace: manager totalFreeOldSpace + (lilliputianListSize * manager lilliputianChunkSize)]. self assert: manager totalFreeOldSpace = manager totalFreeListBytes. "update free lists mask just to be sure as we probably manipulated it here" (manager freeLists at: 2) = 0 ifTrue: [manager freeListsMask: (manager freeListsMask bitClear: 2)] ifFalse: [manager freeListsMask: (manager freeListsMask bitOr: 2r100)]. self assert: manager bitsSetInFreeSpaceMaskForAllFreeLists !
Item was changed: ----- Method: SpurIncrementalSweeper>>doIncrementalSweeping (in category 'api - incremental') ----- doIncrementalSweeping "Scan the heap for unmarked objects and free them. Coalescence " self assert: currentSweepingEntity notNil. currentsCycleSeenObjectCount := 0.
[self oop: currentSweepingEntity isLessThan: manager endOfMemory] whileTrue: [ currentSweepingEntity = currentSegmentsBridge ifTrue: [self advanceSegment] ifFalse: [self sweepFromCurrentSweepingEntity]. currentSweepingEntity := self nextSweepingEntity. "do not end on a bridge. While the mutator runs the bridge can get an overhead header and we wouldn't handle that correctly -> avoid this case" (currentSweepingEntity ~= currentSegmentsBridge and: [(manager segmentManager isEmptySegment: (manager segInfoAt: currentSegmentsIndex)) not and: [coInterpreter ioUTCMicrosecondsNow - sStartTime >= 5000]]) + ifTrue: [ + self cleanUpLilliputianChunks. + "manager checkFreeSpace: GCCheckFreeSpace." + ^ false]]. - ifTrue: [^ false]]. "set occupation for last segment" self setOccupationAtIndex: currentSegmentsIndex used: currentSegmentUsed unused: currentSegmentUnused. + + self cleanUpLilliputianChunks. + "manager checkFreeSpace: GCCheckFreeSpace." + - manager checkFreeSpace: GCModeIncremental. ^ true!
Item was changed: ----- Method: SpurIncrementalSweeper>>incrementalSweep (in category 'api - incremental') ----- incrementalSweep <inline: #never> "for profiling" self initIfNecessary. "should in between sweeper calls segments be removed the index would not be correct anymore. Reset it here so we can be sure it is correct" currentSegmentsIndex := manager segmentManager segmentIndexContainingObj: currentSweepingEntity. "if the bridge between segments was small before and the segment directly after the current one was removed the position of the bridge moved. Update the current position to avoid this case" currentSegmentsBridge := manager segmentManager bridgeAt: currentSegmentsIndex. sweepingStart := currentSweepingEntity. lilliputianList := 0. lilliputianListEnd := 0. lilliputianListSize := 0. + lilliputianChunksToFree := 0. self assert: manager validObjectColors. sStartTime := coInterpreter ioUTCMicrosecondsNow. self doIncrementalSweeping + ifTrue: [self finishSweeping. - ifTrue: [ - "self cleanUpLilliputianChunks." - self finishSweeping. ^ true]. - "self cleanUpLilliputianChunks." ^ false !
vm-dev@lists.squeakfoundation.org