Discussion :

[poukill]

Bonjour à tous,

Je dois construire une appli de traitement de données multimodales (images et signaux) temps-réel avec une période de traitement fixe de 20ms.
- Pour information, je dispose d'une accélération matérielle à base de FPGA -

Le post ici ne concerne nullement les algorithmes, déjà choisis et peu gourmands, mais le stockage et le post traitement de ces données sur les 15 ms restantes dans la RAM.
Comme le programme global d'analyse de données doit être au maximum modulaire, et avoir quand même de super performances, j'avoue être un peu tremblant dans mes choix de structure pour mes données.

Comme j'ai beaucoup de données de types différents, ma première idée était de partir sur une std::map<std::string, Data*> avec Data une interface abstraite... On s'en sort avec un bête cast à faire (comme le tuto de Laurent )

Code :

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

1
2
3
4
5
6
7
8
9
10
struct Data
{
    double      m_time;
    std::string m_name;
};
 
struct ImageD : public Data
{
    std::vector<double> m_data;
};

Je me demande si pour plus d'évolutivité (arrivée de nouveaux signaux), je ne devrais pas partir sur quelquechose de plus "sioux" genre un boost::multi_index, avec une possibilité de tri suivant plusieurs critères : temps, noms des signaux...
Ce serait vraiment une structure idéale pour moi, mais j'ai vraiment peur que l'insertion systématique de nouveaux éléments (environ 1Go au bout d'une minute et fin d'expérience ) plombe mes performances.

Ma question est donc : dans mon cas (contraintes assez fortes), est-ce qu'il faut oublier ce genre d'approche trop "haut-niveau" et faire plus simple (mon premier exemple en haut).

J'attends vos remarques / suggestions, et je pense me lancer dans des benchmarks derrière.

[loufoque]

Bah déjà le problème de std::map<std::string, Data*>, c'est que ça ne suit pas le RAII et que ce n'est pas exception-safe.

Sinon, boost::multi_index n'est pas plus lent que de faire des indexes à la main. Si t'as besoin de trier/indexer les éléments selon plusieurs critères, c'est la solution.
Après niveau utilisation mémoire je sais pas trop, mais je suppose que chaque index nécessite quelque chose comme n*8 octets en plus des données elles-mêmes.

[3DArchi]

Salut,
Quels seront les traitements dimensionnant sur tes structures (tri ? mise à jour ? lecture ? Accès par clé, linéaire ?). Sur le stockage, le plus simple est le vecteur... mais tu n'as aucune information 'structurante' à côté. Cela dépend donc de ce que tu vas faire avec?

[koala01]

Salut,

Je vais, une fois n'est pas coutume, présenter mon raisonnement sur le sujet, histoire de permettre à d'autres de le rectifier

Selon moi, une implémentation générique est toujours préférable à une implémentation polymorphe, car qui dit polymorphisme dit, malgré tout, indirection supplémentaire (passage par la vtable), et donc "délais" supplémentaire.

De plus, l'index unique de boost::multi_index est sans doute (je n'ai pas vérifié le code source) géré sous la forme d'un arbre binaire, qui reste, malgré tout, la structure la plus efficiente dans une optique de gestion d'une collection triée et de maintient de ce tri après insertion.

Je ne serais pas étonné outre mesure (je le répète, je n'ai pas vérifié le code source) que les indexes non uniques de boost::multi_index soient gérés sous la forme d'une table de hachage ou d'un multi_set (et donc un d'arbre binaire), qui représentent à mon sens encore une fois le meilleur compromis d'efficacité.

Tu l'auras compris, j'aurais naturellement tendance à envisager boost::multi_index

Maintenant, je n'attends que la preuve que mon raisonnement est erroné, incomplet, histoire de me coucher moins bête ce soir que ce que je ne l'étais ce matin en me levant

[poukill]

Bah déjà le problème de std::map<std::string, Data*>, c'est que ça ne suit pas le RAII et que ce n'est pas exception-safe.

En effet. Mon post était à but "informatif". Évidemment, un boost::ptr_map résoudrait le problème.

Si t'as besoin de trier/indexer les éléments selon plusieurs critères, c'est la solution.

C'est là que le bât blesse. Je peux ne pas avoir besoin de tri, étant donné que je stocke des données temporelles au fur et à mesure qu'elle arrive, il n'y a qu'à faire des push_back() dans mes conteneurs.
Une structure basique pourrait convenir:

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
 
