develooper Front page | perl.perl5.porters | Postings from February 2006

RFC - op-next vs op-sibling (another hairbrained optimization)

Thread Next
From:
Jim Cromie
Date:
February 24, 2006 09:50
Subject:
RFC - op-next vs op-sibling (another hairbrained optimization)
Message ID:
43FF4738.9090906@gmail.com

Aeons ago, I proposed a scheme
http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-07/msg00830.html
to combine storage for op-next and op-sibling.
Id like to revisit it now.

Start with the premises that:

op-sibling, along with optype-specific pointers, is set during bottom-up
parsing, it carries sequence and expression dependencies of the source code.
op-next pointers are all null at this point. 

in the execution-order pass, the tree is linked
into a list using the op_next pointer, giving fast execution.
Once this linkage is done, op-sibling has mostly served its purpose.

IIUC, its only other use is to support uninitialized var reporting.


I propose to:

1, abstract out ->op_sibling and ->op_next references with macros;
PERL_OP_NEXT,  PERL_OP_SETNEXT,
PERL_OP_SIBLING, PERL_OP_SETSIBLING,
The macros will let us instrument those operations with -DFoo builds 
(and patches)

2. replace op_sibling, op_next with struct { next; sibling; } op;
validating the abstraction in 1.  This is done by defining  
OP_NEXT_SIBL_IMP
as 0, 1, or 2, for  legacy, struct, union representations respectively,
overridable with -Accflags

3. save op_sibling values off to a hash, and redirect PERL_OP_SIBLING
to look up from that hash once op_next has been set (which we can remember
in a new flag  bit taken from spare).  Ive based my hash on the 
ptr-table* code in sv.c
Ive arbitrarily put the hash-root in perlvar.h, since its global, and so 
is opcode (shared between threads)

With struct in place, PERL_OP_SIBLING can in principle cross-check
the 2 values (hash and field), pre-validating the switch from struct to 
union.


By itself, this wont save memory, but it does segregate the less-used 
(cooler) field,
leaving the hotter fields in a denser memory layout, which may improve 
caching behavior.
(cache works better on C loops than perl loops :(

Possible optimizations:

uninit-var reporting code may only need some of the op-siblings,
for some op-types (ex: SVOPs ??)
If some are un-needed, they dont have to be added to the hash.


Given that basic-blocks are threaded into an op-next list, a 
corresponding op-siblings
list (ie array) could also be created.  This fails to take advantage of 
any selective hashing,
but that may not be practical anyway.  Presumably, the siblings-list 
would be reachable
if attached to the cops. 

The tree is linklist()ed in a tail-recursive manner, so it might just work
to relink an entire tree in one upwards movement, and create both 
op-next and opsibling
vectors on 2 stacks, but Im starting to flap furiously here, and its 
arguably too clever by half;
using the hash as intermediate storage is nice and explicit, and supports
instrumentation/debug better.

Repeating,
the hash may be needed until the op-next list is complete, then that 
list can be followed,
and the op-sibling retrieved from that hash for each OP in the list,
which is then added to the newly allocated list.  Once this is done, the 
hash can probably be cleared.

Turn off hashing/saving of op-sibling entirely.  With storage separated,
this will reduce total memory required.  Although this kills uninit-var
reporting, a runtime flag could enable/disable it
-w could enable, (perhaps socially unacceptable to alter the default)
-? could disable it (opt-in efficiency - much better)



The attached patch does 1 & 2, and passes all but 3 tests.
they're all 'say' tests, which Im too lazy to look carefully at.
Its puzzling to me why pp_print doesnt show problems, only pp_say,
which IIUC actually uses pp_print.  Robin ?


t/run/switchd..............................................ok
t/run/switches.............................................# Failed at 
run/switches.t line 307
#      got 'Hello, world!'
# expected 'Hello, world!
# '
# Failed at run/switches.t line 313
#      got 'Hello, world!'
# expected 'Hello, world!
# '
# Failed at run/switches.t line 318
#      got 'Hello, world!'
# expected 'Hello, world!
# '
# Failed at run/switches.t line 323
#      got 'Hello, world!'
# expected 'Hello, world!
# '
FAILED at test 28
t/run/switchn..............................................ok
t/run/switchp..............................................ok


Once these bugs are fixed, IMO the patch is safe to apply (it changes 
nothing)
and it prepares for the harder parts.


As ever, please point out any flaws (fatal or otherwize) in this plan.

thanks
jimc


Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About