On 08/30, Jeff King wrote:
> On Wed, Aug 30, 2017 at 08:55:01AM +0200, Michael Haggerty wrote:
>
> > > + tempfile->active = 0;
> > > + for (p = &tempfile_list; *p; p = &(*p)->next) {
> > > + if (*p == tempfile) {
> > > + *p = tempfile->next;
> > > + break;
> > > + }
> > > }
> > > }
> >
> > `deactivate_tempfile()` is O(N) in the number of active tempfiles. This
> > could get noticeable for, say, updating 30k references, which involves
> > obtaining 30k reference locks. I think that code adds the locks in
> > alphabetical order and also removes them in alphabetical order, so the
> > overall effort would go like O(N²). I'm guessing that this would be
> > measurable but not fatal for realistic numbers of references, but it
> > should at least be benchmarked.
> >
> > There are three obvious ways to make this O(1) again:
> >
> > * Make the list doubly-linked.
>
> Yeah, I noticed this when writing it, and the doubly-linked list was my
> first thought. It's much more straight-forward than making guesses about
> traversal order, and we already have a nice implementation in list.h.
I agree that a doubly-linked list is probably the best way to go in
order to solve the performance issue.
>
> What made me hesitate for this demonstration was that it turns the
> removal into _two_ pointer updates. That made me more nervous about the
> racy case where we get a single handler while already deleting
> something. Specifically when we have "a <-> b <-> c" and we've updated
> "a->next" to point to "c" but "c->prev" still points to "b".
>
> But even with the singly-linked list we're not fully race-proof
> (somebody could set *p to NULL between the time we look at it and
> dereference it). What we really care about is not two versions of the
> function running simultaneously, but one version getting interrupted by
> another and having the second one see a sane state (because we'll never
> return to the first signal handler; the second one will raise() and
> die).
>
> And I think we're fine there even with a doubly-linked list. It's still
> the single update of the "next" pointer that controls that second
> traversal.
>
> -Peff
I know it was mentioned earlier but if this is a critical section, and
it would be bad if it was interrupted, then couldn't we turn off
interrupts before attempting to remove an item from the list?
--
Brandon Williams
