include/backoff.hpp - main - Ant010ff/ffpp

include/backoff.hpp
518 строк18 KB
Ant010ff
Version 2.11.3.
08 авг 2026, 16:44
08 авг 2026, 16:44fd187d3
/*
This header is part of a Functional Flow Processing Primitives (FFPP) library, version 2.11.3.

Official repository: https://gitlab.com/ant010ff/ffpp

Licensed under the MIT License <http://opensource.org/licenses/MIT>.
SPDX-License-Identifier: MIT
Copyright (c) 2021 - 2026 Anton Nasonov <ant010fff @ gmail . com>.
*/

#ifndef FFPP_BACKOFF_HPP
#define FFPP_BACKOFF_HPP

namespace FFPP {

	FFPP_ATTR_INLINE
	inline void Pause() noexcept {
		#if defined(__GNUC__) || defined(__clang__)
			#if defined(__i386__) || defined(__x86_64__)
				__asm__ __volatile__("pause" ::: "memory");
			#elif (defined(__ARM_ARCH) && __ARM_ARCH >= 8) || defined(__ARM_ARCH_8A__) || defined(__aarch64__)
				__asm__ __volatile__("yield" ::: "memory");
			#elif defined(__riscv)
				__asm__ __volatile__(".insn i 0x0F, 0, x0, x0, 0x010" ::: "memory");
			#elif defined(__ppc64__) || defined(__powerpc64__)
				__asm__ __volatile__("or 27,27,27" ::: "memory");
			#else
				__asm__ __volatile__("" ::: "memory");
			#endif
		#elif defined(_MSC_VER)
			#if defined(_M_AMD64) || defined(_M_IX86)
				_mm_pause();
				std::atomic_signal_fence(std::memory_order::acq_rel);
			#elif defined(_M_ARM64) || defined(_M_ARM)
				__yield();
				std::atomic_signal_fence(std::memory_order::acq_rel);
			#else
				std::atomic_thread_fence(std::memory_order::acq_rel);
			#endif
		#else
			std::atomic_thread_fence(std::memory_order::acq_rel);
		#endif
	}//Pause

	using BackoffHandlerT = Function<bool()>;
	
    FFPP_ATTR_INLINE
	inline uint8_t RandomJitter(uint8_t nFactor) noexcept {
		//Combining high-order bits of XorShift (better quality) with multiply-shift instead of (% nFactor).
		constexpr uint8_t nShift = std::numeric_limits<size_t>::digits / 2;
		return static_cast<uint8_t>(((prng::XorShift() >> nShift) * nFactor) >> nShift);
	}//RandomJitter

    FFPP_ATTR_INLINE
	inline size_t RandomDeviation(size_t nBase, uint8_t nFactor, size_t nRandom = prng::XoShiRo()) noexcept {
		size_t const nLimit = nBase >> nFactor;
		return (nBase - nLimit) + math::MulHi(nRandom, nLimit << 1);
	}//RandomDeviation

	constexpr auto NoBackoff() {
		return [] () noexcept { return false; };
	}

