[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

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

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

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

[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

[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.