Affichage des articles dont le libellé est Optimisations. Afficher tous les articles
Affichage des articles dont le libellé est Optimisations. Afficher tous les articles

mardi 14 février 2012

dimanche 12 février 2012

Manipulation Big fichiers XML sur iPhone

Jim Dovey (alias @ AlanQuatermain) A mis au point ce qui ressemble à une solution d'énormes pour la manipulation de très gros fichiers XML sur l'iPhone. Jim testé avec un grand (22 Mo) du fichier XML. L'analyse du fichier avec NSXMLDocument pris environ 123 mégaoctets de mémoire virtuelle à analyser (je suppose que cela a été exécuté sur le simulateur car il n'y a aucun moyen que vous pourriez obtenir ce tas beaucoup plus affectés sur le téléphone lui-même).

Exécution exactement le même fichier à travers son propre analyseur utilisé seulement 70 kilo-octets de mémoire virtuelle. C'est une œuvre dramatique, de plusieurs ordre de grandeur de différence. Donc, si de gros fichiers XML sont le fléau de votre existence, vous voudrez peut-être vérifier sa solution en dehors.

Ajout d'Clang votre processus de construction

Frasier Spiers a une morceau astucieux, ce matin sur l'utilisation de Git pré-commit hooks pour exécuter automatiquement l'analyseur statique Clang. Je ne suis pas un utilisateur Git moi, mais je sais que beaucoup de gens sont, donc cela ressemble à bonne info pour ceux d'entre vous qui sont

Vitesse avec une prise

Il ya quelque temps, j'ai écrit un après sur les normales de surface dans OpenGL ES. Hier sur Twitter, il ya eu quelques discussions sur l'utilisation de la fonction racine carré inverse de Quake 3 pour accélérer les performances des applications iPhone OpenGL ES. Voici ce que cette méthode ressemble (convertis en utilisant GL et iPhone types de données):

static inline GLfloat InvSqrt(GLfloat x)
{
GLfloat xhalf = 0.5f * x;
int i = *(int*)&x; // store floating-point bits in integer
i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
x = *(GLfloat*)&i; // convert new bits into float
x = x*(1.5f - xhalf*x*x); // One round of Newton's method
return x;
}

La racine carrée inverse peut être utilisé de plusieurs façons. Noel Llopis des Snappy tactile souligné deux utilisations pour elle sur Twitter hier: le calcul des normales et faisant sphériques mappage de texture UV. Je suis encore en train d'envelopper ma tête dans le Texture Mapping UV, mais je comprends assez bien les normales à ce stade, donc je si j'avais voir quel genre de gains de performance je pourrais obtenir en utilisant cette optimisation vieux. Il ya toutes sortes d'arguments autour de la intertubes savoir si cette fonction donne encore des gains de performance, mais il ya un moyen facile de le savoir: c'est l'utilisation et de mesurer avec Shark.

J'ai utilisé mon Chargeur Wavefront OBJ comme un test, et profilée du chargement de la plus complexe des trois objets - l'avion. La première manche a été avec mon code original, qui bêtement1 sqrt utilisés (). J'ai ensuite re-couru à l'aide sqrtf (), puis à nouveau en utilisant l'InvSqrt Quake3D () la fonction ci-dessus.

Les résultats sont impressionnants, et vous avez certainement do obtenir une augmentation des performances de l'utilisation de cette fonction vieux de dix ans sur l'iPhone. InvSqrt aide () a donné une diminution de 15% du temps passé à calculer les normales de surface sur l'aide sqrtf () et une diminution de 40% par rapport à calculer avec sqrt (). Ce n'est pas une somme à dédaigner, surtout dans les situations où vous avez besoin de calculer les normales sur le temps de voler de nombreux seconde.

Maintenant, si vous vous souvenez, c'était comment nous avons calculé les normales en utilisant la fonction racine carrée de math.h:

static inline GLfloat Vector3DMagnitude(Vector3D vector)
{
return sqrt((vector.x * vector.x) + (vector.y * vector.y) + (vector.z * vector.z));
}

static inline void Vector3DNormalize(Vector3D *vector)
{
GLfloat vecMag = Vector3DMagnitude(*vector);
if ( vecMag == 0.0 )
{
vector->x = 1.0;
vector->y = 0.0;
vector->z = 0.0;
}

vector->x /= vecMag;
vector->y /= vecMag;
vector->z /= vecMag;
}

