Performance: `Sqid.new` is surprisingly expensive

[lawrencegripper]

First up, love sqids, been using them at work for a Ruby GraphQL where the first int represents the model (having given each a unique number) and the second the row. With that we have global ID in nice short string 😍

One thing that did trip me up was the performance of Sqids.new. I saw this taking up to 10ms and averaging around 4-5ms.

In the original implementation we called Sqids.new.encode([1,2]) once for each model the GraphQL API returned and with 100 items >50% of the time for the API response was newing up Sqids. Here is the flame graph from one of those calls:

Most of this time is inside Array.select

I can repro this, not 10ms (guess havin stackprof attached slowed things down), with Benchmark.measure

irb(main):011> Benchmark.measure { Sqids.new }
=> 
#<Benchmark::Tms:0x0000714023f3df70
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.003421891000471078,
 @stime=0.0006750000000000089,
 @total=0.0034240000000000104,
 @utime=0.0027490000000000014>

This gives us around 3.4ms per run of Squid.new

For comparison encoding a Sqid takes 0.1ms

irb(main):017> s = Sqids.new
=> 
#<Sqids:0x000071403df4f508
...
irb(main):018> Benchmark.measure { s.encode([1,2]) }
=> 
#<Benchmark::Tms:0x000071402493e600
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.0001069290010491386,
 @stime=0.0,
 @total=0.00010899999999991472,
 @utime=0.00010899999999991472>
irb(main):019> 

The easy fix for us has been to new up Sqid.new once and reuse.

I'm going to have a quick run at whether I can improve the per now, maybe submit a PR.

If that doesn't work out, would you be up for me submitting a PR flagging folks should reuse the Sqid object not new up one on each request?

[lawrencegripper]

Had a bit of a play and narrowed it down to building the filtered blocked list

irb(main):021> blocklist = DEFAULT_BLOCKLIST
=> 
["0rgasm",
...
irb(main):022> alphabet = DEFAULT_ALPHABET
=> "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
irb(main):023* Benchmark.measure {
irb(main):024*       filtered_blocklist = blocklist.select do |word|
irb(main):025*       word.length >= 3 && (word.downcase.chars - alphabet.downcase.chars).empty?
irb(main):026*       end.to_set(&:downcase)
irb(main):027> }
=> 
#<Benchmark::Tms:0x00007d93771af008
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.0033156600038637407,
 @stime=0.0,
 @total=0.0033170000000000144,
 @utime=0.0033170000000000144>
irb(main):028> 

[lawrencegripper]

Got some wins, currently once per item in the blocked list we call alphabet.downcase.chars. This value is the same on each iteration so we can pre-calculate that once for some extra perf.

That gets us from 0.003315 to 0.00095 🥳

irb(main):034* Benchmark.measure {
irb(main):035*   downcased_alphabet = alphabet.downcase.chars
irb(main):036*     filtered_blocklist = blocklist.select do |word|
irb(main):037*       word.length >= 3 && (word.downcase.chars - downcased_alphabet).empty?
irb(main):038*     end.to_set(&:downcase)
irb(main):039> }
=> 
#<Benchmark::Tms:0x00007d93771d5870
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.0009582439961377531,
 @stime=0.00012899999999999023,
 @total=0.0009590000000000987,
 @utime=0.0008300000000001084>

[lawrencegripper]

Going one step further we can cache the filtered_blocked_list on a class level variable and reuse it if we already have it.

Spoiler: I don't like this, feels very clunky. Not going to use this approach

    @@filtered_blocklist_cache ||= {}
    blocklist_alphabet_hash = Digest::MD5.hexdigest(alphabet + blocklist.join)
    
    filtered_blocklist = if @@filtered_blocklist_cache&.key?(blocklist_alphabet_hash)
      @@filtered_blocklist_cache[blocklist_alphabet_hash]
    else
      downcased_alphabet = alphabet.downcase.chars
      @@filtered_blocklist_cache[blocklist_alphabet_hash] = blocklist.select do |word|
        word.length >= 3 && (word.downcase.chars - downcased_alphabet).empty?
      end.to_set(&:downcase)
    end

Then we pay 1ms on first call and basically nothing on subsiquent calls.

irb(main):002> require_relative "./lib/sqids"
=> true
irb(main):003> require "benchmark"
=> true
irb(main):004> Benchmark.measure { Sqids.new }
=> 
#<Benchmark::Tms:0x00007e38e928ae10
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=0.0013138919966877438,
 @stime=0.00019399999999999973,
 @total=0.0013180000000000136,
 @utime=0.0011240000000000139>
irb(main):005> Benchmark.measure { Sqids.new }
=> 
#<Benchmark::Tms:0x00007e38e88ae4c8
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=5.308000254444778e-05,
 @stime=0.0,
 @total=5.4999999999999494e-05,
 @utime=5.4999999999999494e-05>

[lawrencegripper]

Ok... stopping now I promise. Last one.

Most folks are using default block list and default alphabet right.

The default block list is already lower case and greater than 4 chars so we spend 3ms doing nothing in that case. The result is the same 👇

irb(main):035> a == DEFAULT_BLOCKLIST.to_set
=> true
irb(main):036> downcased_alphabet = alphabet.downcase.chars
irb(main):037* a =      blocklist.select do |word|
irb(main):038*         word.length >= 3 && (word.downcase.chars - downcased_alphabet).empty?
irb(main):039>       end.to_set(&:downcase)
=> 
#<Set:
...
irb(main):040> a.length
=> 560
irb(main):041> DEFAULT_BLOCKLIST.length
=> 560
irb(main):042> a == DEFAULT_BLOCKLIST.to_set
=> true

So we can do this...

filtered_blocklist = if blocklist == DEFAULT_BLOCKLIST && alphabet == DEFAULT_ALPHABET
                           # If the blocklist is the default one, we don't need to filter it
                           # we already know it's valid (lowercase and words longer than 3 chars)
                           blocklist
                         else
                           downcased_alphabet = alphabet.downcase.chars
                           blocklist.select do |word|
                             word.length >= 3 && (word.downcase.chars - downcased_alphabet).empty?
                           end.to_set(&:downcase)
                         end

and then we get... super fast! 🚀 0.000073 seconds or 0.07ms 🥳

irb(main):003> Benchmark.measure { Sqids.new }
=> 
#<Benchmark::Tms:0x00007ae2f0baf650
 @cstime=0.0,
 @cutime=0.0,
 @label="",
 @real=7.324999751290306e-05,
 @stime=1.7000000000003124e-05,
 @total=7.799999999999474e-05,
 @utime=6.0999999999991616e-05>

[lawrencegripper]

Here is a PR implementing the default check and moving alphabet outside of select (when not using default list or alphabet).

• Speedier Sqids.new 🦑 #7

[4kimov]

Hi @lawrencegripper, many thanks for the kind words and the thorough investigation. My Ruby experience is limited, so I definitely appreciate optimizations of any kind.

Give me a bit of time to merge your PR, and push a new release.

[lawrencegripper]

Hi @lawrencegripper, many thanks for the kind words and the thorough investigation. My Ruby experience is limited, so I definitely appreciate optimizations of any kind.

Give me a bit of time to merge your PR, and push a new release.

No problem, happy to help 😄