J'ai récemment interviewé à Amazon. Lors d'une session de codage, l'intervieweur a demandé pourquoi j'avais déclaré une variable dans une méthode. J'ai expliqué mon processus et il m'a mis au défi de résoudre le même problème avec moins de variables. Par exemple (ce n’était pas de l’interview), j’ai commencé avec la méthode A puis l’ améliorais à la méthode B en supprimant int s
. Il était heureux et a déclaré que cela réduirait l'utilisation de la mémoire par cette méthode.
Je comprends la logique derrière cela, mais ma question est la suivante:
Quand est-il approprié d'utiliser la méthode A par rapport à la méthode B et vice versa?
Vous pouvez voir que la méthode A va utiliser plus de mémoire, car elle int s
est déclarée, mais elle ne doit effectuer qu'un seul calcul, à savoir a + b
. En revanche, la méthode B utilise moins de mémoire, mais doit effectuer deux calculs, à savoir a + b
deux fois. Quand est-ce que j'utilise une technique plutôt que l'autre? Ou bien l'une des techniques est-elle toujours préférée par rapport à l'autre? Quelles sont les choses à considérer lors de l'évaluation des deux méthodes?
Méthode A:
private bool IsSumInRange(int a, int b)
{
int s = a + b;
if (s > 1000 || s < -1000) return false;
else return true;
}
Méthode B:
private bool IsSumInRange(int a, int b)
{
if (a + b > 1000 || a + b < -1000) return false;
else return true;
}
la source
int s
tout en étant parfaitement d'accord avec ces nombres magiques pour les limites supérieure et inférieure?Réponses:
Au lieu de spéculer sur ce qui peut ou ne peut pas arriver, regardons, allons-nous? Je vais devoir utiliser le C ++ car je n'ai pas de compilateur C # à portée de main ( voir l'exemple C # de VisualMelon ), mais je suis sûr que les mêmes principes s'appliquent malgré tout.
Nous allons inclure les deux alternatives que vous avez rencontrées dans l'interview. Nous allons également inclure une version qui utilise
abs
comme suggéré par certaines des réponses.Maintenant, compilez-le sans aucune optimisation:
g++ -c -o test.o test.cpp
Nous pouvons maintenant voir précisément ce que cela génère:
objdump -d test.o
On peut voir à partir des adresses de la pile (par exemple,
-0x4
enmov %edi,-0x4(%rbp)
fonction de l'-0x14
enmov %edi,-0x14(%rbp)
) quiIsSumInRangeWithVar()
utilise 16 octets supplémentaires sur la pile.Parce que
IsSumInRangeWithoutVar()
n'alloue aucun espace sur la pile pour stocker la valeur intermédiaire,s
il doit la recalculer, ce qui entraîne une implémentation de 2 instructions de plus.C'est drôle,
IsSumInRangeSuperOptimized()
ça ressemble beaucoupIsSumInRangeWithoutVar()
, sauf que ça se compare à -1000 en premier et à 1000 secondes.Maintenant , nous allons compiler avec seulement les optimisations de base:
g++ -O1 -c -o test.o test.cpp
. Le résultat:Voulez-vous regarder cela: chaque variante est identique . Le compilateur est capable de faire quelque chose d'assez intelligent:
abs(a + b) <= 1000
équivaut àa + b + 1000 <= 2000
envisagersetbe
une comparaison non signée, ainsi un nombre négatif devient un très grand nombre positif. L'lea
instruction peut en réalité effectuer tous ces ajouts en une seule instruction et éliminer toutes les branches conditionnelles.Pour répondre à votre question, l’optimisation n’exige presque toujours ni la mémoire ni la vitesse, mais la lisibilité . Lire du code est beaucoup plus difficile que de l'écrire, et lire du code qui a été mutilé pour "l'optimiser" est beaucoup plus difficile que de lire du code qui a été écrit pour être clair. Le plus souvent, ces "optimisations" ont un impact négligeable, ou comme dans le cas présent, zéro sur les performances.
Mesurons! J'ai transcrit les exemples en Python:
Exécutée avec Python 3.5.2, cela produit la sortie:
Le désassemblage en Python n'est pas très intéressant, car le "compilateur" bytecode ne fait pas beaucoup d'optimisation.
La performance des trois fonctions est presque identique. Nous pourrions être tentés d'y aller en
IsSumInRangeWithVar()
raison de son gain de vitesse marginal. Bien que j'ajoute que j'essayais différents paramètrestimeit
, parfois cela seIsSumInRangeSuperOptimized()
présentait le plus rapidement, alors je suppose que cela pourrait être dû à des facteurs externes responsables de la différence plutôt qu'à tout avantage intrinsèque de toute implémentation.S'il s'agit vraiment d'un code critique en termes de performances, un langage interprété est tout simplement un très mauvais choix. En exécutant le même programme avec pypy, je reçois:
Le simple fait d'utiliser pypy, qui utilise la compilation JIT pour éliminer une bonne partie des frais généraux de l'interprète, a permis d'améliorer les performances d'un ou deux ordres de grandeur. J'ai été assez choqué de voir
IsSumInRangeWithVar()
que l'ordre de grandeur est plus rapide que les autres. J'ai donc changé l'ordre des repères et j'ai couru à nouveau:Il semble donc que ce n’est pas vraiment quelque chose au sujet de la mise en œuvre qui accélère, mais plutôt l’ordre dans lequel je fais le benchmarking!
J'aimerais approfondir cette question car, honnêtement, je ne sais pas pourquoi cela se produit. Mais je crois que l’argument a été formulé: les micro-optimisations telles que la déclaration d’une valeur intermédiaire en tant que variable ou non sont rarement pertinentes. Avec un langage interprété ou un compilateur hautement optimisé, le premier objectif est toujours d’écrire du code clair.
Si une optimisation supplémentaire est nécessaire, comparez . Rappelez-vous que les meilleures optimisations ne proviennent pas des petits détails mais de la plus grande image algorithmique: pypy sera un ordre de grandeur plus rapide pour une évaluation répétée de la même fonction que cpython car il utilise des algorithmes plus rapides (compilateur JIT vs interprétation) pour évaluer la programme. Et il y a aussi l'algorithme codé à considérer: une recherche dans un arbre B sera plus rapide qu'une liste chaînée.
Une fois que vous assurer utilisez les bons outils et des algorithmes pour le travail, soyez prêt à plonger profondément dans les détails du système. Les résultats peuvent être très surprenants, même pour les développeurs expérimentés. C'est pourquoi vous devez disposer d'un point de repère pour quantifier les changements.
la source
Pour répondre à la question posée:
Il y a deux choses que vous devez établir:
Afin de répondre à la première question, vous devez connaître les exigences de performance de votre application. S'il n'y a pas d'exigences de performance, il n'y a aucune raison d'optimiser d'une manière ou d'une autre. Les exigences de performance vous aident à vous rendre à la place de "assez bon".
La méthode que vous avez fournie seule ne poserait pas de problème de performances, mais peut-être qu'en boucle et en traitant une grande quantité de données, vous devez commencer à penser un peu différemment à la façon dont vous abordez le problème.
Détecter ce qui limite l'application
Commencez à examiner le comportement de votre application avec un moniteur de performances. Surveillez l'utilisation du processeur, des disques, du réseau et de la mémoire pendant son fonctionnement. Un ou plusieurs éléments seront maximisés tandis que tout le reste est utilisé avec modération - à moins que vous n'atteigniez l'équilibre parfait, mais cela ne se produit presque jamais).
Lorsque vous devez regarder plus en profondeur, vous utiliserez généralement un profileur . Il existe des profileurs de mémoire et des profileurs de processus qui mesurent différentes choses. Le profilage a un impact significatif sur les performances, mais vous instrumentez votre code pour découvrir ce qui ne va pas.
Disons que l'utilisation de votre processeur et de votre disque est à son maximum. Vous devez d’abord vérifier les «points chauds» ou le code appelé plus souvent que les autres ou nécessitant un pourcentage de traitement beaucoup plus long.
Si vous ne trouvez pas de points chauds, vous commencerez alors à examiner la mémoire. Peut-être créez-vous plus d'objets que nécessaire et votre récupération de place ne fonctionne plus.
Récupérer la performance
Pense de façon critique. La liste de modifications suivante indique le retour sur investissement que vous obtiendrez:
Dans de telles situations, vous devez appliquer la méthode scientifique. Proposez une hypothèse, effectuez les modifications et testez-la. Si vous atteignez vos objectifs de performance, vous avez terminé. Sinon, passez à la prochaine chose dans la liste.
Répondre à la question en gras:
Honnêtement, c’est la dernière étape pour tenter de résoudre les problèmes de performances ou de mémoire. L'impact de la méthode A par rapport à la méthode B sera très différent selon le langage et la plate - forme (dans certains cas).
À peu près n'importe quel langage compilé avec un optimiseur à mi-parcours décent générera un code similaire avec l'une ou l'autre de ces structures. Cependant, ces hypothèses ne restent pas nécessairement vraies dans les langages propriétaires et les langages de jouets ne disposant pas d'optimiseur.
Ce qui aura un meilleur impact dépendra du
sum
type de variable de pile ou de pile. C'est un choix d'implémentation linguistique. En C, C ++ et Java, par exemple, les primitives numériques comme unint
sont des variables de pile par défaut. Votre code n'a pas plus d'impact sur la mémoire en affectant une variable de pile que vous n'auriez avec un code entièrement en ligne.Les autres optimisations que vous pouvez trouver dans les bibliothèques C (en particulier les plus anciennes), où vous pouvez avoir à choisir entre copier un tableau à 2 dimensions en premier ou en premier, est une optimisation dépendante de la plate-forme. Cela nécessite une certaine connaissance de la manière dont le chipset que vous ciblez optimise au mieux l’accès à la mémoire. Il existe des différences subtiles entre les architectures.
En bout de ligne, l'optimisation est une combinaison d'art et de science. Cela nécessite une réflexion critique ainsi qu'une certaine souplesse dans la manière dont vous abordez le problème. Recherchez les grandes choses avant de blâmer les petites choses.
la source
"cela réduirait la mémoire" - em, no. Même si cela était vrai (ce qui n'est pas le cas pour un compilateur décent), la différence serait très probablement négligeable pour toute situation réelle.
Cependant, je recommanderais d'utiliser la méthode A * (méthode A avec une légère modification):
mais pour deux raisons complètement différentes:
en donnant à la variable
s
un nom explicatif, le code devient plus claircela évite d'avoir deux fois la même logique de sommation dans le code, de sorte que le code devient plus sec, ce qui signifie moins d'erreur susceptible de modifications.
la source
sum
variable, conduisant ainsi à une utilisation nulle de la mémoire. Et même si ce n'est pas le cas, il ne s'agit que d'un mot de mémoire dans une méthode «feuille». Compte tenu du fait que Java ou C # peut être extrêmement coûteux en mémoire, en raison de leur modèle d'objet et de catalogue global, uneint
variable locale n'utilise littéralement aucune mémoire visible. C'est une micro-optimisation inutile.sum
serait un détail de mise en œuvre et je doute que quiconque puisse argumenter de manière convaincante sur le point de savoir si un truc idiot, comme éviter un localint
, le mènerait ou non. cette quantité d'utilisation de la mémoire à long terme. La lisibilité de l'OMI est plus importante. La lisibilité peut être subjective, mais FWIW, personnellement, je préférerais que vous ne fassiez jamais le même calcul deux fois, pas pour utiliser le processeur, mais parce que je n'ai qu'à inspecter votre ajout une fois lorsque je cherche un bogue.Vous pouvez faire mieux que les deux avec
La plupart des processeurs (et donc des compilateurs) peuvent exécuter abs () en une seule opération. Vous avez non seulement moins de sommes, mais également moins de comparaisons, qui coûtent généralement plus cher en calcul. Cela supprime également les branchements, ce qui est bien pire pour la plupart des processeurs car cela empêche la création de canaux en pipeline.
L’intervieweur, comme d’autres réponses l’ont dit, parle de la vie de l’usine et n’a pas d’activité à mener une interview technique.
Cela dit, sa question est valide. Et la réponse à apporter lorsque vous optimisez et comment, c’est lorsque vous avez prouvé que c’était nécessaire et que vous l’avez profilée pour prouver exactement quelles pièces en avaient besoin . Knuth a déclaré que l'optimisation prématurée est la racine de tout mal, car il est trop facile d'essayer de mettre en valeur des sections sans importance, ou d'apporter des modifications (comme celle de l'intervieweur) qui n'ont aucun effet, tout en manquant les endroits qui en ont vraiment besoin. Jusqu'à ce que vous ayez une preuve irréfutable, c'est vraiment nécessaire, la clarté du code est la cible la plus importante.
Edit FabioTurati souligne à juste titre que c’est le sens logique opposé à l’original (mon erreur!) Et qu’il illustre un impact supplémentaire de la citation de Knuth dans laquelle nous risquons de casser le code tout en essayant de l’optimiser.
la source
a+b
dansif
et de le faire deux fois. Vous comprenez que c'est faux "Il était ravi et a dit que cela réduirait l'utilisation de la mémoire par cette méthode" - il était gentil avec vous, cachant sa déception avec cette explication dénuée de sens sur la mémoire. Vous ne devriez pas prendre au sérieux de poser la question ici. Avez-vous trouvé un travail? Je suppose que vous ne l'avez pas fait :-(abs()
vous en avez également unereturn
, au lieu d’en avoir une lorsque la condition est vraie ("if branch") et une autre quand il est faux ( "autre branche"). Lorsque vous changez le code de cette manière, faites attention: vous risquez d'écrire par inadvertance une fonction qui renvoie true, alors qu'elle devrait retourner false, et inversement. Ce qui est exactement ce qui s'est passé ici. Je sais que vous vous concentrez sur autre chose et que vous avez fait du bon travail à cet égard. Pourtant, cela aurait pu facilement vous coûter le travail ...adds
, et ARM a prédicté reverse-sub (rsblt
= reverse-sub si less-tha), mais tout le reste nécessite plusieurs instructions supplémentaires à implémenterabs(a+b)
ouabs(a)
. godbolt.org/z/Ok_Con affiche les sorties xm , ARM, AArch64, PowerPC, MIPS et RISC-V. Ce n'est qu'en transformant la comparaison en une vérification de la portée(unsigned)(a+b+999) <= 1998U
que gcc peut l'optimiser comme dans la réponse de Phil.IsSumInRange(INT_MIN, 0)
. Le code d'origine retournefalse
parce queINT_MIN+0 > 1000 || INT_MIN+0 < -1000
; mais le code "nouveau et amélioré" revienttrue
carabs(INT_MIN+0) < 1000
. (Ou, dans certaines langues, une exception ou un comportement indéfini sera lancé. Vérifiez vos listes locales.)Le matériel est bon marché; les programmeurs sont chers . Donc, le coût du temps que vous avez gaspillé sur cette question est probablement bien pire que la réponse.
Quoi qu’il en soit, la plupart des compilateurs modernes trouveraient un moyen d’optimiser la variable locale dans un registre (au lieu d’allouer de l’espace pile), de sorte que les méthodes sont probablement identiques en termes de code exécutable. Pour cette raison, la plupart des développeurs choisissent l'option qui communique le plus clairement l'intention (voir Rédaction de code vraiment évident ). À mon avis, ce serait la méthode A.
D'un autre côté, s'il s'agit d'un exercice purement académique, vous pouvez avoir le meilleur des deux mondes avec la méthode C:
la source
a+=b
C'est une astuce intéressante, mais je dois mentionner (juste au cas où ce ne serait pas implicite dans le reste de la réponse), de par mon expérience des méthodes qui compliquent le fouillis avec les paramètres peuvent être très difficiles à déboguer et à maintenir.if
contrôle, mais vous avez oublié d'annuler le résultat de la comparaison. votre fonction revient maintenanttrue
quanda + b
n'est pas dans la plage. Ajoutez un!
à l'extérieur de la condition (return !(a > 1000 || a < -1000)
), ou distribuez les!
testsreturn a <= 1000 && a >= -1000;
return -1000 <= a && a <= 1000;
<=
/>=
, pas<
/>
(avec<
/>
, 1000 et -1000 sont traités comme étant hors plage, le code d'origine les a traités comme s'ils étaient dans la plage).J'optimiserais pour la lisibilité. Méthode X:
Petites méthodes qui ne font qu'une chose mais sont faciles à raisonner.
(Ceci est une préférence personnelle, j'aime les tests positifs au lieu de négatifs, votre code d'origine teste réellement si la valeur n'est PAS en dehors de la plage.)
la source
a
etb
ànumber1
et lanumber2
lisibilité des aides de quelque façon. De plus, la dénomination des fonctions est incohérente: pourquoiIsSumInRange
coder de manière irréversible la plage si l’IsValueInRange
accepter comme argument?En bref, je ne pense pas que la question ait beaucoup de pertinence dans l’informatique actuelle, mais d’un point de vue historique, c’est un exercice de réflexion intéressant.
Votre intervieweur est probablement un fan du mois de l'homme mythique. Dans le livre, Fred Brooks explique que les programmeurs auront généralement besoin de deux versions des fonctions principales dans leur boîte à outils: une version optimisée pour la mémoire et une version optimisée pour le processeur. Fred s’appuie sur son expérience pour diriger le développement du système d’exploitation IBM System / 360, sur lequel les machines ne disposent que de 8 kilo-octets de RAM. Dans de telles machines, la mémoire requise pour les variables locales dans les fonctions pourrait être potentiellement importante, surtout si le compilateur ne les optimisait pas efficacement (ou si le code était écrit directement en langage assembleur).
Dans l'ère actuelle, je pense que vous auriez du mal à trouver un système où la présence ou l'absence d'une variable locale dans une méthode ferait une différence notable. Pour qu'une variable ait de l'importance, la méthode doit être récursive avec une récursion profonde attendue. Même dans ce cas, il est probable que la profondeur de la pile soit dépassée, ce qui entraîne des exceptions de dépassement de capacité avant que la variable elle-même ne provoque un problème. Le seul scénario réel où cela peut poser problème concerne les très grands tableaux alloués sur la pile de manière récursive. Mais cela est également peu probable, car je pense que la plupart des développeurs réfléchiraient à deux fois aux copies inutiles de grands tableaux.
la source
Après l'affectation, s = a + b; les variables a et b ne sont plus utilisées. Par conséquent, aucune mémoire n'est utilisée pour s si vous n'utilisez pas un compilateur complètement endommagé au cerveau; la mémoire utilisée de toute façon pour a et b est réutilisée.
Mais optimiser cette fonction est un non-sens. Si vous pouviez économiser de l'espace, il serait peut-être 8 octets pendant l'exécution de la fonction (ce qui est récupéré lorsque la fonction revient), donc absolument inutile. Si vous pouviez gagner du temps, ce serait un nombre unique de nanosecondes. Optimiser cela est une perte de temps totale.
la source
Les variables de type de valeur locale sont allouées sur la pile ou (plus probablement pour de tels petits morceaux de code) utilisent des registres dans le processeur et n'arrivent jamais à voir la mémoire RAM. De toute façon ils sont de courte durée et rien à craindre. Vous commencez à envisager l'utilisation de la mémoire lorsque vous devez mettre en mémoire tampon ou mettre en file d'attente des éléments de données dans des collections potentiellement volumineuses et de longue durée.
Ensuite, cela dépend de ce qui compte le plus pour votre application. Vitesse de traitement? Temps de réponse? Empreinte mémoire? Maintenabilité? La cohérence dans la conception? Tout dépend de toi.
la source
stackalloc
et maintenantSpan<T>
. Peut-être utile dans un point chaud, après le profilage. De plus, certains documents autour des structures impliquent que les types de valeur peuvent être sur la pile, alors que les types de référence ne le seront pas . Quoi qu'il en soit, au mieux, vous éviterez peut-être un peu de GC.Comme d'autres réponses l'ont dit, vous devez penser à ce que vous optimisez.
Dans cet exemple, je soupçonne que tout compilateur correct générera un code équivalent pour les deux méthodes, de sorte que la décision n’aura aucun effet sur le temps d’exécution ou la mémoire!
Ce que cela affecte, c'est la lisibilité du code. (Le code est destiné aux humains, pas seulement aux ordinateurs.) Il n'y a pas trop de différence entre les deux exemples; quand toutes les autres choses sont égales, je considère la brièveté comme une vertu, alors je choisirais probablement la méthode B. Mais toutes les autres choses sont rarement égales et, dans un cas plus complexe, les effets pourraient être très importants.
Choses à considérer:
la source
Comme de nombreuses réponses l’ont souligné, tenter d’ajuster cette fonction avec des compilateurs modernes ne changera rien. Un optimiseur peut probablement trouver la meilleure solution (vote positif pour la réponse indiquant le code de l'assembleur pour le prouver!). Vous avez déclaré que le code de l'entrevue n'était pas exactement le code que l'on vous a demandé de comparer, alors l'exemple réel est peut-être un peu plus logique.
Mais jetons un autre regard sur cette question: c’est une question d’entrevue. Le vrai problème est donc: comment devriez-vous y répondre en supposant que vous voulez essayer d'obtenir le poste?
Supposons également que l'intervieweur sache de quoi il parle et qu'il essaye simplement de voir ce que vous savez.
Je mentionnerais que, en ignorant l'optimiseur, le premier peut créer une variable temporaire sur la pile, tandis que le second ne le ferait pas, mais effectuerait le calcul deux fois. Par conséquent, le premier utilise plus de mémoire mais est plus rapide.
Vous pouvez mentionner de toute façon qu'un calcul peut nécessiter une variable temporaire pour stocker le résultat (afin qu'il puisse être comparé). Ainsi, si vous nommez cette variable ou non, cela ne fera aucune différence.
Je mentionnerais ensuite qu'en réalité, le code serait optimisé et très probablement un code machine équivalent serait généré car toutes les variables sont locales. Cependant, cela dépend du compilateur que vous utilisez (il n'y a pas si longtemps, je pouvais obtenir une amélioration de performance utile en déclarant une variable locale comme "finale" en Java).
Vous pouvez mentionner que, dans tous les cas, la pile vit dans sa propre page de mémoire. Par conséquent, à moins que votre variable supplémentaire ne provoque le débordement de la pile, elle n'allouera en réalité plus de mémoire. S'il déborde, il voudra une toute nouvelle page.
Je mentionnerais qu'un exemple plus réaliste pourrait être le choix d'utiliser ou non un cache pour conserver les résultats de nombreux calculs ou non, ce qui soulèverait la question du processeur par rapport à la mémoire.
Tout cela montre que vous savez de quoi vous parlez.
Je laisserais jusqu'à la fin de dire qu'il vaudrait mieux se concentrer sur la lisibilité. Bien que cela soit vrai dans le cas présent, dans le contexte de l'interview, cela peut être interprété comme "Je ne sais pas à propos de la performance mais mon code se lit comme une histoire de Janet et John ".
Ce que vous ne devriez pas faire, c’est extraire les déclarations fades habituelles sur le fait que l’optimisation du code n’est pas nécessaire, n’optimisez pas tant que vous n’avez pas profilé le code (cela indique simplement que vous ne pouvez pas voir le mauvais code pour vous-même), le matériel coûte moins cher que les programmeurs. et s'il vous plait, s'il vous plait, ne citez pas Knuth "blah blah prématuré ...".
La performance du code est un réel problème dans de très nombreuses organisations et de nombreuses organisations ont besoin de programmeurs qui la comprennent.
En particulier, avec des organisations telles qu'Amazon, certains codes ont un effet de levier considérable. Un extrait de code peut être déployé sur des milliers de serveurs ou des millions de périphériques et peut être appelé des milliards de fois par jour, tous les jours de l'année. Il peut y avoir des milliers d'extraits similaires. La différence entre un mauvais algorithme et un bon peut être mille fois supérieure. Faites les chiffres et les multiples tout cela: cela fait une différence. Le coût potentiel pour l'organisation d'un code non performant peut être très important, voire fatal, si un système est à court de capacité.
De plus, bon nombre de ces organisations travaillent dans un environnement concurrentiel. Vous ne pouvez donc pas simplement dire à vos clients d'acheter un ordinateur plus grand si le logiciel de votre concurrent fonctionne déjà correctement sur le matériel dont ils disposent ou s'il fonctionne sur un téléphone mobile et qu'il ne peut pas être mis à niveau. Certaines applications sont particulièrement critiques en termes de performances (on pense aux jeux et aux applications mobiles) et peuvent vivre ou mourir en fonction de leur réactivité ou de leur vitesse.
J'ai personnellement travaillé pendant plus de deux décennies sur de nombreux projets où les systèmes ont échoué ou étaient inutilisables en raison de problèmes de performances. On m'a appelé pour optimiser ces systèmes et dans tous les cas, cela était dû à un code mal écrit par des programmeurs qui ne comprenaient pas. l'impact de ce qu'ils écrivaient. De plus, ce n'est jamais un morceau de code, il est toujours partout. Quand j'arrive, il est trop tard pour commencer à penser à la performance: le mal est fait.
Comprendre les performances du code est une bonne compétence, au même titre que la compréhension de l’exactitude et du style de code. Cela vient de la pratique. Les défaillances de performances peuvent être aussi graves que les défaillances fonctionnelles. Si le système ne fonctionne pas, cela ne fonctionne pas. Peu importe pourquoi. De même, les performances et les fonctionnalités qui ne sont jamais utilisées sont mauvaises.
Donc, si l'intervieweur vous pose des questions sur les performances, je vous recommanderais d'essayer de démontrer autant de connaissances que possible. Si la question semble mauvaise, expliquez poliment pourquoi vous pensez que cela ne serait pas un problème dans ce cas. Ne cite pas Knuth.
la source
Vous devez d'abord optimiser pour l'exactitude.
Votre fonction échoue pour les valeurs d'entrée proches de Int.MaxValue:
Cela retourne true car la somme déborde à -400. La fonction ne fonctionne pas non plus pour a = int.MinValue + 200. (ajoute de manière incorrecte à "400")
Nous ne saurons pas ce que cherchait l'intervieweur à moins qu'il ne vienne nous entendre, mais "le débordement est réel" .
Dans une situation d’entrevue, posez des questions pour clarifier l’ampleur du problème: Quelles sont les valeurs maximales et minimales autorisées? Une fois que vous les avez, vous pouvez lever une exception si l'appelant soumet des valeurs en dehors de la plage. Ou (en C #), vous pouvez utiliser une section vérifiée {}, qui lève une exception en cas de dépassement de capacité. Oui, c'est plus de travail et compliqué, mais parfois c'est ce qu'il faut.
la source
Votre question aurait dû être: "Dois-je optimiser cela du tout?".
Les versions A et B diffèrent par un détail important qui rend A préférable, mais cela n’est pas lié à l’optimisation: vous ne répétez pas le code.
L '"optimisation" actuelle est appelée élimination commune des sous-expressions, ce que font à peu près tous les compilateurs. Certains font cette optimisation de base même lorsque les optimisations sont désactivées. Donc, ce n'est pas vraiment une optimisation (le code généré sera presque certainement exactement le même dans tous les cas).
Mais si ce n'est pas une optimisation, alors pourquoi est-ce préférable? Bon, vous ne répétez pas le code, on s'en fiche!
Tout d’abord, vous ne courez pas le risque de vous tromper accidentellement sur la moitié de la clause conditionnelle. Mais plus important encore, quelqu'un qui lit ce code peut dire immédiatement ce que vous essayez de faire, au lieu d'une
if((((wtf||is||this||longexpression))))
expérience. Ce que le lecteur peut voirif(one || theother)
, c’est une bonne chose. Pas rarement, il se trouve que vous êtes cette autre personne qui lit votre propre code trois ans plus tard et se dit "WTF, ça veut dire quoi?". Dans ce cas, il est toujours utile que votre code communique immédiatement quelle était l'intention. Avec une sous-expression commune nommée correctement, c'est le cas.En outre, si à un moment quelconque dans l’avenir, vous décidez que, par exemple, vous devez changer
a+b
poura-b
, vous devez en changer un.emplacement, pas deux. Et il n’ya aucun risque que le second se trompe par accident.En ce qui concerne votre question, pourquoi devriez-vous optimiser, votre code devrait d’abord être correct . C'est la chose la plus importante. Un code qui n'est pas correct est un code incorrect, même si, malgré tout, il "fonctionne bien", ou du moins il semble que cela fonctionne bien. Après cela, le code devrait être lisible (lisible par quelqu'un qui ne le connaît pas).
En ce qui concerne l’optimisation ... il ne faut certainement pas délibérément écrire du code anti-optimisé, et je ne dis certainement pas que vous ne devriez pas penser au design avant de commencer (comme choisir le bon algorithme pour le problème, pas le moins efficace).
Mais pour la plupart des applications, la plupart du temps, les performances obtenues après l'exécution d'un code lisible et correct à l'aide d'un algorithme raisonnable via un compilateur d'optimisation sont correctes, il n'y a pas de quoi s'inquiéter.
Si tel est le cas contraire , à savoir si la performance de l'application ne fait satisfait pas aux exigences, et alors seulement , vous devriez vous soucier de faire de telles optimisations locales comme celle que vous avez essayé. De préférence, vous reconsidérerez l’algorithme de niveau supérieur. Si vous appelez une fonction 500 fois au lieu de 50 000 fois en raison d'un meilleur algorithme, cela aura un impact plus important que de sauver trois cycles d'horloge sur une micro-optimisation. Si vous ne décrochez pas plusieurs centaines de cycles sur un accès en mémoire aléatoire tout le temps, cela aura un impact plus important que de faire quelques calculs bon marché supplémentaires, etc.
L’optimisation est une question difficile (vous pouvez écrire des livres entiers à ce sujet sans fin) et consacrer du temps à optimiser aveuglément un endroit donné (sans même savoir si c’est le goulot d’étranglement du tout!) Est généralement du temps perdu. Sans profilage, il est très difficile d’optimiser l’optimisation.
Mais en règle générale, lorsque vous volez à l'aveugle et que vous avez juste besoin de / envie de faire quelque chose , ou en tant que stratégie par défaut générale, je suggérerais d'optimiser la "mémoire".
L’optimisation pour la «mémoire» (en particulier la localisation spatiale et les modèles d’accès) offre généralement un avantage, car contrairement à ce qu’il était une fois où tout était «à peu près pareil», l’accès à la RAM est de nos jours l’une des choses les plus coûteuses (à part la lecture sur disque!) que vous pouvez en principe faire. Tandis que ALU, au contraire, est bon marché et va de plus en plus vite chaque semaine. La bande passante mémoire et la latence ne s'améliorent pas aussi rapidement. Une bonne localisation et de bons schémas d'accès peuvent facilement faire une différence de 5x (20x dans les exemples extrêmes, extraites) au moment de l'exécution par rapport aux schémas d'accès incorrect des applications lourdes en données. Soyez gentil avec vos caches et vous serez une personne heureuse.
Pour mettre le paragraphe précédent en perspective, réfléchissez à ce que les différentes choses que vous pouvez faire vous coûtent. Exécuter quelque chose comme
a+b
prend (sinon optimisé sur) un ou deux cycles, mais le processeur peut généralement démarrer plusieurs instructions par cycle et peut générer des instructions non dépendantes de manière plus réaliste, ce qui ne vous coûte qu'environ un demi-cycle ou moins. Idéalement, si le compilateur est bon en planification, et en fonction de la situation, le coût pourrait être nul.Récupérer des données ("mémoire") vous coûte soit 4-5 cycles si vous êtes chanceux et c'est en L1, et environ 15 cycles si vous n'êtes pas aussi chanceux (L2 touché). Si les données ne sont pas du tout dans le cache, cela prend plusieurs centaines de cycles. Si votre modèle d'accès aléatoire dépasse les capacités du TLB (facile à faire avec seulement environ 50 entrées), ajoutez quelques centaines de cycles supplémentaires. Si votre modèle d'accès au hasard provoque en réalité une erreur de page, il vous en coûtera quelques dizaines de milliers de cycles dans le meilleur des cas et plusieurs millions dans le pire des cas.
Maintenant, réfléchis-y, quelle est la chose que tu veux éviter le plus d'urgence?
la source
Après avoir obtenu la fonctionnalité correcte en premier . La sélectivité concerne alors les micro-optimisations.
En tant que question d’entrevue concernant les optimisations, le code provoque la discussion habituelle mais manque l’objectif de niveau supérieur suivant: le code est-il fonctionnellement correct?
C ++ et C et d’autres considèrent le
int
débordement comme un problème dua + b
. Il n’est pas bien défini et C l’appelle comportement indéfini . Il n'est pas spécifié de "boucler" - même s'il s'agit du comportement courant.Une telle fonction appelée
IsSumInRange()
devrait être bien définie et fonctionner correctement pour toutes lesint
valeurs dea,b
. Le bruta + b
n'est pas. La solution AC pourrait utiliser:Le code ci - dessus pourrait être optimisé en utilisant un large type entier que
int
, le cas échéant, comme ci - dessous ou la distribution de lasum > N
, dessum < -N
tests au sein de laif (a >= 0)
logique. Cependant, de telles optimisations ne conduisent pas vraiment à un code émis "plus rapidement" avec un compilateur intelligent, ni à la maintenance supplémentaire d'être intelligent.Même utiliser
abs(sum)
est sujet aux problèmes quandsum == INT_MIN
.la source
De quel genre de compilateur parle-t-on et de quel type de "mémoire"? Parce que dans votre exemple, en supposant un optimiseur raisonnable, l'expression
a+b
doit généralement être stockée dans un registre (une forme de mémoire) avant d'effectuer une telle opération arithmétique.Donc, si nous parlons d’un compilateur stupide qui rencontre
a+b
deux fois, il va allouer plus de registres (mémoire) dans votre deuxième exemple, car votre premier exemple pourrait simplement stocker cette expression une fois dans un seul registre mappé à la variable locale, mais parlons de compilateurs très stupides à ce point ... à moins que vous travaillez avec un autre type de compilateur idiot que pile se répand chaque variable dans tous les sens, dans ce cas , peut - être le premier lui causerait plus de douleur à optimiser que la deuxième*.Tout cela est extrêmement spéculatif, de manière plutôt stupide, en l'absence de mesures / désassemblage, et même dans le pire des cas, il ne s'agit pas d'un cas "mémoire contre performance" (parce que même parmi les pires optimiseurs auxquels je puisse penser, nous ne parlons pas à propos de tout sauf de la mémoire temporaire comme pile / registre), c’est au mieux un cas de "performance", et parmi tout optimiseur raisonnable, les deux sont équivalents, et si l’on n’utilise pas d’optimiseur raisonnable, pourquoi est-il obsédé par l’optimisation mesures particulièrement absentes? Cela ressemble à la sélection d'instructions / attribution de registre au niveau de l'assemblage, ce que je ne m'attendrais pas à ce que quiconque cherche à rester productif le fasse en utilisant, par exemple, un interprète dont la pile déverse tout.
Quant à cette question, si je peux l’aborder plus largement, souvent, je ne trouve pas les deux diamétralement opposés. Surtout si vos modèles d'accès sont séquentiels, et compte tenu de la vitesse du cache de la CPU, une réduction de la quantité d'octets traités séquentiellement pour des entrées non triviales se traduit (jusqu'à un point) par un traitement plus rapide de ces données. Bien sûr, il existe des points de rupture dans lesquels, si les données sont beaucoup, beaucoup plus petites en échange de plusieurs instructions, il peut être plus rapide de traiter séquentiellement sous une forme plus grande en échange de moins d'instructions.
Mais j'ai constaté que de nombreux développeurs ont tendance à sous-estimer à quel point une réduction de l'utilisation de la mémoire dans ces types de cas peut se traduire par une réduction proportionnelle du temps passé à traiter. Il est très humainement intuitif de traduire les coûts de performance en instructions plutôt qu'en accès mémoire, au point d'atteindre de grandes tables de conversion (LUT), dans une tentative vaine d'accélérer de petits calculs, uniquement pour trouver des performances dégradées avec l'accès mémoire supplémentaire.
Pour les cas d’accès séquentiel à travers un très grand tableau (ne parlant pas de variables scalaires locales comme dans votre exemple), j’applique comme règle que moins de mémoire à parcourir séquentiellement se traduit par de meilleures performances, en particulier lorsque le code résultant est plus simple Jusqu'à ce que mes mesures et mon profileur me disent le contraire, et c'est important, de la même façon, je suppose que lire séquentiellement un fichier binaire plus petit sur disque serait plus rapide à parcourir qu'un fichier plus volumineux (même si le plus petit nécessite davantage d'instructions ), jusqu’à démontrer que cette hypothèse ne s’applique plus dans mes mesures.
la source