VM Maker: VMMaker.oscog-cb.2449.mcz

 
ClementBera uploaded a new version of VMMaker to project VM Maker:
http://source.squeak.org/VMMaker/VMMaker.oscog-cb.2449.mcz

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

Name: VMMaker.oscog-cb.2449
Author: cb
Time: 7 October 2018, 8:05:50.988548 pm
UUID: 4018501c-532d-4dfd-8702-9c2df3784942
Ancestors: VMMaker.oscog-cb.2448

Change SelectiveCompactor to annotate segments during sweep phase with the last lilliputian chunk they hold. When compacting specific segments, this information is re-used to jump in the lilliputian single linked list to the free chunk right before hence elements can be cheaply removed from the linked list without iterating over it.

Some numbers:

> Selective compactor compaction pauses
With this fix O(1), in my 20Gb workload, avg compaction pause is now at 3ms, with pathological cases at 20 ms.
With previous commits (no annotation, lilliputian linked list iterated at most once, O(N)), pathological pauses were up to 220ms.
Without lilliputian handling at all O(N^2), the lilliputian single linked list was iterated many times, leading to up to 10 seconds pathological cases.

> Mark pause
In my 20Gb workload, mark pause is around 17 seconds.

> Sweep pause (Selective compactor require the heap to be swept before compating)
In my 20Gb workload, mark pause is around 1.5 seconds.

Note that conceptually Mark/Sweep phases can be incremental or concurrent, which is not the case for the compaction phase.

This is part of a long term project to get OpenSmalltalk-VM GC pauses under 16-20ms (1 frame drop max at 50-60fps).

=============== Diff against VMMaker.oscog-cb.2448 ===============

Item was changed:
  SpurSweeper subclass: #SpurSelectiveCompactor
  instanceVariableNames: 'segmentToFill lastLilliputianChunk'
  classVariableNames: 'MaxOccupationForCompaction'
  poolDictionaries: ''
  category: 'VMMaker-SpurMemoryManager'!
 
+ !SpurSelectiveCompactor commentStamp: 'cb 10/7/2018 19:54' prior: 0!
- !SpurSelectiveCompactor commentStamp: 'cb 10/5/2018 12:58' prior: 0!
  SpurSelectiveCompactor compacts memory by selecting the memory segments with the most free space and compacting only those, to limit fragmentation while being really quick to perform. The algorithm is fast mostly because it does not update pointers: they are updated lazily during the next marking phase, so there is no need to read the fields of objects in other memory segments that the one compacted.
 
  The algorithm works as follow. First, a global sweep pass iterates over the memory linearly, changing unmarked objects to free chunks and concatenating free chunks. During the global sweep phase, the segments of the heap are analysed to determine the percentage of occupation. Second, the least occupied segments are compacted by copying the remaining live objects into an entirely free segment, called regionToFill (we detail later in the paragraph where regionToFill comes from), changing their values to forwarding objects and marking the free chunks as unavailable (removed from free list and marked as data objects). Third, the next marking phase removes all forwarders. Fourth, at the beginning of the next compaction phase the compacted segments from the previous GC can be entirely marked as free space (No need to check anything inside, there were only forwarders and trash data). One of the compacted segment is then selected as the segmentToFill, others are just marked as free chunks.
 
 
  The compaction is effectively partial, compacting only the most critical segments of the heap to limit fragmentation. Compaction time is crazy low, since a low number of objects are moved and pointer updated is lazily done during the next marking phase, while still preventing memory fragmentation.
 
  Now this works well when biasForGC is true, but when performing a snapshot, the compactor is just total crap (we need to figure out a solution).
 
  segmentToFill <SegInfo> the segment that will be filled through the copying algorithm
  lastLilliputianChunk <Oop to FreeChunk> This is used as a performance trick for lilliputian free chunks. See below.
 
  Segment abuse:
  The swizzle field of segInfo is abused by using the low 8 bits for occupation and the 9th bit as isBeingCompacted bit.
 
  Performance trick for lilliputian chunks:
+ Specific free chunks (called lilliputian, see isLilliputianSize:) are managed using a single linked list instead of a double linked list since there's not enough room in the free chunk for the back pointer. During the sweep phase this is not a problem since we're rebuilding the free chunk structure, but during selective compaction we're detaching free chunks from the free chunk structure and that can be horribly slow (10 seconds sometimes at 20Gb heap due to many iteration over the single linked list). To work around this problem, the sweep phase use lastLilliputianChunk variable to sort the lilliputian free chunk single linked list in ascending address order (See interceptAddFreeChunkWithBytes:at:). During the selective compation phase, the same variable is re-used to iterate at most once over the single linked list while detaching lilliputian chunks (See incrementalUnlinkSmallChunk:). In addition, each segment is annotated during the sweep phase with the last lilliputian chunk it
  holds. Hence, during the compaction phase, the linked list is iterated but the iteration can jump to the last chunk of the previous segment to compact.!
