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
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
===
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
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
=
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
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
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