	template<
		bool					t_bYield, 
		uint8_t 				t_nWaitStopFactor 	= 7, 
		uint8_t					t_nSleepFactor		= 8,
		uint16_t				t_usSleep			= 1,
		uint8_t 				t_nWaitStartFactor	= 1,
		std::unsigned_integral	TCounter 			= uint32_t
	>
	consteval auto Backoff() {
		static_assert(t_nWaitStopFactor < std::numeric_limits<TCounter>::digits, "t_nWaitStopFactor exceeds counter limit.");
		static_assert(t_nWaitStopFactor > 0, "t_nWaitStopFactor must be greater than zero.");
		static_assert(t_nWaitStopFactor > t_nWaitStartFactor, "t_nWaitStopFactor must be greater than t_nWaitStartFactor.");
		TCounter constexpr c_nOne = TCounter(1);
		TCounter constexpr c_nWaitStop = (c_nOne << t_nWaitStopFactor);
		TCounter constexpr c_nWaitStart = (c_nOne << t_nWaitStartFactor);
		if constexpr(t_nSleepFactor > 0) {			
			static_assert(t_nSleepFactor < std::numeric_limits<TCounter>::digits, "t_nSleepFactor exceeds counter limit.");
			TCounter constexpr c_nYields = (c_nOne << t_nSleepFactor);
			return [nWait = c_nWaitStart, nUntilSleep = c_nYields] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
						nUntilSleep = c_nYields;
						std::this_thread::sleep_for(std::chrono::microseconds(t_usSleep));
					}
					return false;
				}
				else {
					for(TCounter i = nWait; i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
		else {			
			return [nWait = c_nWaitStart] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					return false;
				}
				else {
					for(TCounter i = nWait; i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
	}//Backoff<>

	template<
		bool					t_bYield, 
		uint8_t 				t_nWaitStopFactor 	= 7, 
		uint8_t					t_nSleepFactor		= 8,
		uint16_t				t_usSleep			= 1,
		uint8_t 				t_nWaitStartFactor	= 1, 
		uint8_t 				t_nJitterFactor 	= 6,
		std::unsigned_integral	TCounter 			= uint32_t
	>
	consteval auto JitteredBackoff() {
		static_assert(t_nWaitStopFactor < std::numeric_limits<TCounter>::digits, "t_nWaitStopFactor exceeds counter limit.");
		static_assert(t_nWaitStopFactor > 0, "t_nWaitStopFactor must be greater than zero.");
		static_assert(t_nWaitStopFactor > t_nWaitStartFactor, "t_nWaitStopFactor must be greater than t_nWaitStartFactor.");
		TCounter constexpr c_nOne = TCounter(1);
		TCounter constexpr c_nZero = TCounter(0);
		TCounter constexpr c_nAll = TCounter(-1);
		TCounter constexpr c_nWaitStop = (c_nOne << t_nWaitStopFactor);
		TCounter constexpr c_nWaitStart = (c_nOne << t_nWaitStartFactor);
		TCounter constexpr c_nJitterStart = c_nWaitStart;
		if constexpr(t_nSleepFactor > 0) {
			static_assert(t_nSleepFactor < std::numeric_limits<TCounter>::digits, "t_nSleepFactor exceeds counter limit.");
			TCounter constexpr c_nYields = (c_nOne << t_nSleepFactor);
			return [
				nWait = c_nWaitStart, 
				nJitter = c_nJitterStart,
				nJitterStop = t_nJitterFactor > 0 ? c_nAll : c_nZero,
				nUntilSleep = c_nYields
			] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					//[2] busy-wait phase completed. Check whether jitter phase enabled (t_nJitterFactor > 0).
					if(nJitterStop == c_nAll) {
						//[3] calculate additional jitter phase duration.
						nJitterStop = (c_nOne << RandomJitter(t_nJitterFactor + 1));
					}
					if(nJitter > nJitterStop || nJitter == 0) [[unlikely]] {
						//[5] jitter phase either completed or disabled. Reset state for next back-off run and yield thread if enabled.
						nWait = c_nWaitStart;
						if constexpr(t_nJitterFactor > 0) {
							nJitter = c_nJitterStart;
							nJitterStop = c_nAll; //new jitter duration for the next back-off run
						}
						if constexpr(t_bYield) std::this_thread::yield();
						if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
							//[6] finally try to sleep thread shortly (actual duration depends on OS/environment) after a number of 
							//busy-wait/yield phases as they failed to mitigate contention.
							nUntilSleep = c_nYields;
							std::this_thread::sleep_for(std::chrono::microseconds(t_usSleep));
						}
						return false;
					}
					else {
						//[4] additional random jitter busy-wait phase.
						for(TCounter i = nJitter; i > 0; --i) FFPP::Pause();
						nJitter <<= 1;
						return true;
					}
				}
				else {
					//[1] main busy-wait phase.
					for(TCounter i = nWait; i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
		else {
			return [
				nWait = c_nWaitStart, 
				nJitter = c_nJitterStart,
				nJitterStop = t_nJitterFactor > 0 ? c_nAll : c_nZero
			] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					//[2] busy-wait phase completed. Check whether jitter phase enabled (t_nJitterFactor > 0).
					if(nJitterStop == c_nAll) {
						//[3] calculate additional jitter phase duration.
						nJitterStop = (c_nOne << RandomJitter(t_nJitterFactor + 1));
					}
					if(nJitter > nJitterStop || nJitter == 0) [[unlikely]] {
						//[5] jitter phase either completed or disabled. Reset state for next back-off run and yield thread if enabled.
						nWait = c_nWaitStart;
						if constexpr(t_nJitterFactor > 0) {
							nJitter = c_nJitterStart;
							nJitterStop = c_nAll; //new jitter duration for the next back-off run
						}
						if constexpr(t_bYield) std::this_thread::yield();
						return false;
					}
					else {
						//[4] additional random jitter busy-wait phase.
						for(TCounter i = nJitter; i > 0; --i) FFPP::Pause();
						nJitter <<= 1;
						return true;
					}
				}
				else {
					//[1] main busy-wait phase.
					for(TCounter i = nWait; i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
	}//JitteredBackoff<>

	template<
		bool					t_bYield, 
		uint8_t 				t_nWaitStopFactor 	= 7, 
		uint8_t					t_nSleepFactor		= 8,
		uint16_t				t_usSleep			= 1,
		uint8_t 				t_nWaitStartFactor	= 1,
		uint8_t 				t_nDeviationFactor 	= 2, //random deviation within +-25% from current exponential base value
		std::unsigned_integral	TCounter 			= uint32_t
	>
	consteval auto NoisyBackoff() {
		static_assert(t_nWaitStopFactor < std::numeric_limits<TCounter>::digits, "t_nWaitStopFactor exceeds counter limit.");
		static_assert(t_nWaitStopFactor > 0, "t_nWaitStopFactor must be greater than zero.");
		static_assert(t_nWaitStopFactor > t_nWaitStartFactor, "t_nWaitStopFactor must be greater than t_nWaitStartFactor.");
		TCounter constexpr c_nOne = TCounter(1);
		TCounter constexpr c_nWaitStop = (c_nOne << t_nWaitStopFactor);
		TCounter constexpr c_nWaitStart = (c_nOne << t_nWaitStartFactor);
		if constexpr(t_nSleepFactor > 0) {			
			static_assert(t_nSleepFactor < std::numeric_limits<TCounter>::digits, "t_nSleepFactor exceeds counter limit.");
			TCounter constexpr c_nYields = (c_nOne << t_nSleepFactor);
			return [nRandom = size_t(0), nArbitrary = size_t(0), nWait = c_nWaitStart, nUntilSleep = c_nYields] () mutable noexcept {
				if(nRandom == nArbitrary) [[unlikely]] {
					nRandom = prng::XoShiRo();
					nArbitrary = nRandom;
				}
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
						nUntilSleep = c_nYields;
						std::this_thread::sleep_for(std::chrono::microseconds(t_usSleep));
					}
					return false;
				}
				else {
					for(size_t i = RandomDeviation(nWait, t_nDeviationFactor, nArbitrary); i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					nArbitrary = std::rotr(nArbitrary, int(t_nDeviationFactor));
					return true;
				}
			};
		}
		else {			
			return [nRandom = size_t(0), nArbitrary = size_t(0), nWait = c_nWaitStart] () mutable noexcept {
				if(nRandom == nArbitrary) [[unlikely]] {
					nRandom = prng::XoShiRo();
					nArbitrary = nRandom;
				}
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					return false;
				}
				else {
					for(size_t i = RandomDeviation(nWait, t_nDeviationFactor, nArbitrary); i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					nArbitrary = std::rotr(nArbitrary, int(t_nDeviationFactor));
					return true;
				}
			};
		}
	}//NoisyBackoff<>

	template<
		bool					t_bYield, 
		uint8_t 				t_nWaitStopFactor 	= 7, 
		uint8_t					t_nSleepFactor		= 8,
		uint16_t				t_usSleep			= 1,
		uint8_t 				t_nWaitStartFactor	= 1, 
		uint8_t 				t_nDeviationFactor 	= 1, //random deviation within +-50% from current exponential base value
		std::unsigned_integral	TCounter 			= uint32_t
	>
	consteval auto HighEntropyBackoff() {
		static_assert(t_nWaitStopFactor < std::numeric_limits<TCounter>::digits, "t_nWaitStopFactor exceeds counter limit.");
		static_assert(t_nWaitStopFactor > 0, "t_nWaitStopFactor must be greater than zero.");
		static_assert(t_nWaitStopFactor > t_nWaitStartFactor, "t_nWaitStopFactor must be greater than t_nWaitStartFactor.");
		TCounter constexpr c_nOne = TCounter(1);
		TCounter constexpr c_nWaitStop = (c_nOne << t_nWaitStopFactor);
		TCounter constexpr c_nWaitStart = (c_nOne << t_nWaitStartFactor);
		if constexpr(t_nSleepFactor > 0) {
			static_assert(t_nSleepFactor < std::numeric_limits<TCounter>::digits, "t_nSleepFactor exceeds counter limit.");
			TCounter constexpr c_nYields = (c_nOne << t_nSleepFactor);
			return [nWait = c_nWaitStart, nUntilSleep = c_nYields] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
						nUntilSleep = c_nYields;
						std::this_thread::sleep_for(std::chrono::microseconds(t_usSleep));
					}
					return false;
				}
				else {
					for(size_t i = RandomDeviation(nWait, t_nDeviationFactor); i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
		else {			
			return [nWait = c_nWaitStart] () mutable noexcept {
				if(nWait > c_nWaitStop || nWait == 0) [[unlikely]] {
					nWait = c_nWaitStart;
					if constexpr(t_bYield) std::this_thread::yield();
					return false;
				}
				else {
					for(size_t i = RandomDeviation(nWait, t_nDeviationFactor); i > 0; --i) FFPP::Pause();
					nWait <<= 1;
					return true;
				}
			};
		}
	}//HighEntropyBackoff<>

	constexpr auto Backoff(
		bool		bYield 				= true, 
		uint8_t 	nWaitStopFactor 	= 7, 
		uint8_t		nSleepFactor		= 8,
		uint16_t	usSleep				= 1,
		uint8_t 	nWaitStartFactor	= 1
	) {
		using CounterT = uint32_t;
		CounterT constexpr c_nOne = CounterT(1);
		CounterT constexpr c_nZero = CounterT(0);
		return [
			bYield, 
			nWaitStart = (c_nOne << nWaitStartFactor),
			nWaitStop = (c_nOne << nWaitStopFactor),
			nWait = (c_nOne << nWaitStartFactor),
			nUntilSleep = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			nYields = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			usSleep
		] () mutable noexcept {
			if(nWait > nWaitStop || nWait == 0) [[unlikely]] {
				nWait = nWaitStart;
				if(bYield) std::this_thread::yield();
				if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
					nUntilSleep = nYields;
					std::this_thread::sleep_for(std::chrono::microseconds(usSleep));
				}
				return false;
			}
			else {
				for(uint32_t i = nWait; i > 0; --i) FFPP::Pause();
				nWait <<= 1;
				return true;
			}
		};
	}//Backoff

	constexpr auto JitteredBackoff(
		bool		bYield 				= true, 
		uint8_t 	nWaitStopFactor 	= 7, 
		uint8_t		nSleepFactor		= 8,
		uint16_t	usSleep				= 1,
		uint8_t 	nWaitStartFactor	= 1, 
		uint8_t 	nJitterFactor 		= 6
	) {
		using CounterT = uint32_t;
		CounterT constexpr c_nOne = CounterT(1);
		CounterT constexpr c_nZero = CounterT(0);
		CounterT constexpr c_nAll = CounterT(-1);
		return [
			bYield, 
			nJitterFactor,
			nJitterLimit = nJitterFactor + 1,
			nWaitStart = (c_nOne << nWaitStartFactor),
			nWaitStop = (c_nOne << nWaitStopFactor),
			nWait = (c_nOne << nWaitStartFactor), 
			nJitterStart = (c_nOne << nWaitStartFactor),
			nJitterStop = nJitterFactor > 0 ? c_nAll : c_nZero,
			nJitter = (c_nOne << nWaitStartFactor),
			nUntilSleep = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			nYields = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			usSleep
		] () mutable noexcept {
			if(nWait > nWaitStop || nWait == 0) [[unlikely]] {
				//[2] busy-wait phase completed. Check whether jitter phase enabled (nJitterFactor > 0).
				if(nJitterStop == c_nAll) {
					//[3] calculate additional jitter phase duration.
					nJitterStop = (c_nOne << RandomJitter(nJitterLimit));
				}
				if(nJitter > nJitterStop || nJitter == 0) [[unlikely]] {
					//[5] jitter phase either completed or disabled. Reset state for next back-off run and yield thread if enabled.
					nWait = nWaitStart;
					if(nJitterFactor > 0) {
						nJitter = nJitterStart;
						nJitterStop = c_nAll; //new jitter duration for the next back-off run
					}
					if(bYield) std::this_thread::yield();
					if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
						//[6] finally try to sleep thread shortly (actual duration depends on OS/environment) after a number of 
						//busy-wait/yield phases as they failed to mitigate contention.
						nUntilSleep = nYields;
						std::this_thread::sleep_for(std::chrono::microseconds(usSleep));
					}
					return false;
				}
				else {
					//[4] additional random jitter busy-wait phase.
					for(uint32_t i = nJitter; i > 0; --i) FFPP::Pause();
					nJitter <<= 1;
					return true;
				}
			}
			else {
				//[1] main busy-wait phase.
				for(uint32_t i = nWait; i > 0; --i) FFPP::Pause();
				nWait <<= 1;
				return true;
			}
		};
	}//JitteredBackoff

	constexpr auto NoisyBackoff(
		bool		bYield 				= true, 
		uint8_t 	nWaitStopFactor 	= 7, 
		uint8_t		nSleepFactor		= 8,
		uint16_t	usSleep				= 1,
		uint8_t 	nWaitStartFactor	= 1, 
		uint8_t 	nDeviationFactor 	= 2
	) {
		using CounterT = uint32_t;
		CounterT constexpr c_nOne = CounterT(1);
		CounterT constexpr c_nZero = CounterT(0);
		return [
			bYield, 
			nDeviationFactor,
			nRandom = size_t(0),
			nArbitrary = size_t(0),
			nWaitStart = (c_nOne << nWaitStartFactor),
			nWaitStop = (c_nOne << nWaitStopFactor),
			nWait = (c_nOne << nWaitStartFactor), 
			nUntilSleep = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			nYields = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			usSleep
		] () mutable noexcept {
			if(nRandom == nArbitrary) [[unlikely]] {
				nRandom = prng::XoShiRo();
				nArbitrary = nRandom;
			}
			if(nWait > nWaitStop || nWait == 0) [[unlikely]] {
				nWait = nWaitStart;
				if(bYield) std::this_thread::yield();
				if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
					nUntilSleep = nYields;
					std::this_thread::sleep_for(std::chrono::microseconds(usSleep));
				}
				return false;
			}
			else {
				for(size_t i = RandomDeviation(nWait, nDeviationFactor, nArbitrary); i > 0; --i) FFPP::Pause();
				nWait <<= 1;
				nArbitrary = std::rotr(nArbitrary, int(nDeviationFactor));
				return true;
			}
		};
	}//NoisyBackoff

	constexpr auto HighEntropyBackoff(
		bool		bYield 				= true, 
		uint8_t 	nWaitStopFactor 	= 7, 
		uint8_t		nSleepFactor		= 8,
		uint16_t	usSleep				= 1,
		uint8_t 	nWaitStartFactor	= 1, 
		uint8_t 	nDeviationFactor 	= 2
	) {
		using CounterT = uint32_t;
		CounterT constexpr c_nOne = CounterT(1);
		CounterT constexpr c_nZero = CounterT(0);
		return [
			bYield, 
			nDeviationFactor,
			nWaitStart = (c_nOne << nWaitStartFactor),
			nWaitStop = (c_nOne << nWaitStopFactor),
			nWait = (c_nOne << nWaitStartFactor), 
			nUntilSleep = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			nYields = nSleepFactor > 0 ? (c_nOne << nSleepFactor) : c_nZero,
			usSleep
		] () mutable noexcept {
			if(nWait > nWaitStop || nWait == 0) [[unlikely]] {
				nWait = nWaitStart;
				if(bYield) std::this_thread::yield();
				if(nUntilSleep > 0 && --nUntilSleep == 0) [[unlikely]] {
					nUntilSleep = nYields;
					std::this_thread::sleep_for(std::chrono::microseconds(usSleep));
				}
				return false;
			}
			else {
				for(size_t i = RandomDeviation(nWait, nDeviationFactor); i > 0; --i) FFPP::Pause();
				nWait <<= 1;
				return true;
			}
		};
	}//HighEntropyBackoff

}//FFPP

#endif//FFPP_BACKOFF_HPP