- Specific free chunks (called lilliputian, see isLilliputianSize:) are managed using a single linked list instead of a double linked list since there's not enough room in the free chunk for the back pointer. During the sweep phase this is not a problem since we're rebuilding the free chunk structure, but during selective compaction we're detaching free chunks from the free chunk structure and that can be horribly slow (10 seconds sometimes at 20Gb heap due to many iteration over the single linked list). To work around this problem, the sweep phase use lastLilliputianChunk variable to sort the lilliputian free chunk single linked list in ascending address order (See interceptAddFreeChunkWithBytes:at:). During the selective compation phase, the same variable is re-used to iterate at most once over the single linked list while detaching lilliputian chunks (See incrementalUnlinkSmallChunk:).
- "!

Item was removed:
- ----- Method: SpurSelectiveCompactor>>compactSegment:freeStart: (in category 'compaction') -----
- compactSegment: segInfo freeStart: initialFreeStart
- <var: 'segInfo' type: #'SpurSegmentInfo *'>
- | currentEntity fillStart bytesToCopy bridge copy |
- fillStart := initialFreeStart.
- bridge := manager segmentManager bridgeFor: segInfo.
- currentEntity := manager objectStartingAt: segInfo segStart.
- [self oop: currentEntity isLessThan: bridge] whileTrue:
- [(manager isFreeObject: currentEntity)
- ifTrue:
- ["To avoid confusing too much Spur (especially the leak/free checks), we mark the free chunk as a word object."
- (manager isLilliputianSize: (manager bytesInObject: currentEntity))
- ifTrue: [self incrementalUnlinkLilliputianChunk: currentEntity] "Performance hack for single linked list"
- ifFalse: [manager detachFreeObject: currentEntity].
- manager set: currentEntity classIndexTo: manager wordSizeClassIndexPun formatTo: manager wordIndexableFormat]
- ifFalse:
- ["Copy the object in segmentToFill and replace it by a forwarder."
- self assert: (manager isPinned: currentEntity) not.
- bytesToCopy := manager bytesInObject: currentEntity.
- manager memcpy: fillStart asVoidPointer _: (manager startOfObject: currentEntity) asVoidPointer _: bytesToCopy.
- copy := manager objectStartingAt: fillStart.
- (manager isRemembered: copy) ifTrue:
- ["copy has the remembered bit set, but is not in the remembered table."
- manager setIsRememberedOf: copy to: false.
- scavenger remember: copy].
- manager forward: currentEntity to: (manager objectStartingAt: fillStart).
- fillStart := fillStart + bytesToCopy.
- self assert: (self oop: fillStart isLessThan: (segmentToFill segLimit - manager bridgeSize))].
- currentEntity := manager objectAfter: currentEntity limit: manager endOfMemory].
- self assert: currentEntity = bridge.
- ^ fillStart!

Item was added:
+ ----- Method: SpurSelectiveCompactor>>compactSegment:freeStart:segIndex: (in category 'compaction') -----
+ compactSegment: segInfo freeStart: initialFreeStart segIndex: segIndex
+ <var: 'segInfo' type: #'SpurSegmentInfo *'>
+ | currentEntity fillStart bytesToCopy bridge copy |
+ fillStart := initialFreeStart.
+ bridge := manager segmentManager bridgeFor: segInfo.
+ currentEntity := manager objectStartingAt: segInfo segStart.
+ self deny: segIndex = 0. "Cannot compact seg 0"
+ lastLilliputianChunk := self lastLilliputianChunkAtIndex: segIndex - 1.
+ [self oop: currentEntity isLessThan: bridge] whileTrue:
+ [(manager isFreeObject: currentEntity)
+ ifTrue:
+ ["To avoid confusing too much Spur (especially the leak/free checks), we mark the free chunk as a word object."
+ (manager isLilliputianSize: (manager bytesInObject: currentEntity))
+ ifTrue: [self incrementalUnlinkLilliputianChunk: currentEntity] "Performance hack for single linked list"
+ ifFalse: [manager detachFreeObject: currentEntity].
+ manager set: currentEntity classIndexTo: manager wordSizeClassIndexPun formatTo: manager wordIndexableFormat]
+ ifFalse:
+ ["Copy the object in segmentToFill and replace it by a forwarder."
+ self assert: (manager isPinned: currentEntity) not.
+ bytesToCopy := manager bytesInObject: currentEntity.
+ manager memcpy: fillStart asVoidPointer _: (manager startOfObject: currentEntity) asVoidPointer _: bytesToCopy.
+ copy := manager objectStartingAt: fillStart.
+ (manager isRemembered: copy) ifTrue:
+ ["copy has the remembered bit set, but is not in the remembered table."
+ manager setIsRememberedOf: copy to: false.
+ scavenger remember: copy].
+ manager forward: currentEntity to: (manager objectStartingAt: fillStart).
+ fillStart := fillStart + bytesToCopy.
+ self assert: (self oop: fillStart isLessThan: (segmentToFill segLimit - manager bridgeSize))].
+ currentEntity := manager objectAfter: currentEntity limit: manager endOfMemory].
+ self assert: currentEntity = bridge.
+ ^ fillStart!

