Re: [boost] [type_erasure] Review started (July 18-27, 2012)

Subject: Re: [boost] [type_erasure] Review started (July 18-27, 2012)
From: Chapman, Alec (archapm_at_[hidden])
Date: 2012-08-02 01:09:22

First I want to thank Steven for all the work he has put into this library.  I have a number of cases where this library will be very useful as is.

> Please state clearly whether you think this library should be accepted as a
> Boost library.

Yes, with the conditions below about how references and conversions are handled.  The basic features are very useful by themselves and are suitable for the majority of uses.  If possible, these could be accepted and added to Boost immediately, with a mini-review of the other components when ready.

> 1. What is your evaluation of the design?

For the basic use cases I think this is absolutely the right design.  I like the decision to use an MPL sequence of concepts, and that concepts can be composed this way as well.  This alone meets the needs of the majority of use cases, including the various uses of type erasure already in Boost.  I haven't had a need for something like multiple placeholders, but the design looks reasonable as well.

As far as I can tell, the current design for references would prevent me from being able to use this library in a major portion of my code.  I haven't received Steven's reply to my other email, so I'll just summarize the issue here.

I have some generic function that takes its argument by reference and might modify it or make a copy of it.  I want to provide a version that can be compiled separately.  Something like:

template<class T>
void f_impl(T& t)
{
    ++t;
    T t2(t);
    ++t2;
}

void f(any<...>& i)
{
    f_impl(i);
}

The function won't behave properly if it is instantiated with T = any<..., _self&> (++t2 would increment t), so it has to be instantiated with T = any<..., _self>.  But now calling the function is problematic:

void g(int& i)
{
    ... // do something with i
    f(???);
}

There is no way I can see to have f modify the original variable i.  This is similar to the sort example Steven gave in a previous email [1], but with arguments passed by reference.

I propose an overloaded constructor that signals that the underlying object should be held by reference but copied when the any object is copied:

int i = 0;
any<requirements> a(i, capture_reference);
any<requirements> b(a);
++a;                      // i == 1
++b;                      // i == 1 still, any_cast<int>(b) == 2

This has worked well in my own code and should be easy to implement.  I think this would also avoid the bug mentioned at the bottom of the references page of the documentation.

> 2. What is your evaluation of the implementation?

Unfortunately I have only had time for a brief look at the code, so most of my understanding comes from reading the design notes section of the documentation.  The main point I'm unsure of is the decision to dynamically generate vtables upon conversion.

I have my own class for applying type erasure to any type that models a Fusion associative sequence (templated by an MPL sequence of key/value pairs) that I use pretty heavily.  It uses a custom vtable similar to Steven's library, except that the vtables are always statically generated even for upward and downward conversions.  I was interested to compare the two approaches since I had considered dynamic vtables but never tried to implement them.  I was pleased to find that only a few lines of code were required to make a similar class with Steven's library (although a bunch of boilerplate would still be needed to have the type-erased class itself be a Fusion sequence).

I made a vector of objects of type fusion::map<fusion::pair<key1, int>, fusion::pair<key2, double>>, as well as a vector of type-erased maps (any_map<mpl::vector<mpl::pair<key1, int&>, mpl::pair<key2, double&>>>).  I ran four benchmarks in which I summed key1 of:
1) the Fusion map directly
2) any_map
3) a temporary up-conversion to an any_map with only key1
4) a temporary up-conversion to an any_map with only key1, with the original held by reference

The case I had in mind with tests 3 & 4 was looping through a vector of any_maps and calling some function with a parameter type that requires an up cast.

The results were:
       Boost.TypeErasure          My any_map 
1      0.38 s                     0.37 s
2      5.45 s                     4.08 s
3      105.30 s                   66.69 s
4      72.64 s                    5.28 s

The difference in test 2 is due to my class being smaller (2 pointers/16 bytes for mine vs 32 bytes).  If I increase the size of my class the difference disappears.

The large increase from test 2 to test 3 is expected since it requires memory allocation inside a tight loop, however test 4 shows this can be avoided by using static vtables and capturing references (at the cost of each cast adding an extra layer of virtual function calls).

I was also concerned about the memory cost of storing a large number of casted objects if they each have their own vtable, but haven't tested this.  Presumably a mechanism could be implemented to share dynamically generated vtables that would also improve the tests above.

Steven, do you have cases in mind where dynamic vtables might be more appropriate?

> 3. What is your evaluation of the documentation?

There has already been a lot of discussion about the documentation, so I'll just add a couple thoughts:
I think relaxed_match should be prominently documented, as I found it unexpected that any cannot be default constructed otherwise.
I would like see some examples that demonstrate how the more advanced features would be used in real code.  The example Steven gave by email [1] for a sort function is a good candidate to be flushed out and included.

> 4. What is your evaluation of the potential usefulness of the library?

Very useful.

> 5. Did you try to use the library?  With what compiler?  Did you have any
> problems?

Yes, with VS10 and gcc 4.7.0.  I only have a couple minor points:

I think default construction without relaxed_match could be a very common error, and special care should be taken to provide a clear error message.

In the attached benchmark code, key1 and key2 need to be defined rather than just declared so that the library can determine whether they are placeholder types.  If this cannot be avoided, a note in the documents might be nice, along with whether it is acceptable to specialize is_placeholder.

> 6. How much effort did you put into your evaluation?  A glance?  A quick
> reading?  In-depth study?

At least a full day in total.

> 7. Are you knowledgeable about the problem domain?

Reasonably.  The class I described above for type erasure of Fusion associative sequences is fairly similar in implementation to Steven's.  I have also written type erasure classes to provide Python bindings for something like a Proto-ized version of Boost.Range.

Thanks again for this library,
Alec

[1] http://article.gmane.org/gmane.comp.lib.boost.devel/233069