bugTiny C Compiler - Bugs: bug #46862, "incompatible types for...

 
 

bug #46862: "incompatible types for redefinition" check is extremely slow due to O(N) complexity implementation

Submitted by:  Vlad Frolov <frol>
Submitted on:  Sun 10 Jan 2016 01:34:41 AM UTC  
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  None
Privacy:  Public Assigned to:  None
Open/Closed:  Open

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( Jump to the original submission)

Tue 03 May 2016 04:06:37 PM UTC, comment #10:

Wow, that is cool! I cannot believe I missed this obvious change... I wonder why somebody wrote it this way. Anyway, it is great that the performance degradation can be solved without adding complexity!

Great job, Sergey!

Just to follow the numbers I provided before, I have tested the move of constant expression from the loop on the upstream TCC and for the code of 50000/50000 variables, it takes 8.2 seconds to compile on upstream TCC.

Vlad Frolov <frol>
Tue 03 May 2016 02:52:09 PM UTC, comment #9:

https://github.com/seyko2/tinycc/commit/f2d7cc6db2a4a4f5d943137f18568a6260faadbb

A constant expression removed from the loop.
If subroutine have 50000+ local variables, then currently
compilation of such code takes obly 15 sec. Was 2 min.
gcc-4.1.2 compiles such code in 7 sec. pcc -- 3.44 min.

Sergey Korshunoff <seyko>
Tue 03 May 2016 10:43:17 AM UTC, comment #8:

> Note that your upstream branch is slower than TCC upstream (mob) for some
> reason. I don't have any idea why it is like


I turned on exsymtab in ./configure script for testing pusrpose. tcc
is faster if exsymtab not enabled.

> While your patch significantly improved the situation if you compare it to GCC ....

I will try to clean this patch.

> it seems that the compilation option like you suggested

(-fno-type-redefinition-check) might be still very useful

Yes, I thinks so too.

> By the way, the patch breaks upstream TCC compilation

A patch will be modified for the upstream after testing.

Sergey Korshunoff <seyko>
Tue 03 May 2016 08:23:04 AM UTC, comment #7:

I was able to run your TCC branch, and your TCC branch with your patches and compare with upstream.

number_of_variables = 50000
number_of_local_variable_access = 50000

- TCC upstream: 110-115 seconds
- your seyko2/github TCC branch: 131-132 seconds
- your seyko2/github TCC branch with the patch: 9.0 seconds
- your seyko2/github TCC branch and TCC upstream without the incompatible types redefinition check (the "if" block is just completely commented out): 0.24-0.32 seconds (!)
- GCC 5.3: 5.7 seconds

Note that your upstream branch is slower than TCC upstream (mob) for some reason. I don't have any idea why it is like that since once I comment out the "if" block, the performance is almost the same (0.24 vs 0.26 seconds).

While your patch significantly improved the situation if you compare it to GCC, however, it seems that the compilation option like you suggested (-fno-type-redefinition-check) might be still very useful - 9.0 vs 0.3 seconds is a noticeable speed-up.

By the way, the patch breaks upstream TCC compilation due to the collision in TOK_HASH_INIT macros:

gcc -o x86_64-tcc tcc.c -DONE_SOURCE -DTCC_TARGET_X86_64 -I. -Wall -g -O0 -Wdeclaration-after-statement -Wno-deprecated-declarations -Wno-strict-aliasing -Wno-pointer-sign -Wno-sign-compare -Wno-unused-result -Wno-uninitialized -fno-strict-aliasing -lm -ldl
In file included from libtcc.c:38:0,
from tcc.c:22:
tccgen.c: In function 'sym_push2':
tccpp.c:410:23: error: called object is not a function or function pointer
#define TOK_HASH_INIT 1
^
tccgen.c:182:9: note: in expansion of macro 'TOK_HASH_INIT'
TOK_HASH_INIT(h);
^
tccpp.c:411:29: warning: statement with no effect [-Wunused-value]
#define TOK_HASH_FUNC(h, c) ((h) + ((h) << 5) + ((h) >> 27) + (c))
^
tccgen.c:184:13: note: in expansion of macro 'TOK_HASH_FUNC'
TOK_HASH_FUNC(h, c);
^
In file included from libtcc.c:39:0,
from tcc.c:22:
tccgen.c:185:9: warning: implicit declaration of function 'TOK_HASH_FINISH' [-Wimplicit-function-declaration]
TOK_HASH_FINISH(h);
^

