Partitioner.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2022 Rogiel Sulzbach. All rights reserved.
//
 
#pragma once
 
#include "CeresEngine/Foundation/Threading/ExecutionContext.hpp"
#include "CeresEngine/Foundation/Traits/is_input_iterator.hpp"
#include "CeresEngine/Foundation/Traits/is_input_range.hpp"
#include "CeresEngine/Foundation/Traits/is_range.hpp"
#include "CeresEngine/Foundation/Traits/is_sentinel_for.hpp"
 
#include <algorithm>
#include <cstddef>
#include <thread>
 
 
namespace CeresEngine {
 
    class HalvePartitioner {
        std::size_t mMinimumGrainSize;
 
    public:
        constexpr explicit HalvePartitioner(const std::size_t minimumGrainSize) : mMinimumGrainSize(minimumGrainSize) {}
 
        template<typename I, typename S> auto operator()(I first, S last) {
            const std::size_t size = std::distance(first, last);
            return (size <= mMinimumGrainSize) ? last : std::next(first, (size + 1) / 2);
        }
    };
 
    class ThreadPartitioner {
        std::size_t mMinimumGrainSize;
        std::size_t mThreadCount{hardware_concurrency()};
 
    public:
        explicit ThreadPartitioner(const std::size_t minimumGrainSize, const std::size_t occupancy = hardware_concurrency())
                : mMinimumGrainSize(minimumGrainSize), mThreadCount(occupancy) {}
 
        template<typename I, typename S> auto operator()(I first, S last) {
            if(mThreadCount <= 1) {
                return last;
            }
 
            mThreadCount = (mThreadCount + 1) / 2;
            const std::size_t size = std::distance(first, last);
            return (size <= mMinimumGrainSize) ? last : std::next(first, (size + 1) / 2);
        }
    };
 
    using DefaultPartitioner = ThreadPartitioner;
 
    constexpr std::size_t make_grain_size(const std::size_t n, const std::size_t occupancy = hardware_concurrency()) {
        return std::clamp(n / (8 * std::max(occupancy, static_cast<std::size_t>(1))), size_t(1), size_t(2048));
    }
 
    inline DefaultPartitioner make_default_partitioner(const size_t n, const std::size_t occupancy = hardware_concurrency()) {
        return DefaultPartitioner(make_grain_size(n, occupancy), occupancy);
    }
 
    template<traits::input_iterator I, traits::sentinel_for<I> S>
    DefaultPartitioner make_default_partitioner(I first, S last, const std::size_t occupancy = hardware_concurrency()) {
        return make_default_partitioner(std::distance(first, last), occupancy);
    }
 
    template<traits::input_range R> DefaultPartitioner make_default_partitioner(R&& r, std::size_t occupancy = hardware_concurrency()) {
        return make_default_partitioner(std::begin(r), std::end(r), occupancy);
    }
 
    template<traits::executor E> DefaultPartitioner make_default_partitioner(const E& executor, const size_t n) {
        if constexpr(can_query<E, ExecutorOccupancy>::value) {
            const size_t occupancy = query(executor, ExecutorOccupancy{});
            return make_default_partitioner(n, occupancy);
        }
        return make_default_partitioner(n);
    }
 
    template<traits::executor E, traits::input_iterator I, traits::sentinel_for<I> S>
    DefaultPartitioner make_default_partitioner(const E& executor, I first, S last) {
        return make_default_partitioner(executor, std::distance(first, last));
    }
 
    template<traits::executor E, traits::input_range R> DefaultPartitioner make_default_partitioner(const E& executor, R&& r) {
        return make_default_partitioner(executor, std::begin(r), std::end(r));
    }
 
    namespace traits {
        template<class T, class I, class S>
        using is_partitioner = std::conjunction<std::conditional_t<traits::is_input_iterator_v<I>, std::true_type, std::false_type>,
            std::conditional_t<traits::is_input_iterator_v<S>, std::true_type, std::false_type>, std::is_invocable<T, I, S>>;
 
        template<class T, class I, class S> constexpr bool is_partitioner_v = is_partitioner<T, I, S>::value;
 
        template<class T, class I, class S>
        concept partitioner = is_partitioner_v<T, I, S>;
 
        template<class T, class R> struct is_range_partitioner : std::false_type {};
        template<class T, traits::range R> struct is_range_partitioner<T, R> : is_partitioner<T, traits::iterator_t<R>, traits::iterator_t<R>> {};
 
        template<class T, class R> constexpr bool is_range_partitioner_v = is_range_partitioner<T, R>::value;
 
        template<class T, class R>
        concept range_partitioner = is_range_partitioner_v<T, R>;
    } // namespace traits
 
} // namespace CeresEngine