Détection dynamique de courses avec O(1) échantillons

L'analyse dynamique basée sur l'ordre "happens before" est la technique de référence pour détecter les courses de données dans les projets logiciels à grande échelle en raison de l'absence de faux positifs. Cependant, de telles analyses sont coûteuses car elles nécessitent des mises à jour de l'horloge vectorielle coûteuses à chaque événement, ce qui les rend utilisables uniquement pour des tests internes. Dans cet article, nous présentons un détecteur de courses basé sur l'échantillonnage et aléatoire qui traite uniquement un nombre constant d'événements de la trace d'entrée même dans le pire des cas. Il s'agit du premier algorithme de détection de courses dynamique en temps sous-linéaire (c'est-à-dire s'exécutant en o (n) où n est la longueur de la trace) ; les approches précédentes basées sur l'échantillonnage fonctionnent en temps linéaire (c'est-à-dire O (n)). Notre algorithme est un testeur de propriété pour la détection de -courses : il est sûr en ce sens qu'il ne rapporte jamais de faux positifs, et sur des traces qui sont éloignées, par rapport à la distance de Hamming, de toute trace sans courses, l'algorithme détecte une -course avec une probabilité élevée. Notre évaluation expérimentale de l'algorithme et sa comparaison avec des détecteurs de courses déterministes et basés sur l'échantillonnage de pointe montrent que l'algorithme a effectivement un temps d'exécution significativement bas, et détecte des courses assez souvent.