From patchwork Fri Jul 30 11:47:36 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411095 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=-10.0 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,UNWANTED_LANGUAGE_BODY 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 5698EC4338F for ; Fri, 30 Jul 2021 11:47:52 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 378C16052B for ; Fri, 30 Jul 2021 11:47:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238723AbhG3Lrz (ORCPT ); Fri, 30 Jul 2021 07:47:55 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56046 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238692AbhG3Lrx (ORCPT ); Fri, 30 Jul 2021 07:47:53 -0400 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7E0DCC0613C1 for ; Fri, 30 Jul 2021 04:47:48 -0700 (PDT) Received: by mail-wr1-x42b.google.com with SMTP id b13so90278wrs.3 for ; Fri, 30 Jul 2021 04:47:48 -0700 (PDT) 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=Yzkzbi/Slg3JVOXhChvUByogsyK3fYn9Uf+8FgTW9dE=; b=j8UAfSsklfN1HDw0VsnG3e2ULkKpHzJbLV4pg2Tp4D9TyScflqKNKU9gvg69Un/FL0 YLhwf9pfTNcZ+QcFRR84jRZ/oJMk6UMi//IUkR6tLVwUV5n9JWZQSF0uMYmw7EjbgNEs F7jo/0nqNLFqAZ7IWj2AGr1x2eUKzilIRVdscFFujkpdT9MBHDJGqHIWM36NSUpxoXBl akvTkDlXtQV6ym45Pb5Whh+DiBGfxvc9CsnKWs6lPQiKRr1krqGnKig8m/C/aGqkfY1g h/9YgySFIO+bT9dyEmBM9AjS+6ee4E+m7lIorktYdS5nz7pZztZq4U/umk3Ot/HJ5Qqh bHsg== 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=Yzkzbi/Slg3JVOXhChvUByogsyK3fYn9Uf+8FgTW9dE=; b=aJ8L/tY8sMZ4cQAAcAqf8O49ZLKbfelyIXIhNRmn+quAiDjcWAHL9nJ/Ub3XVAKdqB YPTUeiCtIP00yv7ZVHkJf+YUO4nFhQKSweVgIohyK0EOxyqNg6Sjp4gp+Yr/Ufkj7IuJ 21i3UHW0Jys79HWgfhdvLg9KJMrvBK2Hpqtj00uVYHOLl7TGxFDhp2MpodDzkzbWcvjg XQzs8+/zap0NJ70IIWFKKI9/9wRncAxoL2RjBoh5o59nHMjlj+7Nm/tczGiXRlcI0sU/ JqBUrR9otwuP1aQFao9WIkDqfwNXGCJ1qlN3Pnmo7uQezqfpuA19Es11zPh/qGw3Gh+i gmTQ== X-Gm-Message-State: AOAM530iWAxDslFUAZEZ6myE4CBYsx6VoyTT7PV8aI5fsYqTGoWQd5pt xt+D6kC/ReJ3+GJZp6jR7XmbJBu15y4= X-Google-Smtp-Source: ABdhPJxVYVpvFAP6CGNCZ1sSbiJPa9FpJcrvZ7hRdNZPsC9R8P9aoMrliN7JIcA6lkif3jnJOQyhQQ== X-Received: by 2002:a5d:4562:: with SMTP id a2mr2553891wrc.347.1627645667139; Fri, 30 Jul 2021 04:47:47 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id k186sm1862406wme.45.2021.07.30.04.47.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:46 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:36 +0000 Subject: [PATCH v3 1/9] merge-ort: rename str{map,intmap,set}_func() Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren In order to make it clearer that these three variables holding a function refer to functions that will clear the strmap/strintmap/strset, rename them to str{map,intmap,set}_clear_func(). Signed-off-by: Elijah Newren --- merge-ort.c | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index e75b524153e..401a40247a3 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -519,11 +519,11 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, { struct rename_info *renames = &opti->renames; int i; - void (*strmap_func)(struct strmap *, int) = + void (*strmap_clear_func)(struct strmap *, int) = reinitialize ? strmap_partial_clear : strmap_clear; - void (*strintmap_func)(struct strintmap *) = + void (*strintmap_clear_func)(struct strintmap *) = reinitialize ? strintmap_partial_clear : strintmap_clear; - void (*strset_func)(struct strset *) = + void (*strset_clear_func)(struct strset *) = reinitialize ? strset_partial_clear : strset_clear; /* @@ -534,14 +534,14 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, * to deallocate them. */ free_strmap_strings(&opti->paths); - strmap_func(&opti->paths, 1); + strmap_clear_func(&opti->paths, 1); /* * All keys and values in opti->conflicted are a subset of those in * opti->paths. We don't want to deallocate anything twice, so we * don't free the keys and we pass 0 for free_values. */ - strmap_func(&opti->conflicted, 0); + strmap_clear_func(&opti->conflicted, 0); /* * opti->paths_to_free is similar to opti->paths; we created it with @@ -559,24 +559,24 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, /* Free memory used by various renames maps */ for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) { - strintmap_func(&renames->dirs_removed[i]); - strmap_func(&renames->dir_renames[i], 0); - strintmap_func(&renames->relevant_sources[i]); + strintmap_clear_func(&renames->dirs_removed[i]); + strmap_clear_func(&renames->dir_renames[i], 0); + strintmap_clear_func(&renames->relevant_sources[i]); if (!reinitialize) assert(renames->cached_pairs_valid_side == 0); if (i != renames->cached_pairs_valid_side && -1 != renames->cached_pairs_valid_side) { - strset_func(&renames->cached_target_names[i]); - strmap_func(&renames->cached_pairs[i], 1); - strset_func(&renames->cached_irrelevant[i]); + strset_clear_func(&renames->cached_target_names[i]); + strmap_clear_func(&renames->cached_pairs[i], 1); + strset_clear_func(&renames->cached_irrelevant[i]); partial_clear_dir_rename_count(&renames->dir_rename_count[i]); if (!reinitialize) strmap_clear(&renames->dir_rename_count[i], 1); } } for (i = MERGE_SIDE1; i <= MERGE_SIDE2; ++i) { - strintmap_func(&renames->deferred[i].possible_trivial_merges); - strset_func(&renames->deferred[i].target_dirs); + strintmap_clear_func(&renames->deferred[i].possible_trivial_merges); + strset_clear_func(&renames->deferred[i].target_dirs); renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */ } renames->cached_pairs_valid_side = 0; From patchwork Fri Jul 30 11:47:37 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411097 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 3B9E7C432BE for ; Fri, 30 Jul 2021 11:47:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1F8916052B for ; Fri, 30 Jul 2021 11:47:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238729AbhG3Lr4 (ORCPT ); Fri, 30 Jul 2021 07:47:56 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56054 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238705AbhG3Lry (ORCPT ); Fri, 30 Jul 2021 07:47:54 -0400 Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3D29FC061765 for ; Fri, 30 Jul 2021 04:47:49 -0700 (PDT) Received: by mail-wm1-x32d.google.com with SMTP id b128so5787561wmb.4 for ; Fri, 30 Jul 2021 04:47:49 -0700 (PDT) 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=AXse4muAeaYC3gLbixhZ8tneVeIz+kqzyPqgyg820Pk=; b=GdGpcS+B4riH/nhq7JrcAOp358n2OHNvuToXDhq2cwMUhyQpTNUL0SB9uiY4lXXM0a j11+bc4bAY6yvFM9n4vnWX+DyyYRnghC0N9T8TyOocxpmCQUzPszaDn9vBZvVCaALRyz 7ILl234wakRVyIssvheCGU9bKBJw534fJ27nYRcvdwgX22Yu0YnenSTwtq5wiMnGfXNM o3pPfFAKfuzupW33i5pNCAA10BeDvLRPZSqhI6xQXY1bPtMiumfX2Hl9ID1va8gyhmfy HhoPHfKjE6PqS6VwcEi4V5QZRDulUmtOiFkBXhc2SgtMFHWtDZSeD0C6uqAQg8xaGMp4 Ygug== 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=AXse4muAeaYC3gLbixhZ8tneVeIz+kqzyPqgyg820Pk=; b=YzJSgmcE9zf4SE/zVLzZwkbuR6uTpoqwjwX1A48HF7qng6RPHUHc/B5qLrHeBNaZd/ gjqvZNduccH0/6GV+f4UB2+ydwT6fkTmVCWxZXoyOTbY98pYx3xQXYw1AZk+k/ZRSPlD eD8ItZU1nkmNUq0nVBqEfKq8NRYm4eXpzZNbaXxEnMwXuZBiwL95jY3UlXG8cLxWLCAV X2PeodNVdYmEOgelpJfudzFVqN2zotG/tnqsG6+SZFsSOirclbNiPQWhhAF/g185lB9N MXWuy+0nXZhWPd1DhwW54DsS/DfWVr4C+sHxmHeGMLhU64sU9Ur6onlKaKLIIRZplKTK p9xQ== X-Gm-Message-State: AOAM531HrShD5ls8IZ1qds1LrrpouMc9oUcV/wkt5nuIiX1PFy4ZRcJN LVp1AeDPARMPAVnMXbkgEYcGtLpL3LA= X-Google-Smtp-Source: ABdhPJxyRG9XqGoCr0l358TIvFc9KORCE2Uohjq7JR2V9YRPTs6Tl2Cj/tJjpT4TorSoDAhbSNfvtQ== X-Received: by 2002:a7b:cc16:: with SMTP id f22mr2572757wmh.99.1627645667867; Fri, 30 Jul 2021 04:47:47 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id w13sm1424248wrq.91.2021.07.30.04.47.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:47 -0700 (PDT) Message-Id: <8416afa89fb9d1e638bf6f52403f113c82de7424.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:37 +0000 Subject: [PATCH v3 2/9] diffcore-rename: use a mem_pool for exact rename detection's hashmap MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Exact rename detection, via insert_file_table(), uses a hashmap to store files by oid. Use a mem_pool for the hashmap entries so these can all be allocated and deallocated together. For the testcases mentioned in commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28), this change improves the performance as follows: Before After no-renames: 204.2 ms ± 3.0 ms 202.5 ms ± 3.2 ms mega-renames: 1.076 s ± 0.015 s 1.072 s ± 0.012 s just-one-mega: 364.1 ms ± 7.0 ms 357.3 ms ± 3.9 ms Signed-off-by: Elijah Newren --- diffcore-rename.c | 22 ++++++++++++++++------ 1 file changed, 16 insertions(+), 6 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index 4ef0459cfb5..73d884099eb 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -317,10 +317,11 @@ static int find_identical_files(struct hashmap *srcs, } static void insert_file_table(struct repository *r, + struct mem_pool *pool, struct hashmap *table, int index, struct diff_filespec *filespec) { - struct file_similarity *entry = xmalloc(sizeof(*entry)); + struct file_similarity *entry = mem_pool_alloc(pool, sizeof(*entry)); entry->index = index; entry->filespec = filespec; @@ -336,7 +337,8 @@ static void insert_file_table(struct repository *r, * and then during the second round we try to match * cache-dirty entries as well. */ -static int find_exact_renames(struct diff_options *options) +static int find_exact_renames(struct diff_options *options, + struct mem_pool *pool) { int i, renames = 0; struct hashmap file_table; @@ -346,7 +348,7 @@ static int find_exact_renames(struct diff_options *options) */ hashmap_init(&file_table, NULL, NULL, rename_src_nr); for (i = rename_src_nr-1; i >= 0; i--) - insert_file_table(options->repo, + insert_file_table(options->repo, pool, &file_table, i, rename_src[i].p->one); @@ -354,8 +356,8 @@ static int find_exact_renames(struct diff_options *options) for (i = 0; i < rename_dst_nr; i++) renames += find_identical_files(&file_table, i, options); - /* Free the hash data structure and entries */ - hashmap_clear_and_free(&file_table, struct file_similarity, entry); + /* Free the hash data structure (entries will be freed with the pool) */ + hashmap_clear(&file_table); return renames; } @@ -1341,6 +1343,7 @@ void diffcore_rename_extended(struct diff_options *options, int num_destinations, dst_cnt; int num_sources, want_copies; struct progress *progress = NULL; + struct mem_pool local_pool; struct dir_rename_info info; struct diff_populate_filespec_options dpf_options = { .check_binary = 0, @@ -1409,11 +1412,18 @@ void diffcore_rename_extended(struct diff_options *options, goto cleanup; /* nothing to do */ trace2_region_enter("diff", "exact renames", options->repo); + mem_pool_init(&local_pool, 32*1024); /* * We really want to cull the candidates list early * with cheap tests in order to avoid doing deltas. */ - rename_count = find_exact_renames(options); + rename_count = find_exact_renames(options, &local_pool); + /* + * Discard local_pool immediately instead of at "cleanup:" in order + * to reduce maximum memory usage; inexact rename detection uses up + * a fair amount of memory, and mem_pools can too. + */ + mem_pool_discard(&local_pool, 0); trace2_region_leave("diff", "exact renames", options->repo); /* Did we only want exact renames? */ From patchwork Fri Jul 30 11:47:38 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411099 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 3ABD1C4338F for ; Fri, 30 Jul 2021 11:47:55 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 1CFA06052B for ; Fri, 30 Jul 2021 11:47:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238734AbhG3Lr5 (ORCPT ); Fri, 30 Jul 2021 07:47:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56058 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238709AbhG3Lry (ORCPT ); Fri, 30 Jul 2021 07:47:54 -0400 Received: from mail-wm1-x32d.google.com (mail-wm1-x32d.google.com [IPv6:2a00:1450:4864:20::32d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0372CC061765 for ; Fri, 30 Jul 2021 04:47:50 -0700 (PDT) Received: by mail-wm1-x32d.google.com with SMTP id a192-20020a1c7fc90000b0290253b32e8796so7080565wmd.0 for ; Fri, 30 Jul 2021 04:47:49 -0700 (PDT) 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=4W9WNGrc3ipNQPgdDdR8WMqa8vuANw1l/AK9OiUX2hw=; b=vTa/5UoXfMij8+vu4zNPedivi9c+If6uMK4aIRIsrYd1XrWk1wwsoR5nyOkg24ZgcV bpH3+0QPE6xrqb/6uOb1phekN17EwXAsco7x5R1dwLtThm/uHUUN2v61PTqtCenVUEpF SyRQ8//tTvS4ZEN+J3wGZq66YF+W0+SttPLyFEl0ThbGiPb8oGEWKJvA5ELO5xOF4rmp GFdBUIftv0KRY0/8S8OB9R2HKq2qrz4Q3AbPKaeFe6D3fCY32xVxktXUgY3Nkn9VobFy XbjAbxdw8zG58IW1RIB4uYVHelWfzi6FDcVrGVRqiRBYTxxsDXiyhGgDvDh5NycAx9Jk g2nQ== 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=4W9WNGrc3ipNQPgdDdR8WMqa8vuANw1l/AK9OiUX2hw=; b=m9nG6FybbDwS+ffUxoWmNOyal76f+T1wfu4k3ERzHO2LAcwYB5rGCsesdYxVxWsUeO Sx78MIHcmnr+sxdcWz1CfaTkHVyGLPpf9rfZItsPvF/UPS2IPLgPwPdMjvSoRfC/su6D j1nyxwedicecflbXfvo3qiKvV3j4UB5gSmir16ImSysjctcUSPKSRdOf36uflVKMvkuT /fyrgtFdMHfY/WanhGtzbsLDcAJhoTkrR7O3oYEUfvZ4W7BzAUY3h+2b6pgEjKwvHQo3 Y3OIuPWcOvT3BHo+UhprL/yQg8s2QLkgf1OjdZMwU5O1ycYNf4iIRABcLprO3pEoUHcD aWFQ== X-Gm-Message-State: AOAM531EmJvDiJdTfCjCgM0FjFmdRXqHaPDa9fBcxNwOo5mW8+9zwsRL /RnSdow4hknoYNfrh9mo29Ks0NuRQr0= X-Google-Smtp-Source: ABdhPJxkkEJUOCcLPYza8u9QcpYWF9YOpVb/pybV2Jy9hN7yt0ABthkUyASMRVafZ2RdsJdXl4AoLQ== X-Received: by 2002:a1c:a78a:: with SMTP id q132mr2466043wme.76.1627645668670; Fri, 30 Jul 2021 04:47:48 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id d15sm1584217wri.39.2021.07.30.04.47.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:48 -0700 (PDT) Message-Id: <2c0b90eaba5bbf03553c8ac2487b57b66a6ed18e.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:38 +0000 Subject: [PATCH v3 3/9] merge-ort: add pool_alloc, pool_calloc, and pool_strndup wrappers Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Make the code more flexible so that it can handle both being run with or without a memory pool by adding utility functions which will either call xmalloc, xcalloc, xstrndup or mem_pool_alloc, mem_pool_calloc, mem_pool_strndup depending on whether we have a non-NULL memory pool. A subsequent commit will make use of these. (We will actually be dropping these functions soon and just assuming we always have a memory pool, but the flexibility was very useful during development of merge-ort so I want to be able to restore it if needed.) Signed-off-by: Elijah Newren --- merge-ort.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 401a40247a3..63f67246d3d 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -664,6 +664,30 @@ static void path_msg(struct merge_options *opt, strbuf_addch(sb, '\n'); } +MAYBE_UNUSED +static void *pool_calloc(struct mem_pool *pool, size_t count, size_t size) +{ + if (!pool) + return xcalloc(count, size); + return mem_pool_calloc(pool, count, size); +} + +MAYBE_UNUSED +static void *pool_alloc(struct mem_pool *pool, size_t size) +{ + if (!pool) + return xmalloc(size); + return mem_pool_alloc(pool, size); +} + +MAYBE_UNUSED +static void *pool_strndup(struct mem_pool *pool, const char *str, size_t len) +{ + if (!pool) + return xstrndup(str, len); + return mem_pool_strndup(pool, str, len); +} + /* add a string to a strbuf, but converting "/" to "_" */ static void add_flattened_path(struct strbuf *out, const char *s) { From patchwork Fri Jul 30 11:47:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411103 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 046D7C4320A for ; Fri, 30 Jul 2021 11:48:00 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id DA2A86103B for ; Fri, 30 Jul 2021 11:47:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238771AbhG3LsD (ORCPT ); Fri, 30 Jul 2021 07:48:03 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56068 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238728AbhG3Lr4 (ORCPT ); Fri, 30 Jul 2021 07:47:56 -0400 Received: from mail-wr1-x432.google.com (mail-wr1-x432.google.com [IPv6:2a00:1450:4864:20::432]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AF0B3C0613D3 for ; Fri, 30 Jul 2021 04:47:50 -0700 (PDT) Received: by mail-wr1-x432.google.com with SMTP id n12so10981151wrr.2 for ; Fri, 30 Jul 2021 04:47:50 -0700 (PDT) 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=0G2Aq0f99MPciHnA4RscP5rIVPzkEOXnzeJ+kRWgLxI=; b=vFAK0RtNHQy/5q/Z232GWuKXRDme3koSMm5RKqI0AqW2aA08D6SwXtHBt6qwJQvtIJ 9lT2j4ClJLw8Q3RVxWWa0Wz8fM7VF3vDbRZYr2BtFp/Aa7bgy3mooVWLCZQ1GfF1Od5v dnFOwOztECPJVOT5O7VrmAK+uyEPQeX45T9h93X2/9BgDvibnlEvJ+Y8yL8Ljcd+zOsw UFapl5mi3iPnwDlZpe/az7pXJQ/XhdOW+FyJd+POl2PszcoBs5Y/Q80L2XhpFFmEQceM dUsLcJKv3Nay+NRuWX5mqgN4rSLFDtcrlwv6a2Eu57jkHfF7XRNnA/hoCTB11Z/V+2wL pj4A== 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=0G2Aq0f99MPciHnA4RscP5rIVPzkEOXnzeJ+kRWgLxI=; b=lk4xTYxrzHo8UTuK+PxczzLBrI0C1ptqtIFODBl2JlJ/ZIyoGhPJLv7LIebRBKetG2 8Gi6aRuTKm9qYtBm/AgwgrEPVhITOP+cAFDa1EPvJF7H6d3YD/7mz+sE39gLhxyxJqxV xobfEbh78QmfayNaknJs6mjkjvx3f1y/su3YHe9u2wY0yFb7vTgpwSETWgz8Q30rrjuZ nPOzufP3Q+FhRdCH9ob5zUKo6vM5bb6MNn3jSSoiCTPCH6zlrbYEdBXZts0tHxWKcHlr Z3tn5Ps/drTkASKMKZs7LtbJjfxB+dMGTkgiBWmgbMrKqRqJ26n257/29oux8jq31NGN tHSg== X-Gm-Message-State: AOAM532RYX0+A5godJ3yN9uI5J6Zv0NBhHbzjQeKtRseA5iuymFd86RS sfejDrCQlHCR9wJ/rRtk9LQT358CPxg= X-Google-Smtp-Source: ABdhPJymrSz2yEDX4X9OGireS5uQLAEmB2djCVfG/Qd/ncM7ArWRLypZQpN0YtNPfLAmp9EmUJsTAA== X-Received: by 2002:a5d:6908:: with SMTP id t8mr2635561wru.421.1627645669326; Fri, 30 Jul 2021 04:47:49 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id b15sm1755093wrr.27.2021.07.30.04.47.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:48 -0700 (PDT) Message-Id: <6646f6fd1cae3b7ebe279317b95405f2b6d71e9e.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:39 +0000 Subject: [PATCH v3 4/9] merge-ort: set up a memory pool Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren merge-ort has a lot of data structures, and they all tend to be freed together in clear_or_reinit_internal_opts(). Set up a memory pool to allow us to make these allocations and deallocations faster. Future commits will adjust various callers to make use of this memory pool. Signed-off-by: Elijah Newren --- merge-ort.c | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/merge-ort.c b/merge-ort.c index 63f67246d3d..3f425436263 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -37,6 +37,8 @@ #include "unpack-trees.h" #include "xdiff-interface.h" +#define USE_MEMORY_POOL 1 /* faster, but obscures memory leak hunting */ + /* * We have many arrays of size 3. Whenever we have such an array, the * indices refer to one of the sides of the three-way merge. This is so @@ -339,6 +341,17 @@ struct merge_options_internal { */ struct strmap conflicted; + /* + * pool: memory pool for fast allocation/deallocation + * + * We allocate room for lots of filenames and auxiliary data + * structures in merge_options_internal, and it tends to all be + * freed together too. Using a memory pool for these provides a + * nice speedup. + */ + struct mem_pool internal_pool; + struct mem_pool *pool; /* NULL, or pointer to internal_pool */ + /* * paths_to_free: additional list of strings to free * @@ -603,6 +616,12 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, strmap_clear(&opti->output, 0); } +#if USE_MEMORY_POOL + mem_pool_discard(&opti->internal_pool, 0); + if (!reinitialize) + opti->pool = NULL; +#endif + /* Clean out callback_data as well. */ FREE_AND_NULL(renames->callback_data); renames->callback_data_nr = renames->callback_data_alloc = 0; @@ -4381,6 +4400,12 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) /* Initialization of various renames fields */ renames = &opt->priv->renames; +#if USE_MEMORY_POOL + mem_pool_init(&opt->priv->internal_pool, 0); + opt->priv->pool = &opt->priv->internal_pool; +#else + opt->priv->pool = NULL; +#endif for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) { strintmap_init_with_options(&renames->dirs_removed[i], NOT_RELEVANT, NULL, 0); From patchwork Fri Jul 30 11:47:40 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411101 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 15150C4338F for ; Fri, 30 Jul 2021 11:47:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id F1B3E6103B for ; Fri, 30 Jul 2021 11:47:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238768AbhG3LsC (ORCPT ); Fri, 30 Jul 2021 07:48:02 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56076 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238707AbhG3Lr4 (ORCPT ); Fri, 30 Jul 2021 07:47:56 -0400 Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com [IPv6:2a00:1450:4864:20::329]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8C8CBC061765 for ; Fri, 30 Jul 2021 04:47:51 -0700 (PDT) Received: by mail-wm1-x329.google.com with SMTP id h24-20020a1ccc180000b029022e0571d1a0so6215640wmb.5 for ; Fri, 30 Jul 2021 04:47:51 -0700 (PDT) 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=+9eI3QJnaA9ojY4vp8WbYszLhiAHQHDYAfyuZDfzWVY=; b=HC+BZVWaIJFoJ0LxvBnzL1yREsSSzRPvivXHdVWtqp+Y469VH1QcK6UTanauAVu0El knPp1BUDeb04sQ9cMERjF9XrxFjJCfO0IiZVRFg1GxqaAP/CahHm3bQPcozJPw5/QFcS yByunoLORLjifT2PVI9kGITAJKIBAxB4SatnS+TrA0GRHhfWFpxzA7pQ8sscG8Jj5Y6x 3un78m4pvuk4BuVOTNOuL5bbgS8/KU8Ztzq1zjv+aJIGC44OP22S+SsjEK+/UPcRe3Rt x+UkKtUXE4lN7HzipLHhYZe3CPPF4GnhsENoNsMam9fCsKMzggQaZUziv85+V/7rMGyv tVCQ== 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=+9eI3QJnaA9ojY4vp8WbYszLhiAHQHDYAfyuZDfzWVY=; b=LkWdoyzzyuhzLz3QRrBXVMuR7ZHH7A8aooiwbcQMteZrz+9CSM4QkT1twIDEa26Odt +ZPvSNv2j//Ehu+xXL34+2Nt9GDeZlP7S3lTnt+1/hWoyTa394dYUKZstofHuOHSxiHD b9grGMJCRrslcKozVrb2oEH/I8iYdp6Yf1pLULDLimjZNwjtKObcnrvhaJst7sDflvax fMhCfJp7eCn3UQPa4LtpNoOKed7u6ZaxBMQc/z48AU9qqxiMGkRPRAiWunXAEFZLGxTG yZR4ury/n4d0WRj7i79UdFsIF43MZmharjq9IesJmsiU3WGATFzeUGKqk7bXmoDfjbBu kMtg== X-Gm-Message-State: AOAM530YmHaijAZFbkcguLOiMfna8TPJoVXEsli3YiVx1Ro18CjAaXNL knJ5vNUrZwSAyTNl4cGCDYoxkougXoc= X-Google-Smtp-Source: ABdhPJz177ZvgzTnU6hcOEX8vTy8MSKC+fBiSRHCJbioyfAWywuUXv2FOt9R3xw7S+rGQBbmSMB9zw== X-Received: by 2002:a05:600c:298:: with SMTP id 24mr2447686wmk.93.1627645670080; Fri, 30 Jul 2021 04:47:50 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id t17sm1329396wmq.17.2021.07.30.04.47.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:49 -0700 (PDT) Message-Id: <7c49aa601d0b0880dde559579a336809d88a1c01.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:40 +0000 Subject: [PATCH v3 5/9] merge-ort: switch our strmaps over to using memory pools MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren For all the strmaps (including strintmaps and strsets) whose memory is unconditionally freed as part of clear_or_reinit_internal_opts(), switch them over to using our new memory pool. For the testcases mentioned in commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28), this change improves the performance as follows: Before After no-renames: 202.5 ms ± 3.2 ms 198.1 ms ± 2.6 ms mega-renames: 1.072 s ± 0.012 s 715.8 ms ± 4.0 ms just-one-mega: 357.3 ms ± 3.9 ms 276.8 ms ± 4.2 ms Signed-off-by: Elijah Newren --- merge-ort.c | 125 +++++++++++++++++++++++++++++++--------------------- 1 file changed, 75 insertions(+), 50 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 3f425436263..99c75690855 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -539,15 +539,19 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, void (*strset_clear_func)(struct strset *) = reinitialize ? strset_partial_clear : strset_clear; - /* - * We marked opti->paths with strdup_strings = 0, so that we - * wouldn't have to make another copy of the fullpath created by - * make_traverse_path from setup_path_info(). But, now that we've - * used it and have no other references to these strings, it is time - * to deallocate them. - */ - free_strmap_strings(&opti->paths); - strmap_clear_func(&opti->paths, 1); + if (opti->pool) + strmap_clear_func(&opti->paths, 0); + else { + /* + * We marked opti->paths with strdup_strings = 0, so that + * we wouldn't have to make another copy of the fullpath + * created by make_traverse_path from setup_path_info(). + * But, now that we've used it and have no other references + * to these strings, it is time to deallocate them. + */ + free_strmap_strings(&opti->paths); + strmap_clear_func(&opti->paths, 1); + } /* * All keys and values in opti->conflicted are a subset of those in @@ -556,16 +560,19 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, */ strmap_clear_func(&opti->conflicted, 0); - /* - * opti->paths_to_free is similar to opti->paths; we created it with - * strdup_strings = 0 to avoid making _another_ copy of the fullpath - * but now that we've used it and have no other references to these - * strings, it is time to deallocate them. We do so by temporarily - * setting strdup_strings to 1. - */ - opti->paths_to_free.strdup_strings = 1; - string_list_clear(&opti->paths_to_free, 0); - opti->paths_to_free.strdup_strings = 0; + if (!opti->pool) { + /* + * opti->paths_to_free is similar to opti->paths; we + * created it with strdup_strings = 0 to avoid making + * _another_ copy of the fullpath but now that we've used + * it and have no other references to these strings, it is + * time to deallocate them. We do so by temporarily + * setting strdup_strings to 1. + */ + opti->paths_to_free.strdup_strings = 1; + string_list_clear(&opti->paths_to_free, 0); + opti->paths_to_free.strdup_strings = 0; + } if (opti->attr_index.cache_nr) /* true iff opt->renormalize */ discard_index(&opti->attr_index); @@ -683,7 +690,6 @@ static void path_msg(struct merge_options *opt, strbuf_addch(sb, '\n'); } -MAYBE_UNUSED static void *pool_calloc(struct mem_pool *pool, size_t count, size_t size) { if (!pool) @@ -691,7 +697,6 @@ static void *pool_calloc(struct mem_pool *pool, size_t count, size_t size) return mem_pool_calloc(pool, count, size); } -MAYBE_UNUSED static void *pool_alloc(struct mem_pool *pool, size_t size) { if (!pool) @@ -699,7 +704,6 @@ static void *pool_alloc(struct mem_pool *pool, size_t size) return mem_pool_alloc(pool, size); } -MAYBE_UNUSED static void *pool_strndup(struct mem_pool *pool, const char *str, size_t len) { if (!pool) @@ -835,8 +839,9 @@ static void setup_path_info(struct merge_options *opt, assert(!df_conflict || !resolved); /* df_conflict implies !resolved */ assert(resolved == (merged_version != NULL)); - mi = xcalloc(1, resolved ? sizeof(struct merged_info) : - sizeof(struct conflict_info)); + mi = pool_calloc(opt->priv->pool, 1, + resolved ? sizeof(struct merged_info) : + sizeof(struct conflict_info)); mi->directory_name = current_dir_name; mi->basename_offset = current_dir_name_len; mi->clean = !!resolved; @@ -1128,7 +1133,7 @@ static int collect_merge_info_callback(int n, len = traverse_path_len(info, p->pathlen); /* +1 in both of the following lines to include the NUL byte */ - fullpath = xmalloc(len + 1); + fullpath = pool_alloc(opt->priv->pool, len + 1); make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen); /* @@ -1383,7 +1388,7 @@ static int handle_deferred_entries(struct merge_options *opt, copy = renames->deferred[side].possible_trivial_merges; strintmap_init_with_options(&renames->deferred[side].possible_trivial_merges, 0, - NULL, + opt->priv->pool, 0); strintmap_for_each_entry(©, &iter, entry) { const char *path = entry->key; @@ -2335,12 +2340,21 @@ static void apply_directory_rename_modifications(struct merge_options *opt, VERIFY_CI(ci); /* Find parent directories missing from opt->priv->paths */ - cur_path = new_path; + if (opt->priv->pool) { + cur_path = mem_pool_strdup(opt->priv->pool, new_path); + free((char*)new_path); + new_path = (char *)cur_path; + } else { + cur_path = new_path; + } + while (1) { /* Find the parent directory of cur_path */ char *last_slash = strrchr(cur_path, '/'); if (last_slash) { - parent_name = xstrndup(cur_path, last_slash - cur_path); + parent_name = pool_strndup(opt->priv->pool, + cur_path, + last_slash - cur_path); } else { parent_name = opt->priv->toplevel_dir; break; @@ -2349,7 +2363,8 @@ static void apply_directory_rename_modifications(struct merge_options *opt, /* Look it up in opt->priv->paths */ entry = strmap_get_entry(&opt->priv->paths, parent_name); if (entry) { - free((char*)parent_name); + if (!opt->priv->pool) + free((char*)parent_name); parent_name = entry->key; /* reuse known pointer */ break; } @@ -2376,12 +2391,15 @@ static void apply_directory_rename_modifications(struct merge_options *opt, parent_name = cur_dir; } - /* - * We are removing old_path from opt->priv->paths. old_path also will - * eventually need to be freed, but it may still be used by e.g. - * ci->pathnames. So, store it in another string-list for now. - */ - string_list_append(&opt->priv->paths_to_free, old_path); + if (!opt->priv->pool) { + /* + * We are removing old_path from opt->priv->paths. + * old_path also will eventually need to be freed, but it + * may still be used by e.g. ci->pathnames. So, store it + * in another string-list for now. + */ + string_list_append(&opt->priv->paths_to_free, old_path); + } assert(ci->filemask == 2 || ci->filemask == 4); assert(ci->dirmask == 0); @@ -2416,7 +2434,8 @@ static void apply_directory_rename_modifications(struct merge_options *opt, new_ci->stages[index].mode = ci->stages[index].mode; oidcpy(&new_ci->stages[index].oid, &ci->stages[index].oid); - free(ci); + if (!opt->priv->pool) + free(ci); ci = new_ci; } @@ -3623,7 +3642,8 @@ static void process_entry(struct merge_options *opt, * the directory to remain here, so we need to move this * path to some new location. */ - CALLOC_ARRAY(new_ci, 1); + new_ci = pool_calloc(opt->priv->pool, 1, sizeof(*new_ci)); + /* We don't really want new_ci->merged.result copied, but it'll * be overwritten below so it doesn't matter. We also don't * want any directory mode/oid values copied, but we'll zero @@ -3715,7 +3735,7 @@ static void process_entry(struct merge_options *opt, const char *a_path = NULL, *b_path = NULL; int rename_a = 0, rename_b = 0; - new_ci = xmalloc(sizeof(*new_ci)); + new_ci = pool_alloc(opt->priv->pool, sizeof(*new_ci)); if (S_ISREG(a_mode)) rename_a = 1; @@ -3788,12 +3808,14 @@ static void process_entry(struct merge_options *opt, strmap_remove(&opt->priv->paths, path, 0); /* * We removed path from opt->priv->paths. path - * will also eventually need to be freed, but - * it may still be used by e.g. ci->pathnames. - * So, store it in another string-list for now. + * will also eventually need to be freed if not + * part of a memory pool...but it may still be + * used by e.g. ci->pathnames. So, store it in + * another string-list for now in that case. */ - string_list_append(&opt->priv->paths_to_free, - path); + if (!opt->priv->pool) + string_list_append(&opt->priv->paths_to_free, + path); } /* @@ -4335,6 +4357,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) { struct rename_info *renames; int i; + struct mem_pool *pool = NULL; /* Sanity checks on opt */ trace2_region_enter("merge", "sanity checks", opt->repo); @@ -4406,9 +4429,10 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) #else opt->priv->pool = NULL; #endif + pool = opt->priv->pool; for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) { strintmap_init_with_options(&renames->dirs_removed[i], - NOT_RELEVANT, NULL, 0); + NOT_RELEVANT, pool, 0); strmap_init_with_options(&renames->dir_rename_count[i], NULL, 1); strmap_init_with_options(&renames->dir_renames[i], @@ -4422,7 +4446,7 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) */ strintmap_init_with_options(&renames->relevant_sources[i], -1 /* explicitly invalid */, - NULL, 0); + pool, 0); strmap_init_with_options(&renames->cached_pairs[i], NULL, 1); strset_init_with_options(&renames->cached_irrelevant[i], @@ -4432,9 +4456,9 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) } for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) { strintmap_init_with_options(&renames->deferred[i].possible_trivial_merges, - 0, NULL, 0); + 0, pool, 0); strset_init_with_options(&renames->deferred[i].target_dirs, - NULL, 1); + pool, 1); renames->deferred[i].trivial_merges_okay = 1; /* 1 == maybe */ } @@ -4447,9 +4471,10 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) * In contrast, conflicted just has a subset of keys from paths, so * we don't want to free those (it'd be a duplicate free). */ - strmap_init_with_options(&opt->priv->paths, NULL, 0); - strmap_init_with_options(&opt->priv->conflicted, NULL, 0); - string_list_init_nodup(&opt->priv->paths_to_free); + strmap_init_with_options(&opt->priv->paths, pool, 0); + strmap_init_with_options(&opt->priv->conflicted, pool, 0); + if (!opt->priv->pool) + string_list_init_nodup(&opt->priv->paths_to_free); /* * keys & strbufs in output will sometimes need to outlive "paths", From patchwork Fri Jul 30 11:47:41 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411107 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 2BB3BC4338F for ; Fri, 30 Jul 2021 11:48:02 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 18A7D60EE6 for ; Fri, 30 Jul 2021 11:48:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238709AbhG3LsF (ORCPT ); Fri, 30 Jul 2021 07:48:05 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56080 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238738AbhG3Lr5 (ORCPT ); Fri, 30 Jul 2021 07:47:57 -0400 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 337C5C0613C1 for ; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) Received: by mail-wm1-x333.google.com with SMTP id u15-20020a05600c19cfb02902501bdb23cdso9031980wmq.0 for ; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) 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=Mxs78hw82mLcuiyukDBRKAlZGx7o8hUECUOhrCJvi0E=; b=VTK1RcPrDXuXN63lFbVWV6/OKvf643hjC6VKpqOa5O4mUH27fL41mydYTO6If5LL4A xQJuqwYVaqV4OJj6A6MHOYEA0KL4k/onE2v1KQBHSayKietbNCOt8mdtIrgUhNEX6P4P 1Z6dH3av7HTsrh2Xgff9/58mWsX89TOuwWnLyjpx9EH6XN21WCqURs7RHDdAvjyXYTTi VDe4dckHmD7m8cJU4vMWv+StVUPj6+lViaSNiTIpmKuk+T5dm069sfEIm1c+MzWmqnAf lUPbJQjiAxvM2YDDIiAsCm8G12J97AlZTPUfJ+M4VwVnjxAWFZUgP0HSUWphr+MQgUVF HlMQ== 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=Mxs78hw82mLcuiyukDBRKAlZGx7o8hUECUOhrCJvi0E=; b=hGDfIo7gbG8eiWq07bN2RiyapAURhZVKI5OzYKiRTQgVgBthVH3zS6t5B3NRORdd14 /gz1wFzyKQmKkB9J82nC7jAG41hUtk4EwfO4vEN/Cinlpal31ViuLmej7KfRVYNbms9A okPSMsN8zP3k9Il9dXFXFfX18yrR/o53T1z5JJEsLb7pGBYABXNVLoCxcacOBVHignN6 A0Inf+KpH2iQj2QdzWvl7xyiYC1yeubyPUkX2dPpQ74gb0g86as8Jg9ZAYF4evT4E8EK +eoQ3SKCApQH7jZBH3cDWGck0q0GZAGnOF1aJPDCPHMLDKa1jgRcUBJ6w8WbiTyzBdhj piHQ== X-Gm-Message-State: AOAM5334oapkLHEdj8CcAjGlr8rVuZscq6WIMWxS9Ukvod4af/56JBWZ HeBQ0jih/p2sB8+LbYiBkTyo7whj9FM= X-Google-Smtp-Source: ABdhPJz79vUPOHGKfcVj55YGLzmlKILNaPmVIJAONj6TywsIQbrTi01DkEQUwbdCdT3nijDiV9HJqg== X-Received: by 2002:a1c:a4c1:: with SMTP id n184mr2497454wme.8.1627645670772; Fri, 30 Jul 2021 04:47:50 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j2sm1484206wrd.14.2021.07.30.04.47.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:50 -0700 (PDT) Message-Id: <08cf2498f96759a94543d61b9a05e02280ab19d2.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:41 +0000 Subject: [PATCH v3 6/9] diffcore-rename, merge-ort: add wrapper functions for filepair alloc/dealloc Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren We want to be able to allocate filespecs and filepairs using a mem_pool. However, filespec data will still remain outside the pool (perhaps in the future we could plumb the pool through the various diff APIs to allocate the filespec data too, but for now we are limiting the scope). Add some extra functions to allocate these appropriately based on the non-NULL-ness of opt->priv->pool, as well as some extra functions to handle correctly deallocating the relevant parts of them. A future commit will make use of these new functions. Signed-off-by: Elijah Newren --- diffcore-rename.c | 41 +++++++++++++++++++++++++++++++++++++++++ diffcore.h | 2 ++ merge-ort.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 85 insertions(+) diff --git a/diffcore-rename.c b/diffcore-rename.c index 73d884099eb..5bc559f79e9 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -1328,6 +1328,47 @@ static void handle_early_known_dir_renames(struct dir_rename_info *info, rename_src_nr = new_num_src; } +static void free_filespec_data(struct diff_filespec *spec) +{ + if (!--spec->count) + diff_free_filespec_data(spec); +} + +MAYBE_UNUSED +static void pool_free_filespec(struct mem_pool *pool, + struct diff_filespec *spec) +{ + if (!pool) { + free_filespec(spec); + return; + } + + /* + * Similar to free_filespec(), but only frees the data. The spec + * itself was allocated in the pool and should not be individually + * freed. + */ + free_filespec_data(spec); +} + +MAYBE_UNUSED +void pool_diff_free_filepair(struct mem_pool *pool, + struct diff_filepair *p) +{ + if (!pool) { + diff_free_filepair(p); + return; + } + + /* + * Similar to diff_free_filepair() but only frees the data from the + * filespecs; not the filespecs or the filepair which were + * allocated from the pool. + */ + free_filespec_data(p->one); + free_filespec_data(p->two); +} + void diffcore_rename_extended(struct diff_options *options, struct strintmap *relevant_sources, struct strintmap *dirs_removed, diff --git a/diffcore.h b/diffcore.h index 533b30e21e7..b58ee6b1934 100644 --- a/diffcore.h +++ b/diffcore.h @@ -127,6 +127,8 @@ struct diff_filepair { #define DIFF_PAIR_MODE_CHANGED(p) ((p)->one->mode != (p)->two->mode) void diff_free_filepair(struct diff_filepair *); +void pool_diff_free_filepair(struct mem_pool *pool, + struct diff_filepair *p); int diff_unmodified_pair(struct diff_filepair *); diff --git a/merge-ort.c b/merge-ort.c index 99c75690855..e79830f9181 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -690,6 +690,48 @@ static void path_msg(struct merge_options *opt, strbuf_addch(sb, '\n'); } +MAYBE_UNUSED +static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool, + const char *path) +{ + struct diff_filespec *spec; + size_t len; + + if (!pool) + return alloc_filespec(path); + + /* Same code as alloc_filespec, except allocate from pool */ + len = strlen(path); + + spec = mem_pool_calloc(pool, 1, st_add3(sizeof(*spec), len, 1)); + memcpy(spec+1, path, len); + spec->path = (void*)(spec+1); + + spec->count = 1; + spec->is_binary = -1; + return spec; +} + +MAYBE_UNUSED +static struct diff_filepair *pool_diff_queue(struct mem_pool *pool, + struct diff_queue_struct *queue, + struct diff_filespec *one, + struct diff_filespec *two) +{ + struct diff_filepair *dp; + + if (!pool) + return diff_queue(queue, one, two); + + /* Same code as diff_queue, except allocate from pool */ + dp = mem_pool_calloc(pool, 1, sizeof(*dp)); + dp->one = one; + dp->two = two; + if (queue) + diff_q(queue, dp); + return dp; +} + static void *pool_calloc(struct mem_pool *pool, size_t count, size_t size) { if (!pool) From patchwork Fri Jul 30 11:47:42 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411105 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 26DB7C432BE for ; Fri, 30 Jul 2021 11:48:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 0EC886052B for ; Fri, 30 Jul 2021 11:48:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238774AbhG3LsE (ORCPT ); Fri, 30 Jul 2021 07:48:04 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56090 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238709AbhG3Lr5 (ORCPT ); Fri, 30 Jul 2021 07:47:57 -0400 Received: from mail-wm1-x336.google.com (mail-wm1-x336.google.com [IPv6:2a00:1450:4864:20::336]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CA8ECC0613CF for ; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) Received: by mail-wm1-x336.google.com with SMTP id u15-20020a05600c19cfb02902501bdb23cdso9032024wmq.0 for ; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) 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=XNtC/p8BeIl4g0JeAYc6QF8lRXLJ0YJUip1x0g2U0sA=; b=GruPoREGGuy2bW3xjldd/Mfx+vOWleYZ6qY5wwYhotldZP63/I3AhkNhPeoaYf8mSQ vdHeyEVfi12sDdc92+FFRNO2dKvvIS3TdrpOfv40GgLSjeRLwdSI/Es0uUOSrx1JbeqT DUnfXuwQJosFLrNQH+IT/KCd9DCXsrbCsxaG5CxDmmINug1tiL96wL74ttSha0pcb9AN EyMMRIG/+1p5yeGWssnWGeMN4XwmFNiUmQB0W9TCy8xCYKfULtlscQ1w36z0wM96CfQK Wj/izRtPG41/iSz6NbMCiXtwV0qqhg38zg1eHQVh6aMKdqLuWrdoDavPyHSMzf/T4GDI Ol9w== 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=XNtC/p8BeIl4g0JeAYc6QF8lRXLJ0YJUip1x0g2U0sA=; b=iTXzBLDAk1C2SCtFSrICy3HT2FzmWBEictXdLnkgK9awxfe0cNrjhBreg1jYQwQx2Z QkYk+yIFdQo/UZwHxzk7W2hjmnrkB3bMuIxIGx0qHZTHrytFF0JdSOUZ2ObNEBwqgkVG LL0iHTzcCyTymM1WudFQyBArNLAYE0D1SsD0OMjrg274pwR6zHVldsBZ21Zpf7a08BDU lienc5cJ4WIieR0jeTSxS8CFEZxI0vkkbkdtApoDUarDf29c3BWxzNKSXjazxSahemND 2NKZsZXOFB7kaxmmq3aU555QY16UGJI94r4anFLDaZzC9mL7d9vbOqZJ2tZiTZzZmcIt AqRg== X-Gm-Message-State: AOAM531hh33vLlfHWHZxOxsgO4OcpS/rg3H/GrhKi2tnodDytlDnNtwI 1+MfxJhedQMrQ/3Vz/W+4ayn05llxWU= X-Google-Smtp-Source: ABdhPJxjZhCYELVy82GdysMDVPYh8s/Osop36dIbFw8eg+0D35r7bw2iifyu53geV+cfZhdO8eM9KQ== X-Received: by 2002:a05:600c:290:: with SMTP id 16mr2533700wmk.71.1627645671406; Fri, 30 Jul 2021 04:47:51 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j14sm1516404wrr.16.2021.07.30.04.47.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:51 -0700 (PDT) Message-Id: <4ffa5af8b570772bc4ccc859ce05c04c289646b0.1627645664.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:42 +0000 Subject: [PATCH v3 7/9] merge-ort: store filepairs and filespecs in our mem_pool MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren For the testcases mentioned in commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28), this change improves the performance as follows: Before After no-renames: 198.1 ms ± 2.6 ms 198.5 ms ± 3.4 ms mega-renames: 715.8 ms ± 4.0 ms 679.1 ms ± 5.6 ms just-one-mega: 276.8 ms ± 4.2 ms 271.9 ms ± 2.8 ms Signed-off-by: Elijah Newren --- diffcore-rename.c | 9 ++++----- diffcore.h | 1 + merge-ort.c | 26 ++++++++++++++------------ 3 files changed, 19 insertions(+), 17 deletions(-) diff --git a/diffcore-rename.c b/diffcore-rename.c index 5bc559f79e9..7e6b3e1b143 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -1334,7 +1334,6 @@ static void free_filespec_data(struct diff_filespec *spec) diff_free_filespec_data(spec); } -MAYBE_UNUSED static void pool_free_filespec(struct mem_pool *pool, struct diff_filespec *spec) { @@ -1351,7 +1350,6 @@ static void pool_free_filespec(struct mem_pool *pool, free_filespec_data(spec); } -MAYBE_UNUSED void pool_diff_free_filepair(struct mem_pool *pool, struct diff_filepair *p) { @@ -1370,6 +1368,7 @@ void pool_diff_free_filepair(struct mem_pool *pool, } void diffcore_rename_extended(struct diff_options *options, + struct mem_pool *pool, struct strintmap *relevant_sources, struct strintmap *dirs_removed, struct strmap *dir_rename_count, @@ -1683,7 +1682,7 @@ void diffcore_rename_extended(struct diff_options *options, pair_to_free = p; if (pair_to_free) - diff_free_filepair(pair_to_free); + pool_diff_free_filepair(pool, pair_to_free); } diff_debug_queue("done copying original", &outq); @@ -1693,7 +1692,7 @@ void diffcore_rename_extended(struct diff_options *options, for (i = 0; i < rename_dst_nr; i++) if (rename_dst[i].filespec_to_free) - free_filespec(rename_dst[i].filespec_to_free); + pool_free_filespec(pool, rename_dst[i].filespec_to_free); cleanup_dir_rename_info(&info, dirs_removed, dir_rename_count != NULL); FREE_AND_NULL(rename_dst); @@ -1710,5 +1709,5 @@ void diffcore_rename_extended(struct diff_options *options, void diffcore_rename(struct diff_options *options) { - diffcore_rename_extended(options, NULL, NULL, NULL, NULL); + diffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL); } diff --git a/diffcore.h b/diffcore.h index b58ee6b1934..badc2261c20 100644 --- a/diffcore.h +++ b/diffcore.h @@ -181,6 +181,7 @@ void partial_clear_dir_rename_count(struct strmap *dir_rename_count); void diffcore_break(struct repository *, int); void diffcore_rename(struct diff_options *); void diffcore_rename_extended(struct diff_options *options, + struct mem_pool *pool, struct strintmap *relevant_sources, struct strintmap *dirs_removed, struct strmap *dir_rename_count, diff --git a/merge-ort.c b/merge-ort.c index e79830f9181..f4f0a3d57f0 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -690,7 +690,6 @@ static void path_msg(struct merge_options *opt, strbuf_addch(sb, '\n'); } -MAYBE_UNUSED static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool, const char *path) { @@ -712,7 +711,6 @@ static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool, return spec; } -MAYBE_UNUSED static struct diff_filepair *pool_diff_queue(struct mem_pool *pool, struct diff_queue_struct *queue, struct diff_filespec *one, @@ -930,6 +928,7 @@ static void add_pair(struct merge_options *opt, unsigned dir_rename_mask) { struct diff_filespec *one, *two; + struct mem_pool *pool = opt->priv->pool; struct rename_info *renames = &opt->priv->renames; int names_idx = is_add ? side : 0; @@ -980,11 +979,11 @@ static void add_pair(struct merge_options *opt, return; } - one = alloc_filespec(pathname); - two = alloc_filespec(pathname); + one = pool_alloc_filespec(pool, pathname); + two = pool_alloc_filespec(pool, pathname); fill_filespec(is_add ? two : one, &names[names_idx].oid, 1, names[names_idx].mode); - diff_queue(&renames->pairs[side], one, two); + pool_diff_queue(pool, &renames->pairs[side], one, two); } static void collect_rename_info(struct merge_options *opt, @@ -2893,6 +2892,7 @@ static void use_cached_pairs(struct merge_options *opt, { struct hashmap_iter iter; struct strmap_entry *entry; + struct mem_pool *pool = opt->priv->pool; /* * Add to side_pairs all entries from renames->cached_pairs[side_index]. @@ -2906,9 +2906,9 @@ static void use_cached_pairs(struct merge_options *opt, new_name = old_name; /* We don't care about oid/mode, only filenames and status */ - one = alloc_filespec(old_name); - two = alloc_filespec(new_name); - diff_queue(pairs, one, two); + one = pool_alloc_filespec(pool, old_name); + two = pool_alloc_filespec(pool, new_name); + pool_diff_queue(pool, pairs, one, two); pairs->queue[pairs->nr-1]->status = entry->value ? 'R' : 'D'; } } @@ -3016,6 +3016,7 @@ static int detect_regular_renames(struct merge_options *opt, diff_queued_diff = renames->pairs[side_index]; trace2_region_enter("diff", "diffcore_rename", opt->repo); diffcore_rename_extended(&diff_opts, + opt->priv->pool, &renames->relevant_sources[side_index], &renames->dirs_removed[side_index], &renames->dir_rename_count[side_index], @@ -3066,7 +3067,7 @@ static int collect_renames(struct merge_options *opt, if (p->status != 'A' && p->status != 'R') { possibly_cache_new_pair(renames, p, side_index, NULL); - diff_free_filepair(p); + pool_diff_free_filepair(opt->priv->pool, p); continue; } @@ -3079,7 +3080,7 @@ static int collect_renames(struct merge_options *opt, possibly_cache_new_pair(renames, p, side_index, new_path); if (p->status != 'R' && !new_path) { - diff_free_filepair(p); + pool_diff_free_filepair(opt->priv->pool, p); continue; } @@ -3197,7 +3198,7 @@ cleanup: side_pairs = &renames->pairs[s]; for (i = 0; i < side_pairs->nr; ++i) { struct diff_filepair *p = side_pairs->queue[i]; - diff_free_filepair(p); + pool_diff_free_filepair(opt->priv->pool, p); } } @@ -3210,7 +3211,8 @@ simple_cleanup: if (combined.nr) { int i; for (i = 0; i < combined.nr; i++) - diff_free_filepair(combined.queue[i]); + pool_diff_free_filepair(opt->priv->pool, + combined.queue[i]); free(combined.queue); } From patchwork Fri Jul 30 11:47:43 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411109 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 002F4C4320E for ; Fri, 30 Jul 2021 11:48:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E05F560EE6 for ; Fri, 30 Jul 2021 11:48:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238686AbhG3LsG (ORCPT ); Fri, 30 Jul 2021 07:48:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56092 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238739AbhG3Lr6 (ORCPT ); Fri, 30 Jul 2021 07:47:58 -0400 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 71ED1C0613D5 for ; Fri, 30 Jul 2021 04:47:53 -0700 (PDT) Received: by mail-wr1-x429.google.com with SMTP id n12so10981282wrr.2 for ; Fri, 30 Jul 2021 04:47:53 -0700 (PDT) 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=I+3F03G+KYmxjI0L6JdxmvBn1HFd+nJBLZJ0YJyORGI=; b=GbUg9MLz40g27+tFPzQkHYInFS7B4VHIJjzvQd0pn6GgARrwii+3ZWhj+i4XDiFKaQ m421gUUC4n5PCeNXSgLVWR6xTiLCearcWIaP9X8tP66tEP2xneQl1YRCXl2PGjvkMF/6 JJnMmV2BsH6oKMdtV/jnZgyGmHZQYtIje+YRRHKN0GnXT0+Duj7lh2gAXWrdLwU2WIaJ Lq6hV3aZD38XgQK4enpjpJBfGycHOTuN/gAqFnJ/j9kYnAWyjsbitvnjLOlVfK0ntNUZ x4C7GO4jcsaHKq0R5MUe2g4AvTmxsh8dekWpr9ePWFKuoZ/kZM1x2+RM1ZS08dN4W1xC qrig== 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=I+3F03G+KYmxjI0L6JdxmvBn1HFd+nJBLZJ0YJyORGI=; b=hfGPEx9ORlzJSDgeZBeUcdddjLhjZBmdz1XX8SVCglEpXpdG1ucriXjjGfxY5PK30D KjH5dTJfFYsceegGCPQ6pSRxuYHAZi1FR4gT19lapAlzjEhi2XIQ3UqBLLCigJAcwfU7 Hd9Yj6qtXUuirgPSbKDzjZ5bG1Oh/XrfnBvD0vlb9fIajRqbrkDoTG87XzYE2T4wpOQx zy2smClDqJojyK8/DBnPgbsRLSjmdvY25kv6dNbsFtmzawCV0j6WJoxi0srrJ1ctqor4 mwJocXznCgxNLT3fGIGhIBTWq6+OP3j4CGJ9FfHH2iw4ZtWei+Ieqt/dn9u2ldIYd05C i/DA== X-Gm-Message-State: AOAM531SpuyNtBHK4Q9wX0m2jvfBjSQUOxt8PfCoZ8ROeZv/dGha2uvl /MXr1FXwcEzg4FrZ5y2GahQZ3+l+mo0= X-Google-Smtp-Source: ABdhPJzG6PaiBOAm+mM4uPALo5CDBtkG7vXjebaD+NEqGH/SWRTHV1m+Wpq3j+PSoJPws8NyH7JdYg== X-Received: by 2002:adf:d22f:: with SMTP id k15mr2606258wrh.335.1627645672097; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id j1sm1545204wrm.86.2021.07.30.04.47.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:51 -0700 (PDT) Message-Id: <1556f0443c35a95fbdbc1cb1841f81f9c4615f4c.1627645665.git.gitgitgadget@gmail.com> In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:43 +0000 Subject: [PATCH v3 8/9] merge-ort: reuse path strings in pool_alloc_filespec MIME-Version: 1.0 Fcc: Sent To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren pool_alloc_filespec() was written so that the code when pool != NULL mimicked the code from alloc_filespec(), which including allocating enough extra space for the path and then copying it. However, the path passed to pool_alloc_filespec() is always going to already be in the same memory pool, so we may as well reuse it instead of copying it. For the testcases mentioned in commit 557ac0350d ("merge-ort: begin performance work; instrument with trace2_region_* calls", 2020-10-28), this change improves the performance as follows: Before After no-renames: 198.5 ms ± 3.4 ms 198.3 ms ± 2.9 ms mega-renames: 679.1 ms ± 5.6 ms 661.8 ms ± 5.9 ms just-one-mega: 271.9 ms ± 2.8 ms 264.6 ms ± 2.5 ms Signed-off-by: Elijah Newren --- merge-ort.c | 29 ++++++++++++++++++++++------- 1 file changed, 22 insertions(+), 7 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index f4f0a3d57f0..86ab8f60121 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -694,17 +694,13 @@ static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool, const char *path) { struct diff_filespec *spec; - size_t len; if (!pool) return alloc_filespec(path); - /* Same code as alloc_filespec, except allocate from pool */ - len = strlen(path); - - spec = mem_pool_calloc(pool, 1, st_add3(sizeof(*spec), len, 1)); - memcpy(spec+1, path, len); - spec->path = (void*)(spec+1); + /* Similar to alloc_filespec, but allocate from pool and reuse path */ + spec = mem_pool_calloc(pool, 1, sizeof(*spec)); + spec->path = (char*)path; /* spec won't modify it */ spec->count = 1; spec->is_binary = -1; @@ -2904,6 +2900,25 @@ static void use_cached_pairs(struct merge_options *opt, const char *new_name = entry->value; if (!new_name) new_name = old_name; + if (pool) { + /* + * cached_pairs has _copies* of old_name and new_name, + * because it has to persist across merges. When + * pool != NULL + * pool_alloc_filespec() will just re-use the existing + * filenames, which will also get re-used by + * opt->priv->paths if they become renames, and then + * get freed at the end of the merge, leaving the copy + * in cached_pairs dangling. Avoid this by making a + * copy here. + * + * When pool == NULL, pool_alloc_filespec() calls + * alloc_filespec(), which makes a copy; we don't want + * to add another. + */ + old_name = mem_pool_strdup(pool, old_name); + new_name = mem_pool_strdup(pool, new_name); + } /* We don't care about oid/mode, only filenames and status */ one = pool_alloc_filespec(pool, old_name); From patchwork Fri Jul 30 11:47:44 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Elijah Newren X-Patchwork-Id: 12411111 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 99864C432BE for ; Fri, 30 Jul 2021 11:48:03 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 8410F6052B for ; Fri, 30 Jul 2021 11:48:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S238728AbhG3LsH (ORCPT ); Fri, 30 Jul 2021 07:48:07 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S238714AbhG3LsA (ORCPT ); Fri, 30 Jul 2021 07:48:00 -0400 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 247C2C06179B for ; Fri, 30 Jul 2021 04:47:54 -0700 (PDT) Received: by mail-wr1-x429.google.com with SMTP id c16so10928974wrp.13 for ; Fri, 30 Jul 2021 04:47:54 -0700 (PDT) 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=x597iJhFZtqHN/owTNr70zLbjS3o+LrLy4Fac+UnZeU=; b=NVQ9bjTr7/cc8DFbpyr8nlSKreadW8a4/2NUadbeukD6X8d7eZxldzamHX8k7FWEfB LQladRyFql9R14o6dm22KamdwdDAxIhM1H/zKl37AqaqRlPTHlgAF05odUrPwsqxI+bV OsQakJ5BMU7k7I8MPDW1jN+0ADBBXLJMkr2a4sTKaAen9TdXUUU/vJJKq5Ux3PMH3Inf HXODGwNUnztX8Vxd5UPRDWm9nsvewBP/xk+QSlZ436RyEcb2ZnJDPvPyT3vrPZpQJqTn 4AYBvnOQwToXnF3liRIIUtgB/77wQrUWbZfdJ3vkktq1tD50rAktPP+lmRGBda7fipkN h/mQ== 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=x597iJhFZtqHN/owTNr70zLbjS3o+LrLy4Fac+UnZeU=; b=PkaqiEnpo79pTXd8mPiMu0/W5PxrUMFsdWHA9cy4YAR5Pl6hO53ax2rb3wUz5P6JCX g3S9SwqoXBUAB6VeOXMkiWIO8eBNlXAicaND0DAvHne3pfzPLb5KufMFiH2vmG7sqEZB mJKjWraz2ptS1G2N1aB9ryoa+zqGQ+rJyMVwLJZR/HvczsMOQQ1kFofuMfI6AyEolNRP 8ceSXtNFWRv9CpT05icgGaE4cwIiyVj12XhI3UAXrF0QNtczENhTpG6V5aVYacvihcy3 M5SsoBhGuxbCNR1OF3Sjj+WNu/uzxwySLAmnefneNWij8JmRAdzrxv93rXg8vxlngvnT pGfg== X-Gm-Message-State: AOAM5320Ocgz0GhtuM1wtDmkBb0jE0yIdQwmSCTkzVWWIK9M9leslwQL JRgNEgO+Si3mI83EDa81+VePLUmRpuY= X-Google-Smtp-Source: ABdhPJzFUbscPqaT03LBIipC6WvL9vWZBiKfjCcdtRphzKdWwCHBSpOx2f+fGBVwAqjROa3hXMCiJQ== X-Received: by 2002:adf:b1c5:: with SMTP id r5mr2684132wra.146.1627645672775; Fri, 30 Jul 2021 04:47:52 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id p4sm1377736wre.83.2021.07.30.04.47.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Jul 2021 04:47:52 -0700 (PDT) Message-Id: In-Reply-To: References: Date: Fri, 30 Jul 2021 11:47:44 +0000 Subject: [PATCH v3 9/9] merge-ort: remove compile-time ability to turn off usage of memory pools Fcc: Sent MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Eric Sunshine , Elijah Newren , Derrick Stolee , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren From: Elijah Newren Simplify code maintenance a bit by removing the ability to toggle between usage of memory pools and direct allocations. This allows us to also remove and simplify some auxiliary functions. Signed-off-by: Elijah Newren --- merge-ort.c | 63 +++++++++++++---------------------------------------- 1 file changed, 15 insertions(+), 48 deletions(-) diff --git a/merge-ort.c b/merge-ort.c index 86ab8f60121..63829f5cace 100644 --- a/merge-ort.c +++ b/merge-ort.c @@ -37,8 +37,6 @@ #include "unpack-trees.h" #include "xdiff-interface.h" -#define USE_MEMORY_POOL 1 /* faster, but obscures memory leak hunting */ - /* * We have many arrays of size 3. Whenever we have such an array, the * indices refer to one of the sides of the three-way merge. This is so @@ -623,11 +621,9 @@ static void clear_or_reinit_internal_opts(struct merge_options_internal *opti, strmap_clear(&opti->output, 0); } -#if USE_MEMORY_POOL mem_pool_discard(&opti->internal_pool, 0); if (!reinitialize) opti->pool = NULL; -#endif /* Clean out callback_data as well. */ FREE_AND_NULL(renames->callback_data); @@ -693,12 +689,10 @@ static void path_msg(struct merge_options *opt, static struct diff_filespec *pool_alloc_filespec(struct mem_pool *pool, const char *path) { + /* Similar to alloc_filespec(), but allocate from pool and reuse path */ struct diff_filespec *spec; - if (!pool) - return alloc_filespec(path); - - /* Similar to alloc_filespec, but allocate from pool and reuse path */ + assert(pool != NULL); spec = mem_pool_calloc(pool, 1, sizeof(*spec)); spec->path = (char*)path; /* spec won't modify it */ @@ -712,12 +706,10 @@ static struct diff_filepair *pool_diff_queue(struct mem_pool *pool, struct diff_filespec *one, struct diff_filespec *two) { + /* Same code as diff_queue(), except allocate from pool */ struct diff_filepair *dp; - if (!pool) - return diff_queue(queue, one, two); - - /* Same code as diff_queue, except allocate from pool */ + assert(pool != NULL); dp = mem_pool_calloc(pool, 1, sizeof(*dp)); dp->one = one; dp->two = two; @@ -726,27 +718,6 @@ static struct diff_filepair *pool_diff_queue(struct mem_pool *pool, return dp; } -static void *pool_calloc(struct mem_pool *pool, size_t count, size_t size) -{ - if (!pool) - return xcalloc(count, size); - return mem_pool_calloc(pool, count, size); -} - -static void *pool_alloc(struct mem_pool *pool, size_t size) -{ - if (!pool) - return xmalloc(size); - return mem_pool_alloc(pool, size); -} - -static void *pool_strndup(struct mem_pool *pool, const char *str, size_t len) -{ - if (!pool) - return xstrndup(str, len); - return mem_pool_strndup(pool, str, len); -} - /* add a string to a strbuf, but converting "/" to "_" */ static void add_flattened_path(struct strbuf *out, const char *s) { @@ -875,9 +846,9 @@ static void setup_path_info(struct merge_options *opt, assert(!df_conflict || !resolved); /* df_conflict implies !resolved */ assert(resolved == (merged_version != NULL)); - mi = pool_calloc(opt->priv->pool, 1, - resolved ? sizeof(struct merged_info) : - sizeof(struct conflict_info)); + mi = mem_pool_calloc(opt->priv->pool, 1, + resolved ? sizeof(struct merged_info) : + sizeof(struct conflict_info)); mi->directory_name = current_dir_name; mi->basename_offset = current_dir_name_len; mi->clean = !!resolved; @@ -1170,7 +1141,7 @@ static int collect_merge_info_callback(int n, len = traverse_path_len(info, p->pathlen); /* +1 in both of the following lines to include the NUL byte */ - fullpath = pool_alloc(opt->priv->pool, len + 1); + fullpath = mem_pool_alloc(opt->priv->pool, len + 1); make_traverse_path(fullpath, len + 1, info, p->path, p->pathlen); /* @@ -2389,9 +2360,9 @@ static void apply_directory_rename_modifications(struct merge_options *opt, /* Find the parent directory of cur_path */ char *last_slash = strrchr(cur_path, '/'); if (last_slash) { - parent_name = pool_strndup(opt->priv->pool, - cur_path, - last_slash - cur_path); + parent_name = mem_pool_strndup(opt->priv->pool, + cur_path, + last_slash - cur_path); } else { parent_name = opt->priv->toplevel_dir; break; @@ -3701,7 +3672,7 @@ static void process_entry(struct merge_options *opt, * the directory to remain here, so we need to move this * path to some new location. */ - new_ci = pool_calloc(opt->priv->pool, 1, sizeof(*new_ci)); + new_ci = mem_pool_calloc(opt->priv->pool, 1, sizeof(*new_ci)); /* We don't really want new_ci->merged.result copied, but it'll * be overwritten below so it doesn't matter. We also don't @@ -3794,7 +3765,8 @@ static void process_entry(struct merge_options *opt, const char *a_path = NULL, *b_path = NULL; int rename_a = 0, rename_b = 0; - new_ci = pool_alloc(opt->priv->pool, sizeof(*new_ci)); + new_ci = mem_pool_alloc(opt->priv->pool, + sizeof(*new_ci)); if (S_ISREG(a_mode)) rename_a = 1; @@ -4482,13 +4454,8 @@ static void merge_start(struct merge_options *opt, struct merge_result *result) /* Initialization of various renames fields */ renames = &opt->priv->renames; -#if USE_MEMORY_POOL mem_pool_init(&opt->priv->internal_pool, 0); - opt->priv->pool = &opt->priv->internal_pool; -#else - opt->priv->pool = NULL; -#endif - pool = opt->priv->pool; + pool = opt->priv->pool = &opt->priv->internal_pool; for (i = MERGE_SIDE1; i <= MERGE_SIDE2; i++) { strintmap_init_with_options(&renames->dirs_removed[i], NOT_RELEVANT, pool, 0);