Re: Less allocated objects on each request

[Eric Wong]

Hi all, this is about a recent rack.git commit:
dc53a8c26dc55d21240233b3d83d36efdef6e924

I don't disagree with this commit at this time, but I hope much of
it will become unnecessary as older versions of Ruby get phased out.

Since Ruby 2.1.0, constant string keys are deduplicated in hash
literals. Thus the following reuses the same "key" string in every
case:

{ "key" => val }
# ref: r44058

Ruby 2.2 (coming December 2014) will also deduplicate the "key" literal
allocation for lookups and assignment on regular hashes:

regular_hash["key"] # opt_aref_with (in insns.def)
regular_hash["key"] = val # opt_aset_with

This speeds up the Rack env hash, but unfortunately won't help with
Rack::Utils::HeaderHash :<
(ref: r44551 + a few subsequent bugfixes)

We originally planned to support dedupe for all strings (not just
literals), but that caused performance regressions :<

On a related note, Ruby 2.2 will also use power-of-two sized hash
tables, speeding up lookups/assignments a little
(~10-20%, CPU-dependent) for String keys [Feature #9425]

This only applies to mainline Ruby, I am not up-to-date with
Rubinius/JRuby internals.

Thanks for reading!

[Eric Wong]

case/when dispatches already optimize away allocation of constant
string literals in all C Ruby 1.9.x/2.x releases
(ref: opt_case_dispatch in Ruby insns.def)

Other Ruby implementations presumably have similar optimizations
to encourage prettier code.

The following code snippet does not cause GC.count to increase
during the two loops, regardless of what `nr' is.
Tested on Ruby 1.9.3, 2.1.3, and trunk r47786:

GET = "GET"
HEAD = "HEAD"
REQUEST_METHOD = "REQUEST_METHOD" # unnecessary in 2.2.0+
env = { REQUEST_METHOD => "GET" }

nr = 10000000
nr.times do |i|
case env[REQUEST_METHOD]
when GET, HEAD
:foo
else
:bar
end
end
a = GC.count

nr.times do |i|
case env[REQUEST_METHOD]
when "GET", "HEAD"
:foo
else
:bar
end
end
b = GC.count
p [ a, b ]
---

Eric Wong <e...@80x24.org> wrote:
> I don't disagree with this commit at this time

OK, I disagree with one part :)

I think the following allocations may be elided in future C Ruby, too:
a) foo == "lit" (and "lit" == foo)
b) str << "lit"

If you prefer `git pull" for this:

The following changes since commit 022b0076b0eacad03eac48060198f05aa776a866:

Merge pull request #739 from schneems/schneems/fix-respond_to (2014-10-02 21:29:17 +0200)

are available in the git repository at:

git://bogomips.org/rack.git when-lit

for you to fetch changes up to 68e086d2b42ee2c9fc8017264aa353a0d543fd13:

conditionalget: avoid const lookup in case/when (2014-10-05 08:09:50 +0000)

----------------------------------------------------------------
Eric Wong (1):
conditionalget: avoid const lookup in case/when

lib/rack/conditionalget.rb | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/rack/conditionalget.rb b/lib/rack/conditionalget.rb
index 3d4c78a..441dd38 100644
--- a/lib/rack/conditionalget.rb
+++ b/lib/rack/conditionalget.rb
@@ -21,7 +21,7 @@ module Rack

def call(env)
case env[REQUEST_METHOD]
- when GET, HEAD
+ when "GET", "HEAD"
status, headers, body = @app.call(env)
headers = Utils::HeaderHash.new(headers)
if status == 200 && fresh?(env, headers)
--
EW

[James Tucker]

Yeah, I've refused a previous patch on related grounds - this should be a language implementation target. I'm glad to hear that reached patches.

Previously, back in the 1.8 days, I benched the aforementioned patch and it was slower than allocating the strings. It turns out that a simple Rack app, when you bench, will happily free these objects and not suffer major problems under high load with the allocations. If I remember correctly the prior patch added constant and method lookup time due to adding hierarchy too.

--

---
You received this message because you are subscribed to the Google Groups "Rack Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to rack-devel+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[James Tucker]

Thanks Eric!

--
EW

[richard schneeman]

Thank you Eric indeed! It took me a little while to figure out, so i thought I would mention, you can reference git commits for ruby/ruby by running:

```
$ git log --grep "trunk@44058"
```

That first SVN commit is
 https://github.com/ruby/ruby/commit/779ae78995977305aa5aec9cb5b562dcf54c22e7

The second commit is:
https://github.com/ruby/ruby/commit/58f800a278b8b70463f4afdbb23a918d8ab441ff

Eric's proposal: https://bugs.ruby-lang.org/issues/9425


I agree that the patch should one day be unnecessary, In the mean time i'm happy to get faster execution while we wait. I was talking with Koichi about how or if we might optimize so we could write "normal" ruby code and still have it run as memory efficient and fast as using constants. He showed me that this string de-duplication feature was in 2.2, though I was having a hard time finding the commits. Thank you Eric for listing them.

In my research it was also pointed out that string de-duplication was added to JVM-8 http://java-performance.info/java-string-deduplication/. I think it's great that Ruby has already started to make string de-duplication optimizations.

Thanks for the perf help and again for the links!

[Eric Wong]

richard schneeman <richard....@gmail.com> wrote:
> That first SVN commit is
>

> *https://github.com/ruby/ruby/commit/779ae78995977305aa5aec9cb5b562dcf54c22e7*
>
> The second commit is:
> *https://github.com/ruby/ruby/commit/58f800a278b8b70463f4afdbb23a918d8ab441ff*
>
> Eric's proposal: *https://bugs.ruby-lang.org/issues/9425*

>
>
> I agree that the patch should one day be unnecessary,

<snip> Hi Richard, ressurrecting since I believe the day has come :)

