Alternative ZFRS to improve memory allocation

[whomwah]

I'm no expert on bitwise optimization, and am trying to investigate and address https://github.com/whomwah/rqrcode_core/issues/27.

After a bit of research on right shift zero fill managed to change it and get some improvements. At least I think I am getting improvements as I don't have much experience with memory profiling either.

~Ultimately I think num.size was very slow and was being used to determine 32 or 64 bit system.~ UPDATE: This is not the issue. See https://github.com/whomwah/rqrcode_core/pull/28#discussion_r695577713

I've just hardcoded 32 for now which may have implications but the test suite doesn't show it. Changing to 64 seems to work too ! so I'd love to know more.

def self.rszf(num, count)
  # right shift zero fill
  (num >> count) & ((1 << (32 - count)) - 1)
end

BEFORE:

{:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>3699640}

vscode ➜ /workspaces/rqrcode_core (master ✗) $ ./bin/console
irb(main):001:0> require 'memory_profiler'; MemoryProfiler.report { RQRCodeCore::QRCode.new(("a" * 200)) }.allocated_memory_by_file
=> 
[{:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>3699640},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_polynomial.rb", :count=>598240},
 {:data=>"<internal:kernel>", :count=>452144},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_code.rb", :count=>26576},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_alphanumeric.rb", :count=>13760},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_numeric.rb", :count=>12721},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_bit_buffer.rb", :count=>11280},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_rs_block.rb", :count=>1232},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_segment.rb", :count=>832},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_math.rb", :count=>384},
 {:data=>"(irb)", :count=>240}]
irb(main):002:0> exit

AFTER:

 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>112240},

vscode ➜ /workspaces/rqrcode_core (master ✗) $ ./bin/console
irb(main):001:0> require 'memory_profiler'; MemoryProfiler.report { RQRCodeCore::QRCode.new(("a" * 200)) }.allocated_memory_by_file
=> 
[{:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_polynomial.rb", :count=>598240},
 {:data=>"<internal:kernel>", :count=>452144},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>112240},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_code.rb", :count=>26576},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_alphanumeric.rb", :count=>13760},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_numeric.rb", :count=>12721},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_bit_buffer.rb", :count=>11280},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_rs_block.rb", :count=>1232},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_segment.rb", :count=>832},
 {:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_math.rb", :count=>384},
 {:data=>"(irb)", :count=>240}]
irb(main):002:0> 

[dixpac]

Hey!

Great news. I've tried your branch and indeed it is better, a lot better.

Here are the numbers from our production profiling (after warmup):

# from master
3197424  rqrcode_core-1.0.0
2561560  /Users/dixpac/.rbenv/versions/2.7.3/lib/ruby/gems/2.7.0/gems/rqrcode_core-1.0.0/lib/rqrcode_core/qrcode/qr_util.rb

# your fix
728968  rqrcode_core-b81eae580602
61600  /Users/dixpac/.rbenv/versions/2.7.3/lib/ruby/gems/2.7.0/bundler/gems/rqrcode_core-b81eae580602/lib/rqrcode_core/qrcode/qr_util.rb

👏🏼 👏🏼

[whomwah]

Wow! OK. I've been looking at other QRCode implementations and I'm beginning to actually wonder if the rszf method is actually needed. But that's for another day.

I'm going to do some more testing on this change. There are so many variations it's almost impossible to know if I have introduced a breaking change but the test suite is pretty good so 🤞.

If it all seems good I'll try and get something merged ASAP. I have a new release to do as part of another piece of work so I'd add it to that.

[dixpac]

"There are so many variations it's almost impossible to know if I have introduced a breaking change but the test suite is pretty good so" - Yup 😄

Run through benchmarks just in case, they both perform the same so 👍🏼

[whomwah]

@dixpac after more testing and research, it does appear that hard coding the Arch to 32 uses less memory on a 64 machine as you may expect, but I don't have enough expertise to know if this will break for some other user in some scenarios.

So to this end I have added the ability to set an ENV variable RQRCODE_CORE_ARCH_BITS that allows you to optionally override the default value should you be happy to do so. Here's some examples on my machine (Mac 64bit):

irb(main):002:0> 1.size * 8
=> 64

vscode ➜ /workspaces/rqrcode_core (dr-memory ✗) $ ./bin/console
irb(main):001:0> require 'memory_profiler'; MemoryProfiler.report { RQRCodeCore::QRCode.new(("a" * 200)) }.allocated_memory_by_file
{:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>2882600}

vscode ➜ /workspaces/rqrcode_core (dr-memory ✗) $ RQRCODE_CORE_ARCH_BITS=32 ./bin/console
irb(main):001:0> require 'memory_profiler'; MemoryProfiler.report { RQRCodeCore::QRCode.new(("a" * 200)) }.allocated_memory_by_file
=> 
{:data=>"/workspaces/rqrcode_core/lib/rqrcode_core/qrcode/qr_util.rb", :count=>112240},

It would be great if you could give it a try to make sure you get the same improvements.