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

Re: ordered string-list considered harmful, was Re: [PATCH v3] Allow aliases that include other aliases

From
Stefan Beller <sbeller@google.com>
Date
Sep 6, 2018, 20:54 UTC
Message-ID
<CAGZ79kbFe8WMswWy+SorYUvEj2r5rUQdjx=zbVK5BfeU+Mgx9A@mail.gmail.com>
In-Reply-To
<20180906204932.GA1482@sigill.intra.peff.net>
Show 19 quoted lines
> > Does a hashmap guarantee an order?
>
> No, it definitely doesn't.
>
> I guess the reading-between-the-lines assumption that I didn't quite say
> is: I think most (if not all) of the users of sorted string lists don't
> actually care about a particular order. They just want efficient lookup.
>
> > I thought we had an example of an ordered list in the submodule code
> > but could not find it, maybe it is gone already or did not rely on the order
> > as I thought.
> >
> > It turns out we make never use of a custom compare function in
> > the stringlist, which helps gaining confidence this use case is nowhere
> > to be found in the code.
>
> Plenty of code uses the default strcmp. You can find users which assume
> sorting by their use of string_list_insert() versus _append(). Or ones
> that call string_list_sort(), of course.
Here comes my reading-between-the-lines assumption:

When using the default comparison function, you probably only care about the efficient lookup as described above, but if you had a non-default order, then we'd have strong evidence of the contrary as the author of such code would have found reasons why that order is superior than default order (and don't tell me a different order helps making lookups even more efficient, this must be another reason).

Previous: Jeff KingNext: Jeff King
Message 12 of 13 in “ordered string-list considered harmful, was Re: [PATCH v3] Allow aliases that include other aliases”
  1. Jeff KingSep 6, 2018
  2. Jeff KingSep 6, 2018
  3. Jonathan NiederSep 6, 2018
  4. Jeff KingSep 7, 2018
  5. Jonathan NiederSep 7, 2018
  6. Ævar Arnfjörð BjarmasonSep 7, 2018
  7. Jonathan NiederSep 7, 2018
  8. brian m. carlsonSep 8, 2018
  9. Jeff KingSep 7, 2018
  10. Stefan BellerSep 6, 2018
  11. Jeff KingSep 6, 2018
  12. Stefan BellerSep 6, 2018
  13. Jeff KingSep 7, 2018

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.