[PATCH] D36423: [libc++] Introsort based sorting function

philnik commandeered this revision. philnik added a reviewer: DIVYA. philnik added a comment. Herald added a subscriber: mgrang. Herald added a project: All. This has been superseded by D113413 . CHANGES SINCE LAST ACTION https://reviews.llvm.org/D36423/new/

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA added a comment. ping https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D36423: [libc++] Introsort based sorting function

hiraditya added a comment. Ping! https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. LGTM. You should probably get one other person to approve though. I'm hoping that @EricWF or @mclow.lists will take a look https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://list

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA updated this revision to Diff 111998. DIVYA added a comment. - added test qsort_worst_uint32 in algorithm.bench.cpp https://reviews.llvm.org/D36423 Files: benchmarks/GenerateInput.hpp benchmarks/algorithms.bench.cpp include/algorithm Index: include/algorithm ===

[PATCH] D36423: [libc++] Introsort based sorting function

hiraditya added a comment. Results with the patch. Before: Run on (8 X 3900 MHz CPU s) 2017-08-20 15:11:41 --- BenchmarkTime CPU Iterations --

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. The test headers should not be in the production include folder. They should probably be in the benchmark folder. If possible, follow the style and conventions of the existing tests. When you can't follow the style and convention of the existing tests, try to make it

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA added a comment. Added benchmark from Aditya's repo into the libcxx benchmark code base https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA updated this revision to Diff 111027. https://reviews.llvm.org/D36423 Files: benchmarks/algorithms.bench.cpp include/algorithm include/rng_utils.h include/test_configs.h include/test_utils.h Index: include/test_utils.h =

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. If you want the performance improvements in the BM_sort_std_worst_quick cases preserved, you really need to port the benchmark from Aditya's repo into the libcxx benchmark code base. Otherwise, the next person that comes along to improve std::sort performance may very w

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA added a comment. Link to algorithm.bench.cpp benchmark https://github.com/hiraditya/std-benchmark/blob/master/cxx/algorithm.bench.cpp Comment at: include/algorithm:4208 + + // Threshold(or depth limit) for introsort is taken to be 2*log2(size) + typedef typename iterat

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. I like this change in general. Dinkumware has been using introsort for 10+ years, so I'm a bit surprised that libc++ wasn't already. Comment at: include/algorithm:4208 + + // Threshold(or depth limit) for introsort is taken to be 2*log2(size) + typed

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. Those are interesting (and useful) results... but they don't look like they came from the same algorithms.bench.cpp that I'm looking at... https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/algorithms.bench.cpp That being said, the benchmark there only does 1k e

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA added a comment. benchmarks/algorithms.bench.cpp Results With old code (in ns) BM_sort_std_common>/16384 : 730752 BM_sort_std_common>/32768 : 1.58E+06 BM_sort_std_ascending>/16384:1716

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. alternatively, you could report the comparison of the old code vs. the new code with an existing benchmark, like benchmarks/algorithms.bench.cpp https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.

[PATCH] D36423: [libc++] Introsort based sorting function

bcraig added a comment. This patch needs benchmarks that demonstrate the performance changes. https://reviews.llvm.org/D36423 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D36423: [libc++] Introsort based sorting function

DIVYA created this revision. The sorting algorithm currently employed in libc+ library uses quicksort with tail recursion elimination, as a result of which the worst case complexity turns out to be O(N^2). This patch reduces the worst case time complexity, by employing Introsort algorithm. Intr