Simon Jakobi pushed to branch wip/sjakobi/uniqfm-note at Glasgow Haskell Compiler / GHC

Commits:

3 changed files:

Changes:

  • compiler/GHC/Types/Unique.hs
    ... ... @@ -88,6 +88,10 @@ to distinguish uniques constructed by different parts of the compiler.
    88 88 
     To ensure that we assign distinct tags for each purpose, we represent tags in the compiler
    89 89 
     via the UniqueTag ADT.
    90 90
    91 
    +The high-order tag also shapes any 'UniqFM' keyed by these uniques, clustering
    92 
    +keys near the trie root; see Note [Uniques and UniqFM shape] in
    93 
    +GHC.Types.Unique.FM.
    94 
    +
    91 95 
     The bidirectional mapping from the UniqueTag ADT to the corresponding character is witnessed
    92 96 
     by the uniqueTag and charToUniqueTag functions.
    93 97 
     See Note [Uniques for wired-in prelude things and known tags]

  • compiler/GHC/Types/Unique/FM.hs
    ... ... @@ -10,13 +10,12 @@ Basically, the things need to be in class @Uniquable@, and we use the
    10 10
    11 11 
     (A similar thing to @UniqSet@, as opposed to @Set@.)
    12 12
    13 
    -The interface is based on @FiniteMap@s, but the implementation uses
    14 
    -@Data.IntMap@, which is both maintained and faster than the past
    15 
    -implementation (see commit log).
    13 
    +The implementation is a 'Word64Map' keyed by each element's 'Unique';
    14 
    +see Note [Uniques and UniqFM shape].
    16 15
    17 
    -The @UniqFM@ interface maps directly to Data.IntMap, only
    18 
    -``Data.IntMap.union'' is left-biased and ``plusUFM'' right-biased
    19 
    -and ``addToUFM\_C'' and ``Data.IntMap.insertWith'' differ in the order
    16 
    +The @UniqFM@ interface maps directly to Word64Map, only
    17 
    +``Word64Map.union'' is left-biased and ``plusUFM'' right-biased
    18 
    +and ``addToUFM\_C'' and ``Word64Map.insertWith'' differ in the order
    20 19 
     of arguments of combining function.
    21 20 
     -}
    22 21
    ... ... @@ -100,6 +99,55 @@ import qualified Data.Semigroup as Semi
    100 99 
     import Data.Functor.Classes (Eq1 (..))
    101 100 
     import Data.Coerce
    102 101
    102 
    +{- Note [Uniques and UniqFM shape]
    103 
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    104 
    +A 'UniqFM' is a 'Word64Map' -- a big-endian PATRICIA trie -- keyed by the
    105 
    +'Word64' underlying each 'Unique'. A 'Unique' splits into a tag in the top 8
    106 
    +bits (UNIQUE_TAG_BITS), identifying the supply or namespace that minted it, and
    107 
    +a running number in the low bits; see Note [Uniques and tags] in
    108 
    +GHC.Types.Unique. Those numbers are allocated sequentially -- from the global
    109 
    +'genSym' counter, or by 'uniqAway' from a set's largest local unique -- so they
    110 
    +stay far below the full 'Word64' range. Within a tag the keys are thus dense and
    111 
    +sequential, not scattered hashes, which keeps the trie shallow and is what makes
    112 
    +a 'Word64Map' a good fit. And because those numbers only grow, inserts within a
    113 
    +cluster tend to land above its existing keys -- a near-monotonic pattern that
    114 
    +big-endian PATRICIA tries service superoptimally, well below the O(log n)
    115 
    +worst case (see #24137).
    116 
    +
    117 
    +A PATRICIA trie branches on the most-significant bit on which its keys disagree,
    118 
    +so the tag bits are tested first, nearest the root. Uniques are therefore
    119 
    +partitioned by tag near the root: all keys with a given tag occupy a single
    120 
    +subtree (the largest one whose prefix already fixes every tag bit), and two
    121 
    +keys with different tags diverge closer to the root, where the trie switches on
    122 
    +a tag bit. In other words the high-order tag clusters together the keys minted
    123 
    +by each part of the compiler.
    124 
    +
    125 
    +This clustering would make tag-keyed bulk operations cheap -- collecting the
    126 
    +distinct tags, filtering to a set of tags, or splitting into per-tag submaps
    127 
    +could each reuse whole subtrees and touch O(number of distinct tags) nodes
    128 
    +rather than O(size). That is only potential, though: GHC has no tag-aware bulk
    129 
    +operations yet.
    130 
    +
    131 
    +The flip side is that the tag bits lengthen the path every per-key operation
    132 
    +walks: a lookup, insert, or delete descends past the tag-distinguishing nodes
    133 
    +near the root before reaching the number bits. Mixing tags thus adds branch
    134 
    +levels above each entry -- at most 7, since the tag is 8 bits with its top bit
    135 
    +clear for every ASCII tag. In-scope sets and 'VarSet's are the heavy case:
    136 
    +keyed by 'Var' uniques, they gather ~8-11 supply tags (desugarer, simplifier,
    137 
    +'uniqAway', wired-in, typechecker), spanning most of the tag bits, so a lookup
    138 
    +descends roughly 3-5 extra levels. A 'NameEnv'/'TypeEnv' is milder: external
    139 
    +names all share HscTag, so it is one big cluster plus a few wired-in and local
    140 
    +tags, ~2-4 levels. A map holding a single tag collapses the tag bits into the
    141 
    +root prefix and is correspondingly shallower, so keeping a map tag-homogeneous
    142 
    +(or splitting it by tag) speeds up its lookups.
    143 
    +
    144 
    +The trie's key order is exploited the other way too, to mint uniques: 'uniqAway'
    145 
    +derives a fresh unique not in an 'InScopeSet' from the largest key already in
    146 
    +that set's local-unique region (an O(depth) 'lookupLT') and increments it,
    147 
    +staying in that dedicated tag region (the 'X' tag), which cannot clash with
    148 
    +counter-allocated ones. See Note [Local uniques] in GHC.Types.Var.Env.
    149 
    +-}
    150 
    +
    103 151 
     -- | A finite map from @uniques@ of one type to
    104 152 
     -- elements in another type.
    105 153 
     --

  • compiler/GHC/Types/Var/Env.hs
    ... ... @@ -228,7 +228,9 @@ uniqAway' in_scope var
    228 228
    229 229 
     -- | @unsafeGetFreshUnique in_scope@ finds a unique that is not in-scope in the
    230 230 
     -- given 'InScopeSet'. This must be used very carefully since one can very easily
    231 
    --- introduce non-unique 'Unique's this way. See Note [Local uniques].
    231 
    +-- introduce non-unique 'Unique's this way. See Note [Local uniques], and
    232 
    +-- Note [Uniques and UniqFM shape] in GHC.Types.Unique.FM for the 'lookupLT'
    233 
    +-- trie mechanics it relies on.
    232 234 
     unsafeGetFreshLocalUnique :: InScopeSet -> Unique
    233 235 
     unsafeGetFreshLocalUnique (InScope set)
    234 236 
       | Just (uniq,_) <- Word64Map.lookupLT (getKey maxLocalUnique) (ufmToIntMap $ getUniqSet set)

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help