Skip to content
  • Ömer Sinan Ağacan's avatar
    Fix CNF handling in compacting GC · 39075176
    Ömer Sinan Ağacan authored and Marge Bot's avatar Marge Bot committed
    Fixes #17937
    
    Previously compacting GC simply ignored CNFs. This is mostly fine as
    most (see "What about small compacts?" below) CNF objects don't have
    outgoing pointers, and are "large" (allocated in large blocks) and large
    objects are not moved or compacted.
    
    However if we do GC *during* sharing-preserving compaction then the CNF
    will have a hash table mapping objects that have been moved to the CNF
    to their location in the CNF, to be able to preserve sharing.
    
    This case is handled in the copying collector, in `scavenge_compact`,
    where we evacuate hash table entries and then rehash the table.
    
    Compacting GC ignored this case.
    
    We now visit CNFs in all generations when threading pointers to the
    compacted heap and thread hash table keys. A visited CNF is added to the
    list `nfdata_chain`. After compaction is done, we re-visit the CNFs in
    that list and rehash the tables.
    
    The overhead is minimal: the list is static in `Compact.c`, and link
    field is added to `StgCompactNFData` closure. Programs that don't use
    CNFs should not be affected.
    
    To test this CNF tests are now also run in a new way 'compacting_gc',
    which just passes `-c` to the RTS, enabling compacting GC for the oldest
    generation. Before this patch the result would be:
    
        Unexpected failures:
           compact_gc.run          compact_gc [bad exit code (139)] (compacting_gc)
           compact_huge_array.run  compact_huge_array [bad exit code (1)] (compacting_gc)
    
    With this patch all tests pass. I can also pass `-c -DS` without any
    failures.
    
    What about small compacts? Small CNFs are still not handled by the
    compacting GC. However so far I'm unable to write a test that triggers a
    runtime panic ("update_fwd: unknown/strange object") by allocating a
    small CNF in a compated heap. It's possible that I'm missing something
    and it's not possible to have a small CNF.
    
    NoFib Results:
    
    --------------------------------------------------------------------------------
            Program           Size    Allocs    Instrs     Reads    Writes
    --------------------------------------------------------------------------------
                 CS          +0.1%      0.0%      0.0%     +0.0%     +0.0%
                CSD          +0.1%      0.0%      0.0%      0.0%      0.0%
                 FS          +0.1%      0.0%      0.0%      0.0%      0.0%
                  S          +0.1%      0.0%      0.0%      0.0%      0.0%
                 VS          +0.1%      0.0%      0.0%      0.0%      0.0%
                VSD          +0.1%      0.0%     +0.0%     +0.0%     -0.0%
                VSM          +0.1%      0.0%     +0.0%     -0.0%      0.0%
               anna          +0.0%      0.0%     -0.0%     -0.0%     -0.0%
               ansi          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               atom          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             awards          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             banner          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
         bernouilli          +0.1%      0.0%      0.0%     -0.0%     +0.0%
       binary-trees          +0.1%      0.0%     -0.0%     -0.0%      0.0%
              boyer          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             boyer2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               bspt          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
          cacheprof          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
           calendar          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           cichelli          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
            circsim          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           clausify          +0.1%      0.0%     -0.0%     +0.0%     +0.0%
      comp_lab_zift          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           compress          +0.1%      0.0%     +0.0%     +0.0%      0.0%
          compress2          +0.1%      0.0%     -0.0%      0.0%      0.0%
        constraints          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
       cryptarithm1          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
       cryptarithm2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
                cse          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
       digits-of-e1          +0.1%      0.0%     +0.0%     -0.0%     -0.0%
       digits-of-e2          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             dom-lt          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
              eliza          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
              event          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
        exact-reals          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             exp3_8          +0.1%      0.0%     +0.0%     -0.0%      0.0%
             expert          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
     fannkuch-redux          +0.1%      0.0%     -0.0%      0.0%      0.0%
              fasta          +0.1%      0.0%     -0.0%     +0.0%     +0.0%
                fem          +0.1%      0.0%     -0.0%     +0.0%      0.0%
                fft          +0.1%      0.0%     -0.0%     +0.0%     +0.0%
               fft2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           fibheaps          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               fish          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
              fluid          +0.0%      0.0%     +0.0%     +0.0%     +0.0%
             fulsom          +0.1%      0.0%     -0.0%     +0.0%      0.0%
             gamteb          +0.1%      0.0%     +0.0%     +0.0%      0.0%
                gcd          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
        gen_regexps          +0.1%      0.0%     -0.0%     +0.0%      0.0%
             genfft          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
                 gg          +0.1%      0.0%      0.0%     +0.0%     +0.0%
               grep          +0.1%      0.0%     -0.0%     +0.0%     +0.0%
             hidden          +0.1%      0.0%     +0.0%     -0.0%      0.0%
                hpg          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
                ida          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
              infer          +0.1%      0.0%     +0.0%      0.0%     -0.0%
            integer          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
          integrate          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
       k-nucleotide          +0.1%      0.0%     +0.0%     +0.0%      0.0%
              kahan          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
            knights          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             lambda          +0.1%      0.0%     +0.0%     +0.0%     -0.0%
         last-piece          +0.1%      0.0%     +0.0%      0.0%      0.0%
               lcss          +0.1%      0.0%     +0.0%     +0.0%      0.0%
               life          +0.1%      0.0%     -0.0%     +0.0%     +0.0%
               lift          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             linear          +0.1%      0.0%     -0.0%     +0.0%      0.0%
          listcompr          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           listcopy          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           maillist          +0.1%      0.0%     +0.0%     -0.0%     -0.0%
             mandel          +0.1%      0.0%     +0.0%     +0.0%      0.0%
            mandel2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               mate          +0.1%      0.0%     +0.0%      0.0%     +0.0%
            minimax          +0.1%      0.0%     -0.0%      0.0%     -0.0%
            mkhprog          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
         multiplier          +0.1%      0.0%     +0.0%      0.0%      0.0%
             n-body          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           nucleic2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               para          +0.1%      0.0%      0.0%     +0.0%     +0.0%
          paraffins          +0.1%      0.0%     +0.0%     -0.0%      0.0%
             parser          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
            parstof          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
                pic          +0.1%      0.0%     -0.0%     -0.0%      0.0%
           pidigits          +0.1%      0.0%     +0.0%     -0.0%     -0.0%
              power          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             pretty          +0.1%      0.0%     -0.0%     -0.0%     -0.1%
             primes          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
          primetest          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             prolog          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             puzzle          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             queens          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
            reptile          +0.1%      0.0%     -0.0%     -0.0%     +0.0%
    reverse-complem          +0.1%      0.0%     +0.0%      0.0%     -0.0%
            rewrite          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
               rfib          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
                rsa          +0.1%      0.0%     -0.0%     +0.0%     -0.0%
                scc          +0.1%      0.0%     -0.0%     -0.0%     -0.1%
              sched          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
                scs          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             simple          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
              solid          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
            sorting          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
      spectral-norm          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
             sphere          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
             symalg          +0.1%      0.0%     -0.0%     -0.0%     -0.0%
                tak          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
          transform          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
           treejoin          +0.1%      0.0%     +0.0%     -0.0%     -0.0%
          typecheck          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
            veritas          +0.0%      0.0%     +0.0%     +0.0%     +0.0%
               wang          +0.1%      0.0%      0.0%     +0.0%     +0.0%
          wave4main          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
       wheel-sieve1          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
       wheel-sieve2          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
               x2n1          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
    --------------------------------------------------------------------------------
                Min          +0.0%      0.0%     -0.0%     -0.0%     -0.1%
                Max          +0.1%      0.0%     +0.0%     +0.0%     +0.0%
     Geometric Mean          +0.1%     -0.0%     -0.0%     -0.0%     -0.0%
    
    Bumping numbers of nonsensical perf tests:
    
    Metric Increase:
        T12150
        T12234
        T12425
        T13035
        T5837
        T6048
    
    It's simply not possible for this patch to increase allocations, and
    I've wasted enough time on these test in the past (see #17686). I think
    these tests should not be perf tests, but for now I'll bump the numbers.
    39075176