Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

caching overloading tables as magic slows down hash lookups #12404

Closed
p5pRT opened this issue Sep 12, 2012 · 16 comments
Closed

caching overloading tables as magic slows down hash lookups #12404

p5pRT opened this issue Sep 12, 2012 · 16 comments

Comments

@p5pRT
Copy link

p5pRT commented Sep 12, 2012

Migrated from rt.perl.org#114864 (status was 'resolved')

Searchable as RT114864$

@p5pRT
Copy link
Author

p5pRT commented Sep 12, 2012

From @nwc10

The CV pointers for overloading methods are cached in a structure stored in
magic which is hung onto the HV representing the symbol table. DESTROY is
also cached here.

It's been like this for approximately forever. (I believe)

The result is that as soon as an object is destroyed, any lookups on that
hash find their way into this code​:

  if (SvSMAGICAL(hv) && SvGMAGICAL(hv) && !(action & HV_DISABLE_UVAR_XKEY)) {
  MAGIC* mg;
  if ((mg = mg_find((const SV *)hv, PERL_MAGIC_uvar))) {

That isn't great.

I suspect that a solution is to move struct am_table from MAGIC into a
pointer in struct hv_aux.

Here's the long version. Looking up 'a' in %​:: twice, before and after an
object in that package is DESTROYed.

Notice how first time through the code goes straight from line 404 to
407. Whereas once overload magic is attached, there's a diversion into the
code at line 405, and calls into Perl_mg_find() and S_mg_findext_flags().

$ gdb --args ./perl -le '$​::{a}; bless []; $​::{a};'
GNU gdb 6.3.50-20050815 (Apple version gdb-1515) (Sat Jan 15 08​:33​:48 UTC 2011)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared libraries ... done

(gdb) b perl_run
Breakpoint 1 at 0x100054b4f​: file perl.c, line 2289.
(gdb) r
Starting program​: /Volumes/Stuff/Perl/perl/perl -le \$​::\{a\}\;\ bless\ \[\]\;\ \$​::\{a\}\;
Reading symbols for shared libraries ++.. done

Breakpoint 1, perl_run (my_perl=0x100600080) at perl.c​:2289
2289 int ret = 0;
(gdb) b Perl_hv_common if keysv
Breakpoint 2 at 0x1001db191​: file hv.c, line 349.
(gdb) c
Continuing.

Breakpoint 2, Perl_hv_common (hv=0x100801f20, keysv=0x100810410, key=0x0, klen=0, flags=0, action=0, val=0x0, hash=3392050242) at hv.c​:349
349 const int return_svp = action & HV_FETCH_JUST_SV;
(gdb) call Perl_sv_dump(hv)
SV = PVHV(0x1008078a0) at 0x100801f20
  REFCNT = 2
  FLAGS = (OOK,SHAREKEYS)
  ARRAY = 0x100606b40 (0​:31, 1​:27, 2​:6)
  hash quality = 121.9%
  KEYS = 39
  FILL = 33
  MAX = 63
  RITER = -1
  EITER = 0x0
  NAME = "main"
  ENAME = "main"
  BACKREFS = 0x100801f80
  SV = PVAV(0x100803c50) at 0x100801f80
  REFCNT = 2
  FLAGS = ()
  ARRAY = 0x1006068d0
  FILL = 38
  MAX = 61
  ARYLEN = 0x0
  FLAGS = ()
(gdb) call Perl_sv_dump(keysv)
SV = PV(0x1008030c0) at 0x100810410
  REFCNT = 1
  FLAGS = (POK,FAKE,READONLY,pPOK)
  PV = 0x100601b60 "a"
  CUR = 1
  LEN = 0
(gdb) s
351 if (!hv)
(gdb)
353 if (SvTYPE(hv) == (svtype)SVTYPEMASK)
(gdb)
356 assert(SvTYPE(hv) == SVt_PVHV);
(gdb)
358 if (SvSMAGICAL(hv) && SvGMAGICAL(hv) && !(action & HV_DISABLE_UVAR_XKEY)) {
(gdb)
383 if (keysv) {
(gdb)
384 if (flags & HVhek_FREEKEY)
(gdb)
386 key = SvPV_const(keysv, klen);
(gdb)
387 is_utf8 = (SvUTF8(keysv) != 0);
(gdb)
388 if (SvIsCOW_shared_hash(keysv)) {
(gdb)
389 flags = HVhek_KEYCANONICAL | (is_utf8 ? HVhek_UTF8 : 0);
(gdb)
390 } else {
(gdb)
393 } else {
(gdb)
397 if (action & HV_DELETE) {
(gdb)
403 xhv = (XPVHV*)SvANY(hv);
(gdb)
404 if (SvMAGICAL(hv)) {
(gdb)
570 if (!HvARRAY(hv)) {
(gdb) c
Continuing.

Breakpoint 2, Perl_hv_common (hv=0x10080fb88, keysv=0x10080fb58, key=0x0, klen=0, flags=0, action=4, val=0x1004c3448, hash=0) at hv.c​:349
349 const int return_svp = action & HV_FETCH_JUST_SV;
(gdb) call Perl_sv_dump(hv)
SV = PVHV(0x100807b40) at 0x10080fb88
  REFCNT = 1
  FLAGS = (TEMP,SHAREKEYS)
  ARRAY = 0x100606720 (0​:7, 1​:1)
  hash quality = 100.0%
  KEYS = 1
  FILL = 1
  MAX = 7
  RITER = -1
  EITER = 0x0
(gdb) c
Continuing.

Breakpoint 2, Perl_hv_common (hv=0x100801f20, keysv=0x100810428, key=0x0, klen=0, flags=0, action=0, val=0x0, hash=3392050242) at hv.c​:349
349 const int return_svp = action & HV_FETCH_JUST_SV;
(gdb) call Perl_sv_dump(hv)
SV = PVHV(0x1008078a0) at 0x100801f20
  REFCNT = 2
  FLAGS = (RMG,OOK,SHAREKEYS)
  MAGIC = 0x100600e90
  MG_VIRTUAL = &PL_vtbl_ovrld
  MG_TYPE = PERL_MAGIC_overload_table(c)
  MG_LEN = 8
  MG_PTR = 0x100606490 "\0\2\0\0\7\0\0\0"
  ARRAY = 0x100606b40 (0​:30, 1​:28, 2​:5, 3​:1)
  hash quality = 116.9%
  KEYS = 41
  FILL = 34
  MAX = 63
  RITER = -1
  EITER = 0x0
  NAME = "main"
  ENAME = "main"
  BACKREFS = 0x100801f80
  SV = PVAV(0x100803c50) at 0x100801f80
  REFCNT = 2
  FLAGS = ()
  ARRAY = 0x1006068d0
  FILL = 40
  MAX = 61
  ARYLEN = 0x0
  FLAGS = ()
  MRO_WHICH = "dfs" (0x1004c10f0)
  CACHE_GEN = 0x1
  PKG_GEN = 0x1
  MRO_LINEAR_CURRENT = 0x10080fb40
  SV = PVAV(0x100803ea8) at 0x10080fb40
  REFCNT = 1
  FLAGS = (READONLY)
  ARRAY = 0x100601820
  FILL = 0
  MAX = 3
  ARYLEN = 0x0
  FLAGS = (REAL)
  ISA = 0x10080fb88
  SV = PVHV(0x100807b40) at 0x10080fb88
  REFCNT = 1
  FLAGS = (READONLY,SHAREKEYS)
  ARRAY = 0x100606720 (0​:6, 1​:2)
  hash quality = 125.0%
  KEYS = 2
  FILL = 2
  MAX = 7
  RITER = -1
  EITER = 0x0
(gdb) call Perl_sv_dump(keysv)
SV = PV(0x100803090) at 0x100810428
  REFCNT = 1
  FLAGS = (POK,FAKE,READONLY,pPOK)
  PV = 0x100601b60 "a"
  CUR = 1
  LEN = 0
(gdb) s
351 if (!hv)
(gdb)
353 if (SvTYPE(hv) == (svtype)SVTYPEMASK)
(gdb)
356 assert(SvTYPE(hv) == SVt_PVHV);
(gdb)
358 if (SvSMAGICAL(hv) && SvGMAGICAL(hv) && !(action & HV_DISABLE_UVAR_XKEY)) {
(gdb)
383 if (keysv) {
(gdb)
384 if (flags & HVhek_FREEKEY)
(gdb)
386 key = SvPV_const(keysv, klen);
(gdb)
387 is_utf8 = (SvUTF8(keysv) != 0);
(gdb)
388 if (SvIsCOW_shared_hash(keysv)) {
(gdb)
389 flags = HVhek_KEYCANONICAL | (is_utf8 ? HVhek_UTF8 : 0);
(gdb)
390 } else {
(gdb)
393 } else {
(gdb)
397 if (action & HV_DELETE) {
(gdb)
403 xhv = (XPVHV*)SvANY(hv);
(gdb)
404 if (SvMAGICAL(hv)) {
(gdb)
405 if (SvRMAGICAL(hv) && !(action & (HV_FETCH_ISSTORE|HV_FETCH_ISEXISTS))) {
(gdb)
406 if (mg_find((const SV *)hv, PERL_MAGIC_tied)
(gdb)
Perl_mg_find (sv=0x100801f20, type=80) at mg.c​:425
425 return S_mg_findext_flags(aTHX_ sv, type, NULL, 0);
(gdb)
S_mg_findext_flags (sv=0x100801f20, type=80, vtbl=0x0, flags=0) at mg.c​:399
399 assert(flags <= 1);
(gdb)
401 if (sv) {
(gdb)
404 for (mg = SvMAGIC(sv); mg; mg = mg->mg_moremagic) {
(gdb)
405 if (mg->mg_type == type && (!flags || mg->mg_virtual == vtbl)) {
(gdb)
408 }
(gdb)
404 for (mg = SvMAGIC(sv); mg; mg = mg->mg_moremagic) {
(gdb)
409 }
(gdb)
411 return NULL;
(gdb)
412 }
(gdb)
0x000000010019d7ca in Perl_mg_find (sv=0x100801f20, type=80) at mg.c​:425
425 return S_mg_findext_flags(aTHX_ sv, type, NULL, 0);
(gdb)
Perl_hv_common (hv=0x100801f20, keysv=0x100810428, key=0x100601b60 "a", klen=1, flags=1024, action=0, val=0x0, hash=3392050242) at hv.c​:480
480 } /* ISFETCH */
(gdb)
568 } /* SvMAGICAL */
(gdb)
570 if (!HvARRAY(hv)) {
(gdb)
598 if (is_utf8 & !(flags & HVhek_KEYCANONICAL)) {
(gdb)

Nicholas Clark

@p5pRT
Copy link
Author

p5pRT commented Sep 12, 2012

From @nwc10

On Wed, Sep 12, 2012 at 08​:54​:15AM -0700, Nicholas Clark wrote​:

I suspect that a solution is to move struct am_table from MAGIC into a
pointer in struct hv_aux.

Oh, addendum that I think I realised a couple of years ago but never got
time to chase up.

I think if DESTROY is cached, an entire array of CV pointers is allocated.
It might be possible to allocate a shorter structure for the case of just
DESTROY.

Nicholas Clark

@p5pRT
Copy link
Author

p5pRT commented Sep 12, 2012

From @cpansprout

On Wed Sep 12 08​:54​:15 2012, nicholas wrote​:

The CV pointers for overloading methods are cached in a structure
stored in
magic which is hung onto the HV representing the symbol table. DESTROY
is
also cached here.

It's been like this for approximately forever. (I believe)

perl-5.6.0-2080-g32251b2

commit 32251b2
Author​: Ilya Zakharevich <ilya@​math.berkeley.edu>
Date​: Fri Dec 15 00​:26​:57 2000 -0500

  speeding up object creation/destruction 4x times
  Message-ID​: <20001215052657.A8319@​math.mps.ohio-state.edu>
 
  p4raw-id​: //depot/perl@​8131

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Sep 12, 2012

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Nov 16, 2012

From @cpansprout

On Wed Sep 12 08​:54​:15 2012, nicholas wrote​:

The CV pointers for overloading methods are cached in a structure
stored in
magic which is hung onto the HV representing the symbol table. DESTROY
is
also cached here.

It's been like this for approximately forever. (I believe)

The result is that as soon as an object is destroyed, any lookups on
that
hash find their way into this code​:

if \(SvSMAGICAL\(hv\) && SvGMAGICAL\(hv\) && \!\(action &

HV_DISABLE_UVAR_XKEY)) {
MAGIC* mg;
if ((mg = mg_find((const SV *)hv, PERL_MAGIC_uvar))) {

That isn't great.

I suspect that a solution is to move struct am_table from MAGIC into a
pointer in struct hv_aux.

Stashes are rarely blessed. Couldn’t we put it in SvSTASH instead?
Just put a CV pointer there and clear it in mro_method_changed_in.

That would avoid making all iterated hashes bigger. It should also make
destruction even faster.

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Nov 17, 2012

From @cpansprout

On Thu Nov 15 21​:48​:43 2012, sprout wrote​:

On Wed Sep 12 08​:54​:15 2012, nicholas wrote​:

The CV pointers for overloading methods are cached in a structure
stored in
magic which is hung onto the HV representing the symbol table. DESTROY
is
also cached here.

It's been like this for approximately forever. (I believe)

The result is that as soon as an object is destroyed, any lookups on
that
hash find their way into this code​:

if \(SvSMAGICAL\(hv\) && SvGMAGICAL\(hv\) && \!\(action &

HV_DISABLE_UVAR_XKEY)) {
MAGIC* mg;
if ((mg = mg_find((const SV *)hv, PERL_MAGIC_uvar))) {

That isn't great.

I suspect that a solution is to move struct am_table from MAGIC into a
pointer in struct hv_aux.

Stashes are rarely blessed. Couldn’t we put it in SvSTASH instead?
Just put a CV pointer there and clear it in mro_method_changed_in.

That would avoid making all iterated hashes bigger. It should also make
destruction even faster.

And it worked. See commit 8c34e50.

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Nov 17, 2012

@cpansprout - Status changed from 'open' to 'resolved'

@p5pRT
Copy link
Author

p5pRT commented Nov 17, 2012

From @cpansprout

On Sat Nov 17 10​:14​:45 2012, sprout wrote​:

On Thu Nov 15 21​:48​:43 2012, sprout wrote​:

On Wed Sep 12 08​:54​:15 2012, nicholas wrote​:

The CV pointers for overloading methods are cached in a structure
stored in
magic which is hung onto the HV representing the symbol table. DESTROY
is
also cached here.

It's been like this for approximately forever. (I believe)

The result is that as soon as an object is destroyed, any lookups on
that
hash find their way into this code​:

if \(SvSMAGICAL\(hv\) && SvGMAGICAL\(hv\) && \!\(action &

HV_DISABLE_UVAR_XKEY)) {
MAGIC* mg;
if ((mg = mg_find((const SV *)hv, PERL_MAGIC_uvar))) {

That isn't great.

I suspect that a solution is to move struct am_table from MAGIC into a
pointer in struct hv_aux.

Stashes are rarely blessed. Couldn’t we put it in SvSTASH instead?
Just put a CV pointer there and clear it in mro_method_changed_in.

That would avoid making all iterated hashes bigger. It should also make
destruction even faster.

And it worked. See commit 8c34e50.

Except I made the mistake of slowing down destruction of objects whose
classes have no DESTROY method, so I fixed that in commit 7cc6787.

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Aug 14, 2013

@doy - Status changed from 'resolved' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Aug 14, 2013

From @doy

Commit 8c34e50 breaks the attached script. I'm not sure if it's magical
stashes or custom mros that affect it, but it made the DESTROY cache
stop being
cleared here when it's supposed to.

--
-doy

@p5pRT
Copy link
Author

p5pRT commented Aug 14, 2013

From @doy

test5.pl

@p5pRT
Copy link
Author

p5pRT commented Aug 14, 2013

From [Unknown Contact. See original ticket]

Commit 8c34e50 breaks the attached script. I'm not sure if it's magical
stashes or custom mros that affect it, but it made the DESTROY cache
stop being
cleared here when it's supposed to.

--
-doy

@p5pRT
Copy link
Author

p5pRT commented Aug 15, 2013

From @cpansprout

On Wed Aug 14 16​:42​:59 2013, doy wrote​:

Commit 8c34e50 breaks the attached script. I'm not sure if it's magical
stashes or custom mros that affect it, but it made the DESTROY cache
stop being
cleared here when it's supposed to.

$\="\n";
sub UNIVERSAL​::DESTROY { print "old" }
$x = bless[];
undef $x; # old
*UNIVERSAL​::DESTROY = sub { print "new" };
$x = bless[];
undef $x; # also old!
undef *UNIVERSAL​::DESTROY;

Mea culpa.

No generation number is associated with the DESTROY cache sneaked into
SvSTASH. If we want to fix this in maint, I think we would have to
disable the optimisation (making DESTROY as slow as before 5.8) or add a
generation number to the end of the mro_meta struct. I *think* the
latter is safe for maint, but I am not a C expert.

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Aug 18, 2013

From @cpansprout

On Wed Aug 14 22​:51​:32 2013, sprout wrote​:

On Wed Aug 14 16​:42​:59 2013, doy wrote​:

Commit 8c34e50 breaks the attached script. I'm not sure if it's magical
stashes or custom mros that affect it, but it made the DESTROY cache
stop being
cleared here when it's supposed to.

$\="\n";
sub UNIVERSAL​::DESTROY { print "old" }
$x = bless[];
undef $x; # old
*UNIVERSAL​::DESTROY = sub { print "new" };
$x = bless[];
undef $x; # also old!
undef *UNIVERSAL​::DESTROY;

Mea culpa.

No generation number is associated with the DESTROY cache sneaked into
SvSTASH. If we want to fix this in maint, I think we would have to
disable the optimisation (making DESTROY as slow as before 5.8) or add a
generation number to the end of the mro_meta struct. I *think* the
latter is safe for maint, but I am not a C expert.

This is fixed in c716b3b, which I would like to nominate for 5.18.2.

--

Father Chrysostomos

@p5pRT
Copy link
Author

p5pRT commented Dec 16, 2013

From @rjbs

This was applied to maint-5.18 as 28dfa18.

--
rjbs

@p5pRT
Copy link
Author

p5pRT commented Dec 16, 2013

@rjbs - Status changed from 'open' to 'resolved'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant