git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 3/6] prune_remote(): sort delete_refs_list references en masse

From
Michael Haggerty <mhagger@alum.mit.edu>
Date
Nov 25, 2014, 07:21 UTC
Message-ID
<54742DEE.7090905@alum.mit.edu>
In-Reply-To
<CAPc5daWubo+CSD-C+AH6Y-PKQ7h2MoUU=DbW+nYKO9uceogsAg@mail.gmail.com>
On 11/21/2014 05:44 PM, Junio C Hamano wrote:
Show 14 quoted lines
> 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.

Show 5 quoted lines
> 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
Previous: Junio C HamanoNext: Michael Haggerty
Message 32 of 61 in “refs.c: use a stringlist for repack_without_refs”
  1. refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 18, 2014
  2. Junio C HamanoNov 18, 2014
  3. Junio C HamanoNov 18, 2014
  4. Jonathan NiederNov 18, 2014
  5. Stefan BellerNov 19, 2014
  6. refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 19, 2014
  7. Junio C HamanoNov 19, 2014
  8. refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 19, 2014
  9. Jonathan NiederNov 19, 2014
  10. refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 19, 2014
  11. refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 19, 2014
  12. Jonathan NiederNov 20, 2014
  13. Junio C HamanoNov 20, 2014
  14. 1/1 refs.c: use a stringlist for repack_without_refsStefan Beller, Nov 20, 2014
  15. refs.c: repack_without_refs may be called without error string bufferStefan Beller, Nov 20, 2014
  16. Ronnie SahlbergNov 20, 2014
  17. Jonathan NiederNov 20, 2014
  18. Ronnie SahlbergNov 20, 2014
  19. Stefan BellerNov 20, 2014
  20. Jonathan NiederNov 20, 2014
  21. Jonathan NiederNov 20, 2014
  22. Junio C HamanoNov 20, 2014
  23. Stefan BellerNov 20, 2014
  24. refs.c: use a string_list for repack_without_refsStefan Beller, Nov 20, 2014
  25. Jonathan NiederNov 20, 2014
  26. 0/6 repack_without_refs(): convert to string_listMichael Haggerty, Nov 21, 2014
  27. 1/6 prune_remote(): exit early if there are no stale referencesMichael Haggerty, Nov 21, 2014
  28. Jonathan NiederNov 22, 2014
  29. 2/6 prune_remote(): initialize both delete_refs lists in a single loopMichael Haggerty, Nov 21, 2014
  30. 3/6 prune_remote(): sort delete_refs_list references en masseMichael Haggerty, Nov 21, 2014
  31. Junio C HamanoNov 21, 2014
  32. Michael HaggertyNov 25, 2014
  33. Michael HaggertyNov 25, 2014
  34. Jonathan NiederNov 22, 2014
  35. 4/6 repack_without_refs(): make the refnames argument a string_listMichael Haggerty, Nov 21, 2014
  36. Jonathan NiederNov 22, 2014
  37. Michael HaggertyNov 25, 2014
  38. 5/6 prune_remote(): rename local variableMichael Haggerty, Nov 21, 2014
  39. Jonathan NiederNov 22, 2014
  40. 6/6 prune_remote(): iterate using for_each_string_list_item()Michael Haggerty, Nov 21, 2014
  41. Jonathan NiederNov 22, 2014
  42. Michael HaggertyNov 21, 2014
  43. Junio C HamanoNov 21, 2014
  44. Stefan BellerNov 21, 2014
  45. Our cumbersome mailing list workflow (was: Re: [PATCH 0/6] repack_without_refs(): convert to string_list)Michael Haggerty, Nov 25, 2014
  46. Torsten BögershausenNov 27, 2014
  47. Matthieu MoyNov 27, 2014
  48. Philip OakleyNov 28, 2014
  49. Eric WongNov 27, 2014
  50. Michael HaggertyNov 28, 2014
  51. brian m. carlsonNov 28, 2014
  52. Junio C HamanoDec 1, 2014
  53. Stefan BellerDec 3, 2014
  54. Jonathan NiederDec 3, 2014
  55. Junio C HamanoDec 3, 2014
  56. Torsten BögershausenDec 3, 2014
  57. Michael HaggertyNov 28, 2014
  58. Marc BranchaudNov 28, 2014
  59. Damien RobertNov 28, 2014
  60. Philip OakleyDec 3, 2014
  61. Stefan BellerDec 4, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.