Skip to content
Snippets Groups Projects
Select Git revision
  • 37484f566f6a755843cc88c219327d2d99bd680f
  • master default protected
  • seen
  • next
  • todo
  • maint
  • jch
  • v2.50.1
  • v2.50.0
  • v2.47.3
  • v2.48.2
  • v2.49.1
  • v2.43.7
  • v2.44.4
  • v2.45.4
  • v2.46.4
  • v2.50.0-rc2
  • v2.50.0-rc1
  • v2.50.0-rc0
  • v2.49.0
  • v2.49.0-rc2
  • v2.49.0-rc1
  • v2.49.0-rc0
  • v2.48.1
  • v2.48.0
  • v2.48.0-rc2
  • v2.48.0-rc1
27 results

ewah

  • Clone with SSH
  • Clone with HTTPS
  • user avatar
    Taylor Blau authored and Junio C Hamano committed
    While individual bitmap layers store different commit, type-level, and
    pseudo-merge bitmaps, only the top-most layer is used to compute
    reachability traversals.
    
    Many functions which implement the aforementioned traversal rely on
    enumerating the results according to the type-level bitmaps, and so
    would benefit from a conceptual type-level bitmap that spans multiple
    layers.
    
    Implement `struct ewah_or_iterator` which is capable of enumerating
    multiple EWAH bitmaps at once, and OR-ing the results together. When
    initialized with, for example, all of the commit type bitmaps from each
    layer, callers can pretend as if they are enumerating a large type-level
    bitmap which contains the commits from *all* bitmap layers.
    
    There are a couple of alternative approaches which were considered:
    
      - Decompress each EWAH bitmap and OR them together, enumerating a
        single (non-EWAH) bitmap. This would work, but has the disadvantage
        of decompressing a potentially large bitmap, which may not be
        necessary if the caller does not wish to read all of it.
    
      - Recursively call bitmap internal functions, reusing the "result" and
        "haves" bitmap from the top-most layer. This approach resembles the
        original implementation of this feature, but is inefficient in that
        it both (a) requires significant refactoring to implement, and (b)
        enumerates large sections of later bitmaps which are all zeros (as
        they pertain to objects in earlier layers).
    
        (b) is not so bad in and of itself, but can cause significant
        slow-downs when combined with expensive loop bodies.
    
    This approach (enumerating an OR'd together version of all of the
    type-level bitmaps from each layer) produces a significantly more
    straightforward implementation with significantly less refactoring
    required in order to make it work.
    
    Signed-off-by: default avatarTaylor Blau <me@ttaylorr.com>
    Acked-by: default avatarElijah Newren <newren@gmail.com>
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
    5551ccfe
    History