Accounts for 15% in ruby-prof benchmarks. This is compounded by the fact that there are 160 Ring::Entry per server.
Idea: Pull out the RubyInline binary impl in memcache-client and shoe horn it into Dalli. Rerun your benchmarks.
ruby2 has an Array#bsearch. I'd rather backport that into a cext gem and add that as a dependency.
Try the native_search branch. gem install RubyInline first. See what difference it makes.
gem install RubyInline
pull in native search via rubyinline, #307