Le monitoring et la détection probabiliste

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.

La performance de votre queue

Ç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.

Compiler magic

How do you efficiently divide by 19? All you need is some compiler magic!  It’s all explained here!

1001001 SOS

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…

Bits and Pieces

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 :

1. Why exactly does the override work (in 32bit images)?
2. What changed so that things are different in Squeak 5.1 64bit image (overrides partially work)?

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…

Freewill in progress (2)

(Click to enlarge)

What’s up?

As you can see, Freewill now supports 17 different selection policies.  At this point, all of them are coded but only half of them have been tested.

The 11 available termination policies are coded, half of them tested.

So far, only 2 mutation policies are available.  Both of them are coded and tested. I will probably need a few extras for TSP type of problems as well as numerically parametrized problems (e.g. De Jong functions with a domain for each variable).  I’ll probably add 3-4 other ones specific to the problem that started all this adventure!

Only one immigration policy (no immigration!) is available and it will stay that way for a long time.  I’ll wait until I am hyper confident that this framework is rock solid before introducing parallelism and exchange of individuals between « islands » (i.e. simulations).  This one is a faaaaaaar away!

Six crossover policies are available as of now .  This area will require some (minor I think at first glance) changes for the TSP type of problems : not quite decided on the approach I will take to solve this.  Since crossover is often very problem/chromosome specific, I’ll probably delay those change until the end, once I have all examples coded and ready to be tested to have a better idea of what is needed.  But I will definitely add a few (3-4) crossover policies tailored for the Ruzzle problem.

I have solved the discrepancy (see here and here) between my results and the TSPLIB ones regarding the tour length of the Burma14 problem.  Will probably add a lot bigger TSP problem to see how the framework can handle an extremely huge search space! Oh!  And I need to clean up all the crap I added/modified while looking for the problem of « distance difference » : 2 classes were butchered in the process!

I need to add a few « crash test dummy » classes to test all those different selection policies (and crossover) in a simpler and more efficient manner!  Or I should kick myself in the %*&#$!@ and code the « bits » example classes…

I will soon work on a customizable display of statistics.  All that’s needed is already there, it’s just a matter of gluing everything together!

Once I’m done with the 8 queens problems, I’ll attack the numerically parametrized problems.  Will probably have 2-3 examples (from De Jong functions) as well as the INSANE Griewank function.

The classes used for randomly choosing the next parent chromosomes as well as scaling/ranking can be optimized.  But since they just work great since day 1, I’ll keep that for the very end.  But I know they can be a lot faster than what they are right now.

I also plan on having a very basic export mechanism so I can dump all those ruzzle chromosomes in a MySQL database to be able to do some reporting and study the various policies and their effects.

I started adding comments to the classes, mostly to keep references, maintain a todo list per class and add some notes for myself to quickly remember why things work that way!

I’ll probably have an image by tomorrow that will run simulations for the ruzzle problem full-time. I wanna beat that record!

 

Save

Save

Save

Save

Les casse-tête

Ceux qui me connaissent bien le savent, j’adore me casser la tête sur une foule de « petits » problèmes (mathématiques, algorithmiques ou autres) : ça permet de garder le cerveau en forme et ça me donne une occasion de faire du Smalltalk et de me garder à jour dans mes skills autant de programmation que d’analyse.

Si vous êtes comme moi, voici une liste de ces petits casse-tête qui m’amusent en ce moment (ou depuis un bout) et qui pourrait vous servir de suggestions…

Les nombres de Lychrel

Avant tout, un peu de vocabulaire!

Un palindrome est une mot, une phrase ou un nombre qui s’écrit de la même façon à l’endroit et à l’envers.  Par exemple, Laval, Bob ou 17371.  Ça peut également être une phrase ou un bout de texte comme « Mon nom » ou le célèbre « A man, a plan, a canal: Panama ».

Grosso modo, un nombre de Lychrel est un nombre qui ne peut pas former de nombre palindrome lorsqu’on l’additionne à répétition avec son « inverse ».

Par exemple, 59 n’est pas un nombre de Lychrel puis qu’on aboutit à un palindrome au bout des itérations suivantes:

59 + 95 = 154
154 + 451 = 605
605 + 506 = 1111

