From patchwork Mon May 4 23:12:27 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11527755 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id D9A1514B4 for ; Mon, 4 May 2020 23:12:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id C0A89206EB for ; Mon, 4 May 2020 23:12:31 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="RDpDieQC" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728338AbgEDXMb (ORCPT ); Mon, 4 May 2020 19:12:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49346 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728258AbgEDXMa (ORCPT ); Mon, 4 May 2020 19:12:30 -0400 Received: from mail-pl1-x643.google.com (mail-pl1-x643.google.com [IPv6:2607:f8b0:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 996EFC061A0E for ; Mon, 4 May 2020 16:12:29 -0700 (PDT) Received: by mail-pl1-x643.google.com with SMTP id x10so24424plr.4 for ; Mon, 04 May 2020 16:12:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=lMOBVZeN7SxKVnX5EL34f+UKEgcMo4vQNn6FNQCDqQ0=; b=RDpDieQC3Rz9D0qJ8Z91sZvDs6/gRtAKPr63HCJv49tGlqXGiEAC9C9CUt+90Q/+em zXR4ZC7dM9la+kfdeBox0FYIIvAZAHbuo+tYLdHGEDVfn47yyuZaGnCJm8SE4WhbTCTr 9dYZmyP+j+XTZlJ8WKcMbJGT3l6kaxz77lytwShk4nwxsCGTjJ91u32YhKxfI2GoSsao sOsYG7HZ7bfzygxdv624m7EYQ0xuE2+FkrsdCDEmGFkMGaVBDMjotyQ268zZq8dkcJPi Jsrr0qyabPv19JS+cDCXLamQHxUrMBSf5J3VAFMLWtuhm4Eb5mFwJ4Tm+kvCVOBRakCn nrgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=lMOBVZeN7SxKVnX5EL34f+UKEgcMo4vQNn6FNQCDqQ0=; b=AkzK8ELhNQKFgaYhqgog+VT+ZgsaGjSYSm5O3lT3w/Z+QM1wehYO2mKH4jVF1U5PnM t2wCLqazDqqSgIoaUw3C3052QvnjiLgKqfqSrOSLwiFS/PGG8NP+tPZ1BHgNfBEVaSAr j697jibsNtETQJAd1T8O2aM0UVqPkkT5Lbm/xsuShmStH63zOn+NnpmHXuEyKilRYnAv a0OQk+uLpbATy194L4aH5TbOgSy2BTe+trY2fjteaH/VJKzCSarT1WRArKb7d+KwUL0m SnquVK/rX2N8yU3Wzo/Sl34ELhTVe8Y1MlljvldsJXlLfp9MP4cUJwiSpcAx5ZtVHC7B JVGg== X-Gm-Message-State: AGi0PubbXhQTJvMNBWIlkeehTiDM918RSCULYn8mscnbv41mN3TIjLsJ 3x1mCnkvNPp462cpl2NA+S7JxzURKNPamQ== X-Google-Smtp-Source: APiQypK07hQ4A85MmZLp2im0+HBe1i4V8EM9GpdEA7CtjbPPFsX2wPK9O90jOXhR5HWcTo1Rj3LrdQ== X-Received: by 2002:a17:902:bd81:: with SMTP id q1mr340443pls.46.1588633948795; Mon, 04 May 2020 16:12:28 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id mj4sm76016pjb.0.2020.05.04.16.12.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 May 2020 16:12:28 -0700 (PDT) Date: Mon, 4 May 2020 17:12:27 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 1/4] list-objects-filter: treat NULL filter_options as "disabled" Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jeff King In most callers, we have an actual list_objects_filter_options struct, and if no filtering is desired its "choice" element will be LOFC_DISABLED. However, some code may have only a pointer to such a struct which may be NULL (because _their_ callers didn't care about filtering, either). Rather than forcing them to handle this explicitly like: if (filter_options) traverse_commit_list_filtered(filter_options, revs, show_commit, show_object, show_data, NULL); else traverse_commit_list(revs, show_commit, show_object, show_data); let's just treat a NULL filter_options the same as LOFC_DISABLED. We only need a small change, since that option struct is converted into a real filter only in the "init" function. Signed-off-by: Jeff King Signed-off-by: Taylor Blau --- list-objects-filter.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/list-objects-filter.c b/list-objects-filter.c index 1e8d4e763d..0a3ef3cab3 100644 --- a/list-objects-filter.c +++ b/list-objects-filter.c @@ -663,6 +663,9 @@ struct filter *list_objects_filter__init( assert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT); + if (!filter_options) + return NULL; + if (filter_options->choice >= LOFC__COUNT) BUG("invalid list-objects filter choice: %d", filter_options->choice); From patchwork Mon May 4 23:12:31 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11527757 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 4BB8B14B4 for ; Mon, 4 May 2020 23:12:36 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3559920735 for ; Mon, 4 May 2020 23:12:36 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="N0zE5VMC" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728344AbgEDXMf (ORCPT ); Mon, 4 May 2020 19:12:35 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49364 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728258AbgEDXMe (ORCPT ); Mon, 4 May 2020 19:12:34 -0400 Received: from mail-pj1-x1042.google.com (mail-pj1-x1042.google.com [IPv6:2607:f8b0:4864:20::1042]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 53F3FC061A0E for ; Mon, 4 May 2020 16:12:34 -0700 (PDT) Received: by mail-pj1-x1042.google.com with SMTP id a5so158142pjh.2 for ; Mon, 04 May 2020 16:12:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=Xwp9MlTM06nhTCGk+Beg6uQkrBO7tHv/m7wbf/1smis=; b=N0zE5VMCaPfrlTv/ZGE1DdGa+8TNFbAFkZVatGuQCKuDQY/6bPCy2C64Qnr4N3Sf2l EWnJYn2HoFNaex9Sw1/2DoL3/piFRnnQvgft/YKqav53hMc2889Y2y+7p+lbM7eUBi4e NsIgbPoZCA0C9Ak4b5RBXsaZG7XSH2gp41f8Tu2kQ6tBGW16XPWQnTxD5+HKwxz++cyr 8dKN/wODcgym3uPB0slC+vBGf1sbUYfj5q28DH36yhAMMrCUNvgvNN6rXX6BGPEyPYZM KPmX8tTWZaeqA7NTXSWhivVNaS+apKvOzdnwTAIqr3htnN5mA24jEyvC+XvxDB1xPXMl NcLw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=Xwp9MlTM06nhTCGk+Beg6uQkrBO7tHv/m7wbf/1smis=; b=RtNaSQschSELqsRqUgWy8ahoocdLsGALsdKWLxuwjFXEDd511/Eq/NOUpGgLc4U7PK F2OL5Jw5vmQqJYuB5pGl4h/HqMY70Le+9I2a+vyMD3OfS+X2AoL7+fHjXx1QHiUFaWE4 2xnKabRgYzWHTnytd1lUHr5uYA1bjUkxlZHcqWdfSJipUJu3enkxRm8n7aMdRqIQf5WK f8qJdwbur9iQ8W4aJuBM8tTmR11QwN8nJjq4BTlvJ2iDdhkxQlX5w9sv9Po/gcSpI3gk q6Zy0Ow31nNunSTlr7V1Q2lFDJ5C1f/hB4+PoBGbY7YH0AkueAyiEzFXIsCSL/a9ogg1 is5A== X-Gm-Message-State: AGi0PuYCIMmasXaXPI7hSiZr3JWTjQDDTD+LC4eujQyw8i0liLtCKeya /XQ+/Ut4mIgsC+vxMF/tJE7C9QRdwtvm1Q== X-Google-Smtp-Source: APiQypLlx8xLA+SFBD6gywgB3if8iTJOXvx2sD+nrOlmz1QJ7/Z0bT2Jvh6fTXjIIbahBppY1o0+wg== X-Received: by 2002:a17:90a:cb09:: with SMTP id z9mr181453pjt.120.1588633953451; Mon, 04 May 2020 16:12:33 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id d12sm166691pfq.36.2020.05.04.16.12.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 May 2020 16:12:32 -0700 (PDT) Date: Mon, 4 May 2020 17:12:31 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 2/4] pack-bitmap.c: make object filtering functions generic Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In 4f3bd5606a (pack-bitmap: implement BLOB_NONE filtering, 2020-02-14), filtering support for bitmaps was added for the 'LOFC_BLOB_NONE' filter. In the future, we would like to add support for filters that behave as if they exclude a certain type of object, for e.g., the tree depth filter with depth 0. To prepare for this, make some of the functions used for filtering more generic, such as 'find_tip_blobs' and 'filter_bitmap_blob_none' so that they can work over arbitrary object types. To that end, create 'find_tip_objects' and 'filter_bitmap_exclude_type', and redefine the aforementioned functions in terms of those. Signed-off-by: Taylor Blau --- pack-bitmap.c | 35 ++++++++++++++++++++++++----------- 1 file changed, 24 insertions(+), 11 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 49a8d10d0c..3693c9e62f 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -715,8 +715,9 @@ static int in_bitmapped_pack(struct bitmap_index *bitmap_git, return 0; } -static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, - struct object_list *tip_objects) +static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + enum object_type type) { struct bitmap *result = bitmap_new(); struct object_list *p; @@ -724,7 +725,7 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, for (p = tip_objects; p; p = p->next) { int pos; - if (p->item->type != OBJ_BLOB) + if (p->item->type != type) continue; pos = bitmap_position(bitmap_git, &p->item->oid); @@ -737,9 +738,10 @@ static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git, return result; } -static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, - struct object_list *tip_objects, - struct bitmap *to_filter) +static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter, + enum object_type type) { struct eindex *eindex = &bitmap_git->ext_index; struct bitmap *tips; @@ -747,18 +749,21 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; + if (type != OBJ_BLOB) + BUG("filter_bitmap_exclude_type: unsupported type '%d'", type); + /* * The non-bitmap version of this filter never removes - * blobs which the other side specifically asked for, + * objects which the other side specifically asked for, * so we must match that behavior. */ - tips = find_tip_blobs(bitmap_git, tip_objects); + tips = find_tip_objects(bitmap_git, tip_objects, type); /* * We can use the blob type-bitmap to work in whole words * for the objects that are actually in the bitmapped packfile. */ - for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB); + for (i = 0, init_type_iterator(&it, bitmap_git, type); i < to_filter->word_alloc && ewah_iterator_next(&mask, &it); i++) { if (i < tips->word_alloc) @@ -773,7 +778,7 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, */ for (i = 0; i < eindex->count; i++) { uint32_t pos = i + bitmap_git->pack->num_objects; - if (eindex->objects[i]->type == OBJ_BLOB && + if (eindex->objects[i]->type == type && bitmap_get(to_filter, pos) && !bitmap_get(tips, pos)) bitmap_unset(to_filter, pos); @@ -782,6 +787,14 @@ static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, bitmap_free(tips); } +static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter) +{ + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_BLOB); +} + static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git, uint32_t pos) { @@ -820,7 +833,7 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; - tips = find_tip_blobs(bitmap_git, tip_objects); + tips = find_tip_objects(bitmap_git, tip_objects, OBJ_BLOB); for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB); i < to_filter->word_alloc && ewah_iterator_next(&mask, &it); From patchwork Mon May 4 23:12:35 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11527759 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 42CC181 for ; Mon, 4 May 2020 23:12:39 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 2C07220735 for ; Mon, 4 May 2020 23:12:39 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="w6MkwYOj" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728347AbgEDXMi (ORCPT ); Mon, 4 May 2020 19:12:38 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49374 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728258AbgEDXMh (ORCPT ); Mon, 4 May 2020 19:12:37 -0400 Received: from mail-pj1-x1042.google.com (mail-pj1-x1042.google.com [IPv6:2607:f8b0:4864:20::1042]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id ADC8AC061A0E for ; Mon, 4 May 2020 16:12:37 -0700 (PDT) Received: by mail-pj1-x1042.google.com with SMTP id t9so163451pjw.0 for ; Mon, 04 May 2020 16:12:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=hKNtToHuliZ3nQ0FY+hFcX6SvM5rjP2ey+YWDHWEPGo=; b=w6MkwYOjpfeqH0f3sDJ7ErNJj0S3NNecYcH9kci9xXfnsUnHVFeNHF7cvSF3gYKkTL 6WvK25J7y6x5C1RQ2icH18zCvFaWfJ34hTHRb5B+fdVveLWTKnyWG7rMt6FTq89uCGdd X6J8Rrm8RqQo3HQZ8UHMm0kjuCqh6TqblZ4XSb2HpZXz0RR8ni/cZ72tSwYsCed3Tr2F AuVn/nUMTuKUCVo8FGI9ArtdcszQXIsZoyzYf8yku3sHtuG9ih3GOiRBEietRDTXnh84 5HCLNtVEYplPUB8+A7nWN37ct/qrxUqNGckgepsPYId/8EdfBNRlEQgv1J2MLked1NZ3 SBgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=hKNtToHuliZ3nQ0FY+hFcX6SvM5rjP2ey+YWDHWEPGo=; b=ufa+ExCgu4eUsKYnfXwycWrcqfmav9KeoM3/jN4tudD6gGQ0QGUtByKvJXgkYODhek GZGYgUsUXzCUIw1WZYtEMAcrjZ/BZsOf3q83eaCTlYFd71duS60h3biakhXT0AZ/ga1E c/zfN1m20vosCeAAvbu+xN1xKE+J5HZ/oO6IKTqQrwQaoDQ786faTtEVU3vaocHWiNcA IB20EG5FhWbjhDfIfqfwOPoGNzsKHjSzjzOBgh0PFjzY7pRVL3QkIhnNMWTfk3m6ZANL GgLvMg8WfBzfOT1QrXnR3M2y57QhH6Mvjhl+EFRaduehhHH4o4g0hk65HZnIrCbkq1zO k7IA== X-Gm-Message-State: AGi0Puam4k0tLy7J54W38OfWNv2IAQ4+3sJEjVpoyHGXrMJkAYbL3EL6 av9GEP/qPWX0UJ2gXosOmxyoEC9oCxnD2w== X-Google-Smtp-Source: APiQypJVHI/j23QQwPKbaXHtf14Rn6eJdg25I8MjH3WrGaYeIE7EPCzVCH4778lSwhhjM1xxpYEtQw== X-Received: by 2002:a17:902:b187:: with SMTP id s7mr349048plr.0.1588633956789; Mon, 04 May 2020 16:12:36 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id b3sm100614pgh.75.2020.05.04.16.12.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 May 2020 16:12:36 -0700 (PDT) Date: Mon, 4 May 2020 17:12:35 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 3/4] pack-bitmap.c: support 'tree:0' filtering Message-ID: <87b21d72bb588f7366d928544aeaf4de68b027a7.1588633810.git.me@ttaylorr.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org In the previous patch, we made it easy to define other filters that exclude all objects of a certain type. Use that in order to implement bitmap-level filtering for the '--filter=tree:' filter when 'n' is equal to 0. The general case is not helped by bitmaps, since for values of 'n > 0', the object filtering machinery requires a full-blown tree traversal in order to determine the depth of a given tree. Caching this is non-obvious, too, since the same tree object can have a different depth depending on the context (e.g., a tree was moved up in the directory hierarchy between two commits). But, the 'n = 0' case can be helped, and this patch does so. Running p5310.11 in this tree and on master with the kernel, we can see that this case is helped substantially: Test master this tree -------------------------------------------------------------------------------- 5310.11: rev-list count with tree:0 10.68(10.39+0.27) 0.06(0.04+0.01) -99.4% Signed-off-by: Taylor Blau --- pack-bitmap.c | 25 ++++++++++++++++++++++++- t/perf/p5310-pack-bitmaps.sh | 5 +++++ t/t6113-rev-list-bitmap-filters.sh | 21 +++++++++++++++++++++ 3 files changed, 50 insertions(+), 1 deletion(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 3693c9e62f..195ee8cad0 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -749,7 +749,7 @@ static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git, eword_t mask; uint32_t i; - if (type != OBJ_BLOB) + if (type != OBJ_BLOB && type != OBJ_TREE) BUG("filter_bitmap_exclude_type: unsupported type '%d'", type); /* @@ -867,6 +867,20 @@ static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git, bitmap_free(tips); } +static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git, + struct object_list *tip_objects, + struct bitmap *to_filter, + unsigned long limit) +{ + if (limit) + BUG("filter_bitmap_tree_depth given non-zero limit"); + + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_TREE); + filter_bitmap_exclude_type(bitmap_git, tip_objects, to_filter, + OBJ_BLOB); +} + static int filter_bitmap(struct bitmap_index *bitmap_git, struct object_list *tip_objects, struct bitmap *to_filter, @@ -890,6 +904,15 @@ static int filter_bitmap(struct bitmap_index *bitmap_git, return 0; } + if (filter->choice == LOFC_TREE_DEPTH && + filter->tree_exclude_depth == 0) { + if (bitmap_git) + filter_bitmap_tree_depth(bitmap_git, tip_objects, + to_filter, + filter->tree_exclude_depth); + return 0; + } + /* filter choice not handled */ return -1; } diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh index 80c53edca7..75ccf9f4e3 100755 --- a/t/perf/p5310-pack-bitmaps.sh +++ b/t/perf/p5310-pack-bitmaps.sh @@ -53,6 +53,11 @@ test_perf 'rev-list count with blob:limit=1k' ' --filter=blob:limit=1k >/dev/null ' +test_perf 'rev-list count with tree:0' ' + git rev-list --use-bitmap-index --count --objects --all \ + --filter=tree:0 >/dev/null +' + test_perf 'simulated partial clone' ' git pack-objects --stdout --all --filter=blob:none /dev/null ' diff --git a/t/t6113-rev-list-bitmap-filters.sh b/t/t6113-rev-list-bitmap-filters.sh index 145603f124..2b551e6fd0 100755 --- a/t/t6113-rev-list-bitmap-filters.sh +++ b/t/t6113-rev-list-bitmap-filters.sh @@ -53,4 +53,25 @@ test_expect_success 'blob:limit filter with specified blob' ' test_bitmap_traversal expect actual ' +test_expect_success 'tree:0 filter' ' + git rev-list --objects --filter=tree:0 HEAD >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:0 HEAD >actual && + test_bitmap_traversal expect actual +' + +test_expect_success 'tree:0 filter with specified blob, tree' ' + git rev-list --objects --filter=tree:0 HEAD HEAD:two.t >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:0 HEAD HEAD:two.t >actual && + test_bitmap_traversal expect actual +' + +test_expect_success 'tree:1 filter' ' + git rev-list --objects --filter=tree:1 HEAD >expect && + git rev-list --use-bitmap-index \ + --objects --filter=tree:1 HEAD >actual && + test_cmp expect actual +' + test_done From patchwork Mon May 4 23:12:38 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Taylor Blau X-Patchwork-Id: 11527761 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id CAE0F14B4 for ; Mon, 4 May 2020 23:12:43 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id AE36B20735 for ; Mon, 4 May 2020 23:12:43 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=ttaylorr-com.20150623.gappssmtp.com header.i=@ttaylorr-com.20150623.gappssmtp.com header.b="HLwsovbS" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728354AbgEDXMn (ORCPT ); Mon, 4 May 2020 19:12:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:49390 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728258AbgEDXMm (ORCPT ); Mon, 4 May 2020 19:12:42 -0400 Received: from mail-pl1-x644.google.com (mail-pl1-x644.google.com [IPv6:2607:f8b0:4864:20::644]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3B2DEC061A0E for ; Mon, 4 May 2020 16:12:41 -0700 (PDT) Received: by mail-pl1-x644.google.com with SMTP id x10so24626plr.4 for ; Mon, 04 May 2020 16:12:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ttaylorr-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to; bh=GuFIyRhAir/AJbB2BjMvSmInv3V9LGmoyOzk7hnIUVo=; b=HLwsovbSnHsVsCwTBqtHu7Knu6Riq2/GEkMz1V4wQlTrUjcIQn5HGFnISzsU5pWQb3 x8ljnQ+BLbTCq4fMBcGCF8xcEjHDhZczfUDhMl0CnWG8MCc5o3f+yposLRhQWUbgelwI 9EtOSsoWgQXuz5PtA+3728cNc3sYtZFh4/3W/aEGQlRG0qrJJyE5d30ggeCkw94F8Hej sCPluBHDZ3rytpQmy9XMUu+IrYVfRxs00JiUW46UACA56ReJTPYF1ESLj0aPx14dyfnS e1chYDFg3TmSXZBASOYU3/2RIXzUV1ZQIgyUqNR8Njgtl1xKTO/1g5WoMse5cniOiHhB rUfg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to; bh=GuFIyRhAir/AJbB2BjMvSmInv3V9LGmoyOzk7hnIUVo=; b=E8BnoCgo+YvCkXgLh/u87fXJID42fLKfOzFwHLbm5L6KSvizUlPFoUh4aclFp3gjob UNdzFXZXfSvhG2GvGp5atXmay6wFQfBSaqLXDrDrwonzhLigGE4HerzK2hdKqjswM+HW ok/TK2xbDV0uAQkTrDX/6COJ3Fmv+BkqhPW6VcyqOUt5D4Oy1buC20SbH0G1TIJQVsxS UbsPQYpLnZn/m5QV2PDoGnHHJaVz9GXs8Xycypk/7Ym+iJrn5kJX5CyqmpHjavYGhrXA xzJKFkFzKTjJ9F22g3DQaMO2ye7+P6ldAEVBB1grKoHrybcNLfKTNxyOXzH2iBpqDMq7 Tmcg== X-Gm-Message-State: AGi0PubG/XdwUvz09zV+XbemED3lIjgRN6Xxwlf6zImQesrqz26FSOI3 Xs3UzP/1GvSW9KN87HPMw0709n65lNcC9g== X-Google-Smtp-Source: APiQypKbWHzfE54GIiA0vzCmm3CRPPvRNAoHaxLq4wR229nlIkSTsHWaCgzMI3q7koluOBoh2wWq7w== X-Received: by 2002:a17:90a:d98e:: with SMTP id d14mr181168pjv.178.1588633960311; Mon, 04 May 2020 16:12:40 -0700 (PDT) Received: from localhost ([8.44.146.30]) by smtp.gmail.com with ESMTPSA id j7sm139835pfi.160.2020.05.04.16.12.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 04 May 2020 16:12:39 -0700 (PDT) Date: Mon, 4 May 2020 17:12:38 -0600 From: Taylor Blau To: git@vger.kernel.org Cc: peff@peff.net, chriscool@tuxfamily.org Subject: [PATCH 4/4] pack-bitmap: pass object filter to fill-in traversal Message-ID: References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Jeff King Sometimes a bitmap traversal still has to walk some commits manually, because those commits aren't included in the bitmap packfile (e.g., due to a push or commit since the last full repack). If we're given an object filter, we don't pass it down to this traversal. It's not necessary for correctness because the bitmap code has its own filters to post-process the bitmap result (which it must, to filter out the objects that _are_ mentioned in the bitmapped packfile). And with blob filters, there was no performance reason to pass along those filters, either. The fill-in traversal could omit them from the result, but it wouldn't save us any time to do so, since we'd still have to walk each tree entry to see if it's a blob or not. But now that we support tree filters, there's opportunity for savings. A tree:depth=0 filter means we can avoid accessing trees entirely, since we know we won't them (or any of the subtrees or blobs they point to). The new test in p5310 shows this off (the "partial bitmap" state is one where HEAD~100 and its ancestors are all in a bitmapped pack, but HEAD~100..HEAD are not). Here are the results (run against linux.git): Test HEAD^ HEAD ------------------------------------------------------------------------------------------------- [...] 5310.16: rev-list with tree filter (partial bitmap) 0.19(0.17+0.02) 0.03(0.02+0.01) -84.2% The absolute number of savings isn't _huge_, but keep in mind that we only omitted 100 first-parent links (in the version of linux.git here, that's 894 actual commits). In a more pathological case, we might have a much larger proportion of non-bitmapped commits. I didn't bother creating such a case in the perf script because the setup is expensive, and this is plenty to show the savings as a percentage. Signed-off-by: Jeff King Signed-off-by: Taylor Blau --- pack-bitmap.c | 14 +++++++++----- t/perf/p5310-pack-bitmaps.sh | 5 +++++ 2 files changed, 14 insertions(+), 5 deletions(-) diff --git a/pack-bitmap.c b/pack-bitmap.c index 195ee8cad0..4077e731e8 100644 --- a/pack-bitmap.c +++ b/pack-bitmap.c @@ -506,7 +506,8 @@ static int should_include(struct commit *commit, void *_data) static struct bitmap *find_objects(struct bitmap_index *bitmap_git, struct rev_info *revs, struct object_list *roots, - struct bitmap *seen) + struct bitmap *seen, + struct list_objects_filter_options *filter) { struct bitmap *base = NULL; int needs_walk = 0; @@ -599,8 +600,9 @@ static struct bitmap *find_objects(struct bitmap_index *bitmap_git, show_data.bitmap_git = bitmap_git; show_data.base = base; - traverse_commit_list(revs, show_commit, show_object, - &show_data); + traverse_commit_list_filtered(filter, revs, + show_commit, show_object, + &show_data, NULL); } return base; @@ -999,7 +1001,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, if (haves) { revs->ignore_missing_links = 1; - haves_bitmap = find_objects(bitmap_git, revs, haves, NULL); + haves_bitmap = find_objects(bitmap_git, revs, haves, NULL, + filter); reset_revision_walk(); revs->ignore_missing_links = 0; @@ -1007,7 +1010,8 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs, BUG("failed to perform bitmap walk"); } - wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap); + wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap, + filter); if (!wants_bitmap) BUG("failed to perform bitmap walk"); diff --git a/t/perf/p5310-pack-bitmaps.sh b/t/perf/p5310-pack-bitmaps.sh index 75ccf9f4e3..b3e725f031 100755 --- a/t/perf/p5310-pack-bitmaps.sh +++ b/t/perf/p5310-pack-bitmaps.sh @@ -91,4 +91,9 @@ test_perf 'pack to file (partial bitmap)' ' git pack-objects --use-bitmap-index --all pack2b /dev/null ' +test_perf 'rev-list with tree filter (partial bitmap)' ' + git rev-list --use-bitmap-index --count --objects --all \ + --filter=tree:0 >/dev/null +' + test_done