summaryrefslogtreecommitdiff
path: root/rts/sm
Commit message (Collapse)AuthorAgeFilesLines
* Fix more typosBrian Wignall2019-12-023-3/+3
|
* Fix typos, using Wikipedia list of common typosBrian Wignall2019-11-282-2/+2
|
* nonmoving: Fix handling on large object marking on 32-bitBen Gamari2019-11-191-4/+7
| | | | | | | | | Previously we would reset the pointer pointing to the object to be marked to the beginning of the block when marking a large object. This did no harm on 64-bit but on 32-bit it broke, e.g. `arr020`, since we align pinned ByteArray allocations such that the payload is 8 byte-aligned. This means that the object might not begin at the beginning of the block.,
* nonmoving: Rework mark queue representationBen Gamari2019-11-192-23/+18
| | | | | The previous representation needlessly limited the array length to 16-bits on 32-bit platforms.
* nonmoving: Fix incorrect masking in mark queue type testBen Gamari2019-11-191-2/+2
| | | | | | We were using TAG_BITS instead of TAG_MASK. This happened to work on 64-bit platforms where TAG_BITS==3 since we only use tag values 0 and 3. However, this broken on 32-bit platforms where TAG_BITS==2.
* nonmoving: Use correct info table pointer accessorBen Gamari2019-11-191-5/+7
| | | | | | | | | | | Previously we used INFO_PTR_TO_STRUCT instead of THUNK_INFO_PTR_TO_STRUCT when looking at a thunk. These two happen to be equivalent on 64-bit architectures due to alignment considerations however they are different on 32-bit platforms. This lead to #17487. To fix this we also employ a small optimization: there is only one thunk of type WHITEHOLE (namely stg_WHITEHOLE_info). Consequently, we can just use a plain pointer comparison instead of testing against info->type.
* rts/nonmoving: Catch failure of createOSThreadBen Gamari2019-11-081-2/+4
|
* rts/NonMoving: Fix various Windows build issuesBen Gamari2019-11-072-5/+6
| | | | | The Windows build seems to be stricter about not providing threading primitives in the non-threaded RTS.
* rts: Remove undesireable inline specifierBen Gamari2019-11-071-1/+1
| | | | | I have no idea why I marked this as inline originally but clearly it shouldn't be inlined.
* rts: Add missing const in HEAP_ALLOCED_GCBen Gamari2019-11-051-1/+1
| | | | | This was previously unnoticed as this code-path is hit on very few platforms (e.g. OpenBSD).
* Merge non-moving garbage collectorBen Gamari2019-10-2325-206/+6176
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces a concurrent mark & sweep garbage collector to manage the old generation. The concurrent nature of this collector typically results in significantly reduced maximum and mean pause times in applications with large working sets. Due to the large and intricate nature of the change I have opted to preserve the fully-buildable history, including merge commits, which is described in the "Branch overview" section below. Collector design ================ The full design of the collector implemented here is described in detail in a technical note > B. Gamari. "A Concurrent Garbage Collector For the Glasgow Haskell > Compiler" (2018) This document can be requested from @bgamari. The basic heap structure used in this design is heavily inspired by > K. Ueno & A. Ohori. "A fully concurrent garbage collector for > functional programs on multicore processors." /ACM SIGPLAN Notices/ > Vol. 51. No. 9 (presented at ICFP 2016) This design is intended to allow both marking and sweeping concurrent to execution of a multi-core mutator. Unlike the Ueno design, which requires no global synchronization pauses, the collector introduced here requires a stop-the-world pause at the beginning and end of the mark phase. To avoid heap fragmentation, the allocator consists of a number of fixed-size /sub-allocators/. Each of these sub-allocators allocators into its own set of /segments/, themselves allocated from the block allocator. Each segment is broken into a set of fixed-size allocation blocks (which back allocations) in addition to a bitmap (used to track the liveness of blocks) and some additional metadata (used also used to track liveness). This heap structure enables collection via mark-and-sweep, which can be performed concurrently via a snapshot-at-the-beginning scheme (although concurrent collection is not implemented in this patch). Implementation structure ======================== The majority of the collector is implemented in a handful of files: * `rts/Nonmoving.c` is the heart of the beast. It implements the entry-point to the nonmoving collector (`nonmoving_collect`), as well as the allocator (`nonmoving_allocate`) and a number of utilities for manipulating the heap. * `rts/NonmovingMark.c` implements the mark queue functionality, update remembered set, and mark loop. * `rts/NonmovingSweep.c` implements the sweep loop. * `rts/NonmovingScav.c` implements the logic necessary to scavenge the nonmoving heap. Branch overview =============== ``` * wip/gc/opt-pause: | A variety of small optimisations to further reduce pause times. | * wip/gc/compact-nfdata: | Introduce support for compact regions into the non-moving |\ collector | \ | \ | | * wip/gc/segment-header-to-bdescr: | | | Another optimization that we are considering, pushing | | | some segment metadata into the segment descriptor for | | | the sake of locality during mark | | | | * | wip/gc/shortcutting: | | | Support for indirection shortcutting and the selector optimization | | | in the non-moving heap. | | | * | | wip/gc/docs: | |/ Work on implementation documentation. | / |/ * wip/gc/everything: | A roll-up of everything below. |\ | \ | |\ | | \ | | * wip/gc/optimize: | | | A variety of optimizations, primarily to the mark loop. | | | Some of these are microoptimizations but a few are quite | | | significant. In particular, the prefetch patches have | | | produced a nontrivial improvement in mark performance. | | | | | * wip/gc/aging: | | | Enable support for aging in major collections. | | | | * | wip/gc/test: | | | Fix up the testsuite to more or less pass. | | | * | | wip/gc/instrumentation: | | | A variety of runtime instrumentation including statistics | | / support, the nonmoving census, and eventlog support. | |/ | / |/ * wip/gc/nonmoving-concurrent: | The concurrent write barriers. | * wip/gc/nonmoving-nonconcurrent: | The nonmoving collector without the write barriers necessary | for concurrent collection. | * wip/gc/preparation: | A merge of the various preparatory patches that aren't directly | implementing the GC. | | * GHC HEAD . . . ```
| * nonmoving: Upper-bound time we hold SM_MUTEX for during sweepwip/gc/opt-pauseBen Gamari2019-10-221-1/+25
| |
| * nonmoving: Don't do two passes over large and compact object listsBen Gamari2019-10-221-10/+14
| | | | | | | | | | | | | | | | | | | | | | Previously we would first move the new objects to their appropriate non-moving GC list, then do another pass over that list to clear their mark bits. This is needlessly expensive. First clear the mark bits of the existing objects, then add the newly evacuated objects and, at the same time, clear their mark bits. This cuts the preparatory GC time in half for the Pusher benchmark with a large queue size.
| * nonmoving: Trace GC preparation stepsBen Gamari2019-10-221-0/+4
| |
| * rts: Mark nonmoving GC paths in moving collector as unlikelywip/gc/compact-nfdataBen Gamari2019-10-221-8/+8
| | | | | | | | | | | | The expectation here is that the nonmoving GC is latency-centric, whereas the moving GC emphasizes throughput. Therefore we give the latter the benefit of better static branch prediction.
| * rts: COMPACT_NFDATA support for the nonmoving collectorÖmer Sinan Ağacan2019-10-2211-18/+139
| | | | | | | | | | | | This largely follows the model used for large objects, with appropriate adjustments made to account for references in the sharing deduplication hashtable.
| *-. Merge branches 'wip/gc/segment-header-to-bdescr' and 'wip/gc/docs' into ↵wip/gc/everything2Ben Gamari2019-10-225-28/+233
| |\ \ | | | | | | | | | | | | wip/gc/everything2
| | | * NonMoving: Add summarizing Notewip/gc/docsBen Gamari2019-10-222-1/+186
| | | |
| | * | NonMoving: Move next_free_snap to block descriptorwip/gc/segment-header-to-bdescrBen Gamari2019-10-225-12/+17
| | | |
| | * | NonMoving: Move block size to block descriptorBen Gamari2019-10-223-5/+15
| | | |
| | * | NonMoving: Introduce nonmovingSegmentLogBlockSize acccessorBen Gamari2019-10-223-14/+19
| | |/ | | | | | | | | | This will allow us to easily move the block size elsewhere.
| * | NonMoving: Implement -xns to disable selector optimizationwip/gc/shortcuttingÖmer Sinan Ağacan2019-10-221-1/+5
| | |
| * | NonMovingMark: Handle INDs left by shortcuttingBen Gamari2019-10-221-2/+11
| | |
| * | NonMoving: Implement selector optimisationÖmer Sinan Ağacan2019-10-224-3/+352
| | |
| * | NonMoving: Implement indirection shortcuttingÖmer Sinan Ağacan2019-10-221-17/+47
| |/ | | | | | | | | This allows indirection chains residing in the non-moving heap to be shorted-out.
| *-. Merge branches 'wip/gc/optimize' and 'wip/gc/test' into wip/gc/everythingwip/gc/everythingBen Gamari2019-10-2212-202/+790
| |\ \
| | * | Unconditionally flush update remembered set during minor GCwip/gc/optimizeBen Gamari2019-10-222-0/+51
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Flush the update remembered set. The goal here is to flush periodically to ensure that we don't end up with a thread who marks their stack on their local update remembered set and doesn't flush until the nonmoving sync period as this would result in a large fraction of the heap being marked during the sync pause.
| | * | NonMoving: Clean mut_listBen Gamari2019-10-221-1/+121
| | | |
| | * | NonMoving: Don't do major GC if one is already runningBen Gamari2019-10-222-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously we would perform a preparatory moving collection, resulting in many things being added to the mark queue. When we finished with this we would realize in nonmovingCollect that there was already a collection running, in which case we would simply not run the nonmoving collector. However, it was very easy to end up in a "treadmilling" situation: all subsequent GC following the first failed major GC would be scheduled as major GCs. Consequently we would continuously feed the concurrent collector with more mark queue entries and it would never finish. This patch aborts the major collection far earlier, meaning that we avoid adding nonmoving objects to the mark queue and allowing the concurrent collector to finish.
| | * | NonMovingMark: Eliminate redundant check_in_nonmoving_heapsBen Gamari2019-10-221-16/+15
| | | |
| | * | NonMoving: Optimise allocator cache behaviorBen Gamari2019-10-222-24/+42
| | | | | | | | | | | | | | | | | | | | Previously we would look at the segment header to determine the block size despite the fact that we already had the block size at hand.
| | * | NonMoving: Prefetch segment headerBen Gamari2019-10-222-2/+8
| | | |
| | * | NonMoving: Pre-fetch during markBen Gamari2019-10-222-1/+55
| | | | | | | | | | | | | | | | This improved overall runtime on nofib's constraints test by nearly 10%.
| | * | NonMoving: Fuse sweep preparation into mark prepBen Gamari2019-10-223-45/+25
| | | |
| | * | NonMoving: Inline nonmovingClearAllBitmapsBen Gamari2019-10-221-25/+10
| | | |
| | * | NonMoving: Prefetch when clearing bitmapsBen Gamari2019-10-221-0/+2
| | | | | | | | | | | | | | | | | | | | Ensure that the bitmap of the segmentt that we will clear next is in cache by the time we reach it.
| | * | NonMoving: Optimize bitmap search during allocationBen Gamari2019-10-221-2/+14
| | | | | | | | | | | | | | | | | | | | Use memchr instead of a open-coded loop. This is nearly twice as fast in a synthetic benchmark.
| | * | NonMovingMark: Optimize representation of mark queueBen Gamari2019-10-222-13/+38
| | | | | | | | | | | | | | | | This shortens MarkQueueEntry by 30% (one word)
| | * | NonMoving: Allocate mark queues in larger block groupsBen Gamari2019-10-222-4/+7
| | | |
| | * | NonMoving: Eliminate integer division in nonmovingBlockCountBen Gamari2019-10-221-4/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Perf showed that the this single div was capturing up to 10% of samples in nonmovingMark. However, the overwhelming majority of cases is looking at small block sizes. These cases we can easily compute explicitly, allowing the compiler to turn the division into a significantly more efficient division-by-constant. While the increase in source code looks scary, this all optimises down to very nice looking assembler. At this point the only remaining hotspots in nonmovingBlockCount are due to memory access.
| | * | More comments for agingwip/gc/agingBen Gamari2019-10-221-5/+91
| | | |
| | * | Disable aging when doing deadlock detection GCBen Gamari2019-10-224-23/+53
| | | |
| | * | Nonmoving: Allow aging and refactor static objects logicBen Gamari2019-10-2210-81/+266
| | |/ | | | | | | | | | | | | | | | | | | This commit does two things: * Allow aging of objects during the preparatory minor GC * Refactor handling of static objects to avoid the use of a hashtable
| * | NonmovingCensus: Emit samples to eventlogwip/gc/instrumentationBen Gamari2019-10-222-0/+21
| | |
| * | Allow census without live word countBen Gamari2019-10-222-16/+47
| | | | | | | | | | | | | | | Otherwise the census is unsafe when mutators are running due to concurrent mutation.
| * | rts: Introduce non-moving heap censusBen Gamari2019-10-223-0/+110
| | | | | | | | | | | | | | | | | | | | | | | | This introduces a simple census of the non-moving heap (not to be confused with the heap census used by the heap profiler). This collects basic heap usage information (number of allocated and free blocks) which is useful when characterising fragmentation of the nonmoving heap.
| * | rts: Tracing support for nonmoving collection eventsBen Gamari2019-10-222-0/+8
| |/ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This introduces a few events to mark key points in the nonmoving garbage collection cycle. These include: * `EVENT_CONC_MARK_BEGIN`, denoting the beginning of a round of marking. This may happen more than once in a single major collection since we the major collector iterates until it hits a fixed point. * `EVENT_CONC_MARK_END`, denoting the end of a round of marking. * `EVENT_CONC_SYNC_BEGIN`, denoting the beginning of the post-mark synchronization phase * `EVENT_CONC_UPD_REM_SET_FLUSH`, indicating that a capability has flushed its update remembered set. * `EVENT_CONC_SYNC_END`, denoting that all mutators have flushed their update remembered sets. * `EVENT_CONC_SWEEP_BEGIN`, denoting the beginning of the sweep portion of the major collection. * `EVENT_CONC_SWEEP_END`, denoting the end of the sweep portion of the major collection.
| * Fix unregisterised buildwip/gc/nonmoving-concurrentBen Gamari2019-10-222-1/+2
| | | | | | | | | | | | This required some fiddling around with the location of forward declarations since the C sources generated by GHC's C backend only includes Stg.h.
| * Nonmoving: Ensure write barrier vanishes in non-threaded RTSBen Gamari2019-10-212-8/+13
| |
| * Don't cleanup until we've stopped the collectorBen Gamari2019-10-203-2/+20
| | | | | | | | | | | | | | This requires that we break nonmovingExit into two pieces since we need to first stop the collector to relinquish any capabilities, then we need to shutdown the scheduler, then we need to free the nonmoving allocators.
View Lorry Controller Status