Alors ... comment peut-on modifier cette option pour utiliser la racine carrée inverse? Eh bien, la racine carrée inverse d'un nombre est simplement une divisé par la racine carrée de ce nombre. En Vector3DNormalize (), on divise chacune des composantes du vecteur (x, y et z) par la grandeur du vecteur, qui est calculée en utilisant la racine carrée. Depuis divisant une valeur par un nombre est le même que la multiplication par 1 divisé par ce même nombre, donc, nous pouvons simplement multiplier chaque composante par l'ampleur inverses au lieu, comme ceci:

static inline GLfloat Vector3DFastInverseMagnitude(Vector3D vector)
{
return InvSqrt((vector.x * vector.x) + (vector.y * vector.y) + (vector.z * vector.z));
}

static inline void Vector3DFastNormalize(Vector3D *vector)
{
GLfloat vecInverseMag = Vector3DFastInverseMagnitude(*vector);
if (vecInverseMag == 0.0)
{
vector->x = 1.0;
vector->y = 0.0;
vector->z = 0.0;
}

vector->x *= vecInverseMag;
vector->y *= vecInverseMag;
vector->z *= vecInverseMag;
}


Doux, non? Si nous utilisons maintenant Vector3DFastNormalize () au lieu de Vector3DNormalize (), et chaque appel sera d'environ 15% plus rapide sur les générations actuelles de l'iPhone et l'iPod Touch par rapport à l'utilisation du haut-fonction racine carrée.

Mais ... il ya un hic. En fait, deux prises.

Les captures


La première prise est que cette optimisation ne fonctionne pas plus rapidement sur tout le matériel. En fait, sur certains matériels, il est mesurable lent que l'utilisation sqrtf (). Cela signifie que vous êtes de jeu que le matériel futures profiteront également de cette optimisation mêmes. Pas une affaire énorme et très probablement une valeur sûre, mais vous devriez en être conscient et être prêt à revenir rapidement qu'Apple devrait sortir un nouvelle génération d'iPhones et d'iPod Touch qui utilisent un processeur différent.

Le deuxième cran, et beaucoup plus important est les ramifications juridiques possibles de l'utilisation de ce code. Vous voyez, Id publié le code source Quake3D en vertu de la Licence publique générale GNU, qui est une licence virale. Si vous utilisez le code source à partir d'un projet GPL, vous devez ouvrir la source de votre projet dans son ensemble sous la licence GPL ainsi. Maintenant, c'est une simplification excessive, et il ya des façons de contourner la GPL, mais en règle générale, si vous utilisez du code sous GPL, vous devez rendre votre code GPL également.

Mais, les eaux sont un peu sombres. John Carmack a admis qu'il n'a pas écrit cette fonction, et ne pense pas que les autres programmeurs à Id ne soit. L'auteur réel de ce code est inconnu. Certains des contributeurs à la fonction ont été trouvés, mais pas l'auteur original. Cela signifie que le code pourrait être dans le domaine public. Si c'est le cas, son inclusion dans une application GPL ne pas sortir du domaine public.

Ainsi, la ligne du bas: est-il sûr? Probablement. Cette fonction est largement connu et largement utilisé et il n'y a eu aucune indication que tout propriétaire possible des droits a tout intérêt à poursuivre de toute utilisation de cette fonction. Y at-il des garanties? Nope.

Ma recommandation est de l'utiliser, mais assurez-vous que chaque endroit que vous l'utilisez, ont une méthode de sauvegarde que vous pouvez repli sur si vous avez besoin. Si vous voulez une certaine assurance, vous pourriez essayer de contacter Id juridiques et d'obtenir une dispense d'utiliser cette fonction. Je ne sais pas si ils vont répondre, ou si ils vont lui accorder, mais les gens de chez Id m'ont toujours frappé comme de bonnes personnes, de sorte qu'il pourrait être utile à une enquête si vous êtes une aversion au risque.

1 - sqrt () est une fonction en double précision. Depuis OpenGL ES ne supporte pas le type de données GLDouble, ce qui signifie que je faisais le calcul sur les bits deux fois plus nombreux que nécessaire, et en convertissant en arrière du simple au double précision, puis revenir.

