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

[PATCH 7/9] p0071: measure sorting of already sorted and reversed files

From
René Scharfe <l.s.r@web.de>
Date
Oct 1, 2021, 09:19 UTC
Message-ID
<3fa28f14-5e53-7367-b628-6eab2d5737be@web.de>
In-Reply-To
<943b1e01-465e-5def-a766-0adf667690de@web.de>

Check if sorting takes advantage of already sorted or reversed content, or if that corner case actually decreases performance, like it would for a simplistic quicksort implementation.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
 t/perf/p0071-sort.sh | 29 ++++++++++++++++++++++-------
 1 file changed, 22 insertions(+), 7 deletions(-)
diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh
index 6e924f5fa3..5b39b68f35 100755
--- a/t/perf/p0071-sort.sh
+++ b/t/perf/p0071-sort.sh
@@ -11,16 +11,31 @@ test_expect_success 'setup' '
 	git cat-file --batch >unsorted
 '

-test_perf 'sort(1)' '
-	sort <unsorted >expect
+test_perf 'sort(1) unsorted' '
+	sort <unsorted >sorted
 '

-test_perf 'string_list_sort()' '
-	test-tool string-list sort <unsorted >actual
+test_expect_success 'reverse' '
+	sort -r <unsorted >reversed
 '

-test_expect_success 'string_list_sort() sorts like sort(1)' '
-	test_cmp_bin expect actual
-'
+for file in sorted reversed
+do
+	test_perf "sort(1) $file" "
+		sort <$file >actual
+	"
+done
+
+for file in unsorted sorted reversed
+do
+
+	test_perf "string_list_sort() $file" "
+		test-tool string-list sort <$file >actual
+	"
+
+	test_expect_success "string_list_sort() $file sorts like sort(1)" "
+		test_cmp_bin sorted actual
+	"
+done

 test_done
--
2.33.0
Previous: René ScharfeNext: René Scharfe
Message 22 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.