Deux excellents papiers (Programmer pour la performance, partie 1 et partie 2) de Romain Dolbeau sur un aspect mal compris, mal aimé et mal géré de la programmation : la performance.
Pour les adeptes de problèmes mathématiques dont je suis, vous aurez sans doute reconnu l’auteur de ces deux articles si vous vous intéressez aux nombres de Lychrel puisque Romain est l’actuel détenteur du record en la matière! Tous les détails de la quête du nombre 196 détaillés ici !
Leave a Comment » | 
informatique, optimisation, performance, programmation | Tagué: 196, Lychrel, mathématiques, nombre, optimisation, performance, Romain Dolbeau | 
Permalien
Publié par endormitoire
Ce blogue est un heureux mélange de mathématiques, d’informatique, d’optimizations, de programmation et d’algorithmes! Un autre des blogues que j’adore : Harder, Better, Faster, Stronger.
Leave a Comment » | algorithmes, informatique, mathématiques, optimisation, performance, programmation | Tagué: algorithmes, Better, Faster, Harder, informatique, mathématiques, optimisation, Stronger | Permalien
Publié par endormitoire
Vous désirez observer comment vos applications ou votre système réagiront lors d’un accroissement des charges sur le CPU, la mémoire ou vos disques? Rien de plus facile avec Linux puisque tout ce dont vous avez besoin est à portée de main!
Un article utile à toujours avoir en mémoire pour simuler des conditions d’utilisation réelles sans trop se casser la tête!
Leave a Comment » | informatique, Linux, optimisation, performance | Tagué: charges, CPU, disque, Linux, mémoire, simulation | Permalien
Publié par endormitoire
Quand MySQL se me à déraper, c’est habituellement l’oeuvre de quelques requêtes SQL problématiques. Un petit rappel pour vous aider à trouver la/les coupables!
Leave a Comment » | bases de données, informatique, MySQL, optimisation, SQL | Tagué: MySQL, optimisation, requêtes, SQL | Permalien
Publié par endormitoire
Le problème du voyageur de commerce est un des problèmes d’optimisation les plus étudiés autant en mathématiques qu’en informatique. Bon nombre de chercheurs ont travaillé sur ce problème complexe, en grande partie à cause de son énorme utilité dans le monde réel.
Une avancée récente (décrite ici) risque de relancer l’intérêt pour cet problème d’optimisation.
Pour les plus curieux, un site web incontournable traitant de ce problème.
Leave a Comment » | algorithmes, informatique, mathématiques, optimisation | Tagué: algorithmes, graphes, informatique, mathématiques, optimisation, Travelling Salesman Problem, TSP, voyageur de commerce | Permalien
Publié par endormitoire
Vous monitorez une instance MySQL, des comptes de dépenses, des accès à un serveur, etc ? Il existe des outils mathématiques pour vous faciliter la tâche et détecter les anomalies! Et ils sont expliqués dans l’article Services Monitoring with Probabilistic Fault Detection.
Leave a Comment » | algorithmes, informatique, mathématiques, optimisation, performance | Tagué: anomalies, détection, fault detection, Monitoring, probabiliste, probabilistic, services, surveillance | Permalien
Publié par endormitoire
Ça y est? J’ai toute votre attention? :)
Ces temps-ci je planche sur un problème relié à la performance de queues de messages (file d’attente de messages, file de messages, message queue). Heureusement, plutôt que d’avoir à expérimenter par essais et erreurs ou à simuler le système final, les mathématiques sont venues à la rescousse.
Deux articles hyper-utiles sur la performance des queues de messages : le premier ici et le second ici.
Et pour ceux que ça intéresse, il est également possible de télécharger gratuitement un document PDF sur le sujet ici.
Leave a Comment » | algorithmes, informatique, mathématiques, optimisation, performance, programmation | Tagué: file d'attente de messages, file de messages, mathématiques, message queue, performance, queue de messages | Permalien
Publié par endormitoire
How do you efficiently divide by 19? All you need is some compiler magic! It’s all explained here!
Leave a Comment » | algorithmes, informatique, mathématiques, optimisation, performance, programming | Tagué: 19, compiler, division, performance | Permalien
Publié par endormitoire
I’ve been dealing a lot with bit operations lately. And doing lots of benchmarking, like here. As I was looking for a bit count method in Pharo (it used to be there but it no longer exists in Pharo 5.0), I got curious about the many different versions of bit counting algorithms I could find on the internet.
What’s so special about bit operations you ask? Not much. Except when you have to do it really fast on 64bit integers! Like in a chess program! Millions of times per position. So instead of copying the #bitCount method that was in Squeak, I decided I’d have a look at what is available on the net…
So I decided to share what I found. This could potentially be useful for people who have to deal with bit counting a lot. Especially if you deal with 14 bits or less!
Here’s a typical run of the different bit counting algorithms I have tested on Squeak 5.1 64bit.
Number of [myBitCount1 (128 bits)] per second: 0.061M Number of [myBitCount1 (14 bits)] per second: 1.417M Number of [myBitCount1 (16 bits)] per second: 1.271M Number of [myBitCount1 (30 bits)] per second: 0.698M Number of [myBitCount1 (32 bits)] per second: 0.651M Number of [myBitCount1 (60 bits)] per second: 0.362M Number of [myBitCount1 (64 bits)] per second: 0.131M Number of [myBitCount1 (8 bits)] per second: 2.255M Number of [myBitCount2 (128 bits)] per second: 0.286M Number of [myBitCount2 (14 bits)] per second: 3.623M Number of [myBitCount2 (16 bits)] per second: 3.630M Number of [myBitCount2 (30 bits)] per second: 2.320M Number of [myBitCount2 (32 bits)] per second: 2.336M Number of [myBitCount2 (60 bits)] per second: 1.415M Number of [myBitCount2 (64 bits)] per second: 1.208M Number of [myBitCount2 (8 bits)] per second: 4.950M Number of [myBitCount3 (128 bits)] per second: 0.498M Number of [myBitCount3 (14 bits)] per second: 4.556M Number of [myBitCount3 (16 bits)] per second: 4.673M Number of [myBitCount3 (30 bits)] per second: 3.401M Number of [myBitCount3 (32 bits)] per second: 3.401M Number of [myBitCount3 (60 bits)] per second: 2.130M Number of [myBitCount3 (64 bits)] per second: 1.674M Number of [myBitCount3 (8 bits)] per second: 4.938M Number of [myBitCount4 (128 bits)] per second: 0.041M Number of [myBitCount4 (14 bits)] per second: 5.333M Number of [myBitCount4 (16 bits)] per second: 4.819M Number of [myBitCount4 (30 bits)] per second: 2.841M Number of [myBitCount4 (32 bits)] per second: 2.674M Number of [myBitCount4 (60 bits)] per second: 1.499M Number of [myBitCount4 (64 bits)] per second: 0.270M Number of [myBitCount4 (8 bits)] per second: 7.435M Number of [myBitCount5 (128 bits)] per second: 0.377M Number of [myBitCount5 (14 bits)] per second: 3.937M Number of [myBitCount5 (16 bits)] per second: 3.035M Number of [myBitCount5 (30 bits)] per second: 2.137M Number of [myBitCount5 (32 bits)] per second: 2.035M Number of [myBitCount5 (60 bits)] per second: 1.386M Number of [myBitCount5 (64 bits)] per second: 1.188M Number of [myBitCount5 (8 bits)] per second: 4.167M Number of [myBitCount6 (128 bits)] per second: 0.381M Number of [myBitCount6 (14 bits)] per second: 5.195M Number of [myBitCount6 (16 bits)] per second: 3.552M Number of [myBitCount6 (30 bits)] per second: 2.488M Number of [myBitCount6 (32 bits)] per second: 2.364M Number of [myBitCount6 (60 bits)] per second: 1.555M Number of [myBitCount6 (64 bits)] per second: 1.284M Number of [myBitCount6 (8 bits)] per second: 5.571M Number of [myPopCount14bit (14 bits)] per second: 18.349M Number of [myPopCount14bit (8 bits)] per second: 18.519M Number of [myPopCount24bit (14 bits)] per second: 7.407M Number of [myPopCount24bit (16 bits)] per second: 7.463M Number of [myPopCount24bit (8 bits)] per second: 7.018M Number of [myPopCount32bit (14 bits)] per second: 4.963M Number of [myPopCount32bit (16 bits)] per second: 5.013M Number of [myPopCount32bit (30 bits)] per second: 4.608M Number of [myPopCount32bit (32 bits)] per second: 4.619M Number of [myPopCount32bit (8 bits)] per second: 4.608M Number of [myPopCount64a (14 bits)] per second: 2.778M Number of [myPopCount64a (16 bits)] per second: 2.793M Number of [myPopCount64a (30 bits)] per second: 2.751M Number of [myPopCount64a (32 bits)] per second: 2.703M Number of [myPopCount64a (60 bits)] per second: 2.809M Number of [myPopCount64a (64 bits)] per second: 1.385M Number of [myPopCount64a (8 bits)] per second: 2.755M Number of [myPopCount64b (14 bits)] per second: 3.063M Number of [myPopCount64b (16 bits)] per second: 3.096M Number of [myPopCount64b (30 bits)] per second: 3.106M Number of [myPopCount64b (32 bits)] per second: 3.053M Number of [myPopCount64b (60 bits)] per second: 3.008M Number of [myPopCount64b (64 bits)] per second: 1.444M Number of [myPopCount64b (8 bits)] per second: 3.091M Number of [myPopCount64c (14 bits)] per second: 1.625M Number of [myPopCount64c (16 bits)] per second: 1.600M Number of [myPopCount64c (30 bits)] per second: 1.542M Number of [myPopCount64c (32 bits)] per second: 1.529M Number of [myPopCount64c (60 bits)] per second: 1.566M Number of [myPopCount64c (64 bits)] per second: 1.082M Number of [myPopCount64c (8 bits)] per second: 3.945M
Now, since method #myBitCount2 is similar to the #bitCount method in Squeak, that means there is still place for improvement as far as a faster #bitCount is needed. Now the question is : do we optimize it for the usual usage (SmallInteger), for 64bit integer or we use an algorithm that performs relatively well in most cases? Obviously, since I will always be working with 64bit positive integers, I have the luxury to pick a method that precisely works best in my specific case!
All test code I have used can be found here.
Note: Rush fans have probably noticed the reference in the title…
Leave a Comment » | optimisation, performance, Pharo, programming, Smalltalk, Squeak | Tagué: algorithms, bit count, bit counting, bit manipulation, bit operations, bitCount, integers, Pharo, Rush, Smalltalk, Squeak | Permalien
Publié par endormitoire
Often times, we take stuff for granted. But while preparing to embark on a crazy project (description in French here and Google translation in English here), I wanted to benchmark the bit manipulation operations in both Squeak and Pharo, for the 32bit and 64bit images (I am on Windows so the 64bit VM is not available for testing yet but it’ll come!). So essentially, it was just a test to compare the VM-Image-Environment combo!
To make a long story short, I was interested in testing the speed of 64bit operations on positive integers for my chess program. I quickly found some cases where LargePositiveInteger operations were more than 7-12 times slower than the SmallInteger equivalences and I became curious since it seemed like a lot. After more testing and discussions (both offline and online), someone suggested that some LargePositiveInteger operations could possibly be slow because they were not inlined in the JIT. It was then recommended that I override those methods in LargePositiveInteger (with primitives 34 to 37), thus shortcutting the default and slow methods in Integer (corresponding named primitives, primDigitBitAnd, primDigitBitOr, primDigitBitXor, primDigitBitShiftMagnitude in LargeIntegers module). I immediately got a 2-3x speedup for LargePositiveInteger but…
Things have obviously changed in the Squeak 64bit image since some original methods (in class Integer) like #bitAnd: and #bitOr: are way faster than the overrides (in class LargePositiveInteger )! Is it special code in the VM that checks for 32bit vs 64bit (more precisely, 30bit vs 60bit integers)? Is it in the LargeIntegers module?
Here are 2 typical runs for Squeak 5.1 32bit (by the way, Pharo 32bit image performs similarly) and Squeak 5.1 64bit images :
Squeak 5.1 32bit
Number of #allMask: per second: 7.637M Number of #anyMask: per second: 8.333M Number of #bitAnd: per second: 17.877M Number of #bitAnd2: per second: 42.105M Method #bitAnd2: seems to work properly! Overide of #bitAnd: in LargeInteger works! Number of #bitAt: per second: 12.075M Number of #bitAt:put: per second: 6.287M Number of #bitClear: per second: 6.737M Number of #bitInvert per second: 5.536M Number of #bitOr: per second: 15.764M Number of #bitOr2: per second: 34.409M Method #bitOr2: seems to work properly! Overide of #bitOr: in LargeInteger works! Method #bitShift2: (left & right shifts) seems to work properly! Overide of #bitShift: in LargeInteger works! Number of #bitXor: per second: 15.385M Number of #bitXor2: per second: 34.043M Method #bitXor2: seems to work properly! Overide of #bitXor: in LargeInteger works! Number of #highBit per second: 12.451M Number of #<< per second: 6.517M Number of #bitLeftShift2: per second: 8.399M Number of #lowBit per second: 10.702M Number of #noMask: per second: 7.064M Number of #>> per second: 7.323M Number of #bitRightShift2: per second: 29.358M
Squeak 5.1 64bit
Number of #allMask: per second: 36.782M Number of #anyMask: per second: 41.026M Number of #bitAnd: per second: 139.130M Number of #bitAnd2: per second: 57.143M Method #bitAnd2: seems to work properly! Overide of #bitAnd: in LargeInteger works! Number of #bitAt: per second: 23.358M Number of #bitAt:put: per second: 8.649M Number of #bitClear: per second: 38.554M Number of #bitInvert per second: 29.630M Number of #bitOr: per second: 139.130M Number of #bitOr2: per second: 58.182M Method #bitOr2: seems to work properly! Overide of #bitOr: in LargeInteger works! Method #bitShift2: (left & right shifts) seems to work properly! Overide of #bitShift: in LargeInteger works! Number of #bitXor: per second: 55.172M Number of #bitXor2: per second: 74.419M Method #bitXor2: seems to work properly! Overide of #bitXor: in LargeInteger works! Number of #highBit per second: 7.921M Number of #<< per second: 10.127M Number of #bitLeftShift2: per second: 12.800M Number of #lowBit per second: 6.823M Number of #noMask: per second: 39.024M Number of #>> per second: 23.188M Number of #bitRightShift2: per second: 56.140M
So now, I’m left with 2 questions :
If you’re curious/interested, the code I have used to test is here.
Leave me a comment (or email) if you have an explanation!
To be continued…
Leave a Comment » | Cog, informatique, Machine virtuelle, optimisation, performance, Pharo, programmation, programming, Smalltalk, Squeak, VM, Windows | Tagué: #bitAnd:, #bitOr:, #bitShift:, #bitXor:, 32bit, 64bit, bit, bit manipulation, bit operations, image, integer, LargeIntegers, LargePositiveInteger, module, named primitive, primDigitBitAnd, primDigitBitOr, primDigitBitShiftMagnitude, primDigitBitXor, primitive, SmallInteger | Permalien
Publié par endormitoire
Vous parcourez actuellement les archives de la catégorie optimisation.