Item was changed:
  ----- Method: SpurSelectiveCompactor>>compactSegmentsToCompact (in category 'compaction') -----
  compactSegmentsToCompact
  "Forwards all objects in segments to compact and removes their freechunks"
  | segInfo fillStart |
  <var: 'segInfo' type: #'SpurSegmentInfo *'>
  fillStart := segmentToFill segStart.
 
  "Removes initial free chunk in segment to fill... (Segment is entirely free)"
  manager detachFreeObject: (manager objectStartingAt: fillStart).
 
- "Set-up hack to iterate at most one over size 1 free chunks single linked list."
- lastLilliputianChunk := 0.
-
  "Compact each segment to compact..."
  0 to: manager numSegments - 1 do:
  [:i|
  segInfo := self addressOf: (manager segmentManager segments at: i).
  (self isSegmentBeingCompacted: segInfo)
+ ifTrue: [fillStart := self compactSegment: segInfo freeStart: fillStart segIndex: i]].
- ifTrue: [fillStart := self compactSegment: segInfo freeStart: fillStart ]].
 
  "Final free chunk in segment to fill..."
  manager
  addFreeChunkWithBytes: segmentToFill segSize - manager bridgeSize + segmentToFill segStart - fillStart
  at: fillStart.
 
  self postCompactionAction
  !

Item was changed:
  ----- Method: SpurSelectiveCompactor>>globalSweepAndSegmentOccupationAnalysis (in category 'sweep phase') -----
  globalSweepAndSegmentOccupationAnalysis
  <inline: #never> "profiling"
  "Iterate over old space, free unmarked objects, annotate each segment with each occupation"
  | currentEntity nextBridge segmentIndex currentUsed currentUnused |
  lastLilliputianChunk := 0. "performance hack for single linked list"
  currentEntity := manager firstObject.
  nextBridge := manager segmentManager bridgeAt: 0.
  segmentIndex := currentUnused := currentUsed := 0.
+ self setLastLilliputianChunkAtindex: 0 to: 0.
  [self oop: currentEntity isLessThan: manager endOfMemory] whileTrue:
  [currentEntity = nextBridge "End of segment, set occupation"
  ifTrue:
  [self
  setOccupationAtIndex: segmentIndex
  used: currentUsed
  unused: currentUnused.
+  self setLastLilliputianChunkAtindex: segmentIndex to: lastLilliputianChunk.
   currentUnused := currentUsed := 0.
   segmentIndex := segmentIndex + 1.
   nextBridge := manager segmentManager bridgeAt: segmentIndex]
  ifFalse:
  [(self canUseAsFreeSpace: currentEntity) "In-segment, sweep and compute occupation"
  ifTrue:
  [currentEntity := self bulkFreeChunkFrom: currentEntity.
  currentUnused := currentUnused + (manager bytesInObject: currentEntity)]
  ifFalse:
  [self unmark: currentEntity.
  currentUsed := currentUsed + (manager bytesInObject: currentEntity)]].
  currentEntity := manager objectAfter: currentEntity limit: manager endOfMemory].
+ "set last segment details"
+ self
- self "set last segment occupation"
  setOccupationAtIndex: segmentIndex
  used: currentUsed
  unused: currentUnused.
+ self setLastLilliputianChunkAtindex: segmentIndex to: lastLilliputianChunk.
  "we set the nextFreeChunk of last chunk at the end of the loop to avoid to set it at each iteration"
  lastLilliputianChunk ~= 0 ifTrue:
  [manager setNextFreeChunkOf: lastLilliputianChunk withValue: 0 isLilliputianSize: true].
 
  manager checkFreeSpace: GCModeFull.
  manager unmarkSurvivingObjectsForCompact.!

Item was added:
+ ----- Method: SpurSelectiveCompactor>>lastLilliputianChunkAtIndex: (in category 'segment access') -----
+ lastLilliputianChunkAtIndex: segIndex
+ <inline: true>
+ "Abuse lastFreeObject field, can be used during compaction only, used for different purpose during snapshot"
+ ^(self addressOf: (manager segmentManager segments at: 0)) lastFreeObject!

Item was added:
+ ----- Method: SpurSelectiveCompactor>>setLastLilliputianChunkAtindex:to: (in category 'segment access') -----
+ setLastLilliputianChunkAtindex: segIndex to: chunk
+ <inline: true>
+ "Abuse lastFreeObject field, can be used during compaction only, used for different purpose during snapshot"
+ (self addressOf: (manager segmentManager segments at: 0)) lastFreeObject: chunk!

Item was removed:
- ----- Method: SpurSelectiveCompactorSimulator>>compactSegment:freeStart: (in category 'compaction') -----
- compactSegment: segInfo freeStart: initialFreeStart
- | res |
- res := super compactSegment: segInfo freeStart: initialFreeStart.
- self checkOnlyForwardersOrWordNonImm: segInfo.
- ^ res!