samedi 4 février 2012

C + + et de performance

Voici un blog intéressant sur l'utilisation ObjC + + pour améliorer les performances dans les applications iPhone. J'ai peut-être dans une minorité à ce sujet, mais je n'ai jamais été un grand fan de l'Objective-C + +. Pourquoi vous chevauchent les limites de deux langues?

D'accord, c'est une simplification excessive, il ya des moments où l'Objective-C + + est un excellent choix, surtout quand vous écrivez la version Mac ou un iPhone d'une application qui s'exécute sur des plateformes multiples. Il ne serait pas cependant être la première option qui bondit sur mon esprit comme un outil pour l'optimisation d'une application iPhone peu performants. Bien que C + + ne certaines choses, comme un message de répartition, plus rapide (enfin, techniquement, c'est un "lookup vtable" sur C + +, pas un envoi de message), il encourt encore quelques généraux pour les choses ainsi, il me semble, aucune optimisation en C + + va laisser une certaine marge d'amélioration. N'importe quelle manière vous le coupez, cependant, il ya certainement quelque chose de vraiment précieux dans ce blogue en termes de codage iPhone et de performance, alors allez le lire.

Je suis dans le milieu de ré-écriture du code de dessin pour mon moteur de particules pour être plus rapide et je suis face à certains des mêmes problèmes de cette entretiens blog sur, cependant, j'ai choisi un peu différent, option plus vieille école de mes optimisations : statique inline fonctions C et des structures pour les trucs vraiment sensibles au temps, et droites Objective-C pour tout ce qui n'est pas sensible au temps. Bien sûr, il peut être une douleur à déboguer, mais je ne déplacer le code dans une fonction inline statique après que j'ai eu il fonctionne dans un mode régulier ou la fonction première. J'utilise les structs pour éviter la surcharge de création d'objets sur des choses comme les particules, qui, il y aura beaucoup d'.

Jusqu'ici, il semble être un bon choix - j'ai eu une 2000 particules par seconde avec un générateur de 12 secondes la durée de vie des particules en utilisant le rendu GL_POINT tourne à 20 images par seconde sur un iPhone de première génération, sans beaucoup plus sensible à sauter, qui est une énorme amélioration sur ma première version, qui ignorées, même avec quelques centaines de particules par seconde. J'espère que je vois des améliorations similaires dans d'autres types de rendu quand j'ai fini d'écrire ces ré-.

vendredi 27 janvier 2012

iPhone «optimisé» PNG

Pour la plupart, de la documentation développeur d'Apple pour Mac et iPhone est excellente. Ils sont bien écrits, précis et fournir des exemples de code excellente. Il ya, bien sûr, toujours des lacunes, en particulier avec les nouveaux domaines. Parfois, ces écarts sont simplement une question de contraintes de ressources, le volume de la documentation les équipes doivent maintenir la documentation est stupéfiante, et les cadres sont constamment ajoutés et mis à jour.

D'autres fois, Apple est peu loquace à propos de choses non pas parce que des contraintes de ressources, mais plutôt intentionnellement, si ce n'est pas toujours bien pourquoi. Voulez-vous savoir à quelle vitesse le processeur de votre iPhone est, ou combien de mémoire est disponible à votre demande? Ces deux sont évidemment pertinentes pour le développement pour l'iPhone, mais ne regardez pas à Apple pour cette information. L'information est disponible (processor | memory), Mais pas par Apple.

Voici un autre domaine où Apple est moins bien paraître: Quand il s'agit d'utiliser l'iPhone d'images PNG, Apple vous dit que Xcode "optimise" PNG dans le cadre du processus de construction et, par conséquent, vous devriez toujours utiliser des images PNG dans vos projets iPhone. Les images PNG sont généralement plus grandes que les fichiers JPEG, ce qui provoque votre application soit un peu plus grand, mais vous serez récompensé par une sorte mystérieuse de l'amélioration.

Puisque cette information n'est pas documentée, ce qui suit est quelque chose d'une supposition éclairée basée sur la recherche et des observations. Je serai heureux de corriger sur toute inexactitude, alors n'hésitez pas à me ping si vous voyez quelque chose de mal.

