Lorsque j'envisageais ce que je voulais implémenter, dans le processus, il est devenu nécessaire de "compter les bits avec l'entier 1". Cependant, j'ai remarqué qu'il était assez lent à implémenter dans Ruby, j'ai donc décidé de l'implémenter en langage C etc. (jkr2255 / bit_counter).

Cas précédent

Récemment, c'est devenu une instruction CPU appelée POPCNT (décrite plus tard), et quand j'ai pensé que quelqu'un l'avait implémentée, j'ai réalisé que, étonnamment, Bignum était presque intacte.

"Si vous n'en avez pas, vous pouvez le fabriquer vous-même!"

À propos des nombres négatifs

Dans le cas de Ruby, l'entier autorise des chiffres infinis (conceptuellement), et le nombre négatif est une représentation complémentaire de 2, donc le bit de signe 1 est ** infiniment **. Comme prévu, compter le nombre de 1 dans cet état est "infini" et n'a pas de sens, donc quand il s'agit d'un nombre négatif, "comptez le nombre de 0 et renvoyez-le comme un moins". [^ 1].

Version JRuby ... Implémentée en Java

Si vous créez une extension en langage C, JRuby ne sera pas pris en charge. Cependant, dans ce cas, il y avait des méthodes telles que Long.bitCount () et BigInteger # bitCount () du côté Java, donc Call this. jkr_2255 / items / 33b1eb1b2d4099ca1c67) était presque terminé.

Cependant, si la construction de l'extension C commence par JRuby, une erreur se produira, alors ajoutez une branche conditionnelle pour voir s'il s'agit de JRuby avec Rakefile ou gemspec, et générez une Gem distincte pour JRuby à RubyGems J'ai dû pousser.

Créer une extension C

Les entiers Ruby sont divisés en Fixnum et Bignum, mais Fixnum peut facilement être un entier en langage C, vous devriez donc le faire. C'est

Bits de comptage rapide au niveau du langage C
Convertir Bignum en un tableau de bits

Ces deux.

Nombre de bits au niveau du langage C

Tout d'abord, vérifiez avec CPUID pour voir si l'instruction POPCNT introduite dans SSE 4.2 peut être utilisée, et si elle est valide, comptez avec POPCNT [^ 2]. Sinon, utilisez __builtin_popcountl () intégré à GCC, sinon utilisez une version manuscrite de la fonction count.

Convertit la valeur de `Bignum` en tableau

Si vous continuez l'opération avec Bignum, un objet sera créé à chaque fois, et la vitesse ne sortira pas du tout. Donc, une fois que vous convertissez de Bignum en un tableau numérique, il y a deux fonctions, rb_big_pack et rb_integer_pack, selon la version de Ruby, et celle qui est valide peut différer. De plus, lorsque la capacité du tampon de conversion est petite, ʻALLOCA est utilisé à la place de ʻALLOC pour éviter une surcharge pour la pile (en fait, cela seul est 30% plus rapide pour les petits nombres).

Si vous entrez dans le tableau, le reste compte, mais dans l'environnement Windows x64, long a une largeur de 32 bits, donc le pointeur est lu de sorte que l'instruction POPCNT 64 bits puisse être utilisée.

référence

Comparé au num.to_s (2) .count ('1') couramment utilisé, il était 5 à 20 fois plus rapide (sur les machines avec des instructions POPCNT).

Défis restants

Ichiou Rubinius fonctionne également, mais cela ne va pas beaucoup plus vite, donc j'envisage quelque chose qui ne peut pas être fait.

[^ 1]: Java BigInteger # bitCount () renvoie le nombre de bits qui sont "différents du bit de signe". Autrement dit, il renvoie également une valeur positive pour les nombres négatifs. [^ 2]: Il semble que ce sera un peu plus rapide si vous utilisez AVX etc. pour vous enthousiasmer, mais je n'en ai pas fait tellement.

Popcount rapide en Ruby