git@vger.kernel.org mailing list mirror (one of many)
 help / Atom feed
From: Jeff King <peff@peff.net>
To: Michael Haggerty <mhagger@alum.mit.edu>
Cc: Brandon Williams <bmwill@google.com>,
	Lars Schneider <larsxschneider@gmail.com>,
	Martin Ågren <martin.agren@gmail.com>,
	Git Users <git@vger.kernel.org>
Subject: Re: [PATCH] config: use a static lock_file struct
Date: Wed, 30 Aug 2017 15:53:20 -0400
Message-ID: <20170830195320.27w5mhnrcd2uosvz@sigill.intra.peff.net> (raw)
In-Reply-To: <3e632fd3-7db9-4c38-c524-b56a06cfaa87@alum.mit.edu>

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.

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

  reply index

Thread overview: 43+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-08-27  7:37 [PATCH] pkt-line: re-'static'-ify buffer in packet_write_fmt_1() Martin Ågren
2017-08-27 15:41 ` Jeff King
2017-08-27 18:25   ` Jeff King
2017-08-27 18:21 ` Lars Schneider
2017-08-27 19:09   ` Martin Ågren
2017-08-27 19:15     ` Jeff King
2017-08-27 20:04     ` Lars Schneider
2017-08-27 23:23       ` Jeff King
2017-08-28  4:11         ` Martin Ågren
2017-08-28 17:52           ` Stefan Beller
2017-08-28 17:58             ` Jeff King
2017-09-05 10:03               ` Junio C Hamano
2017-08-29 17:51           ` Lars Schneider
2017-08-29 18:53             ` Jeff King
2017-08-29 18:58               ` [PATCH] config: use a static lock_file struct Jeff King
2017-08-29 19:09                 ` Brandon Williams
2017-08-29 19:10                   ` Brandon Williams
2017-08-29 19:12                   ` Jeff King
2017-08-30  3:25                     ` Michael Haggerty
2017-08-30  4:31                       ` Jeff King
2017-08-30  4:55                         ` Michael Haggerty
2017-08-30  4:55                         ` Jeff King
2017-08-30  5:55                           ` Jeff King
2017-08-30  7:07                             ` Michael Haggerty
2017-09-02  8:44                               ` Jeff King
2017-09-02 13:50                                 ` Jeff King
2017-08-30  6:55                           ` Michael Haggerty
2017-08-30 19:53                             ` Jeff King [this message]
2017-08-30 19:57                               ` Brandon Williams
2017-08-30 20:11                                 ` Jeff King
2017-08-30 21:06                                   ` Brandon Williams
2017-08-31  4:09                                     ` Jeff King
2017-09-06  3:59                 ` Junio C Hamano
2017-09-06 12:41                   ` Jeff King
2017-08-29 19:22               ` [PATCH] pkt-line: re-'static'-ify buffer in packet_write_fmt_1() Martin Ågren
2017-08-29 21:48                 ` Jeff King
2017-08-30  5:31                   ` Jeff King
2017-09-05 10:03                     ` Junio C Hamano
2017-10-10  4:06                       ` [PATCH 0/2] Do not call cmd_*() as a subroutine Junio C Hamano
2017-10-10  4:06                         ` [PATCH 1/2] describe: do not use " Junio C Hamano
2017-10-10 13:43                           ` SZEDER Gábor
2017-10-11  6:00                             ` Junio C Hamano
2017-10-10  4:06                         ` [PATCH 2/2] merge-ours: " Junio C Hamano

Reply instructions:

You may reply publically 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

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20170830195320.27w5mhnrcd2uosvz@sigill.intra.peff.net \
    --to=peff@peff.net \
    --cc=bmwill@google.com \
    --cc=git@vger.kernel.org \
    --cc=larsxschneider@gmail.com \
    --cc=martin.agren@gmail.com \
    --cc=mhagger@alum.mit.edu \
    /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

git@vger.kernel.org mailing list mirror (one of many)

Archives are clonable:
	git clone --mirror https://public-inbox.org/git
	git clone --mirror http://ou63pmih66umazou.onion/git
	git clone --mirror http://czquwvybam4bgbro.onion/git
	git clone --mirror http://hjrcffqmbrq6wope.onion/git

Newsgroups are available over NNTP:
	nntp://news.public-inbox.org/inbox.comp.version-control.git
	nntp://ou63pmih66umazou.onion/inbox.comp.version-control.git
	nntp://czquwvybam4bgbro.onion/inbox.comp.version-control.git
	nntp://hjrcffqmbrq6wope.onion/inbox.comp.version-control.git
	nntp://news.gmane.org/gmane.comp.version-control.git

 note: .onion URLs require Tor: https://www.torproject.org/
       or Tor2web: https://www.tor2web.org/

AGPL code for this site: git clone https://public-inbox.org/ public-inbox