Re: [boost] Abstract STL Container Adaptors

Subject: Re: [boost] Abstract STL Container Adaptors
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2013-03-19 03:17:30

Jeffrey Lee Hellrung, Jr. wrote:
> On Thu, Mar 14, 2013 at 10:20 AM, Andy Jost <Andrew.Jost_at_[hidden]>wrote:
>
>> Hi Boosters,
>>
>> Is there any interest in an abstract container adaptor library (I'll
>> describe what I mean below)?  I'm a little surprised if this has never come
>> up in the context of Boost, but I couldn't find anything on the archives.
>>   I did find something on stack overflow (
>> http://stackoverflow.com/questions/5329555/abstract-wrapper-for-stl-containers),
>> but it did not uncover an existing solution.
>>
>>
>> Motivation:
>>
>> Sometimes we want to write functions that take a container as an argument.
>>   For instance, say I have a graph object implemented in terms of ``class
>> Node``.  I may expose an algorithm like this:
>>
>> void my_algorithm(Node & root, std::set<Node const *> const & marked);
>>
>> In this case, ``root`` is the root of a graph, and ``marked`` is a set of
>> marked nodes.  The problem with this approach is that it forces a
>> particular choice of the set implementation onto the caller.  He may, for
>> example, prefer to use ``tr1::unordered_set``.  We could get around that
>> limitation by using a template parameter, like this:
>>
>>                  template<typename Set> void my_algorithm(Node & root, Set
>> const & marked);
>>
>> The problem here is that it forces the implementer of ``my_algorithm`` to
>> expose that code and, potentially, recompile it many times (for different
>> Set types).
>>
>> In some cases, particularly when compile times are more critical than
>> execution times, it would be preferable to let the caller choose the set
>> implementation without losing the advantages of separate compilation.  A
>> simple solution is to write an adaptor that mimics the interface of
>> ``set``.  With that, the function call would appear as shown here:
>>
>>                  void my_algorithm(Node & root, abstract_set<Node const *>
>> const & marked);
>>
>> Here, abstract_set<Node const *> is implicitly convertible from any type
>> having the interface of std::set<Node const *>.  It internally holds a
>> reference to some implementation of a suitable set-like object and mediates
>> interactions with the outside world through virtual methods.
>>
>>
>> It seems the implementation of this would be a straightforward application
>> of type erasure.  It seems too easy, in fact, which makes me wonder whether
>> I'm missing something.
>>
>> In any case, is this a good idea?
>>
>
> Despite the other comments, this has a legitimate use case:
> - The algorithm is code-wise large and called many times on different
> containers, or, say, embedded within compiled library, so either it isn't
> practical or isn't possible to inline it.
> - The dispatch overhead from the type erasure is negligible compared with
> other operations in the algorithm.
> - You want to avoid imposing unnecessary memory requirements on the caller,
> such as forcing them to copy their data into a specific data structure.
>
> Off the top of my head, computational geometry algorithms are sometimes of
> this nature.
>
> Additionally, I think this functionality is basically or entirely present
> in Steven Watanabe's Boost.TypeErasure library [1; warning: docs may be
> outdate, I just did a Google search].
>

There are also some algorithms of a nature that are large with many 
variations and performance critical enough that you can't really afford 
to instantiate all variations in code with templates and you can't 
afford the overhead of internal runtime dispatch.

A good example of this would be a complex software renderer. There are 
configurable paths but the path is known at the start of the algorithm 
and will not change for a given set of data. For example the properties 
of a vertex that must be interpolated over the face of a triangle in 
addition to position there may be any/all/none of texture coordinates, 
normals, colors, etc.

You can't really afford any dispatch in code that is in such an inner 
loop but instantiating all possible options and compile time would lead 
to a huge code bloat, especially when most of the configurations would 
never be used in practice.

A solution to these types of problems is essentially jit compiling the 
algorithm to run by fitting together prefabricated blocks depending on 
all the configuration as if you were doing template instantiation at 
runtime.

I think it would be an interesting area of exploration.

http://tinyurl.com/optimizing-pixomatic1
http://tinyurl.com/optimizing-pixomatic2
http://tinyurl.com/optimizing-pixomatic3