struct dummy{};
 
struct IData
{
	typedef dummy data_type;
 
	std::string name;
	int position;
	double time;
};
 
struct CImage : public IData
{
	typedef std::vector<double> data_type;
 
	data_type data;
};
 
struct CSignal : public IData
{
	typedef double data_type;
 
	data_type data;
};

Ainsi, cette structure serait mise à jour régulièrement au fur et à mesure que des données arrivent.

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
#include <boost/circular_buffer.hpp>
typedef boost::shared_ptr<IData> data_ptr;
 
int main()
{
	std::map<std::string, boost::circular_buffer<data_ptr> > my_map;
	boost::circular_buffer<data_ptr> buffer(10);
	my_map["Cupper"]= buffer;
	boost::circular_buffer<data_ptr> buffer2(5);
	my_map["IR"] = buffer2;
 
	boost::shared_ptr<CImage> image (new CImage);
	image->data = std::vector<double>(25,5);
	boost::shared_ptr<CSignal> signal (new CSignal);
	signal->data = 2.65;
 
	my_map["IR"].push_back(image);
	my_map["Cupper"].push_back(signal);
 
	return 0;
}

Je pense que ce genre de structure pourrait bien me convenir, étant donné que je n'ai que des push_back à effectuer, sur un buffer circulaire car je dois effacer mes données au fur et à mesure de leur arrivée.

[poukill]

Je pense m'orienter vers un conteneur de type

Code :

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

std::map<std::string, boost::circular_buffer<IData*> >

Après, j'ai besoin de votre avis. Ce conteneur n'est pas exception safe, et ne suit pas le RAII. Mais si je le remplace par :

Code :

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

std::map<std::string, boost::circular_buffer<boost::shared_ptr<IData> > >

afin d'utiliser des pointeurs intelligents. Est-ce que quelqu'un a une idée du coût en performance (la perte de mémoire n'est pas importante dans mon cas) ? Est-ce viable dans une appli temps-réel?
J'aurais tendance à dire oui, mais je préfère vérifier !

[Alp]

Le circular buffer semble être un bon choix.

It supports random access iterators, constant time insert and erase operations at the beginning or the end of the buffer and interoperability with std algorithms. The circular_buffer is especially designed to provide fixed capacity storage. When its capacity is exhausted, newly inserted elements will cause elements either at the beginning or end of the buffer (depending on what insert operation is used) to be overwritten.

The circular_buffer only allocates memory when created, when the capacity is adjusted explicitly, or as necessary to accommodate resizing or assign operations. On the other hand, there is also a circular_buffer_space_optimized available. It is an adaptor of the circular_buffer which does not allocate memory at once when created, rather it allocates memory as needed.

L'indirection introduite par shared_ptr ne coûtera pas grand chose, ne t'inquièts pas.

Quand à std::map :
C++ STL Hash Containers

[poukill]

Le circular buffer semble être un bon choix.

Oui, les benchs que j'ai réalisé ce matin sont vraiment très bons.

L'indirection introduite par shared_ptr ne coûtera pas grand chose, ne t'inquiètes pas.

Oui, et puis dans mon cas le shared_ptr va bien m'arranger pour la gestion des ressources.

Quand à std::map :
C++ STL Hash Containers

Merci Alp pour ces infos !
Vu que je n'ai pas besoin de tri, je pense utilise boost::unordered_map en fait.
De toute façon, j'aurai au maximum une dizaine d'élements dans ma map, c'est pas énorme !

[NiamorH]

A la lecture de l'article Dr Dobb's, il me semble qu'une question importante reste en suspend :

Next, the bucket number is computed by taking the hash value modulo the number of buckets.
(...)
Thankfully, as the number of items in your hash set grows, the number of buckets automatically increases.

Les items sont-ils alors déplacés ? J'imagine le temps nécessaire pour cela (recalcul de tous les codes de hash).

[loufoque]

Ben oui, c'est un peu le principe d'une table de hachage...
Pas besoin de lire un article de Dr Dobb pour savoir ça;

[NiamorH]

Je suis juste étonné que cet article n'en parle même pas, ça me paraît important.

[loufoque]

Suis un cours de base sur les structures de données, c'est dedans.
Et c'est pas particulièrement important non. La complexité d'ajout est linéaire amortie.