Re: [boost] Any interest in a framework for memoization?

Subject: Re: [boost] Any interest in a framework for memoization?
From: Piotr Wygocki (vwygos_at_[hidden])
Date: 2013-11-23 05:25:16

On 22 November 2013 14:35, Giacomo Drago <giacomo_at_[hidden]> wrote:

> Hi Giacomo, thank you for your contribution.
>>
>> I'm interested in this kind of library, particularly I often implement
>> dynamic programs. I've got some remarks/questions.
>>
>> * In your implementation you use std::function adaptor. You can remove it
>> by making some of the member functions templates( e.g. getValue).
>>
>
> I see. Out of curiosity, what is the reason to do so (maybe performance)?
> I chose std::function over template parameters as I find it quite
> convenient, e.g. I can pass nullptr to the function and then check this
> condition inside the function body.
>

The std::function is not for free. You gain type erasure but you lose some
performance, you can read about it for example here:

http://stackoverflow
.com/questions/5057382/what-is-the-performance-overhead-of-stdfunction

> Turning getValue into a template function will imply major refactoring:
> Surely I will do it if it's required, and if you have some spare time, I'd
> appreciate insights based on the actual code.

I think in this case it doesn't need major refactoring: each time you use
the underlined type you add template parameter to the function. Maybe I
missed something.

>
>
>
>  * I'm interested in the case when Key type is integral. In this case one
>> can make the following optimization. Let density be the "the number of
>> elements in map" / "the largest element in map" ratio. If the density is
>> large, it is much better to use vector instead of hash map. The idea is to
>> measure the density and  when it exceeds certain threshold switch from
>> hashmap to vector. Did you consider this optimization? (I'm aware this is
>> not as easy as I described). This makes sense when you consider the
>> unbounded knapsack problem. In UKP it is not clear (you have to decide in
>> runtime) if you should use vector/ or hashmap strategy . IMO the "integral
>> Key" case covers many standard dynamic programs.
>>
>
> Interesting. How would you do it, with a template specialization for
> int/long/etc... and maybe std::pair<int, int> keys? This would be
> relatively easy, what I find tricky is to dynamically switch from the
> hashmap to the vector while preserving thread safety. Do you have any
> suggestions/examples?
>

My first thought was specialising the class for the case  when
std::is_integral<Key>::value is true.
Unfortunately, I do not have any smart thoughts concerning the thread
safety.

> I appreciate your feedback and I'll work on your suggestion, but do you
> think this library may eventually find its place into Boost?
>

I can only say that I'd like to see library like that in boost but I'm
afraid this is not my decision.

Regards,

Piotr

>
> Thank you for your time.
>
> Giacomo
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/
> mailman/listinfo.cgi/boost
>