Email Bill directly, or just commit the merge and let him know that you did it.
On Tue, Jul 29, 2014 at 7:53 PM, David Majnemer <[email protected]> wrote: > 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 > >
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
