From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-Status: No, score=-3.7 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_PASS, SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by dcvr.yhbt.net (Postfix) with ESMTP id E03331F66F for ; Thu, 5 Nov 2020 00:24:42 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1732790AbgKEAYg (ORCPT ); Wed, 4 Nov 2020 19:24:36 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54118 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1731212AbgKEAW4 (ORCPT ); Wed, 4 Nov 2020 19:22:56 -0500 Received: from mail-wm1-x341.google.com (mail-wm1-x341.google.com [IPv6:2a00:1450:4864:20::341]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id B0139C0613D2 for ; Wed, 4 Nov 2020 16:22:55 -0800 (PST) Received: by mail-wm1-x341.google.com with SMTP id p22so30118wmg.3 for ; Wed, 04 Nov 2020 16:22:55 -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=egrP2YxGIqUqE7lI0Iu1Sp/CnRg8F1CK39E/Ny45G70=; b=kWjxaYB3uIL+1bhIUD2NOq/wXKTihOfLRMUcunx0b3d9hQ/qB8Dmj/p3SfBuIqpKfJ KLZcHiD/FCxsHrNaj2xgHSvs2NUqvGyiaE+Ru8wSyIYih6g1S9arnMGtsGaL+psMkCT0 5abQuoSMhhTpMtvbX+JJSpPWDEiK738w1MenaezEVghEaI9Xt7WjON9FCliQ5shfJ3s5 0ZcF9+pILUkVucw0v4hXQBTIKZ35JarpjFmlXBW2bgrlTQJnRsR2axDXIccMW3eqt47z 2HzuZaNlD5tsVoUKmqAoTKbQaY/fFXogct74J0HR24t/qIwbslV2N96rhp5ncA6318se 8UFg== 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=egrP2YxGIqUqE7lI0Iu1Sp/CnRg8F1CK39E/Ny45G70=; b=m5uN1l/HWwVVewn0y+I4l9PxoR0LzI+8FftOehaE3i6IdvgBFdkcwXhpTGAYfvJJQh JnY40kDPAjyCnduKfVL8SR+oKA5TrfbJ0IBGKmo8N+Rv7JxvoRtY2sm1GyehEYXSFXoV IAAvZQ3tkazyAg7vpyiP64BpyAj3UCM0YWzOI8SkgWe7ANrDR8Mq3l88G7qS7MPv7fiW sG0BJ1qUmIbdH4Lujqd6QtVg/HB/xLonsO4SimKARUL/3gah/iuQDyGTChc9ADX7ABkP unqPtRT7o1+BBWVTEQhESkPdfD7BouQ0VhsMjqotj9yxaD+VGcEMG68OPQrVnSfvdNAH hgrA== X-Gm-Message-State: AOAM531bHmpBqGDDPYXYVt4eIRyFhJUy+ocrM5tKcNg5JbvOCDPsaavN UNV9kzjGjKxYiQYAIgZhHUGQ1z7Rwas= X-Google-Smtp-Source: ABdhPJwR0Nb4BdqDgkehvZBl/We3ZUvu/DfhsqVP9n21wyZ/jhUtTOyRZ0ITvOtp/+RdbKR/TTpP3A== X-Received: by 2002:a1c:3b87:: with SMTP id i129mr87048wma.134.1604535774251; Wed, 04 Nov 2020 16:22:54 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id x1sm4872781wrl.41.2020.11.04.16.22.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 04 Nov 2020 16:22:53 -0800 (PST) Message-Id: In-Reply-To: References: From: "Elijah Newren via GitGitGadget" Date: Thu, 05 Nov 2020 00:22:40 +0000 Subject: [PATCH v4 08/13] strmap: enable faster clearing and reusing of strmaps Fcc: Sent Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit MIME-Version: 1.0 To: git@vger.kernel.org Cc: Jeff King , Elijah Newren , Elijah Newren , Elijah Newren Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org From: Elijah Newren When strmaps are used heavily, such as is done by my new merge-ort algorithm, and strmaps need to be cleared but then re-used (because of e.g. picking multiple commits to cherry-pick, or due to a recursive merge having several different merges while recursing), free-ing and reallocating map->table repeatedly can add up in time, especially since it will likely be reallocated to a much smaller size but the previous merge provides a good guide to the right size to use for the next merge. Introduce strmap_partial_clear() to take advantage of this type of situation; it will act similar to strmap_clear() except that map->table's entries are zeroed instead of map->table being free'd. Making use of this function reduced the cost of clear_or_reinit_internal_opts() by about 20% in mert-ort, and dropped the overall runtime of my rebase testcase by just under 2%. Signed-off-by: Elijah Newren --- strmap.c | 6 ++++++ strmap.h | 6 ++++++ 2 files changed, 12 insertions(+) diff --git a/strmap.c b/strmap.c index 829f1bc095..c410c5241a 100644 --- a/strmap.c +++ b/strmap.c @@ -64,6 +64,12 @@ void strmap_clear(struct strmap *map, int free_values) hashmap_clear(&map->map); } +void strmap_partial_clear(struct strmap *map, int free_values) +{ + strmap_free_entries_(map, free_values); + hashmap_partial_clear(&map->map); +} + void *strmap_put(struct strmap *map, const char *str, void *data) { struct strmap_entry *entry = find_strmap_entry(map, str); diff --git a/strmap.h b/strmap.h index f74bc582e4..c14fcee148 100644 --- a/strmap.h +++ b/strmap.h @@ -42,6 +42,12 @@ void strmap_init_with_options(struct strmap *map, */ void strmap_clear(struct strmap *map, int free_values); +/* + * Similar to strmap_clear() but leaves map->map->table allocated and + * pre-sized so that subsequent uses won't need as many rehashings. + */ +void strmap_partial_clear(struct strmap *map, int free_values); + /* * Insert "str" into the map, pointing to "data". * -- gitgitgadget