git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH v2 13/15] pack-bitmap: implement BLOB_NONE filtering

From
Derrick Stolee <stolee@gmail.com>
Date
Feb 18, 2020, 19:26 UTC
Message-ID
<800e4714-200e-6256-5538-ef39f6d9246c@gmail.com>
In-Reply-To
<20200214182236.GM150965@coredump.intra.peff.net>
On 2/14/2020 1:22 PM, Jeff King wrote:
Show 9 quoted lines
> We can easily support BLOB_NONE filters with bitmaps. Since we know the
> types of all of the objects, we just need to clear the result bits of
> any blobs.
> 
> Note two subtleties in the implementation (which I also called out in
> comments):
> 
>   - we have to include any blobs that were specifically asked for (and
>     not reached through graph traversal) to match the non-bitmap version

I have a concern here, but maybe I'm worrying about nothing. When a partial clone asks for a pack of missing blobs, will your code create an empty bitmap and then add bits to that bitmap one-by-one instead of appending to a simple object list?

In the typical case where we ask for specific commits and trees, we expect a very small number of blobs to add to the resulting bitmap. When no commits or trees are included in the wants, then we don't need the bitmap at all. IIRC an EWAH bitmap is relatively expensive to update bits one at a time, so this is not incredibly efficient.

I apologize that I don't have the time to dig into this myself.
Show 13 quoted lines
>   - we have to handle in-pack and "ext_index" objects separately.
>     Arguably prepare_bitmap_walk() could be adding these ext_index
>     objects to the type bitmaps. But it doesn't for now, so let's match
>     the rest of the bitmap code here (it probably wouldn't be an
>     efficiency improvement to do so since the cost of extending those
>     bitmaps is about the same as our loop here, but it might make the
>     code a bit simpler).
> 
> Here are perf results for the new test on git.git:
> 
>   Test                                    HEAD^             HEAD
>   --------------------------------------------------------------------------------
>   5310.9: rev-list count with blob:none   1.67(1.62+0.05)   0.22(0.21+0.02) -86.8%
...
Show 12 quoted lines
> diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh
> index e52f66ec9e..936742314c 100755
> --- a/t/perf/p5310-pack-bitmaps.sh
> +++ b/t/perf/p5310-pack-bitmaps.sh
> @@ -47,6 +47,11 @@ test_perf 'rev-list (objects)' '
>  	git rev-list --all --use-bitmap-index --objects >/dev/null
>  '
>  
> +test_perf 'rev-list count with blob:none' '
> +	git rev-list --use-bitmap-index --count --objects --all \
> +		--filter=blob:none >/dev/null
> +'

I wondered why you chose to extend these tests instead of using p5600-partial-clone.sh, but I guess this script definitely creates the bitmap for the test. When I tested p5600-partial-clone.sh below, I manually repacked the Linux repo to have a bitmap:

Test v2.25.0 HEAD ---------------------------------------------------------------------------- 5600.2: clone without blobs 79.81(111.34+11.35) 36.00(69.37+7.30) -54.9% 5600.3: checkout of result 45.56(114.59+4.81) 46.43(80.50+5.41) +1.9%

Perhaps results for these tests would also be appropriate for your commit messages?

Note the +1.9% for the checkout. It's unlikely that this is actually something meaningful, but it _could_ be related to my concerns above about building a blob list from an empty bitmap.

Thanks, -Stolee

