From: Michael Haggerty <mhagger@alum•mit.edu>
To: Junio C Hamano <gitster@pobox•com>
Cc: Stefan Beller <sbeller@google•com>,
Jonathan Nieder <jrnieder@gmail•com>,
Ronnie Sahlberg <sahlberg@google•com>,
Git Mailing List <git@vger•kernel.org>
Subject: Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse
Date: Tue, 25 Nov 2014 08:21:18 +0100 [thread overview]
Message-ID: <54742DEE.7090905@alum.mit.edu> (raw)
In-Reply-To: <CAPc5daWubo+CSD-C+AH6Y-PKQ7h2MoUU=DbW+nYKO9uceogsAg@mail.gmail.com>
On 11/21/2014 05:44 PM, Junio C Hamano wrote:
> On Fri, Nov 21, 2014 at 6:09 AM, Michael Haggerty <mhagger@alum•mit.edu> wrote:
>> Inserting items into a list in sorted order is O(N^2) whereas
>> appending them unsorted and then sorting the list all at once is
>> O(N lg N).
>>
>> string_list_insert() also removes duplicates, and this change loses
>> that functionality. But the strings in this list, which ultimately
>> come from a for_each_ref() iteration, cannot contain duplicates.
>>
>
> A similar conversion in other places we may do in the future
> might find a need for an equivalent to "-u" option of "sort" in the
> string_list_sort() function, but the above nicely explains why
> it is not necessary for this one. Good.
The only reason to integrate "-u" functionality into the sort would be
if one expects a significant fraction of entries to be duplicates, in
which case the sort could be structured to discard duplicates as it
works, thereby reducing the work needed for the sort. I can't think of
such a case in our code. Otherwise, calling sort_string_list() followed
by string_list_remove_duplicates() should be just as clear and
approximately as efficient.
A couple of times I've also felt that an all-purpose *stable* sort would
be convenient (though I can't remember the context offhand). I don't
think we have such a thing.
> Eh, why is that called sort_string_list()? Perhaps it is a good
> opening to introduce string_list_sort(list, flag) where flag would
> be a bitmask that represents ignore-case, uniquify, etc., and
> then either deprecate the current one or make it a thin wrapper
> of the one that is more consistently named.
I agree. Indeed, I typed that function's name wrong once when
constructing this patch. It would be better to name it consistently with
the other string_list_*() functions.
I put it on my todo list (but don't let that dissuade somebody else from
doing it).
Michael
--
Michael Haggerty
mhagger@alum•mit.edu
next prev parent reply other threads:[~2014-11-25 7:21 UTC|newest]
Thread overview: 61+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-11-18 22:43 [PATCH] refs.c: use a stringlist for repack_without_refs Stefan Beller
2014-11-18 23:06 ` Junio C Hamano
2014-11-18 23:39 ` Junio C Hamano
2014-11-18 23:45 ` Jonathan Nieder
2014-11-19 0:28 ` Stefan Beller
2014-11-19 1:08 ` Stefan Beller
2014-11-19 18:00 ` Junio C Hamano
2014-11-19 18:50 ` Stefan Beller
2014-11-19 20:44 ` Jonathan Nieder
2014-11-19 21:54 ` Stefan Beller
2014-11-19 21:59 ` [PATCH v4] " Stefan Beller
2014-11-20 2:15 ` Jonathan Nieder
2014-11-20 16:47 ` Junio C Hamano
2014-11-20 18:04 ` [PATCH v5 1/1] " Stefan Beller
2014-11-20 18:10 ` [PATCH] refs.c: repack_without_refs may be called without error string buffer Stefan Beller
2014-11-20 18:15 ` Ronnie Sahlberg
2014-11-20 18:35 ` Jonathan Nieder
2014-11-20 18:36 ` Ronnie Sahlberg
2014-11-20 18:56 ` Stefan Beller
2014-11-20 18:29 ` [PATCH v5 1/1] refs.c: use a stringlist for repack_without_refs Jonathan Nieder
2014-11-20 18:37 ` Jonathan Nieder
2014-11-20 19:01 ` Junio C Hamano
2014-11-20 19:05 ` Stefan Beller
2014-11-20 20:07 ` [PATCH v6] refs.c: use a string_list " Stefan Beller
2014-11-20 20:36 ` Jonathan Nieder
2014-11-21 14:09 ` [PATCH 0/6] repack_without_refs(): convert to string_list Michael Haggerty
2014-11-21 14:09 ` [PATCH 1/6] prune_remote(): exit early if there are no stale references Michael Haggerty
2014-11-22 21:07 ` Jonathan Nieder
2014-11-21 14:09 ` [PATCH 2/6] prune_remote(): initialize both delete_refs lists in a single loop Michael Haggerty
2014-11-21 14:09 ` [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse Michael Haggerty
2014-11-21 16:44 ` Junio C Hamano
2014-11-25 7:21 ` Michael Haggerty [this message]
2014-11-25 8:04 ` Michael Haggerty
2014-11-22 21:08 ` Jonathan Nieder
2014-11-21 14:09 ` [PATCH 4/6] repack_without_refs(): make the refnames argument a string_list Michael Haggerty
2014-11-22 21:17 ` Jonathan Nieder
2014-11-25 7:42 ` Michael Haggerty
2014-11-21 14:09 ` [PATCH 5/6] prune_remote(): rename local variable Michael Haggerty
2014-11-22 21:18 ` Jonathan Nieder
2014-11-21 14:09 ` [PATCH 6/6] prune_remote(): iterate using for_each_string_list_item() Michael Haggerty
2014-11-22 21:19 ` Jonathan Nieder
2014-11-21 14:25 ` [PATCH 0/6] repack_without_refs(): convert to string_list Michael Haggerty
2014-11-21 18:00 ` Junio C Hamano
2014-11-21 19:57 ` Stefan Beller
2014-11-25 0:28 ` Our cumbersome mailing list workflow (was: Re: [PATCH 0/6] repack_without_refs(): convert to string_list) Michael Haggerty
2014-11-27 17:46 ` Our cumbersome mailing list workflow Torsten Bögershausen
2014-11-27 18:24 ` Matthieu Moy
2014-11-28 12:09 ` Philip Oakley
2014-11-27 22:53 ` Eric Wong
2014-11-28 15:34 ` Michael Haggerty
2014-11-28 16:24 ` brian m. carlson
2014-12-01 2:46 ` Junio C Hamano
2014-12-03 2:20 ` Stefan Beller
2014-12-03 3:53 ` Jonathan Nieder
2014-12-03 17:18 ` Junio C Hamano
2014-12-03 17:28 ` Torsten Bögershausen
2014-11-28 14:31 ` Michael Haggerty
2014-11-28 15:42 ` Marc Branchaud
2014-11-28 21:39 ` Damien Robert
2014-12-03 23:57 ` Philip Oakley
2014-12-04 2:03 ` Stefan Beller
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=54742DEE.7090905@alum.mit.edu \
--to=mhagger@alum$(echo .)mit.edu \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=jrnieder@gmail$(echo .)com \
--cc=sahlberg@google$(echo .)com \
--cc=sbeller@google$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox