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

[Erk]

Merci à Robert pour l'analyse,
le code du hash_bob est déjà dans l'arbo TSP:

tsp/src/util/libutil/tsp_hash.[h,c]

j'ai d'ailleurs ré-activé la compil de ce module
pas plus tard qu'avant hier :))

Je l'avais utilisé mais sur des clefs de trop grande taille
(du coup ça coutait cher en mémoire)
mais effectivement pour des clefs de petites taille
ça m'a l'air bien sympathique.

Eric

Le 28/11/05, PAGNOT, Robert<address@hidden> a écrit :
>
> 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.
>
> ---------------------------------------------------------
>
>
> _______________________________________________
> Tsp-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/tsp-devel
>


--
erk