Since rack.git depends on Ruby 2.2.2+ which has the
aforementioned string deduplication, I think we can undo
most (if not all) of these ugly constants and reduce constant
cache overheads while we're at it.

I can followup with patches to the list hopefully in the next
few weeks if nobody beats me to it (occupied with other stuff,
at the moment)

To summarize, the following are optimized in 2.2 (or earlier):

{ "foo" => "bar" } # "foo" is deduped
# "bar" is duplicated unless 'frozen_string_literal: true'

base_hash["foo"] = "bar" # same as above
base_hash["foo"] # "foo" is deduped ditto

The Hash#[] and Hash#[]= optimizations unfortunately do not
transfer to subclasses like HeaderHash.

# string literals in the "when" statement
# this has been optimized for many years, now.
case var
when "foo"
do_foo
when "bar"
do_bar
end

"string".freeze on any string literal is deduped since 2.1,
which might be useful for performance-critical subclasses of Hash.

"frozen_string_literal: true" magic comment exists since 2.3;
but I'm not sure how much it helps and it's easy to introduce
new bugs, so I'm not enthusiastic about it for old code.

Regardless, constants are expensive in both space and time. The
inline constant cache takes space, and the cache needs to be
checked every time a constant is accessed. String literals do
not have that cost.

Constants still have one minor advantage: runtime NameError in
case of typos. But I don't think that benefit is worth it
as they make code harder-to-read.

I mainly bring this up because I had trouble following some
of the hijack code for webrick:
http://mid.gmane.org/20160511050...@dcvr.yhbt.net

