From patchwork Thu Jan 7 16:32:02 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004419 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 250FBC433E0 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id D9EE0233FC for ; Thu, 7 Jan 2021 16:33:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728142AbhAGQc4 (ORCPT ); Thu, 7 Jan 2021 11:32:56 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47258 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726468AbhAGQc4 (ORCPT ); Thu, 7 Jan 2021 11:32:56 -0500 Received: from mail-wr1-x430.google.com (mail-wr1-x430.google.com [IPv6:2a00:1450:4864:20::430]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CEE47C0612F5 for ; Thu, 7 Jan 2021 08:32:15 -0800 (PST) Received: by mail-wr1-x430.google.com with SMTP id y17so6219391wrr.10 for ; Thu, 07 Jan 2021 08:32:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=Dkys2TZsvFsYLc4Nzw+wTJ/OAwTXIQdwI+QSCleLVFI=; b=UZY8mM8r/vYJvIlQl61Wo9xVpINe7M5uosebvOlbbsTpoBPKw2DOeNaDnQFgizrkYr sr4eJbAcm9HgKG6c0eaTH3kXEfcnELoK5WV90W3e4agXKnvn73VVJ0SphuDEeZmT4t/f scwQrDZHkoaT2MJICXKEQw+0eSa+1PJ2RguGS8zBt8VSKgNMmfnuUsY2TJ+kkncQoeoN itCrm8vq8L6gLXrZjyqDX8AALDjlkqx1oNr9MszGbIcehRSWhUXNzh/ttS6uoCZOnkxS xCie63w64emwXGyP8DsAO0zOKPCZZxg7G1o1JjoT4NxomOkHZ34F6D1IGPFwf4u/q7R8 SoAg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=Dkys2TZsvFsYLc4Nzw+wTJ/OAwTXIQdwI+QSCleLVFI=; b=Pi/X0NS1xZXqd3Cm2yrnyIJ82o8WJyNBPfx3KGNjT8ZSpqs7Q4RmNEe6TPo/hUGMr3 CwlXl0vcdu8GRzqZtC/qAJ4ZP4VyLSnNYV8Cs7MLz8LDPjjpG+RDkYy8Ct9VpBfY0acA dg8qEj8SnvMq2KAg11nc6EZORwkEhv8UdB6MsOwaUv5HAxqYM+fAeYPmFXJBcq6n3xgt Qq6fICyyldFdXuVUBtHmg5Rq3v/7+w/hZNmg5WYw5wwg05hZN0rPbtSw4w8nZA0ZOjCP WTsEtyYK/9HJkqzjpShFnyXYlo8DL3YjNbqk9+Ww0XIsWhHdfL4zmLQ/6bhRikKbaRQj hwkQ== X-Gm-Message-State: AOAM532FAiOtCKP3KUKwLk8cTH1iTcJQ80LTYglGuoJuBNTVORKWctbR nChgDM2U+t/LceUmk3rLPt+1ZxAytjg= X-Google-Smtp-Source: ABdhPJwY6GIr98pgaio6g7WsZvlorfnVuX71zMUCBAahLn5vdCdZ7dhl78cqhlOjZ7/YGKCt7C4UqQ== X-Received: by 2002:adf:f605:: with SMTP id t5mr9564439wrp.39.1610037134253; Thu, 07 Jan 2021 08:32:14 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id s63sm9493806wms.18.2021.01.07.08.32.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:13 -0800 (PST) Message-Id: <0e500c86f397987c4d03beac52b1e91f683e4d11.1610037131.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:02 +0000 Subject: [PATCH v3 01/10] tree-walk: report recursion counts Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The traverse_trees() method recursively walks through trees, but also prunes the tree-walk based on a callback. Some callers, such as unpack_trees(), are quite complicated and can have wildly different performance between two different commands. Create constants that count these values and then report the results at the end of a process. These counts are cumulative across multiple "root" instances of traverse_trees(), but they provide reproducible values for demonstrating improvements to the pruning algorithm when possible. This change is modeled after a similar statistics reporting in 42e50e78 (revision.c: add trace2 stats around Bloom filter usage, 2020-04-06). Signed-off-by: Derrick Stolee --- tree-walk.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) diff --git a/tree-walk.c b/tree-walk.c index 0160294712b..2d6226d5f18 100644 --- a/tree-walk.c +++ b/tree-walk.c @@ -4,6 +4,7 @@ #include "object-store.h" #include "tree.h" #include "pathspec.h" +#include "json-writer.h" static const char *get_mode(const char *str, unsigned int *modep) { @@ -167,6 +168,25 @@ int tree_entry_gently(struct tree_desc *desc, struct name_entry *entry) return 1; } +static int traverse_trees_atexit_registered; +static int traverse_trees_count; +static int traverse_trees_cur_depth; +static int traverse_trees_max_depth; + +static void trace2_traverse_trees_statistics_atexit(void) +{ + struct json_writer jw = JSON_WRITER_INIT; + + jw_object_begin(&jw, 0); + jw_object_intmax(&jw, "traverse_trees_count", traverse_trees_count); + jw_object_intmax(&jw, "traverse_trees_max_depth", traverse_trees_max_depth); + jw_end(&jw); + + trace2_data_json("traverse_trees", the_repository, "statistics", &jw); + + jw_release(&jw); +} + void setup_traverse_info(struct traverse_info *info, const char *base) { size_t pathlen = strlen(base); @@ -180,6 +200,11 @@ void setup_traverse_info(struct traverse_info *info, const char *base) info->namelen = pathlen; if (pathlen) info->prev = &dummy; + + if (trace2_is_enabled() && !traverse_trees_atexit_registered) { + atexit(trace2_traverse_trees_statistics_atexit); + traverse_trees_atexit_registered = 1; + } } char *make_traverse_path(char *path, size_t pathlen, @@ -416,6 +441,12 @@ int traverse_trees(struct index_state *istate, int interesting = 1; char *traverse_path; + traverse_trees_count++; + traverse_trees_cur_depth++; + + if (traverse_trees_cur_depth > traverse_trees_max_depth) + traverse_trees_max_depth = traverse_trees_cur_depth; + if (n >= ARRAY_SIZE(entry)) BUG("traverse_trees() called with too many trees (%d)", n); @@ -515,6 +546,8 @@ int traverse_trees(struct index_state *istate, free(traverse_path); info->traverse_path = NULL; strbuf_release(&base); + + traverse_trees_cur_depth--; return error; } From patchwork Thu Jan 7 16:32:03 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004423 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 33B9BC433E6 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 084ED23432 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728381AbhAGQc6 (ORCPT ); Thu, 7 Jan 2021 11:32:58 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47262 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726468AbhAGQc5 (ORCPT ); Thu, 7 Jan 2021 11:32:57 -0500 Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9E064C0612F6 for ; Thu, 7 Jan 2021 08:32:16 -0800 (PST) Received: by mail-wr1-x42f.google.com with SMTP id r3so6263892wrt.2 for ; Thu, 07 Jan 2021 08:32:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=TlE4Wa/PmXo18jG1onlTnDHaohvuR3hpK+GpRAAFDa4=; b=WkY2k0UQRRJs6TmsNu8Zd/gED+yVCk5hHzaw8jT0QZsPzxH5mAbYW/MiGxQV/UZ2H7 GTlGVgA8tc0bVZpfzDWWdmOvyp4oTpY6eU26ycZlJK5Pkkd3fliCX9nmA2XMLO9Rfaue 76xEyU9+XOP6KAMehbaueU+UBIjZkiuONOunKAv7p8lT9NZmrvbx6RCFRQYXAAE3Zhbw MLmx2imhJILiCOmyCbvaBqOvejD+T2LN3FY1IAbY+6EQSO3sMQ3MaXRDYL1TWvy6NDbe yKp0VT0xBfoHBdrew2ugT4uKMzfTGAhltzwLKt9SvcooH7vaNLCLD0JCAf6KXOEcsE3H M4eg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=TlE4Wa/PmXo18jG1onlTnDHaohvuR3hpK+GpRAAFDa4=; b=b2rEL9uix20JzPBVqTRkGdzqp6wVI5lVhMP2sk/tSCP1CoMw91XJq7bV4GOaHbR13z sl9Qa6/HbtyQ78AIr1TngUH8ByqGEB9T/wIIJb4ySISJcptWEf/OJ6FasAh9XFM1uYDZ 17Ls/OIdo6aKG3ThLHVcHjOiR0oUEh/hJvLm5wfqZKZE430Mtl8EkDOrxeF5HXxpWNCk QYcnxe+3G5Bk8vyX/+74DwjxUrzjm+aKBXswtRB/SAoLMfTFLHfB3pgzvtMQjQ4tLt90 R3dyNTk1KKiy+zN4iiTCDVTpeagr8BfVWQYGV315uwenWtz0U2YbVOzGTqB+ypCw3qUj ddKQ== X-Gm-Message-State: AOAM533DnEQy0Kx83XwY9XIBYg5sCcV0gQehlyAe6vvozo2uMnt4Ox35 AhSskghjYw+Ug2cbkr39lRfIXpPdJiE= X-Google-Smtp-Source: ABdhPJxRVbGmO7rwMlpymdQNARXGdmGc7yrp43QatYd72GEG+UxyMtcyJf1I0knN6JEWBb2ocvvvJA== X-Received: by 2002:adf:c6c4:: with SMTP id c4mr9947196wrh.348.1610037135215; Thu, 07 Jan 2021 08:32:15 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h16sm8297390wmb.41.2021.01.07.08.32.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:14 -0800 (PST) Message-Id: <4157b91acf8009ef2136c0856b6b61833d82873e.1610037131.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:03 +0000 Subject: [PATCH v3 02/10] unpack-trees: add trace2 regions Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The unpack_trees() method is quite complicated and its performance can change dramatically depending on how it is used. We already have some performance tracing regions, but they have not been updated to the trace2 API. Do so now. We already have trace2 regions in unpack_trees.c:clear_ce_flags(), which uses a linear scan through the index without recursing into trees. Signed-off-by: Derrick Stolee --- unpack-trees.c | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/unpack-trees.c b/unpack-trees.c index 323280dd48b..af6e9b9c2fd 100644 --- a/unpack-trees.c +++ b/unpack-trees.c @@ -1580,6 +1580,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options die("unpack_trees takes at most %d trees", MAX_UNPACK_TREES); trace_performance_enter(); + trace2_region_enter("unpack_trees", "unpack_trees", the_repository); + if (!core_apply_sparse_checkout || !o->update) o->skip_sparse_checkout = 1; if (!o->skip_sparse_checkout && !o->pl) { @@ -1653,7 +1655,9 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options } trace_performance_enter(); + trace2_region_enter("unpack_trees", "traverse_trees", the_repository); ret = traverse_trees(o->src_index, len, t, &info); + trace2_region_leave("unpack_trees", "traverse_trees", the_repository); trace_performance_leave("traverse_trees"); if (ret < 0) goto return_failed; @@ -1741,6 +1745,7 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options done: if (free_pattern_list) clear_pattern_list(&pl); + trace2_region_leave("unpack_trees", "unpack_trees", the_repository); trace_performance_leave("unpack_trees"); return ret; From patchwork Thu Jan 7 16:32:04 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004425 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4B5BBC433E9 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1EF21233F6 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728576AbhAGQc7 (ORCPT ); Thu, 7 Jan 2021 11:32:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47264 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728312AbhAGQc6 (ORCPT ); Thu, 7 Jan 2021 11:32:58 -0500 Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7EB68C0612F8 for ; Thu, 7 Jan 2021 08:32:17 -0800 (PST) Received: by mail-wm1-x330.google.com with SMTP id 190so5712131wmz.0 for ; Thu, 07 Jan 2021 08:32:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=Beof6wirizOKpfsWwTbU2ekekdWsETRnVpYiQCmgFkc=; b=SFHm909zzvxfwO1WbegXeHndk/NjIHzlIKWHLVpPoVZgoyWHL6tlVMugICa1hL0pe5 N5kerfhO2QdtqRYyLN2txF95Vxha99tLRn+sVq1y11VSEaPgb9o6pLMiwTAEOszCxem4 8R4OHUM9G7UP2s+Lyj7/ZjdSQI9aAySm/8pirc8qx36lSXL7+hbFizH3CPXJlC26P5MK A89tQQm3igm9/tKYdQzNy/8Y8kLt0cuBNG0TuI6Eef05oPKF8PytPzkkjJyzEPGt9UM0 hvfrRAKYpz/pO7BCgL4DObTu7UewW+2KOkDWuuS624kiIZ9qhwSuOKAYLmZaLvMu/Uvu mg/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=Beof6wirizOKpfsWwTbU2ekekdWsETRnVpYiQCmgFkc=; b=q2EXk1i1ee8Nn1j959uDEtt75U74COaw9XCSA24Ks9sjGyK2X6l1hGGZ/9WX6WCvRD 5/5Sa5N8RLnVpcFbvdm0QPNeoGCMWNH1IKA1AgDTaeST1ncqeDCXxTK4tKSgL++e1xJn ZR1qkm8h/0IVBe97L2PyIlX8aowmp9H4t+iKFVmeYMnUimhPQYaz546hY/20m8uAIwkE syMBXry+2z4XQPKUh9PW0SzbBZEFI8przGP65N/WXVBQmhyjt1rhAZkEI2wTTgbtrs3d dl54KSiGWFSsW5SAF3uN6TEMlsIq6JhgtwER9JqmbgZd5G+inrMqNs7BOSfRJh4QbWiW GiWA== X-Gm-Message-State: AOAM532Fi6j8oMm6/SRFSW1w6xAJf47oIUmf88xpCYiSVHtLvVIMw2o5 cEJVEDit+PMp/tuMRVjDiXMAmOxCPns= X-Google-Smtp-Source: ABdhPJy2CO1FDuFpfl66EKAUtkoT5kK1HLVzzSg1E6lHHP5Vm8t2TacUVfsmY4q1AsFJtp+se1MD0A== X-Received: by 2002:a1c:17:: with SMTP id 23mr8499459wma.35.1610037136130; Thu, 07 Jan 2021 08:32:16 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t1sm9846209wro.27.2021.01.07.08.32.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:15 -0800 (PST) Message-Id: <8959d57abddd620f4b597e4c43c5d2545c666e97.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:04 +0000 Subject: [PATCH v3 03/10] cache-tree: use trace2 in cache_tree_update() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee This matches a trace_performance_enter()/trace_performance_leave() pair added by 0d1ed59 (unpack-trees: add performance tracing, 2018-08-18). Signed-off-by: Derrick Stolee --- cache-tree.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/cache-tree.c b/cache-tree.c index a537a806c16..9efb6748662 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -442,7 +442,9 @@ int cache_tree_update(struct index_state *istate, int flags) if (i) return i; trace_performance_enter(); + trace2_region_enter("cache_tree", "update", the_repository); i = update_one(it, cache, entries, "", 0, &skip, flags); + trace2_region_leave("cache_tree", "update", the_repository); trace_performance_leave("cache_tree_update"); if (i < 0) return i; From patchwork Thu Jan 7 16:32:05 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004427 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5DBDFC43381 for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 34820233FC for ; Thu, 7 Jan 2021 16:33:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728606AbhAGQc7 (ORCPT ); Thu, 7 Jan 2021 11:32:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47270 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728571AbhAGQc7 (ORCPT ); Thu, 7 Jan 2021 11:32:59 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A29F5C0612F9 for ; Thu, 7 Jan 2021 08:32:18 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id y23so6081623wmi.1 for ; Thu, 07 Jan 2021 08:32:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=F5mr/fFvRdXYRRCHVaEtFFWbeGwbu/OPMWpaJOKG0T0=; b=JD2s5A4wYI9V+u/X2B/z+iP66px6YaegPv6JrpqoVNY9i02PfjcUaU20VrlnT7akme PU4LjyqRNcBvEXq6bFVq2x0GN165+ano0eEMynTqlfY4Eh7KaY0fSvEP1k7TJMpq51UX DlbJ+qKfv3xRF54mu9gujVoqUN2ptKvEqYRNJOkv0keBVjQa2+JbrtePhjmOROxbdGk2 8xqcAJCWEfxKX+DDuFasFcr+Jfac+ThRqo937mBtv+779n9t+Rl7fUQchzzEInKlMPzJ VQ5g1Ad/cptovBIVZQ+XcLcwkPLDXaf3esUzYhEgzNokmKgwa95EJGzJv3c0TdAua2He GVLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=F5mr/fFvRdXYRRCHVaEtFFWbeGwbu/OPMWpaJOKG0T0=; b=IXvUthSR2BCSVXfTD2pWsHB5qdvhccJlNM2i0xfB/vLb96DFBBgtADO7XMD1bz7L6E xduZEtzJM7oYyYUhNu/RVcEa+lV13gF/vl3AbSrc0qrALRQ3JCs0elJ9DI8D9N6ma92N lecsEybAtrBd08KQFvnspnz46IU2S+84ptWy96kQAYq4vNNRQ+oQ50zgJ+hTt7JCjHLF +sH5Kd+9O6L+xUQY5+LXZ+QKN00XuySjlUxJkPq17BPDNMrVYZnTScvmAgPp0ehPFvW4 dFsStr+ElQZLGaXZ2n7CrNKA5ZwgU3Mh3e9owvEGfHXSS8p7UErlhe334KJqaFkmH+tz F7vA== X-Gm-Message-State: AOAM532TF6UpYj2+FgeQHFFoTQryFh4TMh7++Y8tvuXXwHIJ+f1Vc9h5 pHxfmPtk3Qp/kfaSrrXH90BN72eRbGI= X-Google-Smtp-Source: ABdhPJy1DN/25RzGuRfnnfyLx5fGgPmlajqZkch6OhFx6EIrZWJJZRM5qr19u6pkAnEO/ou96nxGHw== X-Received: by 2002:a1c:de41:: with SMTP id v62mr8856493wmg.135.1610037137257; Thu, 07 Jan 2021 08:32:17 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id c81sm8710592wmd.6.2021.01.07.08.32.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:16 -0800 (PST) Message-Id: <1d8a797ee2650e8c815281b0c672301c7f24a724.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:05 +0000 Subject: [PATCH v3 04/10] cache-tree: trace regions for I/O Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee As we write or read the cached tree index extension, it can be good to isolate how much of the file I/O time is spent constructing this in-memory tree from the existing index or writing it out again to the new index file. Use trace2 regions to indicate that we are spending time on this operation. Signed-off-by: Derrick Stolee --- cache-tree.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) diff --git a/cache-tree.c b/cache-tree.c index 9efb6748662..45fb57b17f3 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -494,7 +494,9 @@ static void write_one(struct strbuf *buffer, struct cache_tree *it, void cache_tree_write(struct strbuf *sb, struct cache_tree *root) { + trace2_region_enter("cache_tree", "write", the_repository); write_one(sb, root, "", 0); + trace2_region_leave("cache_tree", "write", the_repository); } static struct cache_tree *read_one(const char **buffer, unsigned long *size_p) @@ -583,9 +585,16 @@ static struct cache_tree *read_one(const char **buffer, unsigned long *size_p) struct cache_tree *cache_tree_read(const char *buffer, unsigned long size) { + struct cache_tree *result; + if (buffer[0]) return NULL; /* not the whole tree */ - return read_one(&buffer, &size); + + trace2_region_enter("cache_tree", "read", the_repository); + result = read_one(&buffer, &size); + trace2_region_leave("cache_tree", "read", the_repository); + + return result; } static struct cache_tree *cache_tree_find(struct cache_tree *it, const char *path) From patchwork Thu Jan 7 16:32:06 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004437 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id BBCF7C4332B for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id A352D233FC for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728644AbhAGQdg (ORCPT ); Thu, 7 Jan 2021 11:33:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47362 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1727753AbhAGQdf (ORCPT ); Thu, 7 Jan 2021 11:33:35 -0500 Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 79B9DC0612FA for ; Thu, 7 Jan 2021 08:32:19 -0800 (PST) Received: by mail-wm1-x333.google.com with SMTP id 190so5712204wmz.0 for ; Thu, 07 Jan 2021 08:32:19 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=1cXbZJPHh6PbIf9iSugyF98nzI72FppH2Gn56ddappw=; b=IarpQOBlNs+ZA/I8l2LL5wnq8KdrM5bbgmbZQRRNLRCqdCXhTwlUOC4zeMjes7hRGG dA7M0SGhlnpBjNKjkgteUfQOJ9ZmHSIOuhwMEBDkQm3trsMDyad38cMYV65KyXGY6N22 FaON3nDAovbPtXu2MRJB/r4CQ3TyBvOifIaC55QM1gOVmcd0fj3tjG3M3+y2qlUYxW7A +prxs1cbSw6lvXZlLwqPcr+x8tdbrtbkE3rj9QSwFOE3vrTfEKC3GghCgPXcPCfmoR7r XG+kYYskhxaMqNFtv+jVlZuB6LmZ5TR98zUAvNO8BkxwHh2Al5GBZbFCSAkZGOtAseGT 9n6w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=1cXbZJPHh6PbIf9iSugyF98nzI72FppH2Gn56ddappw=; b=HQlmsnAsEP98MklEHfqvyOHhPaxAIx/q/0jelae/DDJGUoYGCh3joI1hL8M+Dbcjrd wdkUHIwQdrNcBWpEob0bDtv6fwnwyWv0QU2MKym1sMjQP3DR11DZbrdnn/NCFn+8uEs2 xts7naLQWPbOxFBWoc1Kudw5F/sYAsnmERvy7Eld/iC5stlLFlCGTv2+W1X6dY96E7TE 1uL+ANvYAjNTjEf+VJq7QD1JOE3f1iY4T70UotdGqkE2QCJW6oEb4Yw9PUJXgr7amE3/ /X9xbTKt/J/U/kcF7u4tsz31tzM/k9+sQgTtjCB2iuI0NCaxsksMVq/sik8tJPOUZUPe Y2aw== X-Gm-Message-State: AOAM532pSxga0CnObE0COra+2fKbTyKUHcwwxTbIHiZ+feB3/wAAtHWO E9Kg+CpKd2z0tgjqfFeq/QoNcUMKYA4= X-Google-Smtp-Source: ABdhPJxgywc3OJbsJkkbDU96CJ0xc06K4sM5MaxiGFk8ZTAyvbUbnkR69CIPwT+rnUrL4KSFMV4hWg== X-Received: by 2002:a1c:a706:: with SMTP id q6mr8729482wme.7.1610037138112; Thu, 07 Jan 2021 08:32:18 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h16sm8630574wrq.29.2021.01.07.08.32.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:17 -0800 (PST) Message-Id: <2b2e70bb77c8dafbf2cfedd9e68f834f02deb4a2.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:06 +0000 Subject: [PATCH v3 05/10] cache-tree: trace regions for prime_cache_tree Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee Commands such as "git reset --hard" rebuild the in-memory representation of the cached tree index extension by parsing tree objects starting at a known root tree. The performance of this operation can vary widely depending on the width and depth of the repository's working directory structure. Measure the time in this operation using trace2 regions in prime_cache_tree(). Signed-off-by: Derrick Stolee --- cache-tree.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/cache-tree.c b/cache-tree.c index 45fb57b17f3..7da59b2aa07 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -744,10 +744,13 @@ void prime_cache_tree(struct repository *r, struct index_state *istate, struct tree *tree) { + trace2_region_enter("cache-tree", "prime_cache_tree", the_repository); cache_tree_free(&istate->cache_tree); istate->cache_tree = cache_tree(); + prime_cache_tree_rec(r, istate->cache_tree, tree); istate->cache_changed |= CACHE_TREE_CHANGED; + trace2_region_leave("cache-tree", "prime_cache_tree", the_repository); } /* From patchwork Thu Jan 7 16:32:07 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004429 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 57EBDC433E0 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 29CB0233FC for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728734AbhAGQdg (ORCPT ); Thu, 7 Jan 2021 11:33:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47364 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728201AbhAGQdf (ORCPT ); Thu, 7 Jan 2021 11:33:35 -0500 Received: from mail-wm1-x334.google.com (mail-wm1-x334.google.com [IPv6:2a00:1450:4864:20::334]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 6C47DC0612FB for ; Thu, 7 Jan 2021 08:32:20 -0800 (PST) Received: by mail-wm1-x334.google.com with SMTP id v14so5702391wml.1 for ; Thu, 07 Jan 2021 08:32:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=MFoyZvSH404fKlOXAhW3wSlHVKAaWMcAXJn9MXCrdIg=; b=Dwduus8GiyCI1JmWc+ElHKAlBkj4UjYVYd7aN6unQvN/tYA+8UEec7TtXJQcDdw/bP qzyPSO6aZLg2oPSl5QYXu3PHSXW7LQseuCafOfpOaOwuKO+XZAithK26A8d+9wGmowNr KjuzWF9Xb6LkVC96GI5/43l8wErpaCNUWH4xK+gdIWcaiRC5s221H+wVrdwjqw4+Hw8g PHuH7sQOijhq3FVv+RT50ZvwIK/9HRHBSp1/mYn86cMY57ONAhhrc6mPjrS5f/BSfkGS JSTOnGGqFecf7IA0d/qwv7PlXRS6Sc589/r+LJ99J1kcUx+OhDjqPFBqPCPLwppqJmPo nt3Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=MFoyZvSH404fKlOXAhW3wSlHVKAaWMcAXJn9MXCrdIg=; b=XVzJCqaS7VaCtjcrlz0klxJXN4CgUqM2k8tSl97d49SllYS4DNQRQbXuf3t97FqryN 0paVEbvNJ8Ps2vWx778q5vgckZlPaxp11rTlKwIe7Emb9qMp6z9S0vwtoCJvfTN5oBcL us/1MR1cWnZizwpCxEnvon4hOFApwtp+gCH4igghAvvc+Qavxjb7DmN3LUUSDD5J1fUY uR1jB+vD4hGE6PFVAFqBuPDdSZ88qf2bOZSR+WapM1cVnV/CgDNohQWwPgpKHsu/vT2Z WLNLRG2/VOjd80wrvTYfeYjc1jF/A7Ofa8XvrrnqwzF6yJ4Sx8wakuu1+2M3cYoxodsu djQQ== X-Gm-Message-State: AOAM531TK6coyn3Deu1pa8xUFb0ZRI20+KwiZ0FGAeRLl/YeIlODit6v ngC2LVtm5CO4V59Tq1AljN228HiJaU0= X-Google-Smtp-Source: ABdhPJxYZfHlbl++4iFn50OpsSq3jP578/RIQQNJM30BPLmw6Fjrj3Lt7YnKyEgJ6QxH9Jrnf9nVSQ== X-Received: by 2002:a7b:c959:: with SMTP id i25mr8811399wml.74.1610037139003; Thu, 07 Jan 2021 08:32:19 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w8sm8668139wrl.91.2021.01.07.08.32.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:18 -0800 (PST) Message-Id: <2d7b18c2e0b351e98e687126fc067dc4fcd7a498.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:07 +0000 Subject: [PATCH v3 06/10] index-format: use 'cache tree' over 'cached tree' Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The index has a "cache tree" extension. This corresponds to a significant API implemented in cache-tree.[ch]. However, there are a few places that refer to this erroneously as "cached tree". These are rare, but notably the index-format.txt file itself makes this error. The only other reference is in t7104-reset-hard.sh. Reported-by: Junio C Hamano Signed-off-by: Derrick Stolee --- Documentation/technical/index-format.txt | 6 +++--- t/t7104-reset-hard.sh | 2 +- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index 69edf46c031..c71314731ec 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -26,7 +26,7 @@ Git index format Extensions are identified by signature. Optional extensions can be ignored if Git does not understand them. - Git currently supports cached tree and resolve undo extensions. + Git currently supports cache tree and resolve undo extensions. 4-byte extension signature. If the first byte is 'A'..'Z' the extension is optional and can be ignored. @@ -136,9 +136,9 @@ Git index format == Extensions -=== Cached tree +=== Cache tree - Cached tree extension contains pre-computed hashes for trees that can + Cache tree extension contains pre-computed hashes for trees that can be derived from the index. It helps speed up tree object generation from index for a new commit. diff --git a/t/t7104-reset-hard.sh b/t/t7104-reset-hard.sh index 16faa078137..7948ec392b3 100755 --- a/t/t7104-reset-hard.sh +++ b/t/t7104-reset-hard.sh @@ -33,7 +33,7 @@ test_expect_success 'reset --hard should restore unmerged ones' ' ' -test_expect_success 'reset --hard did not corrupt index or cached-tree' ' +test_expect_success 'reset --hard did not corrupt index or cache-tree' ' T=$(git write-tree) && rm -f .git/index && From patchwork Thu Jan 7 16:32:08 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004439 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 86036C433DB for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 56BA023434 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728763AbhAGQdh (ORCPT ); Thu, 7 Jan 2021 11:33:37 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47370 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728649AbhAGQdg (ORCPT ); Thu, 7 Jan 2021 11:33:36 -0500 Received: from mail-wr1-x42f.google.com (mail-wr1-x42f.google.com [IPv6:2a00:1450:4864:20::42f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 60F46C0612FC for ; Thu, 7 Jan 2021 08:32:21 -0800 (PST) Received: by mail-wr1-x42f.google.com with SMTP id w5so6210157wrm.11 for ; Thu, 07 Jan 2021 08:32:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=Q090u5Fq3VEjw4SQHi6ensgBXQAOMjkEb5mKuxxqt3k=; b=dAYhAyAfOeDLx1mJBLhBOpM9xGT3gzbDH5XVTakDr0RpQF2zbnEu48+ZmskJxDu+Lg JhVCL83/frg0iOLTy3pSNZzX+zY4CtUu295EPe33KrZBbB77uSd4EdIyqQQ5gb72XEE/ CehMml19f5Ylb9asR5A1uu3ZOfV+GXm2JSx9JNkkqBIO9ii0aDO5S7XrdilHlP3lFRzZ ge6/JQC5LU2JrZOUT5CKNtOKjSCUxkCkH+j9txEE+iRakLO1HFkn24zUPIC1Eglw4hoU LGi99lIVWVz4q082f+Nm9OxQrSZFLUYFp412ka+Sk+livtprhOHpDHeMcO0yk4Ny9fDq 4dSw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=Q090u5Fq3VEjw4SQHi6ensgBXQAOMjkEb5mKuxxqt3k=; b=eLG5OABYlz39vWhssmZ+3/CCV6JzYX1DmKssijOj2DDLKXfUGV0h1fLqMb0qKZZY/X 5QbOMCIz/01q8qsDVhSvq5fb9l2nSYynwOoeaQ0YNHurOD4IyABR9K8D+JrPubAzghDI oyF9thK/2J4GF3XVPU0p4NOG/splUyUVI600illTwaKu8/28T5r+zHK2PGaRpM/Cb8JP wQsm4UUcRWs3jMWHkEJrjMht3cumXqF6XRzABdooj9rFAYl33vvNrajfc6ZAktMSqLR6 Y+NgQ4vzMOAQ9DtIaTPPApoV3azMCpWaZ3QD6zZ0GkV92vysPwBWxeWvHLrk32Ox4tkw 4yNg== X-Gm-Message-State: AOAM531YEcqhvJqmboyS9gPHpMSPm0G4aSo1MixxrYc3p9ZJDzBdL/nJ FmKp/7ABfWNhe5QV9BOAB1nL8E7HcCQ= X-Google-Smtp-Source: ABdhPJyJPDZxHd8/TacmvB3PouOdyPjpk7IUYnFUZKS/YD4f6XGsFP9GBxVuL/bqSW5GrLFeMHYFzA== X-Received: by 2002:a5d:6cc2:: with SMTP id c2mr9688246wrc.374.1610037139909; Thu, 07 Jan 2021 08:32:19 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h83sm8961719wmf.9.2021.01.07.08.32.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:19 -0800 (PST) Message-Id: In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:08 +0000 Subject: [PATCH v3 07/10] index-format: update preamble to cache tree extension Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee I had difficulty in my efforts to learn about the cache tree extension based on the documentation and code because I had an incorrect assumption about how it behaved. This might be due to some ambiguity in the documentation, so this change modifies the beginning of the cached tree format by expanding the description of the feature. My hope is that this documentation clarifies a few things: 1. There is an in-memory recursive tree structure that is constructed from the extension data. This structure has a few differences, such as where the name is stored. 2. What does it mean for an entry to be invalid? 3. When exactly are "new" trees created? Helped-by: Junio C Hamano Signed-off-by: Derrick Stolee --- Documentation/technical/index-format.txt | 33 +++++++++++++++++++----- 1 file changed, 27 insertions(+), 6 deletions(-) diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index c71314731ec..65dcfa570df 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -138,12 +138,33 @@ Git index format === Cache tree - Cache tree extension contains pre-computed hashes for trees that can - be derived from the index. It helps speed up tree object generation - from index for a new commit. - - When a path is updated in index, the path must be invalidated and - removed from tree cache. + Since the index does not record entries for directories, the cache + entries cannot describe tree objects that already exist in the object + database for regions of the index that are unchanged from an existing + commit. The cache tree extension stores a recursive tree structure that + describes the trees that already exist and completely match sections of + the cache entries. This speeds up tree object generation from the index + for a new commit by only computing the trees that are "new" to that + commit. It also assists when comparing the index to another tree, such + as `HEAD^{tree}`, since sections of the index can be skipped when a tree + comparison demonstrates equality. + + The recursive tree structure uses nodes that store a number of cache + entries, a list of subnodes, and an object ID (OID). The OID references + the existing tree for that node, if it is known to exist. The subnodes + correspond to subdirectories that themselves have cache tree nodes. The + number of cache entries corresponds to the number of cache entries in + the index that describe paths within that tree's directory. + + The extension tracks the full directory structure in the cache tree + extension, but this is generally smaller than the full cache entry list. + + When a path is updated in index, Git invalidates all nodes of the + recursive cache tree corresponding to the parent directories of that + path. We store these tree nodes as being "invalid" by using "-1" as the + number of cache entries. Invalid nodes still store a span of index + entries, allowing Git to focus its efforts when reconstructing a full + cache tree. The signature for this extension is { 'T', 'R', 'E', 'E' }. From patchwork Thu Jan 7 16:32:09 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004431 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6D936C433E6 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 4012623433 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728793AbhAGQdi (ORCPT ); Thu, 7 Jan 2021 11:33:38 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47372 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728672AbhAGQdg (ORCPT ); Thu, 7 Jan 2021 11:33:36 -0500 Received: from mail-wr1-x431.google.com (mail-wr1-x431.google.com [IPv6:2a00:1450:4864:20::431]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5226AC0612FD for ; Thu, 7 Jan 2021 08:32:22 -0800 (PST) Received: by mail-wr1-x431.google.com with SMTP id m5so6228677wrx.9 for ; Thu, 07 Jan 2021 08:32:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:fcc :content-transfer-encoding:mime-version:to:cc; bh=J0quDYQmAimfPiktYyMvKlXlNzw88Ny8gDuLOVi5x64=; b=h4DLMc2q9Ba6QOCNKe390hoTbfoTru/9GbprwngEh1Yk+LVtOLg3NgqYCHbH+aD6eP oouJzlDsKuF4aVXUS5PmshkITQtJItw7piXNfAVVV69UJmBsKL4D/RIwoB3EHvX+uFsb OQ+wWY6t1v4pPhvdvpJRj2BjXZJB5djApBY94L3pVCMl1e3zjfQ5vMSESP6fhmnHYj1c UijpyPebJSGLz4lwjq0bFBivFBTcfNVc54IUyFt1w34JXGyLyrHqYgjOxD5Ft+DVs3O/ LqkdZHDNIOp33lQxyGGnhZSHbMYlfm3Vc81jXVWB+jSHg00g52fUfuHFjMp3VIcvgo2Q ryuw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:fcc:content-transfer-encoding:mime-version:to:cc; bh=J0quDYQmAimfPiktYyMvKlXlNzw88Ny8gDuLOVi5x64=; b=iIAP6y+NH+FgMc/LAiEtkYepcv0O58+InKjlCWoTtW8sP9RxBd+jGoFi/T8cZZ4TdF cRxP/UaojShFZBAzUrNRKtPoieGKxitPRrp3ZG9J/hqh1CIqXAL1yc1juMFKH9Mcx+O1 VxDj91/xOzlC/MVVsYkUuIvyZ/7F3V7oopbxkqQ01wlS0ZXneM2sdeV872TD4Cy5dAJs CcT2468nx4Ed6aHeMMhzo/0o35m6Zem/alS1cmgJYVOmw86UHBeDT34JNHhFojTD0F/V w/XGwFDmS8v2kAI6NUVjo3Yj8H6K8e2BYkTVHi4xaOmza0ta6241RHZP80NhJ5Irh2Gi u8dg== X-Gm-Message-State: AOAM532TDtDLBhKiJWZ6zIRhBgT2xq0KJlNK//+qs+EZtJ8RC+A/zWB8 BK4pdyi4mSGxRDFEqKK2ViZ/7KFvg/U= X-Google-Smtp-Source: ABdhPJxUZoO4HPTcK+7SK/hTgydNpZDhNWz4QDTAK53xcF2Sw3qP6eC2d0KLtrFsN6Lw3777DFk0bA== X-Received: by 2002:adf:84c1:: with SMTP id 59mr10129536wrg.409.1610037140933; Thu, 07 Jan 2021 08:32:20 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p15sm8671229wrt.15.2021.01.07.08.32.20 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:20 -0800 (PST) Message-Id: <97c06c80a8543d29bf9390fc8ae5b73ae140c057.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:09 +0000 Subject: [PATCH v3 08/10] index-format: discuss recursion of cached-tree better Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The end of the cached tree index extension format trails off with ellipses ever since 23fcc98 (doc: technical details about the index file format, 2011-03-01). While an intuitive reader could gather what this means, it could be better to use "and so on" instead. Really, this is only justified because I also wanted to point out that the number of subtrees in the index format is used to determine when the recursive depth-first-search stack should be "popped." This should help to add clarity to the format. Signed-off-by: Derrick Stolee --- Documentation/technical/index-format.txt | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/Documentation/technical/index-format.txt b/Documentation/technical/index-format.txt index 65dcfa570df..b633482b1bd 100644 --- a/Documentation/technical/index-format.txt +++ b/Documentation/technical/index-format.txt @@ -195,7 +195,8 @@ Git index format first entry represents the root level of the repository, followed by the first subtree--let's call this A--of the root level (with its name relative to the root level), followed by the first subtree of A (with - its name relative to A), ... + its name relative to A), and so on. The specified number of subtrees + indicates when the current level of the recursive stack is complete. === Resolve undo From patchwork Thu Jan 7 16:32:10 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Ren=C3=A9_Scharfe?= X-Patchwork-Id: 12004433 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9881CC433E9 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 7AB26233FC for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728804AbhAGQdj (ORCPT ); Thu, 7 Jan 2021 11:33:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47376 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728735AbhAGQdh (ORCPT ); Thu, 7 Jan 2021 11:33:37 -0500 Received: from mail-wr1-x434.google.com (mail-wr1-x434.google.com [IPv6:2a00:1450:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 304C9C0612FE for ; Thu, 7 Jan 2021 08:32:23 -0800 (PST) Received: by mail-wr1-x434.google.com with SMTP id d13so6191850wrc.13 for ; Thu, 07 Jan 2021 08:32:23 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:mime-version :content-transfer-encoding:fcc:to:cc; bh=2sQ7U1FWgBOX7rWhIg5mwDJ4gGLWmHnYWn6oA+HXRLA=; b=IqdMywB74uQbQePWMYVKi4HLn8qkLGyABEwxJu8/1cHh8K+HMuEr3qVc7XB1Sx55QF PdMUWarURR4APz7ZsrFOhZsR//sjlQ5rIIZiU/hnyOTe2Jd9/VX/AQOiBn2FFAVjih3Z /xYM0AVhwWtXT3gm1v3f49z1om3xLg+YoMdIZQ46AXA8JxECQzQsgC2cO/quV/R3+DB5 BlcEODoDzv19PIsqcAvC9i+gbP82G84TY3j14Sbrt4RhB5j015G9yg33YcPZ3TEJeTwu XbIW26X6yOcRm6gfmGyVrbo3TJmLxDabqVhLrpdKf9IaxHcd75ODx+odW5OIzVZUOUlc 1uFA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:mime-version:content-transfer-encoding:fcc:to:cc; bh=2sQ7U1FWgBOX7rWhIg5mwDJ4gGLWmHnYWn6oA+HXRLA=; b=gTNojeRCx0JvGf+c03f1R5TmP88w7N00tCV6aYIlktMc6gJMVfdh3LXeHqJnitDvhg c7g0Mm/61RJM2uq3NiX/TmNwsu5UnuUqqesWdjCB7c1hvFF/iUo3CdpcvheupGuKb2pj HkI1q5GD4yeiP8JIyEkNIZtDW0w7MkRlm4KxyK71thmoxGwjkGZPJH8mHsQ6Xbdd7et0 mjhxgyC5cHEqjS93WmFZ3jjEg+LmUz5U22wUVTSx5hkQh3988Fqu51GGtbnOyClxS8F7 xfJGGcmMcu+iFseZCNyk2dKNCMb4OJIHxnDwgMg0AerXM24NlLBDwMrM+wBNgxPfTta3 NgSw== X-Gm-Message-State: AOAM533Q8fOyd6lOPNNeADZXN14o3FmUVAmNypXMsRHyNAfXMjtV10Tq ckodyypaCjAvIMUP7qRAiLiO9SPdpU0= X-Google-Smtp-Source: ABdhPJz7ggX6lD1j3/8W7KsoDN2yWKTa1WNJtcrQHRMIS/36aQ7FoZ9xSGsN+Tt16UaXW/p9jZkNgg== X-Received: by 2002:adf:f5c5:: with SMTP id k5mr10060794wrp.286.1610037141806; Thu, 07 Jan 2021 08:32:21 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id o8sm8917137wrm.17.2021.01.07.08.32.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:21 -0800 (PST) Message-Id: <2532f5cc1898fa1652e828f26fb83c8b211a18f0.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:10 +0000 Subject: [PATCH v3 09/10] cache-tree: use ce_namelen() instead of strlen() MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , =?utf-8?q?Ren=C3=A9_Scharfe?= Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: =?utf-8?q?Ren=C3=A9_Scharfe?= From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Use the name length field of cache entries instead of calculating its value anew. Signed-off-by: René Scharfe Signed-off-by: Derrick Stolee --- cache-tree.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/cache-tree.c b/cache-tree.c index 7da59b2aa07..4274de75bac 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache, * the cache is sorted. Also path can appear only once, * which means conflicting one would immediately follow. */ - const char *this_name = cache[i]->name; - const char *next_name = cache[i+1]->name; - int this_len = strlen(this_name); - if (this_len < strlen(next_name) && + const struct cache_entry *this_ce = cache[i]; + const struct cache_entry *next_ce = cache[i + 1]; + const char *this_name = this_ce->name; + const char *next_name = next_ce->name; + int this_len = ce_namelen(this_ce); + if (this_len < ce_namelen(next_ce) && strncmp(this_name, next_name, this_len) == 0 && next_name[this_len] == '/') { if (10 < ++funny) { From patchwork Thu Jan 7 16:32:11 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 12004435 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id ADE75C43381 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8F87423433 for ; Thu, 7 Jan 2021 16:33:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728812AbhAGQdj (ORCPT ); Thu, 7 Jan 2021 11:33:39 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47378 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728741AbhAGQdh (ORCPT ); Thu, 7 Jan 2021 11:33:37 -0500 Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com [IPv6:2a00:1450:4864:20::429]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 21C19C0612FF for ; Thu, 7 Jan 2021 08:32:24 -0800 (PST) Received: by mail-wr1-x429.google.com with SMTP id w5so6210273wrm.11 for ; Thu, 07 Jan 2021 08:32:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=message-id:in-reply-to:references:from:date:subject:mime-version :content-transfer-encoding:fcc:to:cc; bh=RWzNeO0RUBCbiAHqidiz31YNJN86Cus3A4MuiXII+/s=; b=RtAPVIWEieGYsb9bWyM4S2J3cEVTLBi1lWao5b9gx10IgP9arcPnR9aZVmbNJX5Rjm tPhsKKbbekF5NnydQ0myDFQOCKAbyGC15LYzOi07kERyTG0GYts+y/zUi7TnqXZJMfX1 A5HBhO64Rjyf9NYR9r9YE+JQTzm7SX2A0TjGL8X1pkPtTyWnTQjM76S722rD01pPy0Sb WMiFHv12iiYehEUU2mxag/5ullhyiMQsGc3jrgu95+V12U/S5oFqC0ktRd0gC9b2AqGv pvoOs70eefEaFd5oGI06jwPmOSqFheeJ5vMNUXVn6R/+smdkK0A7Qtz5QWJHP/uDwKET fczQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:in-reply-to:references:from:date :subject:mime-version:content-transfer-encoding:fcc:to:cc; bh=RWzNeO0RUBCbiAHqidiz31YNJN86Cus3A4MuiXII+/s=; b=umX1pWStaW1vhVbYG0IH1OIGCP9i4rodT1OirS3PlaOrsg9aUeYP/vu9O2SmDm6jLC PhVDGQoB+ryvKN+1dXSDts9NPKFxSTPQS5uc9Xx41ZzZeJC1UqC1Av3m9WkGyHtrsk2Q 4mdnzxVIN4LG8DWsGKD7i7DfIprQxxoN9bkercDoQBQM5Qy2iw7zTIO5DiwZvJLrw8QM UkKSTQQFEyzUdX8V7V5gm/u/AtDp96ADhiS3Pi3pyfnIAHzKWRbaEPwlz0TL3yxHZqyX 8rWhWyntivvfn8OECQDWJr84MubJTwjsKBf/hyV6BMR8AHquZ0klYRvmv54dSE920O2e a0uw== X-Gm-Message-State: AOAM530bpn7m0C/9aQsVkStAJnBU5M1L2otEgxQ3BM2UqsNLHSlKImfQ RaAKAQJCQNWNFBOVXGDSJZK4DMVBcUk= X-Google-Smtp-Source: ABdhPJzuXbPgIt3cz3Cc4lhx7gAVnoIqIh6HNsd7d+YC0aktUYifF8UcAJIsNqEWJhSoq4pSUk1eZA== X-Received: by 2002:adf:ded1:: with SMTP id i17mr9611469wrn.190.1610037142689; Thu, 07 Jan 2021 08:32:22 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id h15sm8625068wru.4.2021.01.07.08.32.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 07 Jan 2021 08:32:22 -0800 (PST) Message-Id: <7c1c206a0bccd25842e49b282d64432d61e879d8.1610037132.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Thu, 07 Jan 2021 16:32:11 +0000 Subject: [PATCH v3 10/10] cache-tree: speed up consecutive path comparisons MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: gitster@pobox.com, newren@gmail.com, Derrick Stolee , =?utf-8?b?UmVuw6k=?= Scharfe , Derrick Stolee , Derrick Stolee Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Derrick Stolee From: Derrick Stolee The previous change reduced time spent in strlen() while comparing consecutive paths in verify_cache(), but we can do better. The conditional checks the existence of a directory separator at the correct location, but only after doing a string comparison. Swap the order to be logically equivalent but perform fewer string comparisons. To test the effect on performance, I used a repository with over three million paths in the index. I then ran the following command on repeat: git -c index.threads=1 commit --amend --allow-empty --no-edit Here are the measurements over 10 runs after a 5-run warmup: Benchmark #1: v2.30.0 Time (mean ± σ): 854.5 ms ± 18.2 ms Range (min … max): 825.0 ms … 892.8 ms Benchmark #2: Previous change Time (mean ± σ): 833.2 ms ± 10.3 ms Range (min … max): 815.8 ms … 849.7 ms Benchmark #3: This change Time (mean ± σ): 815.5 ms ± 18.1 ms Range (min … max): 795.4 ms … 849.5 ms This change is 2% faster than the previous change and 5% faster than v2.30.0. Signed-off-by: Derrick Stolee --- cache-tree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/cache-tree.c b/cache-tree.c index 4274de75bac..3f1a8d4f1b7 100644 --- a/cache-tree.c +++ b/cache-tree.c @@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache, const char *next_name = next_ce->name; int this_len = ce_namelen(this_ce); if (this_len < ce_namelen(next_ce) && - strncmp(this_name, next_name, this_len) == 0 && - next_name[this_len] == '/') { + next_name[this_len] == '/' && + strncmp(this_name, next_name, this_len) == 0) { if (10 < ++funny) { fprintf(stderr, "...\n"); break;