Saturday, December 28, 2013

Objects, slots, functors, duality

C++ smart pointers rely on the ability to overload operator-> (and, less importantly, operator->*), whose invocation precedes any access to the pointee. Unfortunately, there is no such thing as overloading operator. (even though the possibility to do so has been considered by Bjarne Stroustrup and others), which would allow for the creation of "smart reference" classes. Lacking this ability, a wrapper class has to go through the painful and non-generic process of replicating the interface of the wrapped object. We present here an approach to class interface design, let's call it slot-based interfaces, that allows for easy wrapping without losing much expressivity with respect to traditional C++ interfaces. The techniques described are exercised by a program available for download (a fairly C++11-compliant compiler such as GCC 4.8 is needed).
Say we have a container class like the following:
template <class T, class Allocator = std::allocator<T>>
class vector {
  ...
  iterator       begin();
  const_iterator begin()const;
  iterator       end();
  const_iterator end()const;
  ...
  template <class... Args>
  void emplace_back(Args&&... args);
  void push_back(const T& x);
  ...
};
The interface of this vector can be changed to one based in slots by replacing each member function with an equivalent overload of operator():
template <class T, class Allocator = std::allocator<T>>
class vector {
  ...
  iterator       operator()(begin_s);
  const_iterator operator()(begin_s)const;
  iterator       operator()(end_s);
  const_iterator operator()(end_s)const;
  ...
  template <class... Args>
  void operator()(emplace_back_s,Args&&... args);
  void operator()(push_back_s,const T& x);
  ...
};
where begin_s, end_s, emplace_back_s, etc. are arbitrary, different types called slots, of each of which there is a corresponding global instance with name begin, end, emplace_back, etc. Traditional code such as
vector<int> c;
for(int i=0;i<10;++i){
  c.push_back(2*i);
  c.emplace_back(3*i);
}
for(auto it=c.begin(),it_end=c.end();it!=it_end;++it){
  std::cout<<*it<<" ";
}
looks like the following when using a slot-based interface:
vector<int> c;
for(int i=0;i<10;++i){
  c(push_back,2*i);
  c(emplace_back,3*i);
}
for(auto it=c(begin),it_end=c(end);it!=it_end;++it){
  std::cout<<*it<<" ";
}
Legibility is still excelent, if a little odd at the beginning. The big advantage of a slot-based interface is that all of it is mediated through invocations of (overloads of) operator(), so wrapping, with the aid of C++11 perfect forwarding, is an extremely simple business:
template <typename T>
class logger
{
  T t;
public:
  template<typename ...Args>
  logger(Args&&... args):t(std::forward<Args>(args)...){}

  template<typename Q,typename ...Args>
  auto operator()(Q&& q,Args&&... args)
    ->decltype(t(std::forward<Q>(q),std::forward<Args>(args)...))
  {
     std::cout<<typeid(q).name()<<std::endl;
     return t(std::forward<Q>(q),std::forward<Args>(args)...);
  }

  template<typename Q,typename ...Args>
  auto operator()(Q&& q,Args&&... args)const
    ->decltype(t(std::forward<Q>(q),std::forward<Args>(args)...))
  {
     std::cout<<typeid(q).name()<<std::endl;
     return t(std::forward<Q>(q),std::forward<Args>(args)...);
  }
};
logger<T> merely adorns the interface of T (which is, remember, entirely comprised of overloads of operator()) by registering the name of the first argument type, i.e. the slot used. Substituting logger<T> by T in any piece of code works immediately without further modifications, regardless of the interface of T (provided, of course, it is slot-based). The following is probably more interesting:
template <typename T>
class shared_ref
{
  std::shared_ptr<T> p;
public:
  template<typename ...Args>
  shared_ref(Args&&... args):p(std::forward<Args>(args)...){}

  template<typename ...Args>
  auto operator()(Args&&... args)
    ->decltype((*p)(std::forward<Args>(args)...))
  {
     return (*p)(std::forward<Args>(args)...);
  }
};
Much as shared_ptr<T> acts as regular T*, shared_ref<T> acts as a regular T& whose (slot-based) interface can be unencumberedly used. This even works with run-time polymorphism based on virtual overloads of operator().
We can continue expanding on this new interface paradigm. So far slots have been regarded as passive types whose only mission is to adorn interfaces with convenient names, but nothing stops us from making these slots active classes in a curiously useful way:
struct begin_s
{
  template<typename T,typename ...Args>
  auto operator()(T&& t,Args&&... args)const
    ->decltype(t(*this,std::forward<Args>(args)...))
  {
    return t(*this,std::forward<Args>(args)...);
  }
};
extern begin_s begin;
We have defined begin_s as a functor performing the following transformation:
begin(t,...) t(begin,...),
which allows us to write (assuming all the slots are defined in an equivalent way) code like this:
vector<int> c;
for(int i=0;i<10;++i){
  push_back(c,2*i);
  emplace_back(c,3*i);
}
for(auto it=begin(c),it_end=end(c);it!=it_end;++it){
  std::cout<<*it<<" ";
}
So, slots give us for free the additional possibility to use them with global function syntax. In fact, we can take this behavior as the very definition of a slot.
Definition. A basic slot is a functor S resolving each invocation of s(t,...) to an invocation of t(s,...), for any s of type S.
Those readers with a mathematical inclination will have detected a nice duality pattern going on here. On one hand, slot-based classes are functors whose overloads of operator() take slots as their first parameter, and on the other hand slots are functors whose first parameter is assumed to be a slot-based class type.
The diagram shows a number of different classes against several slot names, where succesful combinations are marked by a dot: in a sense it is immaterial which axis is considered to hold classes and which holds slots, as their roles can be reversed from a syntactical point of view. One unexpected implication of this duality is that slot-based class wrappers will also work as slot wrappers. For instance, much as we can write
// register access to the interface of c
logger<vector<int>> c;
...
we can also write
// register invocations to emplace_back
logger<emplace_back_s> logged_emplace_back;
logged_emplace_back(c,100);
...
Or, if we make vector open-ended by accepting any slot, we can use logged_emplace_back with member function syntax:
template <typename T>
class open_ended
{
  T t;
public:
  template<typename ...Args>
  open_ended(Args&&... args):t(std::forward<Args>(args)...){}
      