Vlad Frolov <frol>
Mon 02 May 2016 08:52:58 PM UTC, comment #6:

Sorry, a patch is against https://github.com/seyko2/tinycc
You can look tccpp.c for [mob] version of the HASH_* macros.

Sergey Korshunoff <seyko>
Mon 02 May 2016 08:43:36 PM UTC, comment #5:

timing with 01-types-redefinition.patch
gcc-4.1.2 -- 8 sec
tcc -- 14.4 sec

(file #37054)

Sergey Korshunoff <seyko>
Mon 02 May 2016 01:11:28 PM UTC, comment #4:

The option is not a solution, but it is indeed the fastest workaround. The solution would be to use an appropriate data structure (e.g. hashmap), though, since I have no experience with the source code (and also due to the fact that I find it hard to understand what this naming might mean: (Sym **ps, int v, int t, long c)), I cannot say for certain whether it is a good idea.

Vlad Frolov <frol>
Mon 02 May 2016 12:50:00 PM UTC, comment #3:

> + number_of_local_variable_access = 50000
> - TCC: 110 seconds (almost 2 minutes)
> - GCC: 5.6 seconds


gcc-4.1.2 Yes, 8 seconds
gcc-3.4.6 No, I don't know how long it will to compile this. More then 4 minutes. 1 hour? I don't have time to check.

> However, if I comment the block for checking "incompatible types > for redefinition" in tccgen.c:168 (http://repo.or.cz/tinycc.git
> /blob/HEAD:/tccgen.c#l168), the compilation time drops to 3
> seconds!


May be an option like -fno-type-redefinition-check ?
PS: what you suggested for the option name?

Sergey Korshunoff <seyko>
Mon 02 May 2016 10:51:23 AM UTC, comment #2:

I have written a code generator (see in the attachments), which prints C code that hits the compilation time performance degradation:

$ tcc -run generator.c > test.c

I use the latest TCC mob branch where the latest commit is 6afe668ec7a11736a9418a46370af89a8c657ee8 now.

Here are some execution time measurements:

  • number_of_local_variables = 50000

+ number_of_local_variable_access = 1
- TCC: 6.2 seconds
- GCC: 0.8 seconds

+ number_of_local_variable_access = 10000
- TCC: 13 seconds
- GCC: 1.7 seconds

+ number_of_local_variable_access = 50000
- TCC: 110 seconds (almost 2 minutes)
- GCC: 5.6 seconds

  • number_of_local_variables = 100000

+ number_of_local_variable_access = 1
- TCC: 30 seconds
- GCC: 1.6 seconds

Currently, the link to the blamed code is correct, but here is the copy for future:

169 if (ps == &local_stack) {
170 for (s = *ps; s && s != scope_stack_bottom; s = s->prev)
171 if (!(v & SYM_FIELD) && (v & ~SYM_STRUCT) < SYM_FIRST_ANOM && s->v == v)
172 tcc_error("incompatible types for redefinition of '%s'",
173 get_tok_str(v, NULL));
174 }

(file #37045)

Vlad Frolov <frol>
Mon 02 May 2016 09:17:00 AM UTC, comment #1:

And where is the file?
A code snippet of the tccgen.c is welcom too (location may change)

Sergey Korshunoff <seyko>
Sun 10 Jan 2016 01:34:41 AM UTC, original submission:

I have a generated .c file with over 50k variables in one function (120MB file). It takes 37 minutes to compile it with upstream TCC, and only 1.5 minutes with GCC.

However, if I comment the block for checking "incompatible types for redefinition" in tccgen.c:168 (http://repo.or.cz/tinycc.git/blob/HEAD:/tccgen.c#l168), the compilation time drops to 3 seconds!

Vlad Frolov <frol>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #37054:  01-types-redefinition.patch added by seyko (2KiB - application/octet-stream)
file #37045:  generator.c added by frol (466B - text/x-csrc - Code generator for bug reproduction)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by seyko (Posted a comment)
  • -email is unavailable- added by frol (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-05-02 seyko Attached File- => Added 01-types-redefinition.patch, #37054
    2016-05-02 frol Attached File- => Added generator.c, #37045

    Back to the top


    Powered by Savane 3.3