Fast popcount in Ruby

When I was imagining what I wanted to implement, in the process it became necessary to "count the bits with the integer 1". However, I noticed that implementing it in Ruby is quite slow, so I decided to implement it in C language etc. (jkr2255 / bit_counter).

Preceding case

Recently, it has become a CPU instruction called POPCNT (described later), and when I thought that someone had implemented it, I realized that surprisingly, Bignum was almost untouched.

"If you don't have one, you can make it yourself!"

About negative numbers

In the case of Ruby, integers allow infinite digits (conceptually), and negative numbers are two's complement representations, so the sign bit 1 is ** infinitely continuous **. As expected, counting the number of 1s in this state is "infinite" and is meaningless, so when it is a negative number, it is implemented as "counting the number of 0s and then returning it as a minus". [^ 1].

JRuby version ... Implemented in Java

If you make an extension in C language, JRuby will not be supported. However, in this case, there were methods such as Long.bitCount () and BigInteger # bitCount () on the Java side, so call this. jkr_2255 / items / 33b1eb1b2d4099ca1c67) was almost done.

However, if the C extension build starts in JRuby, an error will occur, so add a conditional branch to see if it is JRuby in Rakefile or gemspec, and generate a separate Gem for JRuby to RubyGems. I had to push.

Creating a C extension

Ruby integers are divided into Fixnum and Bignum, but Fixnum can easily be a C integer, so you should do it. That is

These two.

Bit count at C language level

First, check with CPUID to see if the POPCNT instruction introduced in SSE 4.2 can be used, and if it is valid, count with POPCNT [^ 2]. If not, use GCC's built-in __builtin_popcountl (), otherwise use a handwritten version of the count function.

Convert the value of Bignum to an array

If you continue the operation with Bignum, an object will be created each time, and the speed will not come out at all. So, once you convert from Bignum to a numeric array, there are two functions, rb_big_pack and rb_integer_pack, depending on the version of Ruby, and which one is valid may differ. Also, when the capacity of the conversion buffer is small, ʻALLOCA is used instead of ʻALLOC to avoid overhead for the stack (in fact, this alone is 30% faster for small numbers).

If you enter the array, the rest is counting, but in the Windows x64 environment, long is 32 bits wide, so the pointer is read so that the 64-bit POPCNT instruction can be used.


Compared to the commonly used num.to_s (2) .count ('1'), it was 5 to 20 times faster (on machines with POPCNT instructions).

Remaining challenges

Ichiou Rubinius also works, but it doesn't get much faster, so I'm considering something that can't be done.

[^ 1]: Java's BigInteger # bitCount () is to return the number of bits "different from the sign bit". That is, it also returns a positive value for negative numbers. [^ 2]: It seems that it will be a little faster if you use AVX etc. to get enthusiastic, but I have not done so much.

Recommended Posts

Fast popcount in Ruby
Class in Ruby
Heavy in Ruby! ??
About eval in Ruby
Output triangle in Ruby
Variable type in ruby
ABC177 --solving E in Ruby
Validate JWT token in Ruby
Implemented XPath 1.0 parser in Ruby
Read design patterns in Ruby
Write class inheritance in Ruby
Update Ruby in Unicorn environment
Integer unified into Integer in Ruby 2.4
[Ruby] Exception handling in functions
Use ruby variables in javascript.
Multiplication in a Ruby array
Birthday attack calculation in Ruby
Judgment of fractions in Ruby
Find Roman numerals in Ruby
Try using gRPC in Ruby
[Ruby] Find numbers in arrays
NCk mod p in Ruby
Chinese Remainder Theorem in Ruby
Sorting hashes in a Ruby array
Basics of sending Gmail in Ruby
Try to implement Yubaba in Ruby
Implementation of ls command in Ruby
Encoding when getting in Windows + Ruby
Ruby on Rails Japanese-English support i18n
[Ruby] Extracting double hash in array
[Ruby] then keyword and case in
How to install Bootstrap in Ruby
String output method memo in Ruby
Write keys and values in Ruby
[Super Introduction] About Symbols in Ruby
Hanachan in Ruby (non-destructive array manipulation)
Manipulating data in GCS during Ruby
Is there no type in Ruby?
Try file locking in Ruby directory
[Ruby] undefined method `dark?'occurs in rqr_code
openssl version information in ruby OPENSSL_VERSION
Ruby methods often used in Rails
Make Ruby segfault in two lines
Be careful when omitting return in Ruby
I tried a calendar problem in Ruby
Implementing poker little by little in Ruby Part 2
How to get date data in Ruby
Acquisition of article information in ruby ​​scraping
Implementing poker little by little in Ruby Part 1
Make bubble sort and selection sort in Ruby
Differences in writing in Ruby, PHP, Java, JS
[Technical memo] What is "include" in Ruby?
Implementing poker little by little in Ruby Part 4
Implement the algorithm in Ruby: Day 1 -Euclidean algorithm-
Convert numbers to Roman numerals in Ruby
Implemented "Floyd Cycle Detection Method" in Ruby
Implementing poker little by little in Ruby Part 3
Ruby on Rails in Visual Studio Codespaces
Summary of hashes and symbols in Ruby
Methods that I found useful in Ruby
Use selenium (Firefox) in Ruby in WSL environment