Donc, juste quelle est cette magie, le mystère «optimisation»?



Pendant la construction, Xcode essentiellement vis de votre image PNG, le transformant en quelque chose qui techniquement n'est plus une image PNG. Xcode ne modifie pas votre fichier original, mais quand il le copie dans le dossier Resources de votre paquet de demande, ce qu'il fait est qu'il byte-échange les octets en rouge et bleu et aussi "premultiplies l'alpha" (si cela ne fait pas sens, ne vous inquiétez pas, nous en parlerons dans un instant). L' PNG spécifications ne supporte pas non plus de ces changements, ce qui explique pourquoi l'image n'est plus techniquement un PNG et ne peut pas être chargé par la plupart des logiciels de retouche d'image. Non pas que ce qui importe vraiment, puisque la nouvelle version existe seulement à l'intérieur de votre paquet d'application, mais cela signifie que tout fichier PNG que vous incluez dans votre bundle soft ne devrait pas être, par exemple, FTPed ou par courriel à partir de votre application directement, parce que le fichier sera corrompu dans la mesure où la plupart des logiciels sont concernés.

Échange d'octets


Byte swap est exactement ce que cela ressemble. Images de synthèse non compressé graphiques sont les plus souvent stockés en séquences de trois ou quatre octets, ou "octets" représentant chaque pixel de l'image. Chaque octet dans le pixel représente l'une des trois couleurs primaires additives (rouge, bleu et vert), plus il ya souvent un autre octet appelé «alpha», que nous allons examiner dans un instant. Il ya d'autres manières de stocker des images, mais c'est la technique la plus courante. Le plus commun des octets de commande utilisés dans cette technique est RVB (ou RGBA) qui signifie rouge-vert-bleu (-alpha). Cela signifie qu'un pixel est représenté en mémoire par quatre octets, le premier représentant de l'intensité du rouge, la seconde représentant l'intensité du vert, et le troisième représentant l'intensité du bleu (nous ignorerons alpha pour l'instant). La spécification PNG utilise cet octet de commandes, comme le font de nombreux formats d'image.

Cependant, la mémoire vidéo de l'iPhone utilise un octet de commande non-standard de BGR ou bleu-vert-rouge (je ne crois pas qu'il ya une composante alpha dans VRAM de l'iPhone). Pour copier à partir d'une image en mémoire en utilisant RGBA à la mémoire vidéo en utilisant la BSG est plus coûteux que de simples calculs à partir de copier, par exemple, BGR BGR, qui peut être fait avec un seul, déplacer de la mémoire rapide (ou «blit») opération. En faisant cela, byte-swap dans la copie de fichiers Phase de construction, votre demande est (dans certaines situations) capable d'ignorer la composante alpha lors du chargement du fichier dans la mémoire de sorte qu'il peut utiliser l'opération mémoire plus rapide déplacer pour obtenir l'image dans la mémoire vidéo ( et donc sur l'écran).

Alpha prémultipliées


Okay, c'est logique, mais que dire de ce "multipliant à gauche de l'alpha" chose? Que l'on sorte de sons mystérieux, n'est-ce pas? Comme mentionné dans la section précédente, VRAM de l'iPhone n'a pas de composante alpha, donc si nous allons à ignorer cette composante, nous avons encore besoin de le prendre en compte une certaine manière. Rappelez-vous que les images PNG qui ont été optimisés pour l'iPhone sont stockées sous forme de quatre valeurs, représentant le Bleu, Vert, Rouge, et des composants Alpha (dans cet ordre). Bien qu'il soit appelé un "composant", Alpha n'est pas vraiment une composante de couleur du tout. C'est plus comme un modificateur qui agit sur les trois autres valeurs, et elle représente la quantité de tout ce qui est sous la couleur va montrer à travers. Ainsi, une couleur qui ressemble à ceci:

B:1.0
G:0.0
R:0.0
A:0.5

Représenterait la couleur bleue, mais avec une opacité de 50%. Pour que l'ordinateur pour utiliser le composant alpha, il doit multiplier les temps de l'alpha des trois autres composantes (et éventuellement par d'autres valeurs) avant de les mettre en mémoire vidéo. Ce processus de multiplication est plus coûteux en calcul de simplement copier la valeur dans la mémoire vidéo. Ainsi, Xcode premultiplies aussi l'alpha par les trois composantes et stocke la valeur multipliée. En conséquence, la couleur ci-dessus ressemblerait à ceci après que les fichiers de copie Phase de construction:

B:0.5
G:0.0
R:0.0
A:0.5

Notez que la composante bleue dans ce nouveau pixel est égale à la composante bleue de la version précédente, multiplié par l'alpha. Le résultat de cette prémultiplication, est que la composante alpha peut être ignoré lors du chargement de l'image dans la mémoire et l'image peut alors être placés directement sur la mémoire vidéo sans avoir à faire de coûteuses en virgule flottante multiplications pour calculer l'alpha. Eh bien, au moins, parfois. Ce pixel est ce que le pixel ressemblerait quand il est dessiné sur fond blanc.

Alors, qu'advient-il si il ya une couleur sous qui doit montrer à travers? C'est là que les choses peuvent devenir un peu déroutant. Si votre demande est le dessin de l'image sur le dessus de quelque chose d'autre, ou si vous êtes en utilisant le canal alpha dans l'image comme un masque, puis l'iPhone ne peut pas utiliser cette optimisation. Il a pour faire les calculs alpha (c'est pourquoi le canal alpha est laissé intact dans la multiplication de pré-traitement), le byte-swapping l'offre encore quelques améliorations. Pour la plupart, vous ne devez pas vous inquiéter à ce sujet - tout se passe sous le capot. La seule chose que vous devriez prendre loin de lui cependant, c'est que vous pouvez aider votre iPhone savoir quand il est sécuritaire d'utiliser l'optimisation. La façon de faire est de vous assurer que vous cochez la case "opaque" case à cocher dans Interface Builder pour votre point de vue image, ou d'autres vues qui contiennent des images, ou définir la propriété opaques de votre UIImageView à YES dans le code. Ceci indique l'iPhone qu'il est sécuritaire d'effectuer l'opération plus rapide blit et ignorer le canal alpha parce que rien ci-dessous montre à travers un objet opaque et il n'y a aucun besoin de faire des calculs flottants onéreux Point Alpha pour cet objet. Bien sûr, si vous utilisez le canal alpha de votre image, ou si vous faites des compositions d'images complexes dans votre application à l'exécution, vous ne devriez pas faire le point de vue opaque. Mais, si vous êtes simplement l'affichage d'une image dans une UIImageView, en vérifiant que la case opaque est une idée vraiment, vraiment bon.

Énormément de temps, des images PNG ont 1,0 pour la valeur alpha dans chaque pixel. En conséquence, plus souvent qu'autrement, le programme fonctionne plus rapidement et utiliser moins de mémoire à cause de la PNG "optimisations" fait par Xcode.

Qu'advient-il lorsque vous utilisez différents types de fichiers


Lorsque vous utilisez un autre type de fichier (ou si vous chargez un fichier non optimisés PNG), votre iPhone doit faire le byte-swapping et prémultiplication alpha à la charge en temps (et éventuellement refaire la multiplication alpha à l'affichage en temps). Votre demande a essentiellement pour faire le même traitement que Xcode fait, mais c'est de le faire au moment de l'exécution au lieu de construire des temps. Cela va vous coûter tant en termes de cycles de processeur et de mémoire supplémentaire. Une des raisons pour lesquelles Safari Mobile est le plus gros du porc de la mémoire de l'intégré dans les applications iPhone c'est parce que les images qu'il a à charge pour l'affichage des pages web sont toutes les images non optimisés, pour la plupart des fichiers JPEG. Depuis JPEG est un format compressé, il a ajouté l'étape supplémentaire d'avoir à décompresser l'image dans la mémoire avant de pouvoir faire le prémultiplication et byte-swapping.

lundi 23 janvier 2012

Le Root of All Evil: Introduction à l'optimisation de l'Objective C

Donald Knuth a une citation très célèbre: «[P] Optimisation remature est la racine de tout mal"1. C'est une idée valable de garder dans votre tête tout en programmation. C'est en fait correct d'écrire du code inefficace à la fois. Dans le contexte de l'Objective-C, cela signifie que c'est correct d'utiliser des méthodes fournies et les objets de votre premier passage au algorithmes par écrit, même si vous savez que ces objets ou de méthodes pourraient ne pas être la meilleure façon de faire la tâche en termes de performances. Obtenir le code de travail, et le faire fonctionner à droite, puis revenez en arrière et d'optimiser intelligemment là où il sensé. Dans de nombreux endroits inefficacités petits n'auront aucun impact notable sur votre application, et en s'appuyant sur le code bien testé à partir de cacao qui a été écrit par Apple informés et ingénieurs Ensuite, vous vous probablement sauvé beaucoup de temps et des maux de tête d'entretien.

Mais, il ya des moments où le code inefficace a un impact et doit être abordée. En Java, Visual Basic, Ruby, et l'autre langages de haut niveau, il ya beaucoup à faire pour optimiser votre code, mais il ya une limite à ce que vous pouvez faire parce que ces langues vous isoler du fonctionnement interne à l'aide de mécanismes tels que collecte des ordures, Et une grande partie du code qui s'exécute lorsque vous exécutez votre code est complètement en dehors de votre contrôle. Dans toutes ces langues, vous pouvez contribuer à l'exécution savoir quand il est correct de libérer de la mémoire que vous avez fini avec elle en suivant de bonnes pratiques de codage, mais la gestion de la mémoire est surtout hors de vos mains. D'autres optimisations comme le déroulement de boucle peut être utilisée dans ces langues, mais le rendement de performance tend à être inférieur à des optimisations même dans un langage de bas niveau compilées directement en code machine.

Voici où Objective-C a vraiment une longueur d'avance. C'est un langage de haut niveau et a beaucoup en commun avec Java, VB, Et C#. Il a collecte des ordures (enfin, pas sur l'iPhone, pas encore) et la gestion des exceptions et il vous protège de nombreux détails d'implémentation de bas niveau comme un bon langage de haut niveau devrait. Mais, Objective-C est un ensemble super- C, Et même si elle a un petit moteur d'exécution pour activer la messagerie objet et d'autres fonctionnalités, la plupart de votre code se compile vers le langage machine. Vous êtes à l'abri des détails d'implémentation de bas niveau, mais pas empêchés d'obtenir pour eux. Lorsque vous avez épuisé vos options pour optimiser l'aide Objective-C et Cocoa, vous avez toujours la possibilité de lever le capot et l'utilisation de bons vieux C procédurales afin d'optimiser encore plus. Un grand Objective-C programmeur doit être d'au moins un bon programmeur C.

Jetons un oeil à un exemple d'optimisation d'un petit morceau de code Objective-C.

Disons que nous avons une NSData qui contient des données binaires codées stockées sous forme de caractères 8-bit ASCII. Dans ces données encodées, nous avons besoin de chercher certaines séquences de caractères pour s'assurer qu'il contient le type de données qu'il est censé le faire. Ces tags sont des séquences simples de caractères ASCII (alias C-cordes).

Voici ma première, la version écrite rapidement profit objets intégrés cacao. Ceci a été écrit dans le cadre d'une catégorie sur NSData, De sorte que toute référence à self est une référence à la NSData objet contenant les données binaires codées.

Je m'excuse pour le formatage du code. Blogger ne coopère pas et refuse de me croire quand je lui dis que mon code est préformaté en utilisant les pre tag.

L'original, horriblement non-Version optimisée




-(BOOL)containsCString:(char *)cmp
{
NSUInteger offset = 0;
char * byte;
const char * bytes = [self bytes];

while (offset {
byte = (char *)bytes ;
NSString * checkString = [NSString stringWithCString:byte length:strlen(cmp)];
if ([checkString isEqualToString:[NSString stringWithCString:cmp length:strlen(cmp)]])
return YES;

offset++;
}
return NO;
}

Dois-je le laisser comme un exercice pour l'étudiant d'identifier exactement pourquoi ce code est pauvre du point de vue d'optimisation? Je ferais mieux de ne pas, si les problèmes sont susceptibles évident pour beaucoup d'entre vous.

Tout d'abord, je suis l'allocation des objets autoreleased l'intérieur d'une boucle. Et cette boucle va octet par octet à travers un morceau potentiellement important de données. Aucun de la mémoire de ces objets seront libérés jusqu'à la fin de la passe de courant à travers la boucle courir, ce qui n'arrivera pas qu'après ma termine la boucle. J'ai créer deux autoreleased NSString cas pour chaque octet dans les données et ensuite exécuter une chaîne de comparer entre eux. NSString est un cluster de classe complexe, conçu pour faire face à une multitude d'encodages chaîne, et pourrait potentiellement être à l'aide caractères multi-octets pour représenter ces chaînes, ce qui signifie que chaque comparez pourrait être la comparaison de deux ou même trois octets plutôt qu'une seule. Maintenant, le NSString grappes de classe est intelligent et ne sera probablement pas l'utilisation multi-octets encodage à moins qu'il doit, mais depuis ce n'est pas notre code et les algorithmes ne sont pas documentées, nous ne pouvons pas savoir avec certitude ce qu'il va faire, et il est possible que quelque chose dans nos données pourraient déclencher l'utilisation de l'encodage multi-octets

Ainsi, fondamentalement, je suis d'être très, très inefficace à la fois avec la mémoire et la puissance de traitement ici. Cela peut ne pas être importante, selon la façon dont j'utilise dans mon application, et cette version ne m'a fallu que quelques minutes pour écrire, donc si je fais cela que rarement et les blocs de données codées sont petites, peut-être ce qui se passe d'être bien juste la façon dont il est. Mais il ya le potentiel pour des problèmes réels avec ce code dans une application.

Une façon de savoir si ça va être un vrai problème est de mettre en place des tests unitaires (vous utilisez des tests unitaires, non?) Qui utilisent des situations représentatives similaire à ce que le code sera confrontée à l'application effective.

Pour sourires et fous rires, nous allons exécuter mes tests unitaires sur cette méthode, qui prend deux à trois morceaux mégaoctet de données codées - celui qui contient les balises d'être recherché et qui n'a pas - et faire deux recherches sur les deux morceaux. Le résultat? 6,8 secondes à faire les deux recherches sur chacun des deux morceaux de trois mégaoctets qu'il fonctionne sur 2.6GHz aa MacBook Pro. C'est définitivement un potentiel Beachball Filature de la Mort situation. Je suppose que nous ferions mieux de chercher à optimiser, hein?

Notez que la quantité de temps qu'il faut pour exécuter ce code dépendra d'un certain nombre de facteurs, et il ne sera pas le même à chaque fois, mais il ne variait que de quelques millisecondes sur une douzaine de pistes, donc je suis assez confiant il est l'algorithme qui est lent et pas autre chose fonctionnant à la fois2.

Optimisation d'abord

La première optimisation et la plus évidente ici devient l'affectation chaîne de comparaison hors de la boucle. Cette valeur ne change pas du tout pendant la boucle, nous allons donc passer à la déclaration avant que tout se passe de telle sorte que seulement une fois par appel à cette méthode. En théorie, qui devrait considérablement réduire les frais généraux de la mémoire et probablement de réduire le temps de traitement de manière significative. Voici la nouvelle version:

-(BOOL)containsCString:(char *)cmp
{
NSUInteger offset = 0;
char * byte;
const char * bytes = [self bytes];
NSString *compareString = [NSString stringWithCString:cmp length:strlen(cmp)];
while (offset {
byte = (char *)bytes ;
NSString * checkString = [NSString stringWithCString:byte length:strlen(cmp)];
if ([checkString isEqualToString:compareString])
return YES;

offset++;
}
return NO;
}

Lançons le test unitaire et voir ce qui se passe. Et le résultat? Cette fois-ci s'exécute dans un peu plus vite, pointant à 3,7 secondes. Une amélioration significative, mais pas assez vite pour éviter que les ballons de plage filer. Peut-être que je vais avoir à frayer les discussions. Je vais faire cet encodage beaucoup dans ma demande.

Alors, est-il un moyen que je peux améliorer cela davantage? Est-il possible pour moi d'éviter autoreleasing tant NSStrings, ou même les créer à tout? Eh bien, il ya un couple d'options. Je ne pouvais allouer manuellement et de libérer les objets chaîne. Ce serait beaucoup plus efficace que de remplir la piscine autorelease, en théorie.

La seconde optimisation

Voici ce que nous obtenons si nous allouer manuellement et la libération de nos instances NSString plutôt que de les laisser aller dans la piscine autorelease. Cela devrait aider avec nos frais généraux de la mémoire, mais on ignore combien d'une augmentation de vitesse, il va nous donner:


-(BOOL)containsCString:(char *)cmp
{
NSUInteger offset = 0;
char * byte;
const char * bytes = [self bytes];
NSString *compareString = [NSString stringWithCString:cmp length:strlen(cmp)];
while (offset {
byte = (char *)bytes ;
NSString *checkString = [[NSString alloc] initWithCString:byte length:strlen(cmp)];
if ([checkString isEqualToString:compareString])
return YES;
[checkString release];
offset++;
}
return NO;
}
Nous l'exécuter et? 3,44 secondes. Hm .. Une amélioration, mais pas un énorme par tout moyen. Il semble que la création de chaînes est un de nos blocages. Dans une méthode plus complexe, nous aurions probablement de recourir à l'aide de requin ou instruments permettant d'identifier les goulots d'étranglement ont été où notre, mais dans ce cas, c'est assez évident, où est le problème.

Donc, nous allons essayer de faire cela en droites C. Après tout, nous sommes simplement comparer des morceaux de mémoire. C peut faire ça, et il peut le faire rapidement sans la surcharge d'objets ou d'encodages de chaîne ou toute autre chose.

L'optimisation finale

Au lieu de cela, oublions l'aide NSString or NSMutableString, Et il suffit d'utiliser C. Nous allons travailler avec des pointeurs, et d'utiliser certaines techniques de la vieille école pour comparer les tampons.



-(BOOL)containsCString:(const char *)cmp
{
NSUInteger offset = 0;
const unsigned char * bytes = [self bytes];

while (offset {
if (memcmp(bytes++, cmp, strlen(cmp))==0)
return YES;

offset++;
}
return NO;
}

Cette version ne crée pas de nouveaux objets Objective-C, il utilise tout simplement une fonction C qui se compare à des morceaux de mémoire. Maintenant il n'ya pas de surcharge due à des objets, et aucune raison d'encodages de chaîne ou de conversions.

Alors, combien est-ce plus rapide? Lançons notre test unitaire et le découvrir. Comment environ 0,4 secondes? Pas terrible du tout pour faire une recherche d'octet par octet à 12 Mo de données, surtout quand la moitié des données qu'elle avait pour la recherche ne contient pas la chose qu'il cherchait.

Pensées finales


Nous pourrions aller plus loin. Il ya des optimisations que nous pouvions faire à ce qui consument plusieurs millisecondes plus, et si notre code nécessaire au traitement d'énormes blocs de données, qui serait probablement utile d'examiner (et peut-être une bonne idée pour une future affectation), mais pour ma fins, j'ai décidé que ce n'est une bonne performance suffisant pour mes besoins. Le point de cet article n'était pas vraiment pour vous enseigner la façon d'optimiser votre code, et n'est certainement pas de vous montrer la mise en œuvre plus rapide possible de cet algorithme, mais je voulais faire passer le point que l'Objective-C est C, et que, beau que tous les bienfaits orienté objet est, il ya des moments où il est logique de retrousser vos manches et de faire l'école de vieilles choses, une option que la plupart des langages de haut niveau ne proposent pas, mais l'Objective-C ne. Je voulais aussi vous de voir quelques-uns des types d'erreurs assez commun que vous voyez souvent dans les langages de haut niveau qui provoquent ballonnements et les goulets d'étranglement de mémoire afin que vous serez moins susceptible de les faire dans l'avenir.

Les timings dans cet article ont toutes été faites en utilisant la cible de débogage. L'optimisation finale chuté à 0,1 secondes en passant à la cible de presse, et j'ai été capable de le laisser tomber encore plus bas en mettant en œuvre un itérateur inverse pour la balise de fin.


1 - Programmation structurée avec de passer aux déclarations, Enquêtes ACM Computing Journal, vol 6, no 4, décembre 1974. p.268
2 - Il le fait, en effet, utile de savoir que j'ai intentionnellement écrit cet inefficacement.