* [GSoC] How to protect cached_objects @ 2019-05-23 16:51 Matheus Tavares Bernardino 2019-05-24 6:13 ` Jeff King 2019-05-24 9:55 ` Duy Nguyen 0 siblings, 2 replies; 6+ messages in thread From: Matheus Tavares Bernardino @ 2019-05-23 16:51 UTC (permalink / raw) To: git Cc: Christian Couder, Nguyễn Thái Ngọc Duy, Оля Тележная Hi, everyone As one of my first tasks in GSoC, I'm looking to protect the global states at sha1-file.c for future parallelizations. Currently, I'm analyzing how to deal with the cached_objects array, which is a small set of in-memory objects that read_object_file() is able to return although they don't really exist on disk. The only current user of this set is git-blame, which adds a fake commit containing non-committed changes. As it is now, if we start parallelizing blame, cached_objects won't be a problem since it is written to only once, at the beginning, and read from a couple times latter, with no possible race conditions. But should we make these operations thread safe for future uses that could involve potential parallel writes and reads too? If so, we have two options: - Make the array thread local, which would oblige us to replicate data, or - Protect it with locks, which could impact the sequential performance. We could have a macro here, to skip looking on single-threaded use cases. But we don't know, a priori, the number of threads that would want to use the pack access code. Any thought on this? Thanks, Matheus Tavares ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GSoC] How to protect cached_objects 2019-05-23 16:51 [GSoC] How to protect cached_objects Matheus Tavares Bernardino @ 2019-05-24 6:13 ` Jeff King 2019-05-25 14:42 ` Matheus Tavares Bernardino 2019-05-24 9:55 ` Duy Nguyen 1 sibling, 1 reply; 6+ messages in thread From: Jeff King @ 2019-05-24 6:13 UTC (permalink / raw) To: Matheus Tavares Bernardino Cc: git, Christian Couder, Nguyễn Thái Ngọc Duy, Оля Тележная On Thu, May 23, 2019 at 01:51:47PM -0300, Matheus Tavares Bernardino wrote: > As one of my first tasks in GSoC, I'm looking to protect the global > states at sha1-file.c for future parallelizations. Currently, I'm > analyzing how to deal with the cached_objects array, which is a small > set of in-memory objects that read_object_file() is able to return > although they don't really exist on disk. The only current user of > this set is git-blame, which adds a fake commit containing > non-committed changes. > > As it is now, if we start parallelizing blame, cached_objects won't be > a problem since it is written to only once, at the beginning, and read > from a couple times latter, with no possible race conditions. > > But should we make these operations thread safe for future uses that > could involve potential parallel writes and reads too? > > If so, we have two options: > - Make the array thread local, which would oblige us to replicate data, or > - Protect it with locks, which could impact the sequential > performance. We could have a macro here, to skip looking on > single-threaded use cases. But we don't know, a priori, the number of > threads that would want to use the pack access code. It seems like a lot of the sha1-reading code is 99% read-only, but very occasionally will require a write (e.g., refreshing the packed_git list when we fail a lookup, or manipulating the set of cached mmap windows). I think pthreads has read/write locks, where many readers can hold the lock simultaneously but a writer blocks readers (and other writers). Then in the common case we'd only pay the price to take the lock, and not deal with contention. I don't know how expensive it is to take such a read lock; it's presumably just a few instructions but implies a memory barrier. Maybe it's worth timing? -Peff ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GSoC] How to protect cached_objects 2019-05-24 6:13 ` Jeff King @ 2019-05-25 14:42 ` Matheus Tavares Bernardino 0 siblings, 0 replies; 6+ messages in thread From: Matheus Tavares Bernardino @ 2019-05-25 14:42 UTC (permalink / raw) To: Jeff King Cc: git, Christian Couder, Nguyễn Thái Ngọc Duy, Оля Тележная On Fri, May 24, 2019 at 3:13 AM Jeff King <peff@peff.net> wrote: > > On Thu, May 23, 2019 at 01:51:47PM -0300, Matheus Tavares Bernardino wrote: > > > As one of my first tasks in GSoC, I'm looking to protect the global > > states at sha1-file.c for future parallelizations. Currently, I'm > > analyzing how to deal with the cached_objects array, which is a small > > set of in-memory objects that read_object_file() is able to return > > although they don't really exist on disk. The only current user of > > this set is git-blame, which adds a fake commit containing > > non-committed changes. > > > > As it is now, if we start parallelizing blame, cached_objects won't be > > a problem since it is written to only once, at the beginning, and read > > from a couple times latter, with no possible race conditions. > > > > But should we make these operations thread safe for future uses that > > could involve potential parallel writes and reads too? > > > > If so, we have two options: > > - Make the array thread local, which would oblige us to replicate data, or > > - Protect it with locks, which could impact the sequential > > performance. We could have a macro here, to skip looking on > > single-threaded use cases. But we don't know, a priori, the number of > > threads that would want to use the pack access code. > > It seems like a lot of the sha1-reading code is 99% read-only, but very > occasionally will require a write (e.g., refreshing the packed_git list > when we fail a lookup, or manipulating the set of cached mmap windows). > > I think pthreads has read/write locks, where many readers can hold the > lock simultaneously but a writer blocks readers (and other writers). > Then in the common case we'd only pay the price to take the lock, and > not deal with contention. I don't know how expensive it is to take such > a read lock; it's presumably just a few instructions but implies a > memory barrier. Maybe it's worth timing? The pthread_rwlock_t, right? Nice! I didn't know about this type of lock. It will be very handy in other situations as well, thanks for the suggestion. > -Peff ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GSoC] How to protect cached_objects 2019-05-23 16:51 [GSoC] How to protect cached_objects Matheus Tavares Bernardino 2019-05-24 6:13 ` Jeff King @ 2019-05-24 9:55 ` Duy Nguyen 2019-05-25 16:04 ` Matheus Tavares Bernardino 1 sibling, 1 reply; 6+ messages in thread From: Duy Nguyen @ 2019-05-24 9:55 UTC (permalink / raw) To: Matheus Tavares Bernardino Cc: git, Christian Couder, Оля Тележная, Jeff King On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino <matheus.bernardino@usp.br> wrote: > > Hi, everyone > > As one of my first tasks in GSoC, I'm looking to protect the global > states at sha1-file.c for future parallelizations. Currently, I'm > analyzing how to deal with the cached_objects array, which is a small > set of in-memory objects that read_object_file() is able to return > although they don't really exist on disk. The only current user of > this set is git-blame, which adds a fake commit containing > non-committed changes. > > As it is now, if we start parallelizing blame, cached_objects won't be > a problem since it is written to only once, at the beginning, and read > from a couple times latter, with no possible race conditions. > > But should we make these operations thread safe for future uses that > could involve potential parallel writes and reads too? > > If so, we have two options: > - Make the array thread local, which would oblige us to replicate data, or > - Protect it with locks, which could impact the sequential > performance. We could have a macro here, to skip looking on > single-threaded use cases. But we don't know, a priori, the number of > threads that would want to use the pack access code. > > Any thought on this? I would go with "that's the problem of the future me". I'll go with a simple global (I mean per-object store) mutex. After we have a complete picture how many locks we need, and can run some tests to see the amount of lock contention we have (or even cache missess if we have so many locks), then we can start thinking of an optimal strategy. I mean, this is an implementation detail and can't affect object access API right? That gives us some breathing room to change stuff without preparing for something that we don't need right now (like multiple cached_objects writers) > Thanks, > Matheus Tavares -- Duy ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GSoC] How to protect cached_objects 2019-05-24 9:55 ` Duy Nguyen @ 2019-05-25 16:04 ` Matheus Tavares Bernardino 2019-05-26 2:43 ` Duy Nguyen 0 siblings, 1 reply; 6+ messages in thread From: Matheus Tavares Bernardino @ 2019-05-25 16:04 UTC (permalink / raw) To: Duy Nguyen Cc: git, Christian Couder, Оля Тележная, Jeff King On Fri, May 24, 2019 at 6:55 AM Duy Nguyen <pclouds@gmail.com> wrote: > > On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino > <matheus.bernardino@usp.br> wrote: > > > > > Hi, everyone > > > > As one of my first tasks in GSoC, I'm looking to protect the global > > states at sha1-file.c for future parallelizations. Currently, I'm > > analyzing how to deal with the cached_objects array, which is a small > > set of in-memory objects that read_object_file() is able to return > > although they don't really exist on disk. The only current user of > > this set is git-blame, which adds a fake commit containing > > non-committed changes. > > > > As it is now, if we start parallelizing blame, cached_objects won't be > > a problem since it is written to only once, at the beginning, and read > > from a couple times latter, with no possible race conditions. > > > > But should we make these operations thread safe for future uses that > > could involve potential parallel writes and reads too? > > > > If so, we have two options: > > - Make the array thread local, which would oblige us to replicate data, or > > - Protect it with locks, which could impact the sequential > > performance. We could have a macro here, to skip looking on > > single-threaded use cases. But we don't know, a priori, the number of > > threads that would want to use the pack access code. > > > > Any thought on this? > > I would go with "that's the problem of the future me". I'll go with a > simple global (I mean per-object store) mutex. Thanks for the help, Duy. What you mean by "per-object store mutex" is to have a lock for every "struct raw_object_store" in the "struct repository"? Maybe I didn't quite understand what the "object store" is, yet. > After we have a > complete picture how many locks we need, and can run some tests to see > the amount of lock contention we have (or even cache missess if we > have so many locks), then we can start thinking of an optimal > strategy. Please correct me if I misunderstand your suggestion. The idea is to protect the pack access code at a higher level, measure contentions, and then start refining the locks, if needed? I'm asking because I was going directly to the lower level protections (or thread-safe conversions) and planning to build it up. For example, I was working this week to eliminate static variables inside pack access functions. Do you think this approach is OK or should I work on a more "broader" thread-safe conversion first (like a couple wide mutex) and refine it down? > I mean, this is an implementation detail and can't affect object > access API right? That gives us some breathing room to change stuff > without preparing for something that we don't need right now (like > multiple cached_objects writers) Indeed, makes sense to leave the multiple writers support to the future, if it's ever needed. Thanks. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [GSoC] How to protect cached_objects 2019-05-25 16:04 ` Matheus Tavares Bernardino @ 2019-05-26 2:43 ` Duy Nguyen 0 siblings, 0 replies; 6+ messages in thread From: Duy Nguyen @ 2019-05-26 2:43 UTC (permalink / raw) To: Matheus Tavares Bernardino Cc: git, Christian Couder, Оля Тележная, Jeff King On Sat, May 25, 2019 at 11:04 PM Matheus Tavares Bernardino <matheus.bernardino@usp.br> wrote: > > On Fri, May 24, 2019 at 6:55 AM Duy Nguyen <pclouds@gmail.com> wrote: > > > > On Thu, May 23, 2019 at 11:51 PM Matheus Tavares Bernardino > > <matheus.bernardino@usp.br> wrote: > > > > > > > > Hi, everyone > > > > > > As one of my first tasks in GSoC, I'm looking to protect the global > > > states at sha1-file.c for future parallelizations. Currently, I'm > > > analyzing how to deal with the cached_objects array, which is a small > > > set of in-memory objects that read_object_file() is able to return > > > although they don't really exist on disk. The only current user of > > > this set is git-blame, which adds a fake commit containing > > > non-committed changes. > > > > > > As it is now, if we start parallelizing blame, cached_objects won't be > > > a problem since it is written to only once, at the beginning, and read > > > from a couple times latter, with no possible race conditions. > > > > > > But should we make these operations thread safe for future uses that > > > could involve potential parallel writes and reads too? > > > > > > If so, we have two options: > > > - Make the array thread local, which would oblige us to replicate data, or > > > - Protect it with locks, which could impact the sequential > > > performance. We could have a macro here, to skip looking on > > > single-threaded use cases. But we don't know, a priori, the number of > > > threads that would want to use the pack access code. > > > > > > Any thought on this? > > > > I would go with "that's the problem of the future me". I'll go with a > > simple global (I mean per-object store) mutex. > > Thanks for the help, Duy. What you mean by "per-object store mutex" is > to have a lock for every "struct raw_object_store" in the "struct > repository"? Maybe I didn't quite understand what the "object store" > is, yet. It's struct 'raw_object_store'. I think that struct encapsulates all data structures around $GIT_DIR/objects. > > After we have a > > complete picture how many locks we need, and can run some tests to see > > the amount of lock contention we have (or even cache missess if we > > have so many locks), then we can start thinking of an optimal > > strategy. > > Please correct me if I misunderstand your suggestion. The idea is to > protect the pack access code at a higher level, measure contentions, > and then start refining the locks, if needed? I'm asking because I was > going directly to the lower level protections (or thread-safe > conversions) and planning to build it up. For example, I was working > this week to eliminate static variables inside pack access functions. > Do you think this approach is OK or should I work on a more "broader" > thread-safe conversion first (like a couple wide mutex) and refine it > down? Having one or two big locks might be easy to get thread safe, but that increases lock contention and may take forever to fix (it took a long time to kill Linux's "big kernel lock", and python's equivalent is still here). So having smaller locks around each shared state makes more sense. At least you will have easier time combining them later if you want (breaking down big locks is much harder). What I was getting at was just stick to simple locks like mutex. Once you have identified all shared states to protect, you can profile to have more information and then decide can to choose a different kind of lock, like the read/write one. We might even need to reorganize data structure to be more lock-friendly (or go lockless if you feel brave)... -- Duy ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-05-26 2:44 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-05-23 16:51 [GSoC] How to protect cached_objects Matheus Tavares Bernardino 2019-05-24 6:13 ` Jeff King 2019-05-25 14:42 ` Matheus Tavares Bernardino 2019-05-24 9:55 ` Duy Nguyen 2019-05-25 16:04 ` Matheus Tavares Bernardino 2019-05-26 2:43 ` Duy Nguyen
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.