Réduisez n'importe quel solveur record à son squelette et vous retrouvez la même
boucle : poser une pièce, vérifier les arêtes, revenir en arrière en cas de
blocage. L'algorithme était figé dès 2007. Ce sur quoi la communauté rivalise
réellement depuis vingt ans, c'est la couche en dessous de l'algorithme :
l'artisanat qui décide si visiter un nœud de cet arbre coûte environ 26 cycles
d'horloge, comme Mike Field l'a mesuré sur son propre moteur
(message 9003), ou cent fois plus
dans un interpréteur naïf. Même arbre, même recherche, deux ordres de grandeur
d'écart en placements par seconde.
Cette page rassemble cet artisanat, technique par technique, chacune avec sa
source primaire dans les archives de la liste de diffusion. La chronologie de la
manière dont un moteur les a cumulées pendant deux décennies est racontée sur la
page McGavin ; l'anatomie du moteur
derrière les plateaux record est sur la
page Blackwood. Voici l'étagère où
tous deux puisent.
Tout backtracker rapide partage une idée porteuse : ne jamais chercher les
pièces candidates, mais les consulter. Fixez
l'ordre de remplissage (un balayage par
lignes, en général), et chaque case expose exactement deux contraintes connues
quand son tour vient, la couleur de son arête nord et celle de son arête ouest.
Vous précalculez donc une table indexée par cette paire de couleurs, et trouver
toutes les pièces qui peuvent légalement occuper la case courante devient un seul
accès mémoire. La recette de Field de 2007 la plaçait en tête de liste, avec son
corollaire : c'est un ordre de recherche fixe qui rend la clé à deux arêtes
possible tout court, et poser une pièce ne met alors à jour que ses voisines sud
et est (message 3098). La même
conception était disséquée la même année autour du solveur C++ public de Marc
Lebel, le backtracker rapide de référence de l'époque, dans le fil qui fait aussi
office de premier séminaire d'ingénierie de la communauté
(message 1704).
La recette de 2007 recèle une troisième forme de table, facile à manquer :
pour la case juste au-dessus ou à côté d'une pièce indice obligatoire, on
indexe la consultation sur trois arêtes (nord, sud, ouest), de sorte que les
candidats sont pré-filtrés contre la couleur fixe de l'indice, sans aucune
perte de complétude
(message 3098). J'ai redécouvert
son intérêt deux décennies plus tard, dans mon propre carnet : sur un plateau
avec indices, les cases entourant un indice se sont révélées un gouffre à
débit, avec des threads brassant ~85 M placements par seconde contre le mur
de l'indice pendant vingt minutes ; le remède était exactement la table à
trois arêtes de Field. Les archives contenaient déjà la réponse.
Tout le reste de cette page est un raffinement de cette table : la rendre plus
petite, densifier ses entrées, ou dérouler le code autour d'elle.
La table de correspondance a un problème de taille dès qu'on l'indexe sur plus de
deux arêtes. Dans le fil Lebel, Nathan a décrit la version en force brute : un
tableau à 4 dimensions indexé par les quatre couleurs d'arêtes,
combo4[32][32][32][32]. Un million d'entrées, majoritairement nulles, des
défauts de cache garantis. Son correctif a adopté le générateur de hachage
parfait minimal (celui de Bob Jenkins) vers lequel un autre membre avait
orienté la liste. Comme les 256 pièces en 4 rotations ne produisent que 1024 quadruplets
d'arêtes distincts, un hachage parfait minimal fait correspondre la clé compactée
de 32 bits à une table de 1024 entrées sans collision : « assez petite pour tenir
dans le cache la plupart du temps », avec un surcoût de hachage quasi nul, et les
clés absentes lisent simplement un compte de zéro
(message 1831). Un million
d'entrées ramené à mille, uniquement pour que l'ensemble de travail vive en L1.
Il a tracé la frontière lui-même : la table à quatre arêtes ne gagne son loyer
que lorsque l'ordre de remplissage peut laisser des trous ; un solveur à balayage
strict n'en a jamais besoin.
Le budget en cycles de Field explique pourquoi tant de cet artisanat porte sur
l'agencement mémoire : à 75 M tuiles par seconde et par cœur, plus de la moitié
du temps était bloquée sur l'accès mémoire, pas sur le calcul
(message 9003). La réponse est de
faire compter chaque octet que la recherche touche. Compactez les quatre côtés
d'une pièce dans un seul entier
(message 3098). Gardez l'ensemble
des pièces utilisées comme un mot de 64 bits par groupe et court-circuitez toute
une boucle de candidats avec un unique test de masque, une optimisation qu'Arnaud
Carré et Adam Miles ont découvert avoir implémentée indépendamment, ligne pour
ligne (message 9808,
message 9809). Dimensionnez
l'entrée de la table de candidats pour que la table entière tienne dans le cache.
C'est exactement la conception de la struct RotatedPiece de six octets de
Blackwood, déjà racontée sur
la page Blackwood : numéro de pièce,
rotation, les deux côtés exposés, un compte de ruptures et un compte heuristique,
et rien d'autre.
Ces astuces se cumulent encore en 2026. Sur un moteur en profondeur d'abord
par ailleurs identique, dans mon carnet, trois micro-changements exactement de
cette famille ont totalisé +27 % (92 à 93 M contre 72 à 73 M placements
par seconde, stable sur des budgets de 3, 5, 10 et 15 secondes ; un moteur,
un puzzle, une machine, donc lisez-y une forme plutôt qu'une constante
universelle). Un : des listes de candidats terminées par sentinelle,
chaque seau se finissant sur une valeur impossible, si bien que le balayage
tient en un chargement et une comparaison au lieu d'un compteur de bornes,
libérant un registre. Deux : l'ensemble des pièces utilisées en mots de
bitset u64 au lieu d'un octet par pièce ; même nombre d'octets, mais le
test est un unique AND et tout l'ensemble tient dans une ou deux lignes de
cache. Trois : un curseur de reprise unique par profondeur au lieu d'une
paire début/fin, divisant par deux la comptabilité du retour arrière. Et
l'artisanat n'est pas propre aux backtrackers : dans un solveur à propagation
de contraintes qui maintient des domaines de candidats complets par case,
passer ces domaines en mots de bitset u64 a transformé la révision
d'arc-cohérence en une poignée d'opérations sur mots et a rapporté +48 à
+101 % selon le mélange de propagateurs, le travail d'agencement qui a suivi
(table de rotations précalculée, consultation de pièce en O(1), annulation
par arène) se cumulant à ~4,6× sur le profil le plus léger. Lectures de
débit à graine unique, et un solveur à propagation fait bien plus de travail
par nœud que les marcheurs rapides de cette page : emportez les ratios, pas
les valeurs absolues. La leçon, elle, voyage entière : la représentation du
domaine est le moteur.
Si une consultation vous donne les pièces candidates, pourquoi ne pas
précomposer des paires en « bipièces » 1×2 et poser deux cases par nœud ? Mesuré
sur le code de Lebel en août 2007, ça marchait : environ 20 à 30 % plus rapide
(message 1734). Mais le compromis
est rude et les archives en documentent les deux faces. En passant aux blocs 2×2,
un membre a mesuré à peu près 4,2× plus lent et a rejeté d'emblée les pièces
plus grandes (message 1730). Pas de
surprise une fois les tables comptées : environ 4 millions de combinaisons 2×2
intérieures distinctes (message 3044).
Louis Verhaard a rapporté que les bipièces n'aidaient « que très marginalement »
dans son propre backtracker rapide
(message 3061). Et en 2008 la liste
a tranché la question théorique sous-jacente : un solveur à métatuiles visite
essentiellement la même frontière de contraintes qu'un solveur 1×1
(« synchronisés toutes les 4 pièces »), de sorte que le gain est au niveau de
l'implémentation, jamais une réduction de l'espace de recherche
(message 5842,
message 5899). La précomposition
est une accélération qu'on paie en mémoire, et au-delà du 1×2 le prix devient
négatif.
Les dernières indirections de la boucle interne (« sur quelle case suis-je ?
quelles sont ses voisines ? ») peuvent être supprimées en n'ayant tout simplement
pas de boucle. La recette de Field : générer procéduralement du code
monolithique en ligne droite, un bloc par case, chaque bloc connaissant ses
propres voisines comme des constantes ; son code généré se compilait en environ
33 instructions par case
(message 3098). L'idée s'est
répandue vite : dès mi-2008, istarinz générait un solveur C non récursif par
puzzle et par chemin de remplissage, compilé avec le compilateur Intel
(message 5480,
message 5438), la même saison où la
liste comparait ses notes sur les backtrackers non récursifs en général
(message 4683). Le body.c de Peter
McGavin, c'est cette idée cumulée pendant vingt ans : des blocs étiquetés comme
cell_9_2_next:, des chaînes de goto remontant dans la case précédente à
l'épuisement, le fichier entier régénéré pour chaque puzzle et chaque jeu
d'indices (message 11337,
message 11782). Et ça marche d'une
langage à l'autre : libblackwood de Jef Bucas, un générateur Python émettant du
C, a rendu l'algorithme C# de Blackwood environ deux fois plus rapide sur la même
machine (message 10065,
message 10078).
La recette se reproduit aussi dans un langage moderne et essentiellement
sûr. Dans mon carnet, une macro procédurale Rust déplie la boucle de
recherche en 256 branches spécialisées par case, les faits de ligne, de
colonne et de bordure devenant des constantes de compilation : mesuré
+21 % seule, +25 % combinée à l'optimisation guidée par profilage,
et +30 à 35 % une fois repliées les tables de constantes par
calendrier de remplissage (dispersion ±1 % sur 4 exécutions ; la
correction est verrouillée sur une profondeur maximale et un score
identiques). L'estimation analytique préalable donnait +5 à 10 % ; le
surplus est venu de la spécialisation de la prédiction de branchement par
branche et de l'agencement du code, pas du repliement de constantes
lui-même. La facture : le temps de compilation est passé de 5 secondes à
41. La recette de Field signalait déjà le revers en 2007 : le code généré
monolithique perd environ un tiers de son avantage sur les grands
ensembles de travail parce que le cache d'instructions déborde
(message 3098), ce qui
recoupe cette expérience mesurée ; une partie de ce que la génération de
code achète, c'est de l'agencement, et l'agencement est précisément ce
qu'un I-cache qui déborde reprend.
Sous le code source, il reste du débit à récolter, dans les instructions et les
drapeaux plutôt que dans les idées. Adam Miles a fait passer son solveur de 78 à
90 millions de placements par seconde avec les instructions d'extraction de bits
bextr de BMI et pext de BMI2, tout en notant qu'il devenait « de plus en plus
difficile » d'aller plus loin
(message 9796). Le manuel de McGavin
de 2026 est le folklore accumulé : essayez clang, icc et icx face à gcc ; essayez
les versions (clang-15 bat clang-19 sur ses cartes ARM) ; ajoutez
-march=native et -mtune=native ; utilisez l'optimisation guidée par profilage.
Aucune de ces astuces n'est une solution miracle
(message 11751). Son astuce de
compteur du même message est le genre en miniature : le compteur de placements de
64 bits est alimenté par un registre de 16 bits qui déborde, ajoutant 0x10000 à
la fois, parce qu'il a chronométré les deux méthodes il y a des années sur du
matériel 32 bits et que l'astuce l'a emporté.
La ligne PGO du manuel peut recevoir des chiffres. Mesurée sur trois moteurs
Rust de mon carnet, même charge de travail et même machine, l'optimisation
guidée par profilage a rapporté +14 %, +12 % et +4 % (une charge de
travail par binaire, donc des chiffres à charge unique), et l'ampleur du
gain suivait le nombre de branchements imprévisibles que chaque boucle
interne laissait encore au compilateur à agencer ; les références standard
sont le
Rust Performance Book
et la documentation PGO de rustc.
Deux notes pratiques voyagent avec ces chiffres. L'exécution
d'entraînement doit être représentative : un build PGO entraîné sur un
seul motif de branchement peut sortir plus lent que la base hors
distribution. Et les optimiseurs post-édition de liens que le manuel
désigne ensuite
(BOLT, via cargo-pgo)
ne traitent que les binaires ELF, donc Linux en pratique ; qui suit le
manuel de la communauté sur un Mac s'arrête au PGO.
Le même réalisme s'applique au matériel. Le multithreading passe à l'échelle de
la manière évidente : les solveurs multi-cœurs ont franchi les 100 M placements/s
en 2008 (message 5804), et un seul
Core i7 a atteint 558 M/s en décembre de cette année-là
(message 6212). Les progrès en
mono-cœur, en revanche, se sont pour l'essentiel arrêtés. En publiant sa table
2025 de neuf combinaisons CPU/compilateur (38 à 84 M placements/s), McGavin
notait que les vitesses sur les CPU les plus récents « ne sont qu'un peu plus
rapides » que sur son Phenom II de 2010
(message 11643). Les moteurs ont
heurté le mur mémoire de Field il y a quinze ans et s'y appuient depuis.
Le budget en cycles de Field ouvrait cette page depuis 2007. Voici la
version refaite depuis mon propre carnet, sur un cœur performance d'Apple
M1 (lignes de cache de 128 octets, 128 Ko de cache de données L1 ;
les tables de latence du M1
sont la version moderne des chiffres contre lesquels Field se battait). Un
nœud de mon backtracker Rust sans élagage coûte environ 90 à 145
cycles : des lectures propres, sans contention, données en fourchette
parce qu'une machine chargée poussait le même binaire bien au-dessus. La
surprise est la destination des cycles. L'arithmétique de vérification des
arêtes est pour ainsi dire gratuite. Le nœud est dominé par l'évacuation
des pièces déjà utilisées hors de la liste de candidats : environ 6,7
lectures de candidats par nœud, dont environ 5,9 (88 %) sont rejetées
uniquement parce que la pièce est déjà sur le plateau. Chaque rejet est un
chargement L1 plus un branchement dépendant des données ; toute la boucle
de rejet tient en dix instructions et un seul chargement.
Trois instruments croisés placent le plancher d'instructions retirées à
environ 75 à 90 instructions par nœud, soit, au débit d'émission de pointe
du cœur, à peu près 12 à 15 cycles. Les 90 à 145 mesurés se situent 7 à
10× au-dessus de ce plancher, et l'écart a un seul nom : la
mauvaise prédiction de branchement sur le test de pièce utilisée, dont
l'issue dépend des pièces que la recherche a posées et ne peut donc pas
être prédite. En 2007, le mur était la mémoire ; Field mesurait la moitié
de ses cycles bloqués sur des chargements
(message 9003). Sur les
larges cœurs à exécution dans le désordre des années 2020, aux caches L1
généreux, le mur s'est déplacé vers l'entropie de branchement.
Une mesure de plus complète l'anatomie. Activer un élagage de
faisabilité correct, du genre que font tourner les moteurs de record,
multiplie le coût du nœud par environ 13 à 24×, à environ 2 180 cycles
par nœud : le test de l'élagage est invoqué environ 8 fois par nœud et,
en rejetant des candidats, force le balayage environ 10× plus loin dans la
liste (les lectures de candidats sautent de 6,7 à 67,6 par nœud). Et cela
reste massivement rentable, parce que l'élagage achète des ordres de
grandeur de nœuds en moins vers la même profondeur. C'est
l'argument élagage contre vitesse saisi
dans une seule table de coûts : le moteur tourne délibérément ~15× plus
lentement par nœud parce que le produit nœuds × coût-par-nœud est ce qui
compte. (Méthodologie : les comptes de nœuds sont identiques au bit près
d'une exécution à l'autre, la discipline de somme de contrôle décrite plus
bas ; les débits sont des médianes sur 7 répétitions ; une machine, un
régime de plateau, donc chaque chiffre est à portée limitée.)
L'anatomie en main, la question suivante est ce qu'une réécriture récupère.
J'ai reconstruit le noyau de placement chaud de six façons dans un
laboratoire isolé : entrées de candidats compactées, préchargement
logiciel, scission de boucle stricte/relâchée, pipelinage logiciel, tables
annexes compactées, et des combinaisons, sous une règle dure : le chrono
d'une variante ne compte que si elle reproduit le compte de nœuds exact,
la profondeur maximale et un hachage de trajectoire roulant du moteur de
production, replié sur chaque validation (profondeur, pièce, rotation). Ce
verrou est le grand frère de la somme de contrôle par compte de nœuds de
la communauté (c'est aussi ainsi que
l'expérience en Rust portable
plus bas vérifie ses échelons) ; aucune accélération issue d'une
sémantique discrètement modifiée ne peut s'y glisser. Chaque chiffre ici
l'a passé. Le total pour une réécriture scalaire à sémantique exacte :
1,2 à 1,4× robuste, environ 1,8× en pointe dans la région la plus
favorable. Pas 10×.
Le résultat porteur est un négatif. Les deux optimisations de cache
« évidentes » furent quasi nulles : compacter les couleurs dans l'entrée de
candidat, pour supprimer deux collectes en table, a rapporté 1,0 à 1,2× et
a parfois régressé ; réduire les tables annexes de 64 Ko à une forme de
1 Ko résidente en L1 a rapporté au plus 1,26×. C'est une preuve par le nul
que les chargements étaient déjà servis par le cache. Le coût résiduel est
le branchement de pièce utilisée qui se prédit mal, et toute variante qui
préserve la trajectoire exacte de la recherche doit garder ce branchement.
Les seules variantes utiles ont restructuré le flot de contrôle autour
de lui (scission de boucle, pipelinage logiciel), raison pour laquelle
elles plafonnent à 1,2 à 1,4× et ne se cumulent pas : elles attaquent le
même résidu. Un premier essai de flux de candidats par bitset sur cette
conception a mesuré 16 à 25 % plus lent, même portée.
L'échappatoire du traitement par lots a eu son procès aussi : fusionner
deux cases horizontalement adjacentes en un pas « domino », vérifié comme
produisant des ensembles de complétions identiques, exhaustivement,
jusqu'à un branchement à 3 171 voies. Cela a rapporté 1,05 à 1,13× dans un
régime où 74 % des cases pouvaient fusionner, et fut net neutre (0,96 à
1,03×) dans le régime où tourne réellement la recherche de type record, où
seules 27 % fusionnent. Le mécanisme explique le plafond : le lot amortit
la coquille de boucle par case, environ 7 % d'un nœud, mais le balayage
dominant filtré par pièces utilisées est irréductible par case ; la
seconde case parcourt quand même son propre seau contre l'ensemble utilisé
vivant, ce qu'aucune table de paires statique ne peut encoder.
L'arithmétique esquissée dit que des blocs plus grands heurtent le même
mur, mais cette extrapolation reste non testée au-delà des paires.
Tout ceci vaut pour une conception de moteur, un jeu d'instructions, un
régime de puzzle ; la formulation juste est que pour cette conception
sur ce matériel, le plafond scalaire est d'environ 1,5 à 2×, et le mur a
un nom. Savoir si un flux de candidats SIMD sans mauvaise prédiction peut
aller plus loin est une direction ouverte, pas un résultat.
Une culture d'ingénierie ne vaut que ses bancs d'essai, et les archives ont dû
bâtir cette discipline à la dure. En janvier 2008, comparer les revendications de
vitesse a forcé la question de définition : Txibilis comptait un nœud comme
chaque pièce valide posée sur le plateau, sans anticipation
(message 3843) ; d'autres comptaient
les placements tentés, ou les étapes, et le fil a conclu qu'une métrique sur
laquelle tout le monde s'accorde n'existe peut-être pas
(message 3946). La question est
revenue en 2017 et a reçu la réponse standard : les « pièces par seconde » de la
communauté comptent les pièces posées par seconde, à la manière des échecs
(message 9739,
message 9740). L'objection standard
l'accompagnait : la métrique flatte les ordres de remplissage à balayage et ne
dit rien sur la couverture de l'espace de recherche par unité de temps
(message 9746).
Deux conséquences pratiques. D'abord : ne jamais comparer les chiffres en M/s de
deux solveurs sans vérifier ce qu'ils comptent ; un solveur « plus rapide » peut
simplement avoir une définition plus généreuse. Ensuite, l'habitude positive qui
en a découlé : publier le compte de nœuds à côté des chronos. Un backtracker
déterministe parcourant un arbre fixe doit compter les mêmes nœuds sur n'importe
quelle machine, si bien que les comptes de nœuds exacts sont devenus les sommes de
contrôle de la communauté, la façon dont les portages, réécritures et nouveaux
matériels prouvent qu'ils parcourent le même arbre avant que leur vitesse ne
signifie quoi que ce soit.
Il y a une troisième confusion à nommer une fois pour toutes, car elle revient dès que
ces nombres atteignent un public plus large. « Rapide » désigne trois quantités sans
rapport, et aucune ne se convertit dans l'autre :
- Placements par seconde (soit pièces/s ou nœuds/s) - à quelle vitesse la recherche
avance. C'est ce que mesure chaque chiffre de cette page, et cela dépend du plateau
autant que du moteur. Le C de McGavin fait ~287 M sur un plateau facile mais ~105 M sur
un difficile ; un
moteur en Rust portable sur ce site
atteint ~110 M sur le même plateau difficile - à égalité là - et ~122 M sur le facile.
- Arêtes appariées sur 480 - à quel point un plateau est bon. C'est l'axe où vivent
les records (le plafond est 470). Il est indépendant de la vitesse
de marche : un moteur lent trouve régulièrement un meilleur plateau qu'un rapide.
- Placements agrégés par seconde - un total de grappe, plusieurs machines
additionnées. Le « ~300 M/s » parfois épinglé sur un seul moteur est en fait la
grappe du Eternity 2 Syndicate, une
vingtaine de machines additionnées, pas un cœur.
Un grand nombre sur le premier axe ne dit rien du deuxième, et le troisième n'est pas du
tout une vitesse de moteur. Quand ce site cite un débit, c'est toujours des placements/s
sur un cœur sauf mention contraire ; là où le compromis entre dépenser le budget d'un
solveur en vitesse ou en jugement est le sujet, cet argument vit sur
aller vite.
La discipline se prolonge sous le banc d'essai, jusque dans la boucle
d'optimisation elle-même. Une passe de profilage sur mon solveur à forte
propagation (un profileur par échantillonnage avec résolution des trames
inlinées) a livré sept correctifs dirigés par flamegraph valant +22 à
27 % au total, chacun mesuré séparément : fusionner un test de vacuité
dans la boucle de bitset a fait +27,5 % sur le profil le plus léger,
remplacer une liste de travail matérialisée par un parcours de bitmap sur
pile +7 %, une reconstruction de compteur par popcount +4,3 %. Pendant ce
temps, cinq optimisations prédites statiquement furent réfutées par le
même profil : chacune un gain d'école de 1 à 5 % sur le papier
(indications d'inline, réutilisation d'instantané, remontée de dispatch,
réordonnancement de struct, déroulage manuel), chacune soit absente des
200 premiers échantillons, soit mesurée neutre, parce que le compilateur
les faisait déjà. Un correctif relevait de la pure hygiène de mesure :
l'appel de chronométrage lui-même pesait 12,4 % du temps d'exécution à
un taux de vérification d'échéance de 1 sur 64, et le ramener à 1 sur
4096 a tout récupéré, le motif de l'échéance masquée à l'état pur.
L'arithmétique de cache sans profil trompe de la même façon, dans les deux
sens. Remplacer une table de consultation plate de 1 Mo par une table
compacte de 16 Ko résidente en L1, créditée d'environ 20 % par
l'arithmétique des latences, a mesuré 0 % avec une légère régression
(trois exécutions de 10 secondes) : les clés réellement touchées se
regroupaient et étaient déjà chaudes en cache. panic = "abort" a de même
mesuré nul une fois la boucle chaude vidée de ses arêtes de panique. Ce
sont des pourcentages à graine unique, machine unique, propres à un
moteur ; le motif durable est qu'environ la moitié des prédictions
statiques d'expert étaient fausses, dans chaque sens, et que le flamegraph
a arbitré chaque litige. Mesurer, pas modéliser.
| Technique | Ce qu'elle coûte | Ce qu'elle a rapporté | Source |
|---|
| Tables de candidats par position (clé à deux arêtes) | mémoire pour les tables ; un ordre de remplissage fixe | les candidats en un seul accès mémoire, la base que partage tout solveur rapide | 3098 |
| Hachage parfait minimal | construction de hachage hors ligne | table d'un million d'entrées → 1024 entrées, résidente en cache | 1831 |
| Compactage de bits, structs taillées pour le cache | contorsions de code | moins de blocages là où >50 % du temps est mémoire ; court-circuits par masque de 64 bits | 9003, 9808 |
| Bipièces (précomposition 1×2) | les tables grossissent vite ; pas de réduction de l'espace de recherche | +20 à 30 % en 1×2 ; ~4,2× plus lent en 2×2 | 1734, 5899 |
| Génération de code (code en ligne droite par case) | un pipeline de compilation ; régénérer par puzzle | ~33 instructions/case (2007) ; ~2× grâce au C de libblackwood (2020) | 3098, 10065 |
| Instructions d'extraction de bits BMI/BMI2 | portabilité | 78 → 90 M placements/s | 9796 |
| Comparatif de compilateurs, drapeaux natifs, PGO | tâtonnements, par machine | gains « significatifs » mais non quantifiés, de quelques à quelques dizaines de pour cent | 11751 |
| Astuces de compteur (alimentation par débordement 16 bits) | obscurité | mesurable seulement sur le matériel de l'ère 32 bits | 11751 |
Prenons maintenant du recul. La recette de Field de 2007 faisait déjà 60 à 80
millions de placements par seconde et par cœur
(message 3098). Les vingt ans
d'artisanat qui ont suivi ont élargi cette fourchette plutôt que de la multiplier
uniformément. Sur du code portable, le gain est modeste, même si les deux
chiffres de 2025 ne portent pas sur le même puzzle : 72,7 M/s d'un solveur C++
affûté sur un plateau 8×8 et 68,4 M/s d'un descendant Rust de celui de Blackwood
sur du 16×16 en 2025 (message 11633,
message 11634), à peine au-dessus
de la base de 2007. Le facteur ~4× n'apparaît qu'avec du C généré par case sur le
matériel le plus récent : autour de 225 à 295 M/s pour celui de McGavin sur de
petits puzzles (message 11751
note que le débit est à peu près divisé par deux sur du 16×16, la taille qu'E2
a réellement ; message 11750), il mêle donc un
gain de génération de code à un gain matériel, pas de l'artisanat seul. Sur ces
mêmes vingt ans, le record a bougé de trois arêtes : de 467 à 470.
Mon propre carnet a rejoué ce registre de vingt ans en un après-midi. Le
premier solveur de ce site, à forte propagation, marchait à environ 370 k
placements par seconde ; le moteur record en C généré de la communauté en
fait environ 295 M sur un matériel comparable, un écart de 800×. Porter la
forme du moteur C vers un Rust penchant vers le sûr (tables de candidats
plates sensibles à la bordure, bitset de pièces utilisées en quatre mots,
listes de candidats terminées par sentinelle, drapeaux précalculés par
profondeur) en a comblé environ 180× en une journée : 65 à 68 M placements
par seconde en mono-thread, médiane 67 M sur 4 graines avec environ 5 % de
dispersion, sur une machine, pour atterrir à ~22 % du moteur C avant toute
spécialisation par case. À ce stade, le portage n'avait pas été vérifié
comme parcourant l'arbre identique : lisez-y un résultat de forme de
débit, pas un portage vérifié ; la comparaison vérifiée est l'expérience
ci-dessous. Mais la leçon tient déjà : chaque technique de ce portage
figure sur l'étagère de cette page, l'étagère appliquée ensemble est le
facteur cent, et l'écart était d'architecture, pas de langage. (Ces 65 à
68 M sont le moteur de ce carnet ; les 68,4 M en Rust de la communauté
cités plus haut sont un autre programme, une coïncidence de fourchettes.)
Une expérience de 2026 sur ce site
sépare directement ces deux gains. Elle prend un backtracker en Rust portable et sûr
et applique le même artisanat - code généré par case, cases empaquetées, ensemble
utilisé en tableau d'octets, fusion de cases - puis le mesure face au C de McGavin sur
une machine, même plateau, tous deux sans affichage, dos à dos. En gardant le matériel
fixe, le moteur portable égale le C sur les plateaux difficiles et profonds (≈105
à 110 M nœuds de recherche/s chacun) tandis que le C reste ~2,3× plus rapide sur les
faciles et peu ramifiés (≈287 M contre ≈122 M) - chaque échelon vérifié comme
parcourant l'arbre identique. La leçon tranche dans les deux sens : l'art de la
génération de code est réel et reproductible dans un langage moderne - assez pour égaler
du C optimisé à la main là où la recherche est difficile - et il reste seulement le
facteur constant que cette page décrit. Le même moteur, pointé sur le vrai puzzle,
plafonne dans les hauts 300 sur 480, exactement là où la vitesse seule vous laisse.
Deux mesures de carnet de plus ferment la comptabilité. D'abord, le
facteur constant pris sur le fait : un gain de +25 % de débit mono-thread
issu du code généré par profondeur n'a pas changé la qualité de plateau
atteinte à budget multi-thread fixe de 5 minutes. Des partiels
identiques à 444 arêtes appariées sur 480, et les mêmes 450 à 451 arêtes
appariées après une passe de réparation, stables sur 3 graines avec
environ 0,5 % de dispersion (une machine, un point de budget ; convention
des arêtes appariées, et voyez la page des records
pour situer tout chiffre de ce genre face à ceux de la communauté). La
recherche converge vers la même trajectoire ; marcher plus vite ne fait
que l'atteindre plus tôt. Ensuite, la mise en garde multithread que 2008
n'a jamais eu à affronter : sur une puce à 8 cœurs au système mémoire
partagé, 4 threads tournaient à 52 M placements par seconde chacun quand
8 threads tombaient à 22 M chacun, un agrégat quasi plat, et les deux
atteignaient le même score au même budget. Le multithread passe à
l'échelle de la manière évidente jusqu'à saturation du système mémoire.
Les praticiens l'ont dit eux-mêmes. Joshua Blackwood, cataloguant ses impasses
après le 469 (solveurs SAT,
GPU, blocs 2×2 en cache, tous mesurés et
abandonnés), a constaté que seul le raffinement des heuristiques avait jamais
payé, valant encore ~2× (message 10056).
Et quand le fil vitesse de 2025 s'est éteint, Razvan en a écrit l'épitaphe :
quelle que soit la vitesse à laquelle on peut vérifier, « nous n'y ferons pas la
moindre entaille » dans l'espace de recherche d'E2
(message 11657). L'artisanat de
cette page est réel, mesurable et vaut la peine d'être appris ; c'est ce qui
permet à une ferme d'amateurs de parcourir 10¹⁷ nœuds. Mais un facteur constant
reste un facteur constant.
Pourquoi rétrécir l'arbre bat accélérer la marche
est l'arithmétique de cette phrase ; cette page en est le registre d'ingénierie.