From: Joseph Jones Date: 2015-12-17T21:13:08-07:00 Subject: [ruby-core:72333] [Ruby trunk - Feature #11405] [Assigned] [PATCH] hash.c: minor speedups to int/fixnum keys --567387d4_5f3534a4_16c Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Joseph Jones liked your message with Boxer. On December 10, 2015 at 03:34= :29 MST, mame=40ruby-lang.org wrote:Issue =2311405 has been updated by Yu= suke Endoh.Status changed from Closed to AssignedAssignee set to Eric Won= gThis caused a lot of trivial hash conflicts of =46ixnums that is >=3D 16= 384.=7E=7E=7E=7E=24 ./miniruby -ve 'p 16384.hash; p 16385.hash'ruby 2.3.0= dev (2015-12-10 master 52945) =5Bx86=5F64-linux=5D11048010433492078001104= 801043349207800=7E=7E=7E=7EOther pairs:=7E=7E=7E=7Ep =5B16386, 16387=5D.m= ap =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B2133837449075777600=5Dp =5B16388= , 16389=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B3903799135928350277=5D= p =5B16390, 16391=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B-383639168= 6716480155=5Dp =5B16392, 16393=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> = =5B1714559302010572050=5Dp =5B16394, 16395=5D.map =7B=7Cn=7C n.hash =7D.u= niq =23=3D> =5B2147130354083423794=5Dp =5B16396, 16397=5D.map =7B=7Cn=7C = n.hash =7D.uniq =23=3D> =5B-679539024000319657=5Dp =5B16398, 16399=5D.map= =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B4056286416392832887=5Dp =5B16400, = 16401=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B2733766810351706956=5D= p =5B16402, 16403=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B-122887663= 1044862612=5Dp =5B16404, 16405=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> = =5B1418226818996216529=5D=7E=7E=7E=7EUnlike the name suggests, rb=5Fobjid= =5Fhash is also used to calculate a hash value of =46ixnum.IMO, we must f= ix this issue before 2.3.0 release.-- Yusuke Endoh ----------------------= ------------------=46eature =2311405: =5BPATCH=5D hash.c: minor speedups = to int/fixnum keyshttps://bugs.ruby-lang.org/issues/11405=23change-55440*= Author: Eric Wong* Status: Assigned* Priority: Normal* Assignee: Eric Wo= ng----------------------------------------Noticed with =5Bruby-core:70159= =5D =5BBug =2311396=5DThe low bits of Ruby object IDs are rarely populate= d in the currentimplementation, so ensure the get used.Early versions of = this patch redundantly shifted static symbols in=60any=5Fhash=60, causing= regressions with static symbols in =60hash=5Faref=5Fsym=60* hash.c (any=5F= hash): skip rb=5Fobjid=5Fhash for static syms (rb=5Fnum=5Fhash=5Fstart): = extract from rb=5Fident=5Fhash (rb=5Fobjid=5Fhash): call rb=5Fnum=5Fhash=5F= start (rb=5Fident=5Fhash): ditto=7E=7E=7Etarget 0: a (ruby 2.3.0dev (2015= -07-30 trunk 51437) =5Bx86=5F64-linux=5Dtarget 1: b (ruby 2.3.0dev (2015-= 07-30 patch 51437) =5Bx86=5F64-linux=5Dbenchmark results from Xeon E3-123= 0 v3 =40 3.30GHz (turbo disabled):minimum results in each 10 measurements= .Execution time (sec)name a bhash=5Faref=5Fdsym 0.316 0.300hash=5Faref=5F= dsym=5Flong 5.106 5.063hash=5Faref=5Ffix 0.304 0.297hash=5Faref=5Fflo 0.0= 61 0.060hash=5Faref=5Fmiss 0.433 0.430hash=5Faref=5Fstr 0.408 0.396hash=5F= aref=5Fsym 0.312 0.306hash=5Faref=5Fsym=5Flong 0.482 0.469hash=5Fflatten = 0.385 0.273hash=5Fident=5Fflo 0.036 0.037hash=5Fident=5Fnum 0.277 0.276ha= sh=5Fident=5Fobj 0.291 0.284hash=5Fident=5Fstr 0.289 0.286hash=5Fident=5F= sym 0.285 0.281hash=5Fkeys 0.269 0.271hash=5Fshift 0.020 0.016hash=5Fvalu= es 0.264 0.264loop=5Fwhileloop2 0.101 0.099vm2=5Fbighash* 3.066 2.972Spee= dup ratio: compare with the result of =60a' (greater is better)name bhash= =5Faref=5Fdsym 1.052hash=5Faref=5Fdsym=5Flong 1.008hash=5Faref=5Ffix 1.02= 4hash=5Faref=5Fflo 1.015hash=5Faref=5Fmiss 1.007hash=5Faref=5Fstr 1.031ha= sh=5Faref=5Fsym 1.018hash=5Faref=5Fsym=5Flong 1.027hash=5Fflatten 1.410ha= sh=5Fident=5Fflo 0.994hash=5Fident=5Fnum 1.001hash=5Fident=5Fobj 1.022has= h=5Fident=5Fstr 1.012hash=5Fident=5Fsym 1.016hash=5Fkeys 0.992hash=5Fshif= t 1.237hash=5Fvalues 1.001loop=5Fwhileloop2 1.013vm2=5Fbighash* 1.032=7E=7E= =7EI will commit in a few weeks if everyone is OK with this.---=46iles---= -----------------------------0001-hash.c-improve-integer-fixnum-hashing.p= atch (5.17 KB)-- https://bugs.ruby-lang.org/ --567387d4_5f3534a4_16c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Joseph Jones liked your message with Boxer.


= On December 10, 2015 at 03:34:29 MST, mame=40ruby-lang.org wrote:
Issue =2311405 has been updat= ed by Yusuke Endoh.

Status changed from Closed to Assigned
Assignee set to Eric Wong

This caused a lot of trivial hash = conflicts of =46ixnums that is >=3D 16384.

=7E=7E=7E=7E
=24= ./miniruby -ve 'p 16384.hash; p 16385.hash'
ruby 2.3.0dev (2015-12-= 10 master 52945) =5Bx86=5F64-linux=5D
1104801043349207800
11048= 01043349207800
=7E=7E=7E=7E

Other pairs:

=7E=7E= =7E=7E
p =5B16386, 16387=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B= 2133837449075777600=5D
p =5B16388, 16389=5D.map =7B=7Cn=7C n.hash =7D= .uniq =23=3D> =5B3903799135928350277=5D
p =5B16390, 16391=5D.map =7B= =7Cn=7C n.hash =7D.uniq =23=3D> =5B-3836391686716480155=5D
p =5B1639= 2, 16393=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B1714559302010572050= =5D
p =5B16394, 16395=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B2= 147130354083423794=5D
p =5B16396, 16397=5D.map =7B=7Cn=7C n.hash =7D= .uniq =23=3D> =5B-679539024000319657=5D
p =5B16398, 16399=5D.map =7B= =7Cn=7C n.hash =7D.uniq =23=3D> =5B4056286416392832887=5D
p =5B16400= , 16401=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B2733766810351706956=5D=
p =5B16402, 16403=5D.map =7B=7Cn=7C n.hash =7D.uniq =23=3D> =5B-122= 8876631044862612=5D
p =5B16404, 16405=5D.map =7B=7Cn=7C n.hash =7D.u= niq =23=3D> =5B1418226818996216529=5D
=7E=7E=7E=7E

Unlike= the name suggests, rb=5Fobjid=5Fhash is also used to calculate a hash va= lue of =46ixnum.

IMO, we must fix this issue before 2.3.0 rele= ase.

--
Yusuke Endoh

-= ---------------------------------------
=46eature =2311405: =5BPATCH= =5D hash.c: minor speedups to int/fixnum keys
https://bugs.ruby-lang= .org/issues/11405=23change-55440

* Author: Eric Wong
* St= atus: Assigned
* Priority: Normal
* Assignee: Eric Wong
--= --------------------------------------
Noticed with =5Bruby-core:701= 59=5D =5BBug =2311396=5D

The low bits of Ruby object IDs are r= arely populated in the current
implementation, so ensure the get use= d.

Early versions of this patch redundantly shifted static sym= bols in
=60any=5Fhash=60, causing regressions with static symbols in= =60hash=5Faref=5Fsym=60

* hash.c (any=5Fhash): skip rb=5Fobji= d=5Fhash for static syms
(rb=5Fnum=5Fhash=5Fstart): extract from r= b=5Fident=5Fhash
(rb=5Fobjid=5Fhash): call rb=5Fnum=5Fhash=5Fstart=
(rb=5Fident=5Fhash): ditto

=7E=7E=7E
target 0: a = (ruby 2.3.0dev (2015-07-30 trunk 51437) =5Bx86=5F64-linux=5D
target = 1: b (ruby 2.3.0dev (2015-07-30 patch 51437) =5Bx86=5F64-linux=5D
benchmark results from Xeon E3-1230 v3 =40 3.30GHz (turbo disabled):<= br />minimum results in each 10 measurements.
Execution time (sec)name a b
hash=5Faref=5Fdsym 0.316 = 0.300
hash=5Faref=5Fdsym=5Flong 5.106 5.063
hash=5Faref=5Ff= ix 0.304 0.297
hash=5Faref=5Fflo 0.061 0.060
hash=5Faref=5Fmiss 0.433 0.430
hash=5Faref=5Fstr = 0.408 0.396
hash=5Faref=5Fsym 0.312 0.306
hash=5Far= ef=5Fsym=5Flong 0.482 0.469
hash=5Fflatten 0.385 0.2= 73
hash=5Fident=5Fflo 0.036 0.037
hash=5Fident=5Fnum = 0.277 0.276
hash=5Fident=5Fobj 0.291 0.284
has= h=5Fident=5Fstr 0.289 0.286
hash=5Fident=5Fsym 0.285= 0.281
hash=5Fkeys 0.269 0.271
hash=5Fshift = 0.020 0.016
hash=5Fvalues 0.264 0.264
loo= p=5Fwhileloop2 0.101 0.099
vm2=5Fbighash* 3.066 2= .972

Speedup ratio: compare with the result of =60a' (greater = is better)
name b
hash=5Faref=5Fdsym 1.05= 2
hash=5Faref=5Fdsym=5Flong 1.008
hash=5Faref=5Ffix 1= .024
hash=5Faref=5Fflo 1.015
hash=5Faref=5Fmiss = 1.007
hash=5Faref=5Fstr 1.031
hash=5Faref=5Fsym = 1.018
hash=5Faref=5Fsym=5Flong 1.027
hash=5Fflatten = 1.410
hash=5Fident=5Fflo 0.994
hash=5Fident=5Fnum = 1.001
hash=5Fident=5Fobj 1.022
hash=5Fident=5Fstr = 1.012
hash=5Fident=5Fsym 1.016
hash=5Fkeys = 0.992
hash=5Fshift 1.237
hash=5Fvalues = 1.001
loop=5Fwhileloop2 1.013
vm2=5Fbighash* 1.0= 32
=7E=7E=7E

I will commit in a few weeks if everyone is = OK with this.


---=46iles--------------------------------=
0001-hash.c-improve-integer-fixnum-hashing.patch (5.17 KB)

--
https://bugs.ruby-lang.org/
--567387d4_5f3534a4_16c--