From: Elijah Newren <newren@gmail.com>
To: Jeff King <peff@peff.net>
Cc: Elijah Newren via GitGitGadget <gitgitgadget@gmail.com>,
Git Mailing List <git@vger.kernel.org>
Subject: Re: [PATCH 4/5] strmap: add strdup_strings option
Date: Fri, 21 Aug 2020 13:41:44 -0700 [thread overview]
Message-ID: <CABPp-BGJK4C7U+-MB-+TUgFAuuFJKE-E7y17FFJDRTyFydVX2A@mail.gmail.com> (raw)
In-Reply-To: <20200821200121.GF1165@coredump.intra.peff.net>
On Fri, Aug 21, 2020 at 1:01 PM Jeff King <peff@peff.net> wrote:
>
> On Fri, Aug 21, 2020 at 06:52:28PM +0000, Elijah Newren via GitGitGadget wrote:
>
> > From: Elijah Newren <newren@gmail.com>
> >
> > Just as it is sometimes useful for string_list to duplicate and take
> > ownership of memory management of the strings it contains, the same is
> > sometimes true for strmaps as well. Add the same flag from string_list
> > to strmap.
>
> This is actually one of the ugliest parts of string_list, IMHO, and I'd
> prefer if we can avoid duplicating it. Yes, sometimes we can manage to
> avoid an extra copy of a string. But the resulting ownership and
> lifetime questions are often very error-prone. In other data structures
> we've moved towards just having the structure own its data (e.g.,
> strvec does so, and things like oidmap store their own oids). I've been
> happy with the simplicity of it.
>
> It also works if you use a flex-array for the key storage in the
> strmap_entry. :)
I can see how it's easier, but that worries me about the number of
extra copies for my usecase. In order to minimize actual computation,
I track an awful lot of auxiliary data in merge-ort so that I know
when I can safely perform many different case-specific optimizations.
Among other things, this means 15 strmaps. 1 of those stores a
mapping from all paths that traverse_trees() walks over (file or
directory) to metadata about the content on the three different sides.
9 of the remaining 14 simply share the strings in the main strmap,
because I don't need extra copies of the paths in the repository. I
could (and maybe should) extend that to 11 of the 14. Only 3 actually
do need to store a copy of the paths (because they store data used
beyond the end of an inner recursive merge or can be used to
accelerate subsequent commits in a rebase or cherry-pick sequence).
So, in most my cases, I don't want to duplicate strings. I actually
started my implementation using FLEX_ALLOC_STR(), as you suggested
earlier in this thread, but tossed it because of this same desire to
not duplicate strings but just share them between the strmaps.
Granted, I made that decision before I had a complete implementation,
so I didn't measure the actual costs. It's possible that was a
premature optimization.
next prev parent reply other threads:[~2020-08-21 20:42 UTC|newest]
Thread overview: 144+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-08-21 18:52 [PATCH 0/5] Add struct strmap and associated utility functions Elijah Newren via GitGitGadget
2020-08-21 18:52 ` [PATCH 1/5] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-08-21 19:22 ` Jeff King
2020-08-21 18:52 ` [PATCH 2/5] strmap: new utility functions Elijah Newren via GitGitGadget
2020-08-21 19:48 ` Jeff King
2020-08-21 18:52 ` [PATCH 3/5] strmap: add more " Elijah Newren via GitGitGadget
2020-08-21 19:58 ` Jeff King
2020-08-21 18:52 ` [PATCH 4/5] strmap: add strdup_strings option Elijah Newren via GitGitGadget
2020-08-21 20:01 ` Jeff King
2020-08-21 20:41 ` Elijah Newren [this message]
2020-08-21 21:03 ` Jeff King
2020-08-21 22:25 ` Elijah Newren
2020-08-28 7:08 ` Jeff King
2020-08-28 17:20 ` Elijah Newren
2020-08-21 18:52 ` [PATCH 5/5] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-08-21 20:10 ` Jeff King
2020-08-21 20:51 ` Elijah Newren
2020-08-21 21:05 ` Jeff King
2020-08-21 20:16 ` [PATCH 0/5] Add struct strmap and associated utility functions Jeff King
2020-08-21 21:33 ` Elijah Newren
2020-08-21 22:28 ` Elijah Newren
2020-08-28 7:03 ` Jeff King
2020-08-28 15:29 ` Elijah Newren
2020-09-01 9:27 ` Jeff King
2020-10-13 0:40 ` [PATCH v2 00/10] " Elijah Newren via GitGitGadget
2020-10-13 0:40 ` [PATCH v2 01/10] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-10-30 12:50 ` Jeff King
2020-10-30 19:55 ` Elijah Newren
2020-11-03 16:26 ` Jeff King
2020-11-03 16:48 ` Elijah Newren
2020-10-13 0:40 ` [PATCH v2 02/10] hashmap: adjust spacing to fix argument alignment Elijah Newren via GitGitGadget
2020-10-30 12:51 ` Jeff King
2020-10-13 0:40 ` [PATCH v2 03/10] hashmap: allow re-use after hashmap_free() Elijah Newren via GitGitGadget
2020-10-30 13:35 ` Jeff King
2020-10-30 15:37 ` Elijah Newren
2020-11-03 16:08 ` Jeff King
2020-11-03 16:16 ` Elijah Newren
2020-10-13 0:40 ` [PATCH v2 04/10] hashmap: introduce a new hashmap_partial_clear() Elijah Newren via GitGitGadget
2020-10-30 13:41 ` Jeff King
2020-10-30 16:03 ` Elijah Newren
2020-11-03 16:10 ` Jeff King
2020-10-13 0:40 ` [PATCH v2 05/10] strmap: new utility functions Elijah Newren via GitGitGadget
2020-10-30 14:12 ` Jeff King
2020-10-30 16:26 ` Elijah Newren
2020-10-13 0:40 ` [PATCH v2 06/10] strmap: add more " Elijah Newren via GitGitGadget
2020-10-30 14:23 ` Jeff King
2020-10-30 16:43 ` Elijah Newren
2020-11-03 16:12 ` Jeff King
2020-10-13 0:40 ` [PATCH v2 07/10] strmap: enable faster clearing and reusing of strmaps Elijah Newren via GitGitGadget
2020-10-30 14:27 ` Jeff King
2020-10-13 0:40 ` [PATCH v2 08/10] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-10-30 14:39 ` Jeff King
2020-10-30 17:28 ` Elijah Newren
2020-11-03 16:20 ` Jeff King
2020-11-03 16:46 ` Elijah Newren
2020-10-13 0:40 ` [PATCH v2 09/10] strmap: add a strset sub-type Elijah Newren via GitGitGadget
2020-10-30 14:44 ` Jeff King
2020-10-30 18:02 ` Elijah Newren
2020-10-13 0:40 ` [PATCH v2 10/10] strmap: enable allocations to come from a mem_pool Elijah Newren via GitGitGadget
2020-10-30 14:56 ` Jeff King
2020-10-30 19:31 ` Elijah Newren
2020-11-03 16:24 ` Jeff King
2020-11-02 18:55 ` [PATCH v3 00/13] Add struct strmap and associated utility functions Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 01/13] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 02/13] hashmap: adjust spacing to fix argument alignment Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 03/13] hashmap: allow re-use after hashmap_free() Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 04/13] hashmap: introduce a new hashmap_partial_clear() Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 05/13] hashmap: provide deallocation function names Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 06/13] strmap: new utility functions Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 07/13] strmap: add more " Elijah Newren via GitGitGadget
2020-11-04 20:13 ` Jeff King
2020-11-04 20:24 ` Elijah Newren
2020-11-02 18:55 ` [PATCH v3 08/13] strmap: enable faster clearing and reusing of strmaps Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 09/13] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-11-04 20:21 ` Jeff King
2020-11-02 18:55 ` [PATCH v3 10/13] strmap: add a strset sub-type Elijah Newren via GitGitGadget
2020-11-04 20:31 ` Jeff King
2020-11-02 18:55 ` [PATCH v3 11/13] strmap: enable allocations to come from a mem_pool Elijah Newren via GitGitGadget
2020-11-02 18:55 ` [PATCH v3 12/13] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Elijah Newren via GitGitGadget
2020-11-04 20:43 ` Jeff King
2020-11-02 18:55 ` [PATCH v3 13/13] Use new HASHMAP_INIT macro to simplify hashmap initialization Elijah Newren via GitGitGadget
2020-11-04 20:48 ` Jeff King
2020-11-04 20:52 ` [PATCH v3 00/13] Add struct strmap and associated utility functions Jeff King
2020-11-04 22:20 ` Elijah Newren
2020-11-05 0:22 ` [PATCH v4 " Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 01/13] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 02/13] hashmap: adjust spacing to fix argument alignment Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 03/13] hashmap: allow re-use after hashmap_free() Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 04/13] hashmap: introduce a new hashmap_partial_clear() Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 05/13] hashmap: provide deallocation function names Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 06/13] strmap: new utility functions Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 07/13] strmap: add more " Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 08/13] strmap: enable faster clearing and reusing of strmaps Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 09/13] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 10/13] strmap: add a strset sub-type Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 11/13] strmap: enable allocations to come from a mem_pool Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 12/13] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Elijah Newren via GitGitGadget
2020-11-05 0:22 ` [PATCH v4 13/13] Use new HASHMAP_INIT macro to simplify hashmap initialization Elijah Newren via GitGitGadget
2020-11-05 13:29 ` [PATCH v4 00/13] Add struct strmap and associated utility functions Jeff King
2020-11-05 20:25 ` Junio C Hamano
2020-11-05 21:17 ` Jeff King
2020-11-05 21:22 ` Elijah Newren
2020-11-05 22:15 ` Junio C Hamano
2020-11-06 0:24 ` [PATCH v5 00/15] " Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 01/15] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 02/15] hashmap: adjust spacing to fix argument alignment Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 03/15] hashmap: allow re-use after hashmap_free() Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 04/15] hashmap: introduce a new hashmap_partial_clear() Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 05/15] hashmap: provide deallocation function names Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 06/15] strmap: new utility functions Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 07/15] strmap: add more " Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 08/15] strmap: enable faster clearing and reusing of strmaps Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 09/15] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 10/15] strmap: split create_entry() out of strmap_put() Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 11/15] strmap: add a strset sub-type Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 12/15] strmap: enable allocations to come from a mem_pool Elijah Newren via GitGitGadget
2020-11-11 17:33 ` Phillip Wood
2020-11-11 18:49 ` Elijah Newren
2020-11-11 19:01 ` Jeff King
2020-11-11 20:34 ` Chris Torek
2020-11-06 0:24 ` [PATCH v5 13/15] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 14/15] Use new HASHMAP_INIT macro to simplify hashmap initialization Elijah Newren via GitGitGadget
2020-11-06 0:24 ` [PATCH v5 15/15] shortlog: use strset from strmap.h Elijah Newren via GitGitGadget
2020-11-06 2:00 ` [PATCH v5 00/15] Add struct strmap and associated utility functions Junio C Hamano
2020-11-06 2:42 ` Elijah Newren
2020-11-06 2:48 ` Jeff King
2020-11-06 17:32 ` Junio C Hamano
2020-11-11 20:02 ` [PATCH v6 " Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 01/15] hashmap: add usage documentation explaining hashmap_free[_entries]() Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 02/15] hashmap: adjust spacing to fix argument alignment Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 03/15] hashmap: allow re-use after hashmap_free() Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 04/15] hashmap: introduce a new hashmap_partial_clear() Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 05/15] hashmap: provide deallocation function names Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 06/15] strmap: new utility functions Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 07/15] strmap: add more " Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 08/15] strmap: enable faster clearing and reusing of strmaps Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 09/15] strmap: add functions facilitating use as a string->int map Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 10/15] strmap: split create_entry() out of strmap_put() Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 11/15] strmap: add a strset sub-type Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 12/15] strmap: enable allocations to come from a mem_pool Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 13/15] strmap: take advantage of FLEXPTR_ALLOC_STR when relevant Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 14/15] Use new HASHMAP_INIT macro to simplify hashmap initialization Elijah Newren via GitGitGadget
2020-11-11 20:02 ` [PATCH v6 15/15] shortlog: use strset from strmap.h Elijah Newren via GitGitGadget
2020-11-11 20:07 ` [PATCH v6 00/15] Add struct strmap and associated utility functions Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CABPp-BGJK4C7U+-MB-+TUgFAuuFJKE-E7y17FFJDRTyFydVX2A@mail.gmail.com \
--to=newren@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitgitgadget@gmail.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.