🎩tip to RGSoC-friendly confs

• ♥ eurucamp ♥ JRubyConf ♥ Deccan RubyConf ♥
• ♥ OTSConf ♥ Madison+ Ruby ♥ BaRuCo ♥
• ♥ Reject.JS ♥ Strange Loop ♥ RailsClub ♥
• ♥ EuRuKo ♥ Øredev ♥ ROSSConf ♥
• ♥ GOTO Conference ♥ dotJS ♥

sooo… who goes where?

• …but how do we track who goes where?

• name-keyed hash? conf-keyed hash?

• how about a logical matrix?

oh of course! (what’s that…?)

• a rectangular table of Boolean values

• true / false relationship representation

confs  = %w(eurucamp JRubyConf ROSSConf BaRuCo EuRuKo)
names  = %w(Tate Isom Genevieve Ola Arielle)
matrix = [
  [true,  true,  true,  false, true],
  [true,  false, false, false, false],
  [false, false, false, true,  true],
  [false, true,  true,  false, true],
  [true,  false, true,  false, true],
]
matrix[confs.index('eurucamp')][names.index('Tate')]        #=> true
matrix[confs.index('ROSSConf')][names.index('Genevieve')]   #=> false

but that’s not very efficient

• every conference adds a row

• every participant adds a column

• confs.size × (names.size Bools + 1 Array) + 1 Array

• how about using zeroes and ones instead?

logical matrix

matrix = [
  [true,  true,  true,  false, true],
  [true,  false, false, false, false],
  [false, false, false, true,  true],
  [false, true,  true,  false, true],
  [true,  false, true,  false, true],
]

bit matrix

matrix = [
  [1, 1, 1, 0, 1],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 1, 1],
  [0, 1, 1, 0, 1],
  [1, 0, 1, 0, 1],
]

bit matrix

matrix = [
  0b11101,
  0b10000,
  0b00011,
  0b01101,
  0b10101,
]

matrix = [29, 16, 3, 13, 21]

how much better?

• names.size Fixnums + 1 Array   →   1 Fixnum

• Fixnums go up to 2E62-1

• …that’s 4611686018427387903

• …that’s 4_611_686_018_427_387_903

• I’m better at estimating things
  than probably 40 or 50 billion people.
  — Randy Tayler

• …that’s over four quintillion

but how do we query it?

confs  = %w(eurucamp JRubyConf ROSSConf BaRuCo EuRuKo)
names  = %w(Tate Isom Genevieve Ola Arielle)
matrix = [
  [true,  true,  true,  false, true],
  [true,  false, false, false, false],
  [false, false, false, true,  true],
  [false, true,  true,  false, true],
  [true,  false, true,  false, true],
]
matrix[confs.index('eurucamp')][names.index('Tate')]        #=> true
matrix[confs.index('ROSSConf')][names.index('Genevieve')]   #=> false

Integer#[]

29 == 0b11101   #=> true
29[0]           #=> 1
29[1]           #=> 0
29[2]           #=> 1

• return the n-th least significant bit

confs  = %w(eurucamp JRubyConf ROSSConf BaRuCo EuRuKo)
names  = %w(Tate Isom Genevieve Ola Arielle).reverse
matrix = [0b11101, 0b10000, 0b00011, 0b01101, 0b10101]
matrix[confs.index('eurucamp')][names.index('Tate')]        #=> 1
matrix[confs.index('ROSSConf')][names.index('Genevieve')]   #=> 0

so… how many go to each conf?

eurucamp = matrix[confs.index('eurucamp')]   #=> [true, true, true, false, true]
eurucamp.count(true)                         #=> 4

eurucamp = matrix[confs.index('eurucamp')]   #=> 0b11101
eurucamp.to_s(2).count('1')                  #=> 4

• number of ones in a binary representation

• ‘population count’

• but to_s(2).count('1') is not very efficient

let’s freedom-patch Integer

class Integer

  def popcount_to_s
    to_s(2).count('1')
  end

  def popcount_cont_shift
    count  = 0
    number = self
    until number == 0
      count += number & 1
      number >>= 1
    end
    count
  end

end

class Integer

  def popcount_bit_elim
    count  = 0
    number = self
    while number != 0
      number &= number - 1
      count += 1
    end
    count
  end

  def popcount_prog_shift
    number  = self
    number -= (number >> 1) & 0x5555555555555555
    number  = (number & 0x3333333333333333) + ((number >> 2) & 0x3333333333333333)
    number  = (number + (number >>  4)) & 0x0f0f0f0f0f0f0f0f
    number  = (number + (number >>  8)) & 0x00ff00ff00ff00ff
    number  = (number + (number >> 16)) & 0x0000ffff0000ffff
    number += number >> 32
    (number + (number >> 64)) & 0xff
  end

end

require 'inline'