L’histoire devient passionnante quand des mathématiciens se sont intéressés au plus petit nombre pour lequel on n’a pas encore trouvé de nombre palindrome après une quantité anormalement élevée d’itérations.  Il s’agit de 196.

Le problème est fascinant en soi de par la simplicité des opérations impliquées (des additions et la détection de palindrome) et les raccourcis et astuces nécessaires (autant mathématiques qu’algorithmiques) pour tenter de le résoudre.

Parmi les incontournables sur le sujet, il y a les sites de Jason Doucet et celui de Wade VanLandingham.

Le site What If?

Un site de questions absurdes avec des explications sérieuses et scientifiques.  Un challenge pour le cerveau quand on essaie de formuler une réponse aux problèmes présentés! Ce qui est intéressant, c’est le raisonnement et les arguments des réponses à des problèmes aussi hypothétiques que, bien souvent, idiots!  Comme celui-ci par exemple.

La persistence multiplicative

On définit grossièrement la persistence multiplicative par le nombre de fois qu’on peut multiplier les chiffres d’un nombre entre eux jusqu’à ce que le résultat ne comporte qu’un seul chiffre.

Par exemple:

679 ->  6 * 7 * 9 = 378
378 ->  3 * 7 * 8 = 168
168 ->  1 * 6 * 8 = 48
48 ->  4 * 8 = 32
32 ->  3 * 2 = 6

On dira donc que le nombre 679 a une persistence multiplicative de 5.

À ce jour, nous ne connaissons aucun nombre en deça de 10^233 (10 à la puissance 233) ayant une persistence multiplicative supérieure à 11. C’est précisément cette limite qui intéresse les mathématiciens!

Évidemment, ce qu’il est intéressant de chercher ce sont les nombres dits candidats.  Tout nombre comportant un 0 est éliminé d’office (ça occasionne forcément un résultat de zéro). Comme la multiplication par 1 n’apporte rien de plus, on ne considérera que les nombres sans le chiffre 1.  De plus, on éliminera les nombres comportant à la fois le chiffre 5 et un nombre pair comme cela produira un multiple de 10, donc un résultat de zéro.

Pour un bref aperçu de la persistence multiplicative, il y a une page de Wolfram sur le sujet. Pour un résumé des optimisations et trucs possibles, il y a ce papier.

La conjecture de Collatz

Un autre problème mathématique non résolu : la conjecture de Collatz (aussi appelée conjecture de Syracuse).

Si vous avez quelques cycles de CPU à partager, il existe un projet BOINC juste ici.

Autrement, je vous recommende de lire sur le sujet.  Les diverses astuces pour accélérer les calculs sont aussi surprenantes qu’efficaces!

Euler Project

Un site qui propose des problèmes mathématiques à être résolus par ordinateur!  Il y a un hic!  Il devient assez rapidement évident que la solution est bien souvent (pour ne pas écrire toujours) algébrique et mathématique.

C’est ce dont je me suis encore rendu compte récemment, en scrappant toute une nuit à faire des calculs pour résoudre le problème 131!

Sudoku

Il y a tant d’articles sur le sujet qu’un simple recherche Google devrait suffire à vous tenir occupé en lecture jusqu’à la fin des temps!

Pour ma part, par pur amusement, je me suis attardé à résoudre ces petits problèmes d’une façon surprenante : le préambule, le premier article, la seconde partie et la dernière partie.

Pour un aperçu des techniques de résolution (autres que la force brute), il y a cette liste.

EinStein würfelt nicht!

Communément appelé EWN, ce petit jeu renforme une quantité de particularités contre-intuitives. Autre difficulté, l’aspect probabiliste qui vient tout brouiller les cartes!

Vous pouvez y jouer sur le site de jeux Little Golem si ça vous intéresse.  Pour ma part, je planche sur quelques idées de stratégies que j’entends bien tester avec un programme bientôt.

Ruzzle

Un petit jeu tout simple!  Et pourtant!

J’ai commencé à étudier de plus près le ruzzle comme en témoigne cet article et celui-ci.

Comme je n’ai toujours pas trouvé de grille meilleure que celle de M. Müller, ma quête se poursuit! Des nouvelles pour très bientôt!