Does anything else have to happen before this gets merged for 3.5? I don't see this change in the 3.5 branch.
On Thu, Jul 24, 2014 at 12:12 PM, Marshall Clow <[email protected]> wrote: > > On Jul 22, 2014, at 8:48 PM, David Majnemer <[email protected]> > wrote: > > Should this be merged for 3.5? > > > Yes. > > — Marshall > > > > On Mon, Jul 21, 2014 at 11:07 PM, David Majnemer <[email protected] > > wrote: > >> Author: majnemer >> Date: Tue Jul 22 01:07:09 2014 >> New Revision: 213615 >> >> URL: http://llvm.org/viewvc/llvm-project?rev=213615&view=rev >> Log: >> Fix std::make_heap's worst case time complexity >> >> std::make_heap is currently implemented by iteratively applying a >> siftup-type algorithm. Since sift-up is O(ln n), this gives >> std::make_heap a worst case time complexity of O(n ln n). >> >> The C++ standard mandates that std::make_heap make no more than O(3n) >> comparisons, this makes our std::make_heap out of spec. >> >> Fix this by introducing an implementation of __sift_down and switch >> std::make_heap to create the heap using it. >> This gives std::make_heap linear time complexity in the worst case. >> >> This fixes PR20161. >> >> Modified: >> libcxx/trunk/include/algorithm >> >> libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp >> >> Modified: libcxx/trunk/include/algorithm >> URL: >> http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/algorithm?rev=213615&r1=213614&r2=213615&view=diff >> >> ============================================================================== >> --- libcxx/trunk/include/algorithm (original) >> +++ libcxx/trunk/include/algorithm Tue Jul 22 01:07:09 2014 >> @@ -4794,49 +4794,8 @@ is_heap(_RandomAccessIterator __first, _ >> >> template <class _Compare, class _RandomAccessIterator> >> void >> -__push_heap_front(_RandomAccessIterator __first, _RandomAccessIterator, >> _Compare __comp, >> - typename >> iterator_traits<_RandomAccessIterator>::difference_type __len) >> -{ >> - typedef typename >> iterator_traits<_RandomAccessIterator>::difference_type difference_type; >> - typedef typename iterator_traits<_RandomAccessIterator>::value_type >> value_type; >> - if (__len > 1) >> - { >> - difference_type __p = 0; >> - _RandomAccessIterator __pp = __first; >> - difference_type __c = 2; >> - _RandomAccessIterator __cp = __first + __c; >> - if (__c == __len || __comp(*__cp, *(__cp - 1))) >> - { >> - --__c; >> - --__cp; >> - } >> - if (__comp(*__pp, *__cp)) >> - { >> - value_type __t(_VSTD::move(*__pp)); >> - do >> - { >> - *__pp = _VSTD::move(*__cp); >> - __pp = __cp; >> - __p = __c; >> - __c = (__p + 1) * 2; >> - if (__c > __len) >> - break; >> - __cp = __first + __c; >> - if (__c == __len || __comp(*__cp, *(__cp - 1))) >> - { >> - --__c; >> - --__cp; >> - } >> - } while (__comp(__t, *__cp)); >> - *__pp = _VSTD::move(__t); >> - } >> - } >> -} >> - >> -template <class _Compare, class _RandomAccessIterator> >> -void >> -__push_heap_back(_RandomAccessIterator __first, _RandomAccessIterator >> __last, _Compare __comp, >> - typename >> iterator_traits<_RandomAccessIterator>::difference_type __len) >> +__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, >> _Compare __comp, >> + typename >> iterator_traits<_RandomAccessIterator>::difference_type __len) >> { >> typedef typename >> iterator_traits<_RandomAccessIterator>::difference_type difference_type; >> typedef typename iterator_traits<_RandomAccessIterator>::value_type >> value_type; >> @@ -4869,10 +4828,10 @@ push_heap(_RandomAccessIterator __first, >> #ifdef _LIBCPP_DEBUG >> typedef typename add_lvalue_reference<__debug_less<_Compare> >::type >> _Comp_ref; >> __debug_less<_Compare> __c(__comp); >> - __push_heap_back<_Comp_ref>(__first, __last, __c, __last - __first); >> + __sift_up<_Comp_ref>(__first, __last, __c, __last - __first); >> #else // _LIBCPP_DEBUG >> typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; >> - __push_heap_back<_Comp_ref>(__first, __last, __comp, __last - >> __first); >> + __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); >> #endif // _LIBCPP_DEBUG >> } >> >> @@ -4887,6 +4846,60 @@ push_heap(_RandomAccessIterator __first, >> // pop_heap >> >> template <class _Compare, class _RandomAccessIterator> >> +void >> +__sift_down(_RandomAccessIterator __first, _RandomAccessIterator __last, >> _Compare __comp, >> + typename >> iterator_traits<_RandomAccessIterator>::difference_type __len, >> + _RandomAccessIterator __start) >> +{ >> + typedef typename >> iterator_traits<_RandomAccessIterator>::difference_type difference_type; >> + typedef typename iterator_traits<_RandomAccessIterator>::value_type >> value_type; >> + // left-child of __start is at 2 * __start + 1 >> + // right-child of __start is at 2 * __start + 2 >> + difference_type __child = __start - __first; >> + >> + if (__len < 2 || (__len - 2) / 2 < __child) >> + return; >> + >> + __child = 2 * __child + 1; >> + _RandomAccessIterator __child_i = __first + __child; >> + >> + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { >> + // right-child exists and is greater than left-child >> + ++__child_i; >> + ++__child; >> + } >> + >> + // check if we are in heap-order >> + if (__comp(*__child_i, *__start)) >> + // we are, __start is larger than it's largest child >> + return; >> + >> + value_type __top(_VSTD::move(*__start)); >> + do >> + { >> + // we are not in heap-order, swap the parent with it's largest >> child >> + *__start = _VSTD::move(*__child_i); >> + __start = __child_i; >> + >> + if ((__len - 2) / 2 < __child) >> + break; >> + >> + // recompute the child based off of the updated parent >> + __child = 2 * __child + 1; >> + __child_i = __first + __child; >> + >> + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + >> 1))) { >> + // right-child exists and is greater than left-child >> + ++__child_i; >> + ++__child; >> + } >> + >> + // check if we are in heap-order >> + } while (!__comp(*__child_i, __top)); >> + *__start = _VSTD::move(__top); >> +} >> + >> +template <class _Compare, class _RandomAccessIterator> >> inline _LIBCPP_INLINE_VISIBILITY >> void >> __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, >> _Compare __comp, >> @@ -4895,7 +4908,7 @@ __pop_heap(_RandomAccessIterator __first >> if (__len > 1) >> { >> swap(*__first, *--__last); >> - __push_heap_front<_Compare>(__first, __last, __comp, __len-1); >> + __sift_down<_Compare>(__first, __last, __comp, __len - 1, >> __first); >> } >> } >> >> @@ -4932,10 +4945,11 @@ __make_heap(_RandomAccessIterator __firs >> difference_type __n = __last - __first; >> if (__n > 1) >> { >> - __last = __first; >> - ++__last; >> - for (difference_type __i = 1; __i < __n;) >> - __push_heap_back<_Compare>(__first, ++__last, __comp, ++__i); >> + // start from the first parent, there is no need to consider >> children >> + for (difference_type __start = (__n - 2) / 2; __start >= 0; >> --__start) >> + { >> + __sift_down<_Compare>(__first, __last, __comp, __n, __first >> + __start); >> + } >> } >> } >> >> @@ -5010,7 +5024,7 @@ __partial_sort(_RandomAccessIterator __f >> if (__comp(*__i, *__first)) >> { >> swap(*__i, *__first); >> - __push_heap_front<_Compare>(__first, __middle, __comp, >> __len); >> + __sift_down<_Compare>(__first, __middle, __comp, __len, >> __first); >> } >> } >> __sort_heap<_Compare>(__first, __middle, __comp); >> @@ -5051,15 +5065,15 @@ __partial_sort_copy(_InputIterator __fir >> _RandomAccessIterator __r = __result_first; >> if (__r != __result_last) >> { >> - typename iterator_traits<_RandomAccessIterator>::difference_type >> __len = 0; >> - for (; __first != __last && __r != __result_last; ++__first, >> ++__r, ++__len) >> + for (; __first != __last && __r != __result_last; ++__first, >> ++__r) >> *__r = *__first; >> __make_heap<_Compare>(__result_first, __r, __comp); >> + typename iterator_traits<_RandomAccessIterator>::difference_type >> __len = __r - __result_first; >> for (; __first != __last; ++__first) >> if (__comp(*__first, *__result_first)) >> { >> *__result_first = *__first; >> - __push_heap_front<_Compare>(__result_first, __r, __comp, >> __len); >> + __sift_down<_Compare>(__result_first, __r, __comp, >> __len, __result_first); >> } >> __sort_heap<_Compare>(__result_first, __r, __comp); >> } >> >> Modified: >> libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp >> URL: >> http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp?rev=213615&r1=213614&r2=213615&view=diff >> >> ============================================================================== >> --- >> libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp >> (original) >> +++ >> libcxx/trunk/test/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.pass.cpp >> Tue Jul 22 01:07:09 2014 >> @@ -35,14 +35,35 @@ struct indirect_less >> void test(unsigned N) >> { >> int* ia = new int [N]; >> + { >> for (int i = 0; i < N; ++i) >> ia[i] = i; >> - { >> std::random_shuffle(ia, ia+N); >> std::make_heap(ia, ia+N, std::greater<int>()); >> assert(std::is_heap(ia, ia+N, std::greater<int>())); >> } >> >> +// Ascending >> + { >> + binary_counting_predicate<std::greater<int>, int, int> pred >> ((std::greater<int>())); >> + for (int i = 0; i < N; ++i) >> + ia[i] = i; >> + std::make_heap(ia, ia+N, std::ref(pred)); >> + assert(pred.count() <= 3*N); >> + assert(std::is_heap(ia, ia+N, pred)); >> + } >> + >> +// Descending >> + { >> + binary_counting_predicate<std::greater<int>, int, int> pred >> ((std::greater<int>())); >> + for (int i = 0; i < N; ++i) >> + ia[N-1-i] = i; >> + std::make_heap(ia, ia+N, std::ref(pred)); >> + assert(pred.count() <= 3*N); >> + assert(std::is_heap(ia, ia+N, pred)); >> + } >> + >> +// Random >> { >> binary_counting_predicate<std::greater<int>, int, int> pred >> ((std::greater<int>())); >> std::random_shuffle(ia, ia+N); >> >> >> _______________________________________________ >> cfe-commits mailing list >> [email protected] >> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits >> > > >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