Previous: Jeff KingNext: Derrick Stolee
Message 70 of 73 in “combining object filters and bitmaps”
  1. 0/13 combining object filters and bitmapsJeff King, Feb 13, 2020
  2. 01/13 pack-bitmap: factor out type iterator initializationJeff King, Feb 13, 2020
  3. Junio C HamanoFeb 13, 2020
  4. 02/13 pack-bitmap: fix leak of haves/wants object listsJeff King, Feb 13, 2020
  5. Junio C HamanoFeb 13, 2020
  6. 03/13 rev-list: fallback to non-bitmap traversal when filteringJeff King, Feb 13, 2020
  7. Junio C HamanoFeb 13, 2020
  8. Jeff KingFeb 13, 2020
  9. 04/13 rev-list: consolidate bitmap-disabling optionsJeff King, Feb 13, 2020
  10. 05/13 rev-list: factor out bitmap-optimized routinesJeff King, Feb 13, 2020
  11. Junio C HamanoFeb 13, 2020
  12. 06/13 rev-list: make --count work with --objectsJeff King, Feb 13, 2020
  13. Junio C HamanoFeb 13, 2020
  14. Jeff KingFeb 13, 2020
  15. 07/13 rev-list: allow bitmaps when counting objectsJeff King, Feb 13, 2020
  16. Junio C HamanoFeb 13, 2020
  17. Jeff KingFeb 13, 2020
  18. 08/13 pack-bitmap: basic noop bitmap filter infrastructureJeff King, Feb 13, 2020
  19. 09/13 rev-list: use bitmap filters for traversalJeff King, Feb 13, 2020
  20. Junio C HamanoFeb 13, 2020
  21. Jeff KingFeb 13, 2020
  22. 10/13 bitmap: add bitmap_unset() functionJeff King, Feb 13, 2020
  23. 11/13 pack-bitmap: implement BLOB_NONE filteringJeff King, Feb 13, 2020
  24. 12/13 pack-bitmap: implement BLOB_LIMIT filteringJeff King, Feb 13, 2020
  25. Junio C HamanoFeb 13, 2020
  26. 13/13 pack-objects: support filters with bitmapsJeff King, Feb 13, 2020
  27. 0/15 combining object filters and bitmapsJeff King, Feb 14, 2020
  28. 01/15 pack-bitmap: factor out type iterator initializationJeff King, Feb 14, 2020
  29. Taylor BlauFeb 15, 2020
  30. 03/15 rev-list: fallback to non-bitmap traversal when filteringJeff King, Feb 14, 2020
  31. Taylor BlauFeb 15, 2020
  32. 04/15 pack-bitmap: refuse to do a bitmap traversal with pathspecsJeff King, Feb 14, 2020
  33. Junio C HamanoFeb 14, 2020
  34. Jeff KingFeb 14, 2020
  35. 05/15 rev-list: factor out bitmap-optimized routinesJeff King, Feb 14, 2020
  36. Taylor BlauFeb 15, 2020
  37. 06/15 rev-list: make --count work with --objectsJeff King, Feb 14, 2020
  38. Taylor BlauFeb 15, 2020
  39. Jeff KingFeb 15, 2020
  40. Junio C HamanoFeb 16, 2020
  41. Jeff KingFeb 18, 2020
  42. Junio C HamanoFeb 18, 2020
  43. Jeff KingFeb 18, 2020
  44. Junio C HamanoFeb 18, 2020
  45. Jeff KingFeb 18, 2020
  46. Derrick StoleeFeb 18, 2020
  47. Jeff KingFeb 18, 2020
  48. 08/15 t5310: factor out bitmap traversal comparisonJeff King, Feb 14, 2020
  49. Taylor BlauFeb 15, 2020
  50. Jeff KingFeb 15, 2020
  51. 07/15 rev-list: allow bitmaps when counting objectsJeff King, Feb 14, 2020
  52. Taylor BlauFeb 15, 2020
  53. Jeff KingFeb 15, 2020
  54. Junio C HamanoFeb 16, 2020
  55. 09/15 rev-list: allow commit-only bitmap traversalsJeff King, Feb 14, 2020
  56. Derrick StoleeFeb 18, 2020
  57. Jeff KingFeb 18, 2020
  58. Derrick StoleeFeb 18, 2020
  59. 10/15 pack-bitmap: basic noop bitmap filter infrastructureJeff King, Feb 14, 2020
  60. 02/15 pack-bitmap: fix leak of haves/wants object listsJeff King, Feb 14, 2020
  61. Taylor BlauFeb 15, 2020
  62. Jeff KingFeb 15, 2020
  63. Derrick StoleeFeb 18, 2020
  64. Jeff KingFeb 18, 2020
  65. 11/15 rev-list: use bitmap filters for traversalJeff King, Feb 14, 2020
  66. 12/15 bitmap: add bitmap_unset() functionJeff King, Feb 14, 2020
  67. 15/15 pack-objects: support filters with bitmapsJeff King, Feb 14, 2020
  68. 14/15 pack-bitmap: implement BLOB_LIMIT filteringJeff King, Feb 14, 2020
  69. 13/15 pack-bitmap: implement BLOB_NONE filteringJeff King, Feb 14, 2020
  70. Derrick StoleeFeb 18, 2020
  71. Derrick StoleeFeb 18, 2020
  72. Jeff KingFeb 18, 2020
  73. Jeff KingFeb 18, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.