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

Re: [PATCH 3/9] test-mergesort: add test subcommand

From
René Scharfe <l.s.r@web.de>
Date
Oct 3, 2021, 10:15 UTC
Message-ID
<850aa059-61d9-0eba-5809-e0c27a19dfb4@web.de>
In-Reply-To
<87o887q0s9.fsf@evledraar.gmail.com>
Am 02.10.21 um 10:35 schrieb Ævar Arnfjörð Bjarmason:
Show 26 quoted lines
>
> On Fri, Oct 01 2021, Junio C Hamano wrote:
>
>> René Scharfe <l.s.r@web.de> writes:
>>
>>> +static void dist_rand(int *arr, int n, int m)
>>> +{
>>> +	int i;
>>> +	for (i = 0; i < n; i++)
>>> +		arr[i] = rand() % m;
>>> +}
>>> ...
>>> +static void dist_shuffle(int *arr, int n, int m)
>>> +{
>>> +	int i, j, k;
>>> +	for (i = j = 0, k = 1; i < n; i++)
>>> +		arr[i] = (rand() % m) ? (j += 2) : (k += 2);
>>> +}
>>
>> I briefly wondered if we want to seed the rand() in some way to make
>> the tests reproducible, but we'd need to ship our own rand() if we
>> wanted to go that route, which would probably be too much.
>
> Wouldn't calling srand() with some constant value suffice on most
> platforms? I'm aware of it being a NOOP and rand() always being randomly
> seeded on (IIRC) OpenBSD, but that should work on e.g. glibc.
Right, so we'd need to ship our own random number generator.

Repeatable tests are not essential (the original paper didn't mention seeding), but shouldn't be much trouble to implement and would simplify comparisons across versions, systems and among testers.

The only downside I can think of is that it may perhaps also simplify over-fitting, i.e. I might find micro-tweaks that only work for our specific rand() sequence and then misinterpret them as general improvements..

René
Previous: René ScharfeNext: Junio C Hamano
Message 11 of 29 in “mergesort: improve tests and performance”
  1. 0/9 mergesort: improve tests and performanceRené Scharfe, Oct 1, 2021
  2. 1/9 test-mergesort: use strbuf_getline()René Scharfe, Oct 1, 2021
  3. Ævar Arnfjörð BjarmasonOct 2, 2021
  4. René ScharfeOct 2, 2021
  5. 2/9 test-mergesort: add sort subcommandRené Scharfe, Oct 1, 2021
  6. Junio C HamanoOct 1, 2021
  7. 3/9 test-mergesort: add test subcommandRené Scharfe, Oct 1, 2021
  8. Junio C HamanoOct 1, 2021
  9. Ævar Arnfjörð BjarmasonOct 2, 2021
  10. René ScharfeOct 3, 2021
  11. René ScharfeOct 3, 2021
  12. Junio C HamanoOct 3, 2021
  13. René ScharfeOct 7, 2021
  14. 10/9 test-mergesort: use repeatable random numbersRené Scharfe, Oct 8, 2021
  15. Jeff KingOct 8, 2021
  16. Ævar Arnfjörð BjarmasonOct 8, 2021
  17. René ScharfeOct 8, 2021
  18. Ævar Arnfjörð BjarmasonOct 8, 2021
  19. 4/9 test-mergesort: add generate subcommandRené Scharfe, Oct 1, 2021
  20. 5/9 test-mergesort: add unriffle modeRené Scharfe, Oct 1, 2021
  21. 6/9 test-mergesort: add unriffle_skewed modeRené Scharfe, Oct 1, 2021
  22. 7/9 p0071: measure sorting of already sorted and reversed filesRené Scharfe, Oct 1, 2021
  23. 8/9 p0071: test performance of llist_mergesort()René Scharfe, Oct 1, 2021
  24. 9/9 mergesort: use ranks stackRené Scharfe, Oct 1, 2021
  25. Ævar Arnfjörð BjarmasonJan 17, 2022
  26. René ScharfeJan 17, 2022
  27. René ScharfeJan 18, 2022
  28. Ævar Arnfjörð BjarmasonJan 18, 2022
  29. René ScharfeJan 18, 2022

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.