indirect_sort.test

PREAMBLE = \
    """
    #include <thrust/sort.h>

    template <typename RandomAccessIterator, typename StrictWeakOrdering> 
    struct indirect_comp
    {
        RandomAccessIterator first;
        StrictWeakOrdering   comp;
    
        indirect_comp(RandomAccessIterator first, StrictWeakOrdering comp)
            : first(first), comp(comp) {}
    
        template <typename IndexType>
        __host__ __device__
        bool operator()(IndexType a, IndexType b)
        {
            return comp(thrust::raw_reference_cast(first[a]), thrust::raw_reference_cast(first[b]));
        }    
    };
    
    
    template <typename RandomAccessIterator, typename StrictWeakOrdering>
    void indirect_sort(RandomAccessIterator first,
                       RandomAccessIterator last,
                       StrictWeakOrdering comp)
    {
        typedef typename thrust::iterator_traits<RandomAccessIterator>::value_type T;
        
        // todo initialize vector in one step
        thrust::device_vector<unsigned int> permutation(last - first);
        thrust::sequence(permutation.begin(), permutation.end());  
        
        thrust::stable_sort(permutation.begin(), permutation.end(),
                            indirect_comp<RandomAccessIterator,StrictWeakOrdering>(first, comp));
    
        thrust::device_vector<T> temp(first, last);
    
        thrust::gather(permutation.begin(), permutation.end(), temp.begin(), first);
    }
    """

INITIALIZE = \
    """
    typedef FixedVector<int,$VectorLength> KeyType;

    const size_t N = $InputSize / sizeof(KeyType);

    thrust::host_vector<KeyType>   h_keys(N);
        
    for(size_t i = 0; i < h_keys.size(); i++)
        h_keys[i] = KeyType(rand());
    
    thrust::device_vector<KeyType> d_keys      = h_keys;
    thrust::device_vector<KeyType> d_keys_copy = d_keys;
   
    thrust::less<KeyType> comp;

    // test sort
    thrust::stable_sort(h_keys.begin(), h_keys.end());
    $Sort(d_keys.begin(), d_keys.end(), comp);

    ASSERT_EQUAL_QUIET(h_keys, d_keys);
    """

TIME = \
    """
    thrust::copy(d_keys_copy.begin(), d_keys_copy.end(), d_keys.begin());
    $Sort(d_keys.begin(), d_keys.end(), comp);
    """

FINALIZE = \
    """
    RECORD_TIME();
    RECORD_SORTING_RATE(double($InputSize));
    """

VectorLengths = [2**N for N in range(1,14)]
Sorts         = ['indirect_sort']

#VectorLengths = range(1,9)
#Sorts         = ['indirect_sort', 'thrust::stable_sort']

InputSizes    = [2**24]

TestVariables = [('VectorLength', VectorLengths), ('Sort', Sorts), ('InputSize', InputSizes)]