J'ai enfoncé environ un mois de temps plein dans un analyseur d'équation C ++ natif. Cela fonctionne, sauf qu'il est lent (entre 30-100 fois plus lent qu'une équation codée dur). Que puis-je changer pour le rendre plus rapide?
Je lis tout ce que je pouvais trouver sur un code efficace. Dans de larges traits:
Il n'y a pas un seul interrupteur si / commutateur rencontré lors de l'évaluation d'une équation - tous les conditionnels sont gérés par l'analyseur lorsqu'il attribuait à l'origine les pointeurs de fonction.
J'ai beaucoup de code. Je ne sais pas quoi distiller / poster. Demandez un aspect de celui-ci et vous recevrez.
6 Réponses :
Dans votre message, vous ne mentionnez pas que vous avez profilé au code. C'est la première chose que je ferais si j'étais à votre place. Cela vous donnera une bonne idée de l'endroit où le temps est passé et où concentrer vos efforts d'optimisation.
Je n'ai pas encore profilé au code. Merci pour la suggestion. Je sais que le goulot d'étranglement est en évaluation, pas analyser.
La toute première chose est la suivante: profil de ce qui s'est mal passé. Est le goulot d'étranglement dans l'analyse ou en évaluation? Valgrind propose des outils qui peuvent vous aider ici.
Si c'est à l'autre, Boost :: Spirit pourrait vous aider. Si dans l'évaluation, rappelez-vous que les fonctions virtuelles peuvent être assez lentes à évaluer. J'ai fait de très bonnes expériences avec un boost récursif :: Variante.
Je ne suis pas trop préoccupé par le temps d'analyse. Cela arrive à l'avant. J'utilise l'évaluation d'environ un million de fois aussi souvent que de l'analyse.
Vous savez, construire un analyseur de descente récursif est vraiment facile, la grammaire LL (1) pour les expressions n'est que quelques règles. L'analyse devient alors une liaison linéaire et tout le reste peut travailler sur l'arbre d'expression (tout en analysant fondamentalement); Vous collectionneriez les données des nœuds inférieurs et transmettez-le aux nœuds supérieurs pour l'agrégation.
Cela éviterait tout autant des pointeurs de fonction / classe pour déterminer le chemin d'appel à l'heure d'exécution, en s'appuyant au lieu de la récursivité éprouvée (ou vous pouvez construire un analyseur Itératif LL si vous le souhaitez).
Il est difficile de dire à votre description si la lenteur comprend l'analyse, ou c'est juste le temps d'interprétation.
L'analyseur, si vous l'écrivez comme une descente récursive (LL1) devrait être I / O liée. En d'autres termes, la lecture des caractères par l'analyseur et la construction de votre arbre d'analyse devraient prendre beaucoup moins de temps qu'il ne faut tout simplement lire le fichier dans un tampon.
L'interprétation est une autre question. Le différentiel de vitesse entre le code interprété et compilé est généralement de 10 à 100 fois plus lent, à moins que les opérations de base elles-mêmes soient longues. Cela dit, vous pouvez toujours l'optimiser.
Vous pouvez profiler, mais dans un cas aussi simple, vous pourriez également simplement ressentir le programme, dans le débogueur, au niveau des instructions individuelles. De cette façon, vous "marchez dans les chaussures de l'ordinateur" et ce sera évident ce qui peut être amélioré.
Chaque fois que je fais ce que vous faites, c'est-à-dire de fournir une langue à l'utilisateur, mais je veux que la langue ait une exécution rapide, ce que je fais est la suivante: Je traduis la langue source en une langue que j'ai un compilateur pour, puis la compilez sur la volée dans un .dll (ou .exe) et courez cela. C'est très rapide et je n'ai pas besoin d'écrire un interprète ou de vous inquiéter de la rapidité.
En plus de profilage, je vais essayer un seul pas à pas comme vous le suggérez. Mais je l'ai conçu avec la stratégie que vous mentionnez - devenant un avec l'ordinateur;)
@Marupio: En outre, dormez dessus, puis essayez l'approche Compile-On-Fly. Vous imprimez un fichier de programme, exécutant le compilateur et la liaison pour créer un fichier .dll, puis chargez le fichier .dll et localisez le point d'entrée que vous souhaitez appeler. Que tout prend environ une seconde. Ensuite, vous pouvez exécuter le code à la vitesse supérieure. J'ai fait cela plus de fois que je ne peux pas compter. Il vole.
J'aime votre suggestion, maintenant que je l'ai relis et compris. Je peux émettre le code dans un fichier source, mais je ne sais pas comment appeler un compilateur à la volée. Je vais regarder dans ça. Ce sera probablement pour la prochaine version. Merci!
@Marupio: Je viens d'écrire un fichier de commandes dans un répertoire pratique. Ensuite, il y a des non-sens sur la création d'un processus et l'attente de se terminer. Les fonctions sont appelées CreateProcess qui vous donne une poignée et waitforsingleObject . Ensuite, pour charger la DLL, c'est LoadLibrary . Pour obtenir les points d'appel, c'est getProcAddress .
Il semble que vous utilisiez une structure de données assez compliquée (si je comprends bien, un arbre de syntaxe avec des pointeurs, etc.). Ainsi, marcher à travers la déréférence du pointeur n'est pas très efficace de mémoire (beaucoup d'accès aléatoires) et pourrait vous ralentir de manière significative. Comme le proposait Mike Dunlavey, vous pouvez compiler toute l'expression à l'exécution d'une autre langue ou en incorporant un compilateur (tel que LLVM). Pour ce que je sais, Microsoft .Net fournit cette fonctionnalité (compilation dynamique) avec réflexion.emit et linq.expression arbres.
C'est ce qui me préoccupe. En fait, pour gérer les pointeurs de fonction, mon équationReader appelle une fonction "CallFunctionPoinger" dans mon objet d'exploitation, qui appelle à son tour la fonction dans l'équationReader. J'étais sur le point de m'attaquer à cette bêtises, mais je pensais que toute la structure a-t-elle besoin de changer. En ce qui concerne la compilée au moment de l'exécution, cela existe déjà dans le projet, mais je suis trop loin dans - je ne veux pas abandonner l'analyseur, et 2. Je veux que l'utilisateur entrait des équations de type Excel, pas de code source.
@MaruPio Eh bien, je ne sais pas vraiment comment votre code source ressemble, mais portant de base C ++ (pointeurs, références et fonctions, aucun modèle de métaprogramming de modèle fou) à C # est assez simple. Et ensuite, vous pouvez utiliser votre analyseur pour générer une AST (arborescence de syntaxe abstraite) de tout ce que l'on ressemble à l'utilisateur. Ensuite, générez du code de cette ast et compilez-le à la volée avec .NET JIT.
C'est l'un de ces moments rares que je conseillerais contre profilage tout simplement. Mon devinette immédiate est que la structure de base que vous utilisez est la source réelle du problème. Profilage Le code vaut rarement beaucoup jusqu'à ce que vous soyez raisonnablement certain que la structure de base est raisonnable et il s'agit principalement de trouver quelles parties de cette structure de base peuvent être améliorées. Ce n'est pas si utile quand ce que vous avez vraiment besoin de faire est de jeter la majeure partie de ce que vous avez et de recommencer essentiellement.
Je conseillerais de convertir l'entrée en RPN. Pour l'exécuter, la seule structure de données dont vous avez besoin est une pile. Fondamentalement, lorsque vous arrivez à un opérande, vous le poussez sur la pile. Lorsque vous rencontrez un opérateur, il fonctionne sur les articles en haut de la pile. Lorsque vous avez terminé d'évaluer une expression bien formée, vous devez avoir exactement un élément sur la pile, qui correspond à la valeur de l'expression.
À peu près la seule chose qui donnera généralement une meilleure performance que celle-ci est de faire comme @Mike Dunlavey conseillée et générer simplement un code source et de l'exécuter via un "vrai" compilateur. C'est cependant une solution assez "lourde". Si vous avez vraiment besoin d'une vitesse maximale, c'est clairement la meilleure solution - mais si vous voulez simplement améliorer ce que vous faites maintenant, la conversion en RPN et l'interprétation qui donnera généralement une amélioration de vitesse décente pour une petite quantité de code. < / p>
J'aurais dû penser à RPN. Néanmoins, je pense que ma perte d'efficacité provient de manière dynamique d'essayer de trouver le bon fonctionnement à exécuter - ce serait également un problème avec RPN. Si RPN dit "3 4 +", quel est le moyen le plus efficace de l'obtenir d'exécuter ajouté (), une parmi 60 fonctions / opérateurs possibles? Vous avez mentionné la réponse de @Mike Dunlavey, alors je l'ai relissi à et réalisez que je n'ai pas bien compris ce qu'il disait. Cela semble lourd, mais je pense que je peux l'essayer.
@Marupio: Habituellement, vous souhaitez affecter une gamme de valeurs consécutives aux opérateurs que vous utilisez au lieu d'utiliser des symboles lisibles humains. Une instruction de commutation est généralement au moins aussi rapide que les alternatives. Un tableau / vecteur de pointeurs vers des fonctions / fonctions a l'air Comme si cela serait plus rapide, mais dans mes tests finissent généralement plus lentement qu'un commutateur .
En ce qui concerne l'idée de @ Mike, cela semble être assez simple: au lieu d'interpréter l'expression, il suffit de le mettre dans un squelette C (ou autre), compilez-le à une DLL / ainsi, puis chargez de manière dynamique le résultat dans votre programme.
Autant que je sache, l'inlinage n'est qu'un indice pour le compilateur, pas une commande. Peut-être essayez peut-être de compiler avec optimisation (
-O3 ou quelque chose) ...En fait, vous ne pouvez pas les fonctions en ligne que vous appelez de manière dynamique via des pointeurs car le compilateur ne sait pas quelle fonction (le cas échéant) vous appelez réellement.
Peut-être devriez-vous examiner la sortie du bytecode au moment de l'exécution. Sous Windows, vous pouvez spécifier un emplacement de mémoire exécutable. Vous pouvez émettre la série d'instructions de montage correspondant à votre équation. Cela vous rapproche généralement des équations à codage dur non optimisées.
Merci pour toutes les réponses rapides, je suis très impressionné par Stackoverflow et sa communauté. Juste quelques petites choses à ajouter: je ne suis pas préoccupé par le temps d'analyse. Il stocke la liste de fonds, de sorte qu'il ne fait qu'une seule fois pour chaque (environ) millions d'évaluations.