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 16:57:10

On 08/02/2012 8:23 AM, Steven Watanabe wrote:
> 
> AMDG
> 
> On 08/01/2012 10:09 PM, Chapman, Alec wrote:
> > 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.
> >
> 
> I don't think this is a good idea, as it would require an extra flag whether
> it's needed or not.
> 

The way I implement it is with a separate vtable for references that is mostly the same as the vtable for values.  The difference is that the reference vtable specifies that when the object is copied the value vtable should be used.  This also works naturally for proxy references (like std::vector<bool>::reference) where the vtables really need to be completely different.  This requires no increase in the object size and only generates the additional vtable if it is actually used.

It looks like you have put a lot of thought into how to apply type erasure to generic algorithms, which was my motivation as well.  Is what I am trying to do already possible with your library, or do you think that generic algorithms that take their arguments by reference aren't a common enough case?

> >> 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'm not sure how you can make this work in all possible cases.  I know that
> there are cases where I can avoid creating a new vtable, but what about
> 

typedef any<mpl::vector<incrementable<>, addable<>>> any1;
typedef any<mpl::vector<addable<>, incrementable<>>> any2;
any1 x(...);
any2 y(x);
++y;

I allow an any to contain another any (if the concepts are different) and treat it the same as other types.  For example, in the code above ++y would go through two virtual functions calls (the first calls increment of any1, which then calls a virtual function that actually does the increment).

> mpl::vector<incrementable<>, addable<> > ->
>   mpl::vector<addable<>, incrementable<> >
> 
> This should be legal, but I can't just take a pointer into the existing vtable.
> 
> > 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.
> >
> 
> Use the any(any<Concept2, T2>, binding<Concept>) constructor.
> It allows you to convert the vtable once, and re-use it for all the anys.
> 

That's good to know; I'll give it a try later.  But wouldn't this only work if I know all the anys in the vector have the same underlying type (in my application they wouldn't)?  I suppose I would have to build a map from type_info to binding and look up the binding for each element.

> > 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.
> >
> 
> That would be a problem.  I'll try to change the implementation so that
> incomplete types are considered to be non-placeholders.
> 
> >> 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.
> >
> 
> In Christ,
> Steven Watanabe
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost