detail/foa/cumulative_stats.hpp

0001 /* Copyright 2024 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See https://www.boost.org/libs/unordered for library home page.
0007  */
0008
0009 #ifndef BOOST_UNORDERED_DETAIL_FOA_CUMULATIVE_STATS_HPP
0010 #define BOOST_UNORDERED_DETAIL_FOA_CUMULATIVE_STATS_HPP
0011
0012 #include <array>
0013 #include <boost/config.hpp>
0014 #include <boost/mp11/tuple.hpp>
0015 #include <cmath>
0016 #include <cstddef>
0017
0018 #if defined(BOOST_HAS_THREADS)
0019 #include <boost/unordered/detail/foa/rw_spinlock.hpp>
0020 #include <mutex>
0021 #endif
0022
0023 namespace boost{
0024 namespace unordered{
0025 namespace detail{
0026 namespace foa{
0027
0028 /* Cumulative one-pass calculation of the average, variance and deviation of
0029  * running sequences.
0030  */
0031
0032 struct sequence_stats_data
0033 {
0034   double m=0.0;
0035   double m_prior=0.0;
0036   double s=0.0;
0037 };
0038
0039 struct welfords_algorithm /* 0-based */
0040 {
0041   template<typename T>
0042   int operator()(T&& x,sequence_stats_data& d)const noexcept
0043   {
0044     static_assert(
0045       noexcept(static_cast<double>(x)),
0046       "Argument conversion to double must not throw.");
0047
0048     d.m_prior=d.m;
0049     d.m+=(static_cast<double>(x)-d.m)/static_cast<double>(n);
0050     d.s+=(n!=1)*
0051       (static_cast<double>(x)-d.m_prior)*(static_cast<double>(x)-d.m);
0052
0053     return 0; /* mp11::tuple_transform requires that return type not be void */
0054   }
0055
0056   std::size_t n;
0057 };
0058
0059 struct sequence_stats_summary
0060 {
0061   double average;
0062   double variance;
0063   double deviation;
0064 };
0065
0066 /* Stats calculated jointly for N same-sized sequences to save the space
0067  * for count.
0068  */
0069
0070 template<std::size_t N>
0071 class cumulative_stats
0072 {
0073 public:
0074   struct summary
0075   {
0076     std::size_t                          count;
0077     std::array<sequence_stats_summary,N> sequence_summary;
0078   };
0079
0080   void reset()noexcept{*this=cumulative_stats();}
0081
0082   template<typename... Ts>
0083   void add(Ts&&... xs)noexcept
0084   {
0085     static_assert(
0086       sizeof...(Ts)==N,"A sample must be provided for each sequence.");
0087
0088     if(BOOST_UNLIKELY(++n==0)){ /* wraparound */
0089       reset();
0090       n=1;
0091     }
0092     mp11::tuple_transform(
0093       welfords_algorithm{n},
0094       std::forward_as_tuple(std::forward<Ts>(xs)...),
0095       data);
0096   }
0097
0098   summary get_summary()const noexcept
0099   {
0100     summary res;
0101     res.count=n;
0102     for(std::size_t i=0;i<N;++i){
0103       double average=data[i].m,
0104              variance=n!=0?data[i].s/static_cast<double>(n):0.0, /* biased */
0105              deviation=std::sqrt(variance);
0106       res.sequence_summary[i]={average,variance,deviation};
0107     }
0108     return res;
0109   }
0110
0111 private:
0112   std::size_t                       n=0;
0113   std::array<sequence_stats_data,N> data;
0114 };
0115
0116 #if defined(BOOST_HAS_THREADS)
0117
0118 template<std::size_t N>
0119 class concurrent_cumulative_stats:cumulative_stats<N>
0120 {
0121   using super=cumulative_stats<N>;
0122   using lock_guard=std::lock_guard<rw_spinlock>;
0123
0124 public:
0125   using summary=typename super::summary;
0126
0127   concurrent_cumulative_stats()noexcept:super{}{}
0128   concurrent_cumulative_stats(const concurrent_cumulative_stats& x)noexcept:
0129     concurrent_cumulative_stats{x,lock_guard{x.mut}}{}
0130
0131   concurrent_cumulative_stats&
0132   operator=(const concurrent_cumulative_stats& x)noexcept
0133   {
0134     auto x1=x;
0135     lock_guard lck{mut};
0136     static_cast<super&>(*this)=x1;
0137     return *this;
0138   }
0139
0140   void reset()noexcept
0141   {
0142     lock_guard lck{mut};
0143     super::reset();
0144   }
0145
0146   template<typename... Ts>
0147   void add(Ts&&... xs)noexcept
0148   {
0149     lock_guard lck{mut};
0150     super::add(std::forward<Ts>(xs)...);
0151   }
0152
0153   summary get_summary()const noexcept
0154   {
0155     lock_guard lck{mut};
0156     return super::get_summary();
0157   }
0158
0159 private:
0160   concurrent_cumulative_stats(const super& x,lock_guard&&):super{x}{}
0161
0162   mutable rw_spinlock mut;
0163 };
0164
0165 #else
0166
0167 template<std::size_t N>
0168 using concurrent_cumulative_stats=cumulative_stats<N>;
0169
0170 #endif
0171
0172 } /* namespace foa */
0173 } /* namespace detail */
0174 } /* namespace unordered */
0175 } /* namespace boost */
0176
0177 #endif