Je suis en train d'exécuter un algorithme de recherche qui est nourri au début avec une seule graine. De ce point, je m'attends à ce que l'algorithme se comporte de manière déterministe, ce qui le fait en grande partie. Je peux en largement vérifier cela en examinant la 10 000e étape, 20 000 étapes et en voyant qu'ils sont identiques. Ce que je vois différent, c'est la longueur du temps du processeur de fil utilisé pour atteindre le même endroit (ayant pris des chemins identiques). Je mesure le temps de fil avec ProcessThread.TotalProcessortime.
Pour quantifier cela, j'ai fait des tests pour vous. J'ai modifié l'heure d'exécution et mesuré le nombre de solutions évaluées dans ce temps
J'ai répété le test 8 fois pour chacun. Les deux lignes inférieures indiquent les solutions moyennes évaluées sur une période de 30 secondes suivie de l'écart type. J'ai répété le test des années 120 car l'écart type était si élevé la première fois et beaucoup plus bas la deuxième fois.
Si mon algorithme fait le même travail, ce qui pourrait causer le même temps de prendre des quantités différentes ? Quel élément aléatoire est introduit?
clarifier quelques points:
meilleures salutations
5 Réponses :
Optimisation, gestion de la mémoire (GC, allocation, pagination, etc.) et juste dans la compilation de temps.
Et la mémoire allouée CLR.
L'optimisation / la compilation JIT sera probablement déterministe, c'est-à-dire que le compilateur compilera toujours le code jusqu'à la recherche de la même chose à moins que les SETGS / COMPILER / CODE changent.
Eh bien, GC est le plus déterministe de tous, et le plus susceptible de faire une différence, mais comme il est "un algorithme de recherche" avec un espace de recherche éventuellement important, je présume que la pagination aura une grand effet.
@Adam: L'allocation est très rapide et déterministe.
@Henk n'a jamais dit que ce n'était pas, mais il n'offre aucune garantie quant à la possibilité de réagir dans un temps donné - le système d'exploitation présentera des problèmes ici. Les systèmes déterministes doivent offrir ces garanties.
Le temps de processeur est le temps partagé, de sorte que toute autre activité qui se produise sur votre machine peut affecter les performances.
Je suis corrigé.
Incorrect - Le temps de processeur est partagé mais le compteur processterthread.totalprocessortime.totalprocessortime n'enregistre que du temps que le processeur dépense sur ce fil. Toute autre activité sur la machine ne sera pas comptée par ce comptoir.
Cependant, pas tout à fait incorrect. Le temps de processeur physique sur une activité peut rester constant, mais le temps de départ à la fin, car un processeur change de tâches contribue au comportement déterministe.
@ADAM Vous voulez dire en raison du changement de contexte?
Pas seulement que, la tranche de temps donnée au processeur pour effectuer une certaine tâche, sur un système d'exploitation normal exécutant plus d'un processus, la tranche de temps n'est pas déterministe du point de vue de l'application. Il est facile de souffler cela dans le domaine du matériel capable, mais l'OP a déclaré .NET et non indiqué de matériel, donc je suppose Windows Desktop.
sur le niveau du processeur, les erreurs de cache et les prédictions de branche incorrectes peuvent avoir une incidence sur la quantité de temps de processeur pouvant être extraite d'une course à une autre. Sur le niveau de cadre, Jiting et GC peuvent également l'affecter. Ces derniers sont plus susceptibles d'être observés que le premier.
Les erreurs de cache et les prévisions de branche incorrectes sont également déterminantes, mais il y aura également des aspects au niveau du système d'exploitation (tels que les allocations de mémoire et lorsqu'un thread est préempté) qui aura également un effet.
Quelles ressources utilisées votre algorithme? Y a-t-il un autre processus qui utilise les mêmes ressources? Cela inclut la CPU, la mémoire, l'IO (pageFile). D'autres processus auront un impact sur la performance de votre algorithme.
Qu'est-ce qu'une différence de temps? 1%? dix%?
Votre algorithme peut être déterministe, mais absolument aucun de l'environnement et des éléments d'exécution sont:
Dans l'ensemble, ne vous attendez pas à un comportement déterministe dans un système non déterministe. Windows CE prend en charge la dure temps réel, mais vous devez toujours utiliser quelque chose d'autre que .net dessus.
garder à l'esprit que "déterministe" est dans un sens qui dit: "Ce morceau de code prend exactement 20 millisecondes chaque fois qu'il fonctionne. Vous n'avez aucun espoir d'atteindre cela avec un runtime qui est non déterministe sur un système d'exploitation non déterministe.
Le déterminisme dans le sens d'un système d'exploitation est généralement moins strict que "exactement", plus comme: "Je peux garantir que je réponds dans X, sinon j'arrive". Doux et dure temps réel sont de plus en plus flexibles sur ce point, respectivement.
Le point GC sonne bien, mais la première et la troisième balle sont fausses ou du moins discutables.
La troisième balle n'est pas discutable, c'est le moteur de planification dans le système d'exploitation de temps non réel qui en fait un temps non réel en premier lieu. Le premier point est vraiment juste de mettre en évidence que les choses à l'intérieur du temps d'exécution n'offrent pas le contrat qu'ils garantissent d'exécuter à l'intérieur d'une certaine période. Le CLR n'offre aucune garantie que ce sera ou ne déclenchera pas un GC, juste que pourrait , et qu'il peut vous garantir que vous avez suffisamment de mémoire pour servir la demande, juste que vous pourrait . Point étant, ne vous attendez pas aux caractéristiques en temps réel sur les systèmes de temps non réel ...
De plus, l'OP avait demandé des choses qui causent les divergences, de sorte que mes points sont toujours valables.
Adam, on dirait que vous discutez du temps écoulé, pas de processorime. Toutes les influences de parcours / planification doivent être filtrées, épargner peut-être de petits effets.
Oui, le temps du processeur restera probablement constamment en supposant que la mise en cache n'est pas un problème, mais le temps écoulé de la commande reste inconnu. Ceci est également important pour le comportement en temps réel.
Adam, la question portait sur le temps pris par un algorithme et non les réponses de RT.
Henk, la question portait sur le temps nécessaire à la gestion de l'algorithme ... sur .NET, probablement sur un bureau et quelles sont les divergences aléatoires dans le temps. S'attendant à ce que cela prenne le même temps chaque fois que chaque fois l'ouvre la porte pour parler de comportement en temps réel et parler de ce comportement devrait conduire à la conclusion que, à moins que ce soit dans de telles circonstances, vous ne pouvez rien espérer Autre que pour chaque course d'avoir des timings légèrement différents.
Est-ce que vous traitez un processeur dédié?
Je suppose que vous n'utilisez pas non plus un système d'exploitation en temps réel, alors les interruptions matérielles causent des différences.
Évaluez-vous votre application ou l'architecture système sous-jacente? C'est à dire. Comment ce compteur est-il affecté par la commutation de thread, Misses de cache, la priorité de processus, etc.?
Aussi, rappelez-vous que le principe de Heisenberg ...
Votre algorithme pourrait être déterministe, mais beaucoup d'autres choses se produisent également sur la machine en même temps qui aura un effet (en particulier avec un système d'exploitation moderne). Le seul moyen réel de rendre votre temps total de processeur déterministe serait probablement la seule chose à exécuter sur la machine (c'est-à-dire aucun système d'exploitation).
@Kragen, même ça ne le ferait pas.
@Adam en fait, je pense que c'est probablement les transformateurs et la mémoire des transformateurs et de la mémoire sont réellement prévisibles et à l'exclusion d'une défaillance matérielle ou de toute sorte d'IO, vous devriez pouvoir prédire cela jusqu'au cycle du processeur.
@Kragen je n'ai pas repéré la partie (sans système d'exploitation), il y a des moyens moins drastiques de le rendre déterministe lol
@HOWARD: Quelle est la taille (absolue et relative) ces différences?