  template<typename Slot,typename ...Args>
  auto operator()(Slot&& s,Args&&... args)
    ->decltype(s(t,std::forward<Args>(args)...))
  {
     return s(t,std::forward<Args>(args)...);
  }

  template<typename Slot,typename ...Args>
  auto operator()(Slot&& s,Args&&... args)const
    ->decltype(s(t,std::forward<Args>(args)...))
  {
     return s(t,std::forward<Args>(args)...);
  }
};
...
logger<emplace_back_s> logged_emplace_back;
open_ended<vector<int>> c;
c(logged_emplace_back,100);
...
By identifying class access with class invocation and reifying member function names into first-class functors, slot-based interfaces allow for a great deal of static composability and provide unified concepts blurring the distinction between classes and functions in ways that are of practical utility. The approach is not perfect: a non-standard syntax has to be resorted to, public inheritance needs special provisions and operators (as opposed to regular member functions, i.e. functions like operator=, operator!, etc.) are not covered. With these limitations in mind, slot-based interfaces can come handy in specialized applications or frameworks requiring interface decoration, smart references or similar constructs.

Wednesday, December 4, 2013

Lookup cost in hash tables with duplicate elements

As a continuation of our previous entry on the statistical properties of hash tables with duplicate elements, let's now analyze how duplicates affect lookup times. Let N be the number of elements in the table, B the number of buckets and F = N/B the associated load factor. We have already learnt that the size S of a bucket follows (for large N) a Poisson distribution PF(n) with mean F. Beginning with the non-duplicate case, what is the average number of elements checked when searching for a given key k? In such general terms, the question is underspecified because lookup times differ depending on whether k is actually present in the table or not. The analysis can be done, though, considering each case in isolation.
Key is not present. This is easy to calculate: the number of elements checked is simply the average length of a bucket, which we know to be F.
Key is present. We assume that the value of k, regarded as a random variable, is evenly distributed among the values stored in the table, i.e. each element has the same probability of being chosen for lookup. Define
B(n) := Pr(k is in a bucket of size n).
It is easy to see that B(n) can be calculated as
B(n) = nPF(n)B/N = nPF(n)/F,
following from the simple fact that there are PF(n)B buckets of size n, each holding precisely n elements. In such a bucket, the number of elements checked when looking for k goes from 1 (k is the first element) to n (k is the last), and is thus in average (1 + ··· + n)/n = (n+1)/2. From this we can calculate in the general case the average number of elements checked as
Σn≥0 ((n+1)/2)B(n) =
= Σn≥0 ((n+1)/2)nPF(n)/F = (1/2F)Σn≥0 (n2+n)PF(n) =
= (1/2F)(E[S] + E[S2]) = (1/2F)(F + F2 + F) = 1+ F/2,
where we have used the fact that the second moment of a Poisson distribution with mean F is F2 + F.
We are now ready to study the case where the hash table holds M groups of duplicate elements, each group with average size G
Key is not present. There are no differences with respect to the non-duplicate case; an entire bucket, whose average size is again F, is traversed when looking up for the non-present key.
Key is present. In terms of distribution of elements, the table is equivalent to another one without duplicates where each group of equal elements is replaced by just one representative. This theoretical table has a load factor F' = F/G and an associated average lookup time 1 + F'/2. Now, searching in our original table incurs the same number of operations, except that all the individual checks before getting to k now turn into checks of an average of G equivalent elements. So, the total number of steps is
1 + GF'/2 = 1 + F/2,
exactly as in the non-duplicate case. How come we see no degradation despite elements being heavily concentrated in fewer buckets? The reason is that the distribution of groups in the table is governed by an equivalent load factor F' = F/G which is much (as much as G) less than F, and the probability that there are two of more groups of elements in the same bucket is in consequence greatly reduced.   
The hash table structures used by some implementations of C++ unordered associative containers such as Boost.Unordered allow for skipping of groups of equivalent elements. For these special hash tables, the average lookup steps are reduced to F/G, if the key is not present, and 1+F/2G, if it is.