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-ASN: AS53758 23.128.96.0/24 X-Spam-Status: No, score=-3.9 required=3.0 tests=AWL,BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE, 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 A47771F8C6 for ; Sun, 27 Jun 2021 02:47:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230354AbhF0Ctm (ORCPT ); Sat, 26 Jun 2021 22:49:42 -0400 Received: from dcvr.yhbt.net ([64.71.152.64]:60426 "EHLO dcvr.yhbt.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230104AbhF0Ctl (ORCPT ); Sat, 26 Jun 2021 22:49:41 -0400 Received: from localhost (dcvr.yhbt.net [127.0.0.1]) by dcvr.yhbt.net (Postfix) with ESMTP id DA7AC1F8C6; Sun, 27 Jun 2021 02:47:18 +0000 (UTC) From: Eric Wong To: git@vger.kernel.org Cc: Jeff King , =?UTF-8?q?Ren=C3=A9=20Scharfe?= Subject: [PATCH 0/5] optimizations for many odb alternates Date: Sun, 27 Jun 2021 02:47:13 +0000 Message-Id: <20210627024718.25383-1-e@80x24.org> In-Reply-To: <20210624005806.12079-1-e@80x24.org> References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Cc-ing Rene and Peff for their previous work on loose object caching speedups (and also Peff on crit-bit trees). I'm expecting a use case involving tens of thousands of repos being tied together by alternates. I realize this is an odd case, but there's some fairly small changes that give significant speedups and memory savings. I can't seem to get consistent benchmarks on my workstation (since it doubles as a public-facing server :x), but things seem generally in the ballpark... 1/5 is a resend and the biggest obvious time improvement (at some cost to space). 2/5 and 4/5 are pretty obvious; 3/5 should be obvious, too, but my arithmetic is terrible :x 5/5 is a big (and easily measured) space improvement that will negate space regression caused by 1/5 (and then some). I'm not sure if there's much or any change in time in either direction, though... Eric Wong (5): speed up alt_odb_usable() with many alternates avoid strlen via strbuf_addstr in link_alt_odb_entry make object_directory.loose_objects_subdir_seen a bitmap oidcpy_with_padding: constify `src' arg oidtree: a crit-bit tree for odb_loose_cache Makefile | 3 + alloc.c | 6 ++ alloc.h | 1 + cbtree.c | 167 ++++++++++++++++++++++++++++++++++++++++ cbtree.h | 56 ++++++++++++++ hash.h | 2 +- object-file.c | 68 +++++++++------- object-name.c | 28 +++---- object-store.h | 24 +++++- object.c | 2 + oidtree.c | 94 ++++++++++++++++++++++ oidtree.h | 29 +++++++ t/helper/test-oidtree.c | 45 +++++++++++ t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + t/t0069-oidtree.sh | 52 +++++++++++++ 16 files changed, 530 insertions(+), 49 deletions(-) create mode 100644 cbtree.c create mode 100644 cbtree.h create mode 100644 oidtree.c create mode 100644 oidtree.h create mode 100644 t/helper/test-oidtree.c create mode 100755 t/t0069-oidtree.sh