🎩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?

	Tate	Isom	Genevieve	Ola	Arielle
eurucamp	✓	✓	✓		✓
JRubyConf	✓
ROSSConf				✓	✓
BaRuCo		✓	✓		✓
EuRuKo	✓		✓		✓

…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    53.000  i/100ms
              cached   276.000  i/100ms
          cont_shift    17.000  i/100ms
          prog_shift   131.000  i/100ms
                to_s    69.000  i/100ms
          bit_elim_c     1.098k i/100ms
             builtin     1.453k i/100ms
Calculating -------------------------------------
            bit_elim    541.127  (± 0.4%) i/s -      2.756k
              cached      2.806k (± 0.3%) i/s -     14.076k
          cont_shift    189.921  (± 1.1%) i/s -    952.000 
          prog_shift      1.596k (± 0.3%) i/s -      7.991k
                to_s    695.528  (± 0.4%) i/s -      3.519k
          bit_elim_c     11.172k (± 1.4%) i/s -     55.998k
             builtin     14.661k (± 1.1%) i/s -     74.103k

Comparison:
             builtin:    14661.1 i/s
          bit_elim_c:    11171.8 i/s - 1.31x slower
              cached:     2805.6 i/s - 5.23x slower
          prog_shift:     1595.7 i/s - 9.19x slower
                to_s:      695.5 i/s - 21.08x slower
            bit_elim:      541.1 i/s - 27.09x slower
          cont_shift:      189.9 i/s - 77.20x slower

	Tate	Isom	Genevieve	Ola	Arielle
eurucamp	✓	✓	✓		✓
JRubyConf	✓
ROSSConf				✓	✓
BaRuCo		✓	✓		✓
EuRuKo	✓		✓		✓

🎩tip to RGSoC-friendly confs

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

Bits of Ruby

🎩tip to RGSoC-friendly confs

sooo… who goes where?

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

but that’s not very efficient

logical matrix

bit matrix

bit matrix

how much better?

but how do we query it?

`Integer#[]`

so… how many go to each conf?

let’s freedom-patch `Integer`

🎩tip to RGSoC-friendly confs

thanks!