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
Jonathan Nieder <jrnieder@gmail.com>
Date
Sep 6, 2018, 23:50 UTC
Message-ID
<20180906235033.GA100309@aiede.svl.corp.google.com>
In-Reply-To
<20180906192021.GB26575@sigill.intra.peff.net>
Hi,
Jeff King wrote:
> But what I think is harmful is a _sorted_ list, because of the
> "accidentally quadratic" nature, and because it's easy to call its
> functions on an unsorted list.

I agree --- in general, it tends to be better to build an unsorted string list and then sort it.

Once I've done so, what is your advice about getting fast lookups in the result? Should I build an auxiliary hashmap as well? Or is this an argument for the 'sorted' flag + BUG approach you already mentioned?

Whatever we do, I agree with your goal of getting rid of string_list_insert.

Thanks, Jonathan

Previous: Jeff KingNext: Jeff King
Message 3 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.