class Integer

  inline do |builder|
    builder.c '
      int popcount_bit_elim_c() {
        long number = NUM2LONG(self);
        int  count;
        for (count = 0; number; count++) number &= number - 1;
        return count;
      }
    '
  end

  inline do |builder|
    builder.c '
      int popcount_builtin() {
        return __builtin_popcountl(NUM2LONG(self));
      }
    '
  end

end

class Integer

  POPCOUNT_CACHE = (0x0000..0xffff).map { |number| number.to_s(2).count('1') }

  def popcount_cached
    POPCOUNT_CACHE[self & 0xffff] +
    POPCOUNT_CACHE[self >> 16 & 0xffff] +
    POPCOUNT_CACHE[self >> 32 & 0xffff] +
    POPCOUNT_CACHE[self >> 48]
  end

end

require 'benchmark/ips'

methods = Integer.instance_methods.grep(/^popcount_/)
numbers = Array.new(1_000) { rand(0...(2**62-1)) }

fail 'oops' unless methods.map { |meth| numbers.map(&meth) }.uniq.size == 1

Benchmark.ips do |bench|
  methods.each do |meth|
    bench.report(meth[9..-1]) { numbers.map(&meth) }
  end
  bench.compare!
end

Warming up --------------------------------------
            bit_elim    73.000  i/100ms
              cached   454.000  i/100ms
          cont_shift    34.000  i/100ms
          prog_shift   265.000  i/100ms
                to_s    81.000  i/100ms
          bit_elim_c     1.408k i/100ms
             builtin     2.164k i/100ms
Calculating -------------------------------------
            bit_elim    752.707  (± 0.1%) i/s -      3.796k in   5.043150s
              cached      4.613k (± 0.7%) i/s -     23.154k in   5.019724s
          cont_shift    347.148  (± 1.2%) i/s -      1.768k in   5.093777s
          prog_shift      2.632k (± 2.3%) i/s -     13.250k in   5.037368s
                to_s    815.852  (± 0.9%) i/s -      4.131k in   5.063780s
          bit_elim_c     14.339k (± 1.1%) i/s -     71.808k in   5.008502s
             builtin     22.184k (± 1.4%) i/s -    112.528k in   5.073427s

Comparison:
             builtin:    22184.1 i/s
          bit_elim_c:    14339.1 i/s - 1.55x slower
              cached:     4612.9 i/s - 4.81x slower
          prog_shift:     2631.8 i/s - 8.43x slower
                to_s:      815.9 i/s - 27.19x slower
            bit_elim:      752.7 i/s - 29.47x slower
          cont_shift:      347.1 i/s - 63.90x slower

require "benchmark"

struct Int
  POPCOUNT_CACHE = (0x0000..0xffff).map { |number| number.to_s(2).count('1') }
  def popcount_bit_elim   # …
  def popcount_cached     # …
  def popcount_cont_shift # …
  def popcount_prog_shift # …
  def popcount_to_s       # …
end

numbers = Array.new(1_000) { rand(0...(2**62-1)) }

Benchmark.ips do |bench|
  bench.report("popcount")   { numbers.map(&.popcount)            }
  bench.report("prog_shift") { numbers.map(&.popcount_prog_shift) }
  bench.report("cached")     { numbers.map(&.popcount_cached)     }
  bench.report("bit_elim")   { numbers.map(&.popcount_bit_elim)   }
  bench.report("cont_shift") { numbers.map(&.popcount_cont_shift) }
  bench.report("to_s")       { numbers.map(&.popcount_to_s)       }
end

Let’s compare Ruby (+ help) to Crystal

$ ruby popcount.rb
Comparison:
             builtin:    22184.1 i/s
          bit_elim_c:    14339.1 i/s - 1.55x slower
              cached:     4612.9 i/s - 4.81x slower
          prog_shift:     2631.8 i/s - 8.43x slower
                to_s:      815.9 i/s - 27.19x slower
            bit_elim:      752.7 i/s - 29.47x slower
          cont_shift:      347.1 i/s - 63.90x slower

$ crystal compile --release popcount.cr
$ ./popcount
  popcount 345.28k (± 3.31%)       fastest
prog_shift 306.29k (± 2.94%)  1.13× slower
    cached 207.46k (± 2.94%)  1.66× slower
  bit_elim  56.94k (± 1.77%)  6.06× slower
cont_shift  56.79k (± 1.14%)  6.08× slower
      to_s    3.5k (± 0.87%) 98.54× slower

🎩tip to RGSoC-friendly confs

• ♥ eurucamp ♥ JRubyConf ♥ Deccan RubyConf ♥
• ♥ OTSConf ♥ Madison+ Ruby ♥ BaRuCo ♥
• ♥ Reject.JS ♥ Strange Loop ♥ RailsClub ♥
• ♥ EuRuKo ♥ Øredev ♥ ROSSConf ♥
• ♥ GOTO Conference ♥ dotJS ♥

thanks!

• @chastell
• talks.chastell.net