(Only speaking for MRI optimizations, I don't know other VMs)

[Aaron Patterson]

Yes please! If you have time. Otherwise I can take care of it.

--
Aaron Patterson
http://tenderlovemaking.com/

[richard schneeman]

I'm in favor of removing the constants for the latest version of Rack. What's the best way to do that? Revert my commit(s)? I'm in the weeds right now and it will take me a bit of time to get around to this. If you have the bandwidth I would appreciate removal. If not, no worries. I'll add it onto my list.

Thanks for bringing this back up again.

-- 
Richard Schneeman

http://schneems.com

On May 12, 2016 at 11:55:00 AM, Aaron Patterson (tende...@ruby-lang.org) wrote:

frozen_string_literal

[Eric Wong]

Aaron Patterson <tende...@ruby-lang.org> wrote:
> Yes please! If you have time. Otherwise I can take care of it.

Much appreciated if you or Richard do; I'm busy with non-Ruby stuff,
but I can help with any VM-related questions you might have.
Thanks.

[richard schneeman]

I have a PR that removes all those constants in rack.rb in favor of string literals:

https://github.com/rack/rack/pull/1085

I also found some places where we should still use `.freeze` in a few cases. There are also some other constants buried around the project, this PR is only the main constants.

Eric & Aaron: on a separate non-rack note, I could use some of your Ruby internals expertise on a performance tuning patch to Sprockets involving `case`. Mostly why is the `case` code not faster than using a hash. Here is the discussion: 

https://github.com/rails/sprockets/pull/312#issuecomment-226369234

-- 
Richard Schneeman

http://schneems.com

[Aaron Patterson]

On Fri, Jun 17, 2016 at 02:43:54PM -0500, richard schneeman wrote:
> I have a PR that removes all those constants in rack.rb in favor of string literals:
> https://github.com/rack/rack/pull/1085

Eric,

Here's a link to the raw diff if you want to take a look:

https://patch-diff.githubusercontent.com/raw/rack/rack/pull/1085.diff

Now that I'm reading this patch, removing the constants worries me
because of backwards compatibility issues. I think removing the
`freeze` is fine, and setting the magic comment to use frozen strings
would be good. But removing the constants seems dangerous since other
libraries use those constants.

Could we just remove the freeze and add the magic comment to that file
that defines the constants?

> I also found some places where we should still use `.freeze` in a few cases. There are also some other constants buried around the project, this PR is only the main constants.
>
> Eric & Aaron: on a separate non-rack note, I could use some of your Ruby internals expertise on a performance tuning patch to Sprockets involving `case`. Mostly why is the `case` code not faster than using a hash. Here is the discussion: 
>
> https://github.com/rails/sprockets/pull/312#issuecomment-226369234

I left a comment. Basically the case statement is doing an is_a? where
the hash version is just doing an equality on the class.

[Eric Wong]

Aaron Patterson <tende...@ruby-lang.org> wrote:
> On Fri, Jun 17, 2016 at 02:43:54PM -0500, richard schneeman wrote:
> > I have a PR that removes all those constants in rack.rb in favor of string literals:
> > https://github.com/rack/rack/pull/1085
>
> Eric,
>
> Here's a link to the raw diff if you want to take a look:
>
> https://patch-diff.githubusercontent.com/raw/rack/rack/pull/1085.diff

Thanks, I added "fetch = +refs/pull/*:refs/remotes/pull/*"
to the remote section of my .git/config to fetch it down
to get my usual git diff/log views.

> Now that I'm reading this patch, removing the constants worries me
> because of backwards compatibility issues. I think removing the
> `freeze` is fine, and setting the magic comment to use frozen strings
> would be good. But removing the constants seems dangerous since other
> libraries use those constants.

Agreed. In my experience, adding the frozen_string_literal
magic comment to existing code needs to be done very carefully.

I suggest local "literal".freeze for method args where it's
difficult to audit and beefing up test cases to ensure
breakage is not introduced.

> Could we just remove the freeze and add the magic comment to that file
> that defines the constants?
>
> > I also found some places where we should still use `.freeze` in a few cases. There are also some other constants buried around the project, this PR is only the main constants.
> >
> > Eric & Aaron: on a separate non-rack note, I could use some of your Ruby internals expertise on a performance tuning patch to Sprockets involving `case`. Mostly why is the `case` code not faster than using a hash. Here is the discussion: 
> >
> > https://github.com/rails/sprockets/pull/312#issuecomment-226369234
>
> I left a comment. Basically the case statement is doing an is_a? where
> the hash version is just doing an equality on the class.

That's part of it.

case/when is a linear scan in this case. case/when gets
transparently optimized into a hash lookup into a jump table
when all the potential "when" matches are frozen literals.

Ruby can't optimize constants for case/when because constants
aren't constant like frozen literals are[1]

As an experiment, it might be worth it to see how only
having literal string matches affects performance:

case value.class.to_s
when "String", "Symbol"
when "Array"
something
else
something_else
end

This will compile to the opt_case_dispatch instruction
and require no extra allocations for the literals.
(but too ugly for real code)

Throwing a non-literal in there will break the optimization:

case value.class.to_s
when "String", "Symbol"
when Array.to_s # oops!
something
else
something_else
end

The following also breaks the opt_case_dispatch optimization so
it becomes a linear scan, but it still avoids allocating:

case value.class.to_s
when "String".freeze, "Symbol".freeze
when "Array".freeze
something
else
something_else
end


[1] - perhaps the VM constant cache can be used in the future
for optimizing case dispatch with constants, though

/me crawls back into his Perl 5 cave :)

[Aaron Patterson]

On Fri, Jun 17, 2016 at 11:12:39PM +0000, Eric Wong wrote:
> The following also breaks the opt_case_dispatch optimization so
> it becomes a linear scan, but it still avoids allocating:
>
> case value.class.to_s
> when "String".freeze, "Symbol".freeze
> when "Array".freeze
> something
> else
> something_else
> end

Huh. I didn't know adding the `freeze` would kill the optimization.
Seems like we could fix that, though I'm not sure why anyone would do
this. You can't access the strings anyway so freezing seems pointless
(maybe even warning worthy?)

[Eric Wong]

Yes, it should be fixable, but probably not worth the
trouble (or slowing down compilation for).

Actually, I think richard found a case last year which forced
the linear scan with "literal".freeze and it was slightly faster
than the hash lookup because there was only one element to
check.

But yeah, pretty minor AFAIK.