Misc #11276: [RFC] compile.c: convert to use ccan/list

• Status: Closed
• Assignee: ko1 (Koichi Sasada)

[normalperson (Eric Wong)]

Not the results I was hoping for, but maybe the LoC and stack
reductions are still worth it.

This reduces lines of code, reduces stack usage due to smaller
anchor (replaced with list_head), but unfortunately also makes the
compiled binary bigger.

On x86-64 (gcc 4.7.2)

   text	   data	    bss	    dec	    hex	filename
  99076	   1480	    152	 100708	  18964	compile.o
  93110	   1480	    152	  94742	  17216	compile.o-orig

scripts/checkstack.pl in Linux kernel shows reductions in
some functions as well as fewer functions having over
100:

before:

     1	0x00002fb3 iseq_compile_each [compile]:                 1224
     2	0x000030d8 iseq_compile_each [compile]:                 1224
     3	0x00012a33 rb_iseq_build_from_ary [compile]:            392
     4	0x00013d3d rb_iseq_build_from_ary [compile]:            392
     5	0x00011030 setup_args [compile]:                        152
     6	0x000114f7 setup_args [compile]:                        152
     7	0x000116ad rb_iseq_compile_node [compile]:              152
     8	0x00011dcb rb_iseq_compile_node [compile]:              152
     9	0x00000bc0 iseq_set_sequence [compile]:                 104
    10	0x00000f20 iseq_set_sequence [compile]:                 104
    11	0x00002116 new_insn_body [compile]:                     104
    12	0x00002271 new_insn_body [compile]:                     104
    13	0x0000f391 compile_massign_opt_lhs [compile]:           104
    14	0x0000f520 compile_massign_opt_lhs [compile]:           104
    15	0x0000f54e compile_massign_opt_lhs [compile]:           104
    16	0x0000f56d add_ensure_iseq [compile]:                   104
    17	0x0000f8b0 add_ensure_iseq [compile]:                   104
    18	0x000103e3 defined_expr [compile]:                      104
    19	0x000106ab defined_expr [compile]:                      104

after:

     1	0x00002f33 iseq_compile_each [compile]:                 1032
     2	0x00003070 iseq_compile_each [compile]:                 1032
     3	0x00013f93 rb_iseq_build_from_ary [compile]:            392
     4	0x00015f14 rb_iseq_build_from_ary [compile]:            392
     5	0x00012a5d rb_iseq_compile_node [compile]:              152
     6	0x0001336b rb_iseq_compile_node [compile]:              152
     7	0x00012450 setup_args [compile]:                        120
     8	0x000128f3 setup_args [compile]:                        120
     9	0x00000c20 iseq_set_sequence [compile]:                 104
    10	0x00000fad iseq_set_sequence [compile]:                 104
    11	0x00002766 new_insn_body [compile]:                     104
    12	0x000028b9 new_insn_body [compile]:                     104
    13	0x00010651 compile_massign_opt_lhs [compile]:           104
    14	0x000107e0 compile_massign_opt_lhs [compile]:           104
    15	0x0001080e compile_massign_opt_lhs [compile]:           104
    16	0x00011733 defined_expr [compile]:                      104
    17	0x00011a10 defined_expr [compile]:                      104

 compile.c | 451 +++++++++++++++++++++-----------------------------------------
 1 file changed, 152 insertions(+), 299 deletions(-)

[normalperson (Eric Wong)]

• Description updated (diff)

[ko1 (Koichi Sasada)]

I have no opinion about that, if there are no behavior changes.
All of operations are , same behavior and same computational complexity?

[normalperson (Eric Wong)]

SASADA Koichi [e-mail] wrote:

I have no opinion about that, if there are no behavior changes.
All of operations are , same behavior and same computational complexity?

Same behavior for enabled features. I was not able to test
OPT_STACK_CACHING since it has been broken for a while and
OPT_INSTRUCTIONS_UNIFICATION seems incomplete.

Computation complexity is shifted:

• APPEND_ELEM, INSERT_ELEM_NEXT, REPLACE_ELEM, REMOVE_ELEM are now
  branchless

• FIRST_ELEMENT, POP_ELEMENT now have branches

• list_next/list_prev/list_tail also have branches compared to
  link->next/link->prev/anchor->last

• get_*_insn need anchor (list_head) argument to stop at tail

I am slightly leaning in favor of this change.

The main advantage is reduction in LoC and common API so it is easier to
modify in the future.

On the other hand, a stripped ruby executable is already 2.8 MB and load
time just loading ruby without gems takes a few hundred milliseconds on
slow drives.

Also, see [misc #10278]

[ko1 (Koichi Sasada)]

Sorry for long absence about this ticket.
Your explanation is great so please commit it.

(I expect computation complexity by O(1), O(n) or something like that)
(I hope it may be similar linked list i know)

[ko1 (Koichi Sasada)]

• Status changed from Open to Closed

[ko1 (Koichi Sasada)]

On 2015/08/21 19:45, Eric Wong wrote:

Sorry, I am mildly against this patch now because it makes
the binary bigger and (slightly) slower.

Do you have upcoming plans/changes to compile.c which can
benefit from this? If so, you can commit my patch.

I have been distracted/busy with other projects, lately.

This comment is not filed on ticket.

I have no idea about this change, so I close it.

--
// SASADA Koichi at atdot dot net