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

Re: [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)

From
René Scharfe <l.s.r@web.de>
Date
Jan 25, 2017, 18:43 UTC
Message-ID
<f41e5053-ee24-060f-0fb9-b257b3ba35a0@web.de>
In-Reply-To
<20170124203949.46lbmiyj26xx4hrk@sigill.intra.peff.net>
Am 24.01.2017 um 21:39 schrieb Jeff King:
Show 19 quoted lines
> On Tue, Jan 24, 2017 at 07:00:03PM +0100, René Scharfe wrote:
>
>>> I do worry about having to support more implementations in the
>>> future that have different function signature for the comparison
>>> callbacks, which will make things ugly, but this addition alone
>>> doesn't look too bad to me.
>>
>> It is unfair of me to show a 5% speedup and then recommend to not
>> include it. ;-)  That difference won't be measurable in real use cases
>> and the patch is not necessary.  This patch is simple, but the overall
>> complexity (incl. #ifdefs etc.) will be lower without it.
>
> I care less about squeezing out the last few percent performance and
> more that somebody libc qsort_r() might offer some other improvement.
> For instance, it could sort in-place to lower memory use for some cases,
> or do some clever thing that gives more than a few percent in the real
> world (something like TimSort).
>
> I don't know to what degree we should care about that.

That's a good question. Which workloads spend a significant amount of time in qsort/qsort_s?

We could track processor time spent and memory allocated in QSORT_S and the whole program and show a warning at the end if one of the two exceeded, say, 5% of the total, asking nicely to send it to our mailing list. Would something like this be useful for other functions or metrics as well? Would it be too impolite to use users as telemetry transports?

If we find such cases then we'd better fix them for all platforms, e.g. by importing timsort, no?

René
Previous: Jeff KingNext: Jeff King
Message 11 of 18 in “string-list: make string_list_sort() reentrant”
  1. 0/5 string-list: make string_list_sort() reentrantRené Scharfe, Jan 22, 2017
  2. 1/5 compat: add qsort_s()René Scharfe, Jan 22, 2017
  3. 3/5 perf: add basic sort performance testRené Scharfe, Jan 22, 2017
  4. 4/5 string-list: use QSORT_S in string_list_sort()René Scharfe, Jan 22, 2017
  5. 5/5 ref-filter: use QSORT_S in ref_array_sort()René Scharfe, Jan 22, 2017
  6. 2/5 add QSORT_SRené Scharfe, Jan 22, 2017
  7. [DEMO][PATCH v2 6/5] compat: add a qsort_s() implementation based on GNU's qsort_r(1)René Scharfe, Jan 22, 2017
  8. Junio C HamanoJan 23, 2017
  9. René ScharfeJan 24, 2017
  10. Jeff KingJan 24, 2017
  11. René ScharfeJan 25, 2017
  12. Jeff KingJan 25, 2017
  13. Johannes SchindelinJan 26, 2017
  14. Jeff KingJan 23, 2017
  15. Johannes SchindelinJan 24, 2017
  16. Jeff KingJan 24, 2017
  17. René ScharfeJan 24, 2017
  18. Jeff KingJan 24, 2017

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.