Re: [boost] [devector] optimum growing/insertion policy

Subject: Re: [boost] [devector] optimum growing/insertion policy
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-11-01 21:29:33

El 01/11/2017 a las 20:21, Thorsten Ottosen escribió:
> Den 26-10-2017 kl. 19:59 skrev Joaquin M López Muñoz via Boost:
>> El 26/10/2017 a las 17:08, Thorsten Ottosen escribió:
>>> But the policy does not know size() unless we pass it that too.
>>
>> Yes, it need access the size and front and back capacity. If the 
>> policy is used via
>> CRTP (which is what I have in mind but admittedly didn't make clear) 
>> then this info
>> can be retrived by the policy through devector's public interface. 
>> Other designs
>> would require that the info be passed as additional arguments to the 
>> member
>> functions.
>
> Regardless,
>
> We also need to see what to test. I have tried to improve the test 
> measurements,
> see attached code. It tests insertion without buffer expansion. 

May I suggest we use something like the following framework:

 Â Â Â  template<typename T>
 Â Â Â  struct default_factory
 Â Â Â  {
 Â Â Â Â Â  using value_type=T;

 Â Â Â Â Â  static value_type get(){return T{};}
 Â Â Â  };

 Â Â Â  template<typename Factory>
 Â Â Â  struct random_process
 Â Â Â  {
 Â Â Â Â Â  using factory_type=Factory;

 Â Â Â Â Â  random_process(
 Â Â Â Â Â Â Â  double wib,double wif,double wim,
 Â Â Â Â Â Â Â  double web,double wef,double wem,
 Â Â Â Â Â Â Â  const Factory& f=Factory{}):
 Â Â Â Â Â Â Â  rnd{{wib,wif,wim,web,wef,wem}},f{f}{}

 Â Â Â Â Â  template<typename Devector>
 Â Â Â Â Â  void operator()(Devector& d){
 Â Â Â Â Â Â Â  using uniform=std::uniform_int_distribution<typename 
Devector::size_type>;
 Â Â Â Â Â Â Â  switch(rnd(gen)){
 Â Â Â Â Â Â Â Â Â  case 0: d.push_back(f.get());break;
 Â Â Â Â Â Â Â Â Â  case 1: d.push_front(f.get());break;
 Â Â Â Â Â Â Â Â Â  case 2: 
d.insert(d.begin()+uniform{0,d.size()}(gen),f.get());break;
 Â Â Â Â Â Â Â Â Â  case 3: if(d.size()>0)d.pop_back();break;
 Â Â Â Â Â Â Â Â Â  case 4: if(d.size()>0)d.pop_front();break;
 Â Â Â Â Â Â Â Â Â  case 5: 
if(d.size()>0)d.erase(d.begin()+uniform{0,d.size()-1}(gen));break;
 Â Â Â Â Â Â Â  }
 Â Â Â Â Â  }

 Â Â Â Â Â  std::mt19937Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  gen{92748}; // some arbitrary random 
seed
 Â Â Â Â Â  std::discrete_distribution<> rnd;
       Factory                      f;
 Â Â Â  };

 Â Â Â  template<typename RandomProcess>
 Â Â Â  void run(RandomProcess p,int n)
 Â Â Â  {
 Â Â Â Â Â  boost::double_ended::devector<
 Â Â Â Â Â Â Â  typename RandomProcess::factory_type::value_type> d;
 Â Â Â Â Â  for(int i=0;i<n;++i)p(d);
 Â Â Â  }

random_process models a, well, random process that, each time it is 
invoked, can
do the following:

 Â  1. push_back
 Â  2. push_front
 Â  3. insert at a random position within the devector
 Â  4. pop_back
 Â  5. pop_front
 Â  6. erase at a random position within the devector

where each action is chosen with probabilistic weights wib, wif, wim, 
web, wef
and wem, respectively. We can then easily model different usage patterns:

 Â  * (1,0,0,0,0,0) --> growing on back
 Â  * (1,1,0,0,0,0) --> growing both ends
 Â  * (1,0,0,0,1,0) --> FIFO (average size = 0)
 Â  * (2,0,0,0,1,0) --> growing FIFO
 Â  * (0,0,1,0,0,0) --> growing, no end bias
 Â  * (0,0,2,0,0,1) --> growing with some deletions, no end bias

Etc.

Joaquín M López Muñoz