compute/algorithm/merge.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
0003 //
0004 // Distributed under the Boost Software License, Version 1.0
0005 // See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // See http://boostorg.github.com/compute for more information.
0009 //---------------------------------------------------------------------------//
0010
0011 #ifndef BOOST_COMPUTE_ALGORITHM_MERGE_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_MERGE_HPP
0013
0014 #include <boost/static_assert.hpp>
0015
0016 #include <boost/compute/system.hpp>
0017 #include <boost/compute/command_queue.hpp>
0018 #include <boost/compute/algorithm/copy.hpp>
0019 #include <boost/compute/algorithm/detail/merge_with_merge_path.hpp>
0020 #include <boost/compute/algorithm/detail/serial_merge.hpp>
0021 #include <boost/compute/detail/iterator_range_size.hpp>
0022 #include <boost/compute/detail/parameter_cache.hpp>
0023 #include <boost/compute/type_traits/is_device_iterator.hpp>
0024
0025 namespace boost {
0026 namespace compute {
0027
0028 /// Merges the sorted values in the range [\p first1, \p last1) with the sorted
0029 /// values in the range [\p first2, last2) and stores the result in the range
0030 /// beginning at \p result. Values are compared using the \p comp function. If
0031 /// no comparision function is given, \c less is used.
0032 ///
0033 /// \param first1 first element in the first range to merge
0034 /// \param last1 last element in the first range to merge
0035 /// \param first2 first element in the second range to merge
0036 /// \param last2 last element in the second range to merge
0037 /// \param result first element in the result range
0038 /// \param comp comparison function (by default \c less)
0039 /// \param queue command queue to perform the operation
0040 ///
0041 /// \return \c OutputIterator to the end of the result range
0042 ///
0043 /// Space complexity: \Omega(distance(\p first1, \p last1) + distance(\p first2, \p last2))
0044 ///
0045 /// \see inplace_merge()
0046 template<class InputIterator1,
0047          class InputIterator2,
0048          class OutputIterator,
0049          class Compare>
0050 inline OutputIterator merge(InputIterator1 first1,
0051                             InputIterator1 last1,
0052                             InputIterator2 first2,
0053                             InputIterator2 last2,
0054                             OutputIterator result,
0055                             Compare comp,
0056                             command_queue &queue = system::default_queue())
0057 {
0058     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator1>::value);
0059     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator2>::value);
0060     BOOST_STATIC_ASSERT(is_device_iterator<OutputIterator>::value);
0061     typedef typename std::iterator_traits<InputIterator1>::value_type input1_type;
0062     typedef typename std::iterator_traits<InputIterator2>::value_type input2_type;
0063     typedef typename std::iterator_traits<OutputIterator>::value_type output_type;
0064
0065     const device &device = queue.get_device();
0066
0067     std::string cache_key =
0068         std::string("__boost_merge_") + type_name<input1_type>() + "_"
0069         + type_name<input2_type>() + "_" + type_name<output_type>();
0070     boost::shared_ptr<detail::parameter_cache> parameters =
0071         detail::parameter_cache::get_global_cache(device);
0072
0073     // default serial merge threshold depends on device type
0074     size_t default_serial_merge_threshold = 32768;
0075     if(device.type() & device::gpu) {
0076         default_serial_merge_threshold = 2048;
0077     }
0078
0079     // loading serial merge threshold parameter
0080     const size_t serial_merge_threshold =
0081         parameters->get(cache_key, "serial_merge_threshold",
0082                         static_cast<uint_>(default_serial_merge_threshold));
0083
0084     // choosing merge algorithm
0085     const size_t total_count =
0086         detail::iterator_range_size(first1, last1)
0087         + detail::iterator_range_size(first2, last2);
0088     // for small inputs serial merge turns out to outperform
0089     // merge with merge path algorithm
0090     if(total_count <= serial_merge_threshold){
0091        return detail::serial_merge(first1, last1, first2, last2, result, comp, queue);
0092     }
0093     return detail::merge_with_merge_path(first1, last1, first2, last2, result, comp, queue);
0094 }
0095
0096 /// \overload
0097 template<class InputIterator1, class InputIterator2, class OutputIterator>
0098 inline OutputIterator merge(InputIterator1 first1,
0099                             InputIterator1 last1,
0100                             InputIterator2 first2,
0101                             InputIterator2 last2,
0102                             OutputIterator result,
0103                             command_queue &queue = system::default_queue())
0104 {
0105     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator1>::value);
0106     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator2>::value);
0107     BOOST_STATIC_ASSERT(is_device_iterator<OutputIterator>::value);
0108     typedef typename std::iterator_traits<InputIterator1>::value_type value_type;
0109     less<value_type> less_than;
0110     return merge(first1, last1, first2, last2, result, less_than, queue);
0111 }
0112
0113 } // end compute namespace
0114 } // end boost namespace
0115
0116 #endif // BOOST_COMPUTE_ALGORITHM_MERGE_HPP