From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on starla X-Spam-Level: X-Spam-Status: No, score=0.1 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_BL_SPAMCOP_NET,SPF_HELO_PASS, SPF_PASS autolearn=no autolearn_force=no version=3.4.6 Received: from nue.mailmanlists.eu (nue.mailmanlists.eu [94.130.110.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id 447B11F44D for ; Tue, 9 Apr 2024 12:54:10 +0000 (UTC) Authentication-Results: dcvr.yhbt.net; dkim=pass (1024-bit key; secure) header.d=ml.ruby-lang.org header.i=@ml.ruby-lang.org header.a=rsa-sha256 header.s=mail header.b=Vn/8gh/+; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=ruby-lang.org header.i=@ruby-lang.org header.a=rsa-sha256 header.s=s1 header.b=f2dblgvZ; dkim-atps=neutral Received: from nue.mailmanlists.eu (localhost [127.0.0.1]) by nue.mailmanlists.eu (Postfix) with ESMTP id 1F14781449; Tue, 9 Apr 2024 12:54:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ml.ruby-lang.org; s=mail; t=1712667242; bh=L8jDggROgHb47rZeoIYscxZ3a/k+8spMD3hmaMlyNIk=; h=Date:References:To:Reply-To:Subject:List-Id:List-Archive: List-Help:List-Owner:List-Post:List-Subscribe:List-Unsubscribe: From:Cc:From; b=Vn/8gh/+FDp7IWXD5qDpHaCtnIpZ8QxRW4vpBe/cIIT1D+WigfC/91qk0F48kddvU 5IqqIXBF8LH0r1WR8KkQl77o+b5TBs5JZEmAe7PKJUyU6MLJMknDSU0ZsN1hrHziTs Ollnj/GFsGvPFpBllMipawa5K4hPtP8k64zL33ko= Received: from s.wrqvtvvn.outbound-mail.sendgrid.net (s.wrqvtvvn.outbound-mail.sendgrid.net [149.72.120.130]) by nue.mailmanlists.eu (Postfix) with ESMTPS id F06DD8138B for ; Tue, 9 Apr 2024 12:53:58 +0000 (UTC) Authentication-Results: nue.mailmanlists.eu; dkim=pass (2048-bit key; unprotected) header.d=ruby-lang.org header.i=@ruby-lang.org header.a=rsa-sha256 header.s=s1 header.b=f2dblgvZ; dkim-atps=neutral DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ruby-lang.org; h=from:references:subject:mime-version:content-type: content-transfer-encoding:list-id:to:cc:content-type:from:subject:to; s=s1; bh=2oE+82uOoJPfypXhVDc5S53q7E0wlZL97DX0MQQud0s=; b=f2dblgvZW23/hWlEgOgs1YxircTA3vw8HfEoW2pyTy2PRZPdsqHqjPEGkMw8tcJUvcMj 3dsBbIzotqpTSGXhWDShiFX6Yheg5zG37YzoUUyEd/Js5V7HpC+VFdCwKbtKCiiyRd27nl rwqqmbgGsoBWPWybaPnJmrvns/+7+ygA0WJLN4jag23nMv+iAM8DHikbOt+UOtg2NltVdi VFsGizhIrDp6JWHHAoszsb0rmTPohtLi8G/Nsk/bEbmtJS6Vq8EDx1ZS5tqcj2mYmOyBQ0 pKAsplu1LUdpLYahC7+yv2SK0ZrGzAvJo84H8Cr+Mm23rRUe2vn9bxpCWE1G9/gQ== Received: by recvd-canary-58c5b9974-5c54c with SMTP id recvd-canary-58c5b9974-5c54c-1-66153A65-1 2024-04-09 12:53:57.529258431 +0000 UTC m=+1872156.192397615 Received: from herokuapp.com (unknown) by geopod-ismtpd-39 (SG) with ESMTP id GxyyFAvkTZqh0kfRiTUivQ for ; Tue, 09 Apr 2024 12:53:57.468 +0000 (UTC) Date: Tue, 09 Apr 2024 12:53:57 +0000 (UTC) Message-ID: References: Mime-Version: 1.0 X-Redmine-Project: ruby-master X-Redmine-Issue-Tracker: Feature X-Redmine-Issue-Id: 20415 X-Redmine-Issue-Author: byroot X-Redmine-Issue-Priority: Normal X-Redmine-Sender: Eregon X-Mailer: Redmine X-Redmine-Host: bugs.ruby-lang.org X-Redmine-Site: Ruby Issue Tracking System X-Auto-Response-Suppress: All Auto-Submitted: auto-generated X-Redmine-MailingListIntegration-Message-Ids: 94067 X-SG-EID: =?us-ascii?Q?u001=2EByjZWvxTCjdoV8K03xEuhE7KqN4thWULFLM7+oH78KY30oYB3qFthsDpL?= =?us-ascii?Q?4w4cbYa3ttBh8bAHPOnE=2FkzPba67JNu7Lnrked2?= =?us-ascii?Q?O7K9VQ=2FJax05prOOEjWZ7wfE9dSyQFEAf+EhmAF?= =?us-ascii?Q?CuRVUereK9Sw5NY9LQTKd+OMcWKF+3boNtDCZlb?= =?us-ascii?Q?f8ytmVzP=2FutH3vJN4naJWrT68gdpP56jfq2Aw64?= =?us-ascii?Q?WSZNWU2iGngz9zQ7ql0Pq3O8eMGWwIrZvPdMuts?= =?us-ascii?Q?X=2Fw7f4a=2F4biFisEvDY1HFoU9iA=3D=3D?= To: ruby-core@ml.ruby-lang.org X-Entity-ID: u001.I8uzylDtAfgbeCOeLBYDww== Message-ID-Hash: YYXUBTAD4RCEV4JMQRU672EJR3W2GWBE X-Message-ID-Hash: YYXUBTAD4RCEV4JMQRU672EJR3W2GWBE X-MailFrom: bounces+313651-b711-ruby-core=ml.ruby-lang.org@em5188.ruby-lang.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.3 Precedence: list Reply-To: Ruby developers Subject: [ruby-core:117472] [Ruby master Feature#20415] Precompute literal String hash code during compilation List-Id: Ruby developers Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: From: "Eregon (Benoit Daloze) via ruby-core" Cc: "Eregon (Benoit Daloze)" Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Issue #20415 has been updated by Eregon (Benoit Daloze). FWIW TruffleRuby already does this, since frozen string literals need to be= deduplicated, the hash needs to be computed, so might as well save it whil= e doing so (the only downside being footprint). ``` truffleruby 24.0.0, like ruby 3.2.2, Oracle GraalVM Native [x86_64-linux] Calculating ------------------------------------- symbol 107.376M (=B1 0.7%) i/s (9.31 ns/i) - 541.038= M in 5.038971s dyn_symbol 106.989M (=B1 0.7%) i/s (9.35 ns/i) - 543.771= M in 5.082698s small_lit 88.014M (=B1 0.6%) i/s (11.36 ns/i) - 442.996= M in 5.033433s frozen_lit 88.174M (=B1 0.3%) i/s (11.34 ns/i) - 444.293= M in 5.038895s Comparison: symbol: 107376115.9 i/s dyn_symbol: 106989494.3 i/s - same-ish: difference falls within e= rror frozen_lit: 88173794.6 i/s - 1.22x slower small_lit: 88013579.7 i/s - 1.22x slower ``` Strings are still slower than Symbol keys, I suspect because `eql?` is quit= e a bit more expensive for Strings. Even if two Strings are interned it's not correct to compare them by identi= ty, because they could still be `eql?` with the same bytes but different en= codings. That case does not exist for Symbols. ---------------------------------------- Feature #20415: Precompute literal String hash code during compilation https://bugs.ruby-lang.org/issues/20415#change-107860 * Author: byroot (Jean Boussier) * Status: Open ---------------------------------------- I worked on a proof of concept with @etienne which I think has some potenti= al, but I'm looking for feedback on what would be the best implementation. The proof of concept is here: https://github.com/Shopify/ruby/pull/553 ### Idea Most string literals are relatively short, hence embedded, and have some wa= sted bytes at the end of their slot. We could use that wasted space to stor= e the string hash. The goal being to make **looking up a literal String key in a hash, as fast= as a Symbol key**. The goal isn't to memoize the hash code of all strings,= but to **only selectively precompute the hash code of literal strings in the compiler**. The compiler could even selectively do this when we lite= ral string is used to lookup a hash (`opt_aref`). Here's the benchmark we used: ```ruby hash =3D 10.times.to_h do |i| [i, i] end dyn_sym =3D "dynamic_symbol".to_sym hash[:some_symbol] =3D 1 hash[dyn_sym] =3D 1 hash["small"] =3D 2 hash["frozen_string_literal"] =3D 2 Benchmark.ips do |x| x.report("symbol") { hash[:some_symbol] } x.report("dyn_symbol") { hash[:some_symbol] } x.report("small_lit") { hash["small"] } x.report("frozen_lit") { hash["frozen_string_literal"] } x.compare!(order: :baseline) end ``` On Ruby 3.3.0, looking up a String key is a bit slower based on the key siz= e: ``` Calculating ------------------------------------- symbol 24.175M (=B1 1.7%) i/s - 122.002M in 5.048306s dyn_symbol 24.345M (=B1 1.6%) i/s - 122.019M in 5.013400s small_lit 21.252M (=B1 2.1%) i/s - 107.744M in 5.072042s frozen_lit 20.095M (=B1 1.3%) i/s - 100.489M in 5.001681s Comparison: symbol: 24174848.1 i/s dyn_symbol: 24345476.9 i/s - same-ish: difference falls within er= ror small_lit: 21252403.2 i/s - 1.14x slower frozen_lit: 20094766.0 i/s - 1.20x slower ``` With the proof of concept performance is pretty much identical: ``` Calculating ------------------------------------- symbol 23.528M (=B1 6.9%) i/s - 117.584M in 5.033231s dyn_symbol 23.777M (=B1 4.7%) i/s - 120.231M in 5.071734s small_lit 23.066M (=B1 2.9%) i/s - 115.376M in 5.006947s frozen_lit 22.729M (=B1 1.1%) i/s - 115.693M in 5.090700s Comparison: symbol: 23527823.6 i/s dyn_symbol: 23776757.8 i/s - same-ish: difference falls within er= ror small_lit: 23065535.3 i/s - same-ish: difference falls within er= ror frozen_lit: 22729351.6 i/s - same-ish: difference falls within er= ror ``` ### Possible implementation The reason I'm opening this issue early is to get feedback on which would b= e the best implementation. #### Store hashcode after the string terminator Right now the proof of concept simply stores the `st_index_t` after the str= ing null terminator, and only when the string is embedded and as enough lef= t over space. Strings with a precomputed hash are marked with an user flag. Pros: - Very simple implementation, no need to change a lot of code, and very e= asy to strip out if we want to. - Doesn't use any extra memory. If the string doesn't have enough left ov= er bytes, the optimization simply isn't applied. - The worst case overhead is a single `FL_TEST_RAW` in `rb_str_hash`. Cons: - The optimization won't apply to certain string sizes. e.g. strings betw= een `17` and `23` bytes won't have a precomputed hash code. - Extracting the hash code requires some not so nice pointer arithmetic. #### Create another RString union Another possibility would be to add another entry in the `RString` struct u= nion, such as we'd have: ```c struct RString { struct RBasic basic; long len; union { // ... existing members struct { st_index_t hash; char ary[1]; } embded_literal; } as; }; ``` Pros: - The optimization can now be applied to all string sizes. - The hashcode is always at the same offset and properly aligned. Cons: - Some strings would be bumped by one slot size, so would use marginally = more memory. - Complexify the code base more, need to modify a lot more string related= code (e.g. `RSTRING_PTR` and many others) - When compiling such string, if an equal string already exists in the `f= string` table, we'd need to replace it, we can't just mutate it in place to= add the hashcode. ### Prior art [Feature #15331] is somewhat similar in its idea, but it does it lazily for= all strings. Here it's much simpler because limited to string literals, wh= ich are the ones likely to be used as Hash keys, and the overhead is on com= pilation, not runtime (aside from a single flag check). So I think most of = the caveats of that original implementation don't apply here. --=20 https://bugs.ruby-lang.org/ ______________________________________________ ruby-core mailing list -- ruby-core@ml.ruby-lang.org To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org ruby-core info -- https://ml.ruby-lang.org/mailman3/postorius/lists/ruby-c= ore.ml.ruby-lang.org/