Discussion :

[Seabirds]

Bonjour à toutes et à tous !

Je cherche à mémoizer une fonction F. J'ai piqué des bouts de code ici : http://cpptruths.blogspot.com/2012/0...moization.html
Toutefois, la différence est que dans mon cas, la fonction F renvoie un foncteur D très lourd (c'est une distribution avec un gros support, qui est longue à construire, et coûteuse à copier). Mon but est donc à la fois de construire D une seule fois, mais aussi d'éviter toutes les opérations de copies pour amener D là où on en a besoin.
J'ai donc modifié le code initial pour aboutir à la version suivante. Comme c'est un bout de code critique, j'aimerais m'assurer que je ne fais pas d'opérations inutiles. Sauf que je suis sûr que j'en ai fait tout plein ! Qu'en pensez-vous ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template<typename Ret, typename... Args>
auto memoize( Ret(*func)(Args...) ) {
  auto cache = std::make_shared<std::map<std::tuple<Args...>, Ret>>();
  return ([=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache->find(t) == cache->end())
            (*cache)[t] = std::move(func(args...));
        return std::cref((*cache)[t]);
        });
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
template <typename Sig, Sig funcptr>
struct static_memoizer;
 
template <typename F_ret, typename... F_args, F_ret (*func)(F_args...)>
struct static_memoizer<F_ret (*)(F_args...), func> {
  static auto get() {
    static auto mfunc (memoize(func));
    return mfunc;
  }
};

Et du coup je l'utilise comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template<typename BigInt, typename BigFloat>
struct in_memoized_distribution{
  template<typename Generator>
  static std::vector<unsigned int> const& build(unsigned int k, unsigned int N, Generator& g){
    return utils::static_memoizer<
        decltype(&coalescence::make_occupancy_spectrum_distribution<BigInt, BigFloat>),
        &coalescence::make_occupancy_spectrum_distribution<BigInt, BigFloat>
      >::get()(k,N)(g);
  }
};

Merci d'avance

[Pyramidev]

Salut,

Pour mémoïser ta fonction :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

D f(unsigned int k, unsigned int N)

de manière optimisée, je propose :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <functional>
#include <unordered_map>
#include <utility>
 
struct MyHash
{
	std::size_t operator()(const std::pair<unsigned int, unsigned int>& param) const 
	{
		static const auto hacher = std::hash<unsigned int>();
		const std::size_t h1 = hacher(param.first);
		const std::size_t h2 = hacher(param.second);
		return h1 ^ (h2 << 1);
	}
};
 
const D& f_memoise(unsigned int k, unsigned int N)
{
	static std::unordered_map<std::pair<unsigned int, unsigned int>, D, MyHash> cache;
	const auto params = std::make_pair(k, N);
	const auto it = cache.find(params);
	if(it != cache.end())
		return it->second;
	auto newResult = f(k, N);
	const auto pair_itNewResult_true = cache.insert(std::make_pair(
		params,
		std::move(newResult)
	));
	return pair_itNewResult_true.first->second;
}

Remarques :

• Le code if (cache->find(t) == cache->end()) [...] std::cref((*cache)[t]) que tu as copié peut faire deux recherches successives dans l'arbre alors qu'une seule suffit.
• Le code que tu utilises appelle std::map::operator[], donc impose que D ait un constructeur par défaut. Cette contrainte peut être évitée avec std::map::find et std::map::insert.
• Ma solution ne s'encombre pas d'un std::shared_ptr qui nécessite une allocation dynamique en plus et du comptage de références.
• Je ne sais pas si l'utilisation de std::unordered_map à la place de std::map augmentera ou baissera tes performances. Il faudra tester les deux.
• Le code que je viens d'écrire n'est pas générique, mais il est plus simple si tu as besoin de ne mémoïser qu'une ou deux fonction(s).

[jo_link_noir]

@Pyramidev: pour l'insertion dans la map/unordered_map, on peut remplacer insert par emplace avec std::piecewise_construct (voir l'exemple de la doc). Cela évite de faire un déplacement qui peut lui même être coûteux.

Le shared_ptr dans la solution de l'article vient à mon avis d'une limitation de c++11 de l'époque: on ne peut pas construire la map dans la clause de capture de la lambda. Je ferrais return ([cache = std::map<...>](Args... args) mutable { ... }.

Par contre, la référence sur le retour de get à sautée, ce qui est une très mauvaise idée: auto & get() ou auto get(unsigned k, unsigned N) (par besoin de référence pour ce dernier puisque le retour de mFunc(k,N) est un reference_wrapper.

[Seabirds]

Ah ouais c'est plus une review, c'est une ré-écriture Merci beaucoup
Vivement que je code comme vous ... dans dix ans ?