| Message ID | pull.835.git.git.1598035949.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Add struct strmap and associated utility functions | expand |
On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote: > Here I introduce a new strmap type, which my new merge backed, merge-ort, > uses heavily. (I also made significant use of it in my changes to > diffcore-rename). This strmap type was based on Peff's proposal from a > couple years ago[1], but has additions that I made as I used it. I also > start the series off with a quick documentation improvement to hashmap.c to > differentiate between hashmap_free() and hashmap_free_entries(), since I > personally had difficulty understanding them and it affects how > strmap_clear()/strmap_free() are written. I like the direction overall (unsurprisingly), but left a bunch of comments. I do think if we're going to do this that it may be worth cleaning up hashmap a bit first, especially around its clear/free semantics, and its ability to lazy-allocate the table. I'm happy to work on that, but don't want to step on your toes. I also wonder if you looked at the khash stuff at all. Especially for storing integers, it makes things much more natural. You'd do something like: /* you might even be able to just write !strcmp in the macro below */ static inline int streq(const char *a, const char *b) { return !strcmp(a, b); } KHASH_INIT(strint_map, char *, int, 1, strhash, streq); and then you'd probably want a "put" wrapper that makes a copy of the string. khash has its own charming awkwardness, but I'm just curious if you looked at it and found it more awkward than hashmap.c, or if you just didn't look at it. -Peff
On Fri, Aug 21, 2020 at 1:16 PM Jeff King <peff@peff.net> wrote: > > On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote: > > > Here I introduce a new strmap type, which my new merge backed, merge-ort, > > uses heavily. (I also made significant use of it in my changes to > > diffcore-rename). This strmap type was based on Peff's proposal from a > > couple years ago[1], but has additions that I made as I used it. I also > > start the series off with a quick documentation improvement to hashmap.c to > > differentiate between hashmap_free() and hashmap_free_entries(), since I > > personally had difficulty understanding them and it affects how > > strmap_clear()/strmap_free() are written. > > I like the direction overall (unsurprisingly), but left a bunch of > comments. I do think if we're going to do this that it may be worth > cleaning up hashmap a bit first, especially around its clear/free > semantics, and its ability to lazy-allocate the table. > > I'm happy to work on that, but don't want to step on your toes. I have patches which introduce hashmap_clear() and hashmap_clear_entries() to hashmap.[ch], which allowed me to simplify strmap_clear(); instead of needing to call both hashmap_free[_entries]() && strmap_init(), I could just call hashmap_clear[_entries](). Doing that surprised me with a significant performance impact (in a good direction), at which point I started adding mem-pool integration into hashmap for storing the entries that hashmap.c allocates and got further good speedups. I thought those were better explained when I got to the performance stuff, so I had held off on those patches. I could pull them out and submit them first. However, there's an important difference here between what I've done and what you've suggested for hashmap: my method did not deallocate hashmap->table in hashmap_clear() and then use lazy initialization. In fact, I think not deallocating the table was part of the charm -- the table had already naturally grown to the right size, and because the repository has approximately the same number of paths in various commits, this provided me a way of getting a table preallocated to a reasonable size for all merges after the first (and there are multiple merges either when recursiveness is needed due to multiple merge bases, OR when rebasing or cherry-picking a sequence of commits). This prevented, as hashmap.h puts it, "expensive resizing". So, once again, my performance ideas might be clashing with some of your desires for the API. Any clever ideas for resolving that? Also, since you want to see hashmap cleanup first, should I submit just the hashmap_clear[_entries()] stuff, or should I also submit the API additions to allow mem-pool integration in hashmap (it's pretty small and self-contained, but it'll be a while before I submit the patches that use it...)? > I also wonder if you looked at the khash stuff at all. Especially for > storing integers, it makes things much more natural. You'd do something > like: > > /* you might even be able to just write !strcmp in the macro below */ > static inline int streq(const char *a, const char *b) > { > return !strcmp(a, b); > } > > KHASH_INIT(strint_map, char *, int, 1, strhash, streq); > > and then you'd probably want a "put" wrapper that makes a copy of the > string. khash has its own charming awkwardness, but I'm just curious if you > looked at it and found it more awkward than hashmap.c, or if you just > didn't look at it. I did look at it, but only briefly. I had a further investigation on my TODO list for months, along with several other improvement ideas. But it seemed like my TODO list was really long, and my new merge backend hasn't benefited anyone yet. At some point, I decided to punt on it and other ideas and start cleaning up my code and submitting. I believe merge-ort is more accurate than merge-recursive (it fixes several test_expect_failures) and is a lot faster as well for the cases I'm looking at. So, for now, I've pulled it off my radar. But I'd be really happy if someone else wanted to jump in and try switching out hashmap for khash in the strmap API and see if it helps merge-ort performance. :-)
On Fri, Aug 21, 2020 at 2:33 PM Elijah Newren <newren@gmail.com> wrote: > > On Fri, Aug 21, 2020 at 1:16 PM Jeff King <peff@peff.net> wrote: > > > > On Fri, Aug 21, 2020 at 06:52:24PM +0000, Elijah Newren via GitGitGadget wrote: > > > > > Here I introduce a new strmap type, which my new merge backed, merge-ort, > > > uses heavily. (I also made significant use of it in my changes to > > > diffcore-rename). This strmap type was based on Peff's proposal from a > > > couple years ago[1], but has additions that I made as I used it. I also > > > start the series off with a quick documentation improvement to hashmap.c to > > > differentiate between hashmap_free() and hashmap_free_entries(), since I > > > personally had difficulty understanding them and it affects how > > > strmap_clear()/strmap_free() are written. > > > > I like the direction overall (unsurprisingly), but left a bunch of > > comments. I do think if we're going to do this that it may be worth > > cleaning up hashmap a bit first, especially around its clear/free > > semantics, and its ability to lazy-allocate the table. > > > > I'm happy to work on that, but don't want to step on your toes. > > I have patches which introduce hashmap_clear() and > hashmap_clear_entries() to hashmap.[ch], which allowed me to simplify > strmap_clear(); instead of needing to call both > hashmap_free[_entries]() && strmap_init(), I could just call > hashmap_clear[_entries](). Doing that surprised me with a significant > performance impact (in a good direction), at which point I started > adding mem-pool integration into hashmap for storing the entries that > hashmap.c allocates and got further good speedups. > > I thought those were better explained when I got to the performance > stuff, so I had held off on those patches. I could pull them out and > submit them first. > > However, there's an important difference here between what I've done > and what you've suggested for hashmap: my method did not deallocate > hashmap->table in hashmap_clear() and then use lazy initialization. > In fact, I think not deallocating the table was part of the charm -- > the table had already naturally grown to the right size, and because > the repository has approximately the same number of paths in various > commits, this provided me a way of getting a table preallocated to a > reasonable size for all merges after the first (and there are multiple > merges either when recursiveness is needed due to multiple merge > bases, OR when rebasing or cherry-picking a sequence of commits). > This prevented, as hashmap.h puts it, "expensive resizing". > > So, once again, my performance ideas might be clashing with some of > your desires for the API. Any clever ideas for resolving that? > > Also, since you want to see hashmap cleanup first, should I submit > just the hashmap_clear[_entries()] stuff, or should I also submit the > API additions to allow mem-pool integration in hashmap (it's pretty > small and self-contained, but it'll be a while before I submit the > patches that use it...)? Nevermind, I mis-remembered. The mempool integration was added specifically to strmap, not to hashmap, because strmap_put() does the allocation of the str_entry. So I'll just pull out the hashmap_clear[_entries]() stuff and send it up. > > > I also wonder if you looked at the khash stuff at all. Especially for > > storing integers, it makes things much more natural. You'd do something > > like: > > > > /* you might even be able to just write !strcmp in the macro below */ > > static inline int streq(const char *a, const char *b) > > { > > return !strcmp(a, b); > > } > > > > KHASH_INIT(strint_map, char *, int, 1, strhash, streq); > > > > and then you'd probably want a "put" wrapper that makes a copy of the > > string. khash has its own charming awkwardness, but I'm just curious if you > > looked at it and found it more awkward than hashmap.c, or if you just > > didn't look at it. > > I did look at it, but only briefly. I had a further investigation on > my TODO list for months, along with several other improvement ideas. > But it seemed like my TODO list was really long, and my new merge > backend hasn't benefited anyone yet. At some point, I decided to punt > on it and other ideas and start cleaning up my code and submitting. I > believe merge-ort is more accurate than merge-recursive (it fixes > several test_expect_failures) and is a lot faster as well for the > cases I'm looking at. So, for now, I've pulled it off my radar. > > But I'd be really happy if someone else wanted to jump in and try > switching out hashmap for khash in the strmap API and see if it helps > merge-ort performance. :-)
On Fri, Aug 21, 2020 at 02:33:54PM -0700, Elijah Newren wrote: > However, there's an important difference here between what I've done > and what you've suggested for hashmap: my method did not deallocate > hashmap->table in hashmap_clear() and then use lazy initialization. > In fact, I think not deallocating the table was part of the charm -- > the table had already naturally grown to the right size, and because > the repository has approximately the same number of paths in various > commits, this provided me a way of getting a table preallocated to a > reasonable size for all merges after the first (and there are multiple > merges either when recursiveness is needed due to multiple merge > bases, OR when rebasing or cherry-picking a sequence of commits). > This prevented, as hashmap.h puts it, "expensive resizing". > > So, once again, my performance ideas might be clashing with some of > your desires for the API. Any clever ideas for resolving that? If the magic is in pre-sizing the hash, then it seems like the callers ought to be feeding the size hint. That does make a little more work for them, but I think there's real value in having consistent semantics for "clear" across our data structures. However, one cheat would be to free the memory but retain the size hint after a clear. And then if we lazy-init, grow immediately to the hint size. That's more expensive than a true reuse, because we do reallocate the memory. But it avoids the repeated re-allocation during growth. It may also be a sign that we should be growing the hash more aggressively in the first place. Of course all of this is predicated having some benchmarks. It would be useful to know which part actually provided the speedup. -Peff
On Fri, Aug 28, 2020 at 12:03 AM Jeff King <peff@peff.net> wrote: > > On Fri, Aug 21, 2020 at 02:33:54PM -0700, Elijah Newren wrote: > > > However, there's an important difference here between what I've done > > and what you've suggested for hashmap: my method did not deallocate > > hashmap->table in hashmap_clear() and then use lazy initialization. > > In fact, I think not deallocating the table was part of the charm -- > > the table had already naturally grown to the right size, and because > > the repository has approximately the same number of paths in various > > commits, this provided me a way of getting a table preallocated to a > > reasonable size for all merges after the first (and there are multiple > > merges either when recursiveness is needed due to multiple merge > > bases, OR when rebasing or cherry-picking a sequence of commits). > > This prevented, as hashmap.h puts it, "expensive resizing". > > > > So, once again, my performance ideas might be clashing with some of > > your desires for the API. Any clever ideas for resolving that? > > If the magic is in pre-sizing the hash, then it seems like the callers > ought to be feeding the size hint. That does make a little more work for > them, but I think there's real value in having consistent semantics for > "clear" across our data structures. I thought about adding a size hint from the callers, but the thing is I don't know how to get a good one short of running a merge and querying how big things were sized in that merge. (In some common cases I can get an upper bound, but I can't get it in all cases and that upper bound might be a couple orders of magnitude too big.) Thus, it's really a case where I just punt on pre-sizing for the first merge, and use the size from the previous merge for subsequent ones. If you have a non-recursive merge or are cherry-picking only a single commit, then no sizing hint is used. > However, one cheat would be to free the memory but retain the size hint > after a clear. And then if we lazy-init, grow immediately to the hint > size. That's more expensive than a true reuse, because we do reallocate > the memory. But it avoids the repeated re-allocation during growth. > > It may also be a sign that we should be growing the hash more > aggressively in the first place. Of course all of this is predicated > having some benchmarks. It would be useful to know which part actually > provided the speedup. Your thoughts here are great; I also had another one this past week -- I could introduce a hashmap_partial_clear() (in addition to hashmap_clear()) for the special usecase I have of leaving the table allocated and pre-sized. It'd prevent people from accidentally using it and forgetting to free stuff, while still allowing me to take advantage. But, as you say, more benchmarks would be useful to find which parts provided the speedup before taking any of these steps.
On Fri, Aug 28, 2020 at 08:29:44AM -0700, Elijah Newren wrote: > > It may also be a sign that we should be growing the hash more > > aggressively in the first place. Of course all of this is predicated > > having some benchmarks. It would be useful to know which part actually > > provided the speedup. > > Your thoughts here are great; I also had another one this past week -- > I could introduce a hashmap_partial_clear() (in addition to > hashmap_clear()) for the special usecase I have of leaving the table > allocated and pre-sized. It'd prevent people from accidentally using > it and forgetting to free stuff, while still allowing me to take > advantage. But, as you say, more benchmarks would be useful to find > which parts provided the speedup before taking any of these steps. Yeah, having a separate function to explicitly do "remove all elements but keep the table allocated" would be fine with me. My big desire is that clear() should do the safe, non-leaking thing by default. -Peff