RE : [Tsp-devel] Problème de sampling.

[PAGNOT, Robert]

Je me réveille un peu tard (enfin, je suis au boulot !).

Avant de se lancer dans des R&D infernales sur le problème de hashing,
sachez que j'ai une solution au problème qui peut vous convenir : la table
de HASH à temps de recherche linéaire en fonction de la longueur (ASCii) de
la clé de recherche. J'ai déjà passé le code à Erk, et il est dispo sous
TnT.

Admettons donc une table de clés dont le domaine ASCii est RE:[0-9], la
Bob's Hash Table construit un arbre de chemins possibles à travers les CLEs
(sequences de [0-9]) qui prends 1x32bits (ID) + 10x32bits ([0-9]), soit 44
bytes par table.

Si l'ID est l'index local du consumer et que la séquence [0-9] est un
printf(%d) de l'index local du provider, l'algo de recherche va déchirer sa
mère en termes de vitesse, mais va prendre de la mémoire quoi qu'il
arrive
!!!

Par exemple, pour "1" à "9", on a une table au premier niveau, et 9 tables
au deuxième niveau (chacune codant l'ID-provider correspondant au chemin).
Si l'on rajoute "10" à "19", on aura encore 10 tables au 3ème niveau, sous
la table "1", et ainsi de suite.

La recherche consiste donc à parcourir l'arbre, et le temps nécessaire est
directement lié à la longueur de la clé, et non pas au nombre de chemins !

L'overhead mémoire par rapport à une table d'indirection fixe (dimemsion des
IDs provider) est de 40 octets, mais l'optimisation mémoire est dans le fait
que les tables des chemins existants sont allouées au fur et à mesure que
l'on "pushe" des couples ID-consumer / printf(%d, ID-provider).

Cela vaut peut-être la peine d'essayer pour un consumer qui veut éviter
d'avoir à dimensionner un tableau d'indirections ulong[1.000.000], soit 4Mb.

Petit calcul rapide : soit 1.000.000 de clés (longueur max de chaîne = 6) et
un consumer qui en prend 100. Il utilisera, pire cas (tous chemins
différents - ce qui n'est pas possible du fait [0-9] !) : 6 x 100 x 44 bytes
de mémoire = 26 koctets.

A+


-----Original Message-----
From: STEF [mailto:address@hidden
Sent: Saturday, November 26, 2005 9:23 PM
To: Erk; TSP Devel ML
Subject: [Tsp-devel] Problème de sampling.



Salut à tous,

Bon, je n'ai pas encore commité la gestion des sessions sous GDisp+
car suite aux dernières recommandations de Erk, j'ai remodelé ma gestion
du sampling et je tombe maintenant sur un problème que je vous expose
ci-dessous.

Jusqu'à présent, GDisp+ demandait aux divers providers disponibles la
TOTALITE des symboles mis à disposition.

ETAPE 1 :
   ...
   provider = TSP_consumer_connect_url(url);
   ...
   TSP_consumer_request_open(provider,(gint)NULL,(gchar**)NULL);
   ...
   TSP_consumer_request_information(provider);
   ...
   providerInfo = TSP_consumer_get_information(provider);
   ...

Puis j'obtenais les symboles via :

   providerInfo.val et providerInfo.len

La mise en sampling se faisait de la façon suivante :

ETAPE 2 :
   ...
   TSP_consumer_request_sample(provider,&sampleList);
   ...
   /* pour avoir les bons index */
   realList = TSP_consumer_get_requested_sample(provider);
   ...
   TSP_consumer_request_sample_init(provider,

(TSP_sample_callback_t)NULL,(void*)NULL);
   ...
   while (keepOn == TRUE) {
     ...
     TSP_consumer_read_sample(provider,&sampleValue,&sampleHasArrived);
     ...
   }
   ...
   TSP_consumer_request_sample_destroy(provider);
   ...

La variable sampleValue.provider_global_index permettait de retrouver
facilement le symbol concerné dans la table globale issue de l'étape 1.

Aujourd'hui, GDisp+ offre la possibilité de charger une session composée
d'un sous-ensemble des symboles existants, et ce SANS DEMANDER L'ENSEMBLE
DES SYMBOLES AU PREALABLE.

Par exemple avec un tsp_stub_server qui offre 1000 symboles, la session
peut n'en contenir que 10 répartis dans plusieurs plots graphiques.

!!! >> Donc en mémoire, GDisp+ a bâti une table de 10 symboles.

Or les index obtenus soit par TSP_consumer_get_requeted_sample, soit par
sampleValue.provider_global_index continuent à arriver avec des valeurs
comprise entre 0 et 999.

J'ai peur des perfos car je dois faire une RECHERCHE MANUELLE des symboles
chaque fois qu'une sampleValue arrive, cad autant de fois qu'il y a de
symboles en sampling toutes les 10 ms.

Que feriez-vous ? Continuer de demander les 1000 symboles avant de charger
la session auquel cas le sampleValue.provider_global_index redevient 
utilisable ?

Euskadi.











_______________________________________________
Tsp-devel mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/tsp-devel

---------------------------------------------------------

CE COURRIER ELECTRONIQUE EST A USAGE STRICTEMENT INFORMATIF ET NE SAURAIT 
ENGAGER DE QUELQUE MANIERE QUE CE SOIT EADS ASTRIUM SAS, NI SES FILIALES.

SI UNE ERREUR DE TRANSMISSION OU UNE ADRESSE ERRONEE A MAL DIRIGE CE COURRIER, 
MERCI D'EN INFORMER L'EXPEDITEUR EN LUI FAISANT UNE REPONSE PAR COURRIER 
ELECTRONIQUE DES RECEPTION. SI VOUS N'ETES PAS LE DESTINATAIRE DE CE COURRIER, 
VOUS NE DEVEZ PAS L'UTILISER, LE CONSERVER, EN FAIRE ETAT, LE DISTRIBUER, LE 
COPIER, L'IMPRIMER OU EN REVELER LE CONTENU A UNE TIERCE PARTIE.



This email is for information only and will not bind EADS Astrium SAS in any 
contract or obligation, nor its subsidiaries.

If you have received it in error, please notify the sender by return email. If 
you are not the addressee of this email, you must not use, keep, disseminate, 
copy, print or otherwise deal with it.

---------------------------------------------------------