Bug 10962 - [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)
Summary: [3.3 regression] lookup_field is a linear search on a linked list (can be slo...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c (show other bugs)
Version: 3.3
: P2 normal
Target Milestone: 3.3.2
Assignee: Andrew Pinski
URL:
Keywords: compile-time-hog
Depends on:
Blocks:
 
Reported: 2003-05-24 02:29 UTC by Andrew Pinski
Modified: 2003-09-05 14:34 UTC (History)
2 users (show)

See Also:
Host: powerpc-apple-darwin6.6
Target: powerpc-apple-darwin6.6
Build: powerpc-apple-darwin6.6
Known to work:
Known to fail:
Last reconfirmed: 2003-08-17 23:04:21


Attachments
Patch for 3.3. (1.36 KB, patch)
2003-05-25 19:07 UTC, Andrew Pinski
Details | Diff
Patch for 3.4 (2.77 KB, patch)
2003-05-27 11:51 UTC, Andrew Pinski
Details | Diff
Patch for 3.4 (4.26 KB, text/plain)
2003-05-31 12:24 UTC, Andrew Pinski
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2003-05-24 02:29:44 UTC
According to the comments of lookup_field, it seems that TYPE_LANG_SPECIFIC should 
have the sorted list for a binary search.
Comment 1 Andrew Pinski 2003-05-24 02:44:23 UTC
This is a regression caused by which removed TYPE_LANG_SPECIFIC.:
Fri Oct 15 02:37:28 1999  Alastair J. Houghton <ajh8@doc.ic.ac.uk>
                          Mumit Khan  <khan@xraylith.wisc.edu>

        * c-parse.in (component_decl): Support anonymous struct/union.
        (%expect): Update.
        * c-parse.y: Regenerate.
        * c-parse.c: Likewise.
        * objc/objc-parse.y: Likewise.
        * objc/objc-parse.c: Likewise.
        * c-decl.c (finish_struct): Don't sort the fields.
        (field_decl_cmp): Delete unused function.
Comment 2 Andrew Pinski 2003-05-25 18:17:37 UTC
I am working on this one.
Comment 3 Andrew Pinski 2003-05-25 19:07:36 UTC
Created attachment 4072 [details]
Patch for 3.3.

this patch just adds back stuff that were removed and adds check for anymous
structs/unions
ChangeLog:

2003-05-25  Andrew Pinski  <pinskia@physics.uc.edu>
	* c-decl.c (field_decl_cmp): add back function.
	(finish_struct): sort fields if number greater than 15
	and no anymous structs/unions.
Comment 4 Andrew Pinski 2003-05-26 02:43:07 UTC
biggen.sh from PR10760:
before the patch:
[zhivago2:~/src/gccPRs/10760] pinskia% sh biggen.sh 20000 > big.c
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
29.270u 0.550s 0:31.55 94.5%    0+0k 0+4io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% sh biggen.sh 10000 > big.c
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
6.530u 0.220s 0:06.95 97.1%     0+0k 0+0io 0pf+0w
after the patch:
[omni:~/src/gccPRs/10760] pinskia% sh biggen.sh 20000 > big.c
[omni:~/src/gccPRs/10760] pinskia% time gcc -S big.c
7.500u 0.630s 0:10.36 78.4%     0+0k 0+4io 0pf+0w
[omni:~/src/gccPRs/10760] pinskia% time gcc -S big.c
3.180u 0.290s 0:04.50 77.1%     0+0k 0+2io 0pf+0w

So I removed the x^2 behavior of gcc, and turned it into a x log(x), because the lookup is now 
log(x).
Comment 5 Andrew Pinski 2003-05-26 03:09:29 UTC
Only problem with the patch is that it does not work with pch, I will fix that.
Comment 6 Andrew Pinski 2003-05-26 03:41:54 UTC
Found the problem is that the indendifiers must be the same memory location, so that the 
cpp_reader's hash_table must contain the indendifiers from the header so therefore I need PCH 
help.
Comment 7 Andrew Pinski 2003-05-27 11:51:37 UTC
Created attachment 4088 [details]
Patch for 3.4

ChangeLog (no tabs):
* ggc.h: add header guards.
* c-decl.c (field_decl_cmp): add back function.
(resort_sorted_fields): New.
(finish_struct): sort fields if number greater than 15
	and no anymous structs/unions.
* c-tree.h: add ggc.h
(lang_type_s): new struct.
(lang_type_s_1): pointer to lang_type_s.
(lang_type): use lang_type_s_1 as s.
(resort_sorted_fields): New prototype.
* c-typeck.c (lookup_field): use s in lang_type.
Comment 8 Andrew Pinski 2003-05-31 12:24:53 UTC
Created attachment 4118 [details]
Patch for 3.4

ChangeLog:
2003-05-30  Andrew Pinski  <pinskia@physics.uc.edu>

	* ggc.h: Add header guards.
	* c-decl.c (finish_struct): Sort fields if
	number greater than 15 and there are no
	anonymous structs/unions.
	* c-common.h: Include ggc.h.
	(sorted_fields_type): New struct.
	(field_decl_cmp): New prototype.
	(resort_sorted_fields): New prototype.
	(DECL_DECLARES_TYPE_NON_TEMPLATE_P): New macro.
	* c-tree.h: (lang_type): Use pointer to sorted_fields_type
	as s, removing other fields.
	* c-typeck.c (lookup_field): Use s in lang_type.
These were mostly moved from cp/class.c:
	* c-common.c (field_decl_cmp): New static function.
	(field_decl_cmp): New function.
	(resort_sorted_fields): New function.


cp/ChangeLog:
2003-05-30  Andrew Pinski  <pinskia@physics.uc.edu>

	* class.c (field_decl_cmp): Remove.
	(resort_field_decl_cmp): Remove.
	(resort_sorted_fields): Remove.
	(add_fields_to_vec): Rename to ...
	(add_fields_to_record_type): this.
	(finish_struct_1): Change to be using
	sorted_fields_type's fields.
	* cp-tree.h (lang_decl): In lang_decl_u3
	change sorted_fields to be a pointer to
	sorted_fields_type.
	(resort_sorted_fields): Remove prototype.
	* search.c (lookup_field_1): Change to be using
	sorted_fields_type's fields.
Comment 9 Andrew Pinski 2003-06-02 00:19:29 UTC
Waiting on me getting my copyright assigment.
Comment 10 Andrew Pinski 2003-06-04 14:10:13 UTC
suspended untill I get my copyright assignment on file.
Comment 11 Andrew Pinski 2003-07-16 16:29:20 UTC
I just recieved cvs access will check in later today after class.
Comment 12 CVS Commits 2003-07-16 18:46:01 UTC
Subject: Bug 10962

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	pinskia@gcc.gnu.org	2003-07-16 18:45:56

Modified files:
	gcc            : ChangeLog c-common.c c-common.h c-decl.c 
	                 c-tree.h c-typeck.c ggc.h 
	gcc/cp         : ChangeLog class.c cp-tree.h search.c 

Log message:
	2003-07-16  Andrew Pinski  <pinskia@physics.uc.edu>
	ChangeLog:
	PR c/10962
	* ggc.h: Add header guards.
	* c-decl.c (finish_struct): Sort fields if
	number greater than 15 and there are no
	anonymous structs/unions.
	* c-common.h: Include ggc.h.
	(sorted_fields_type): New struct.
	(field_decl_cmp): New prototype.
	(resort_sorted_fields): New prototype.
	(DECL_DECLARES_TYPE_NON_TEMPLATE_P): New macro.
	* c-tree.h: (lang_type): Use pointer to sorted_fields_type
	as s, removing other fields.
	* c-typeck.c (lookup_field): Use s in lang_type.
	These were mostly moved from cp/class.c:
	* c-common.c (field_decl_cmp): New static function.
	(field_decl_cmp): New function.
	(resort_sorted_fields): New function.
	cp/ChangeLog:
	* class.c (field_decl_cmp): Remove.
	(resort_field_decl_cmp): Remove.
	(resort_sorted_fields): Remove.
	(add_fields_to_vec): Rename to ...
	(add_fields_to_record_type): this.
	(finish_struct_1): Change to be using
	sorted_fields_type's fields.
	* cp-tree.h (lang_decl): In lang_decl_u3
	change sorted_fields to be a pointer to
	sorted_fields_type.
	(resort_sorted_fields): Remove prototype.
	* search.c (lookup_field_1): Change to be using
	sorted_fields_type's fields.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.527&r2=2.528
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-common.c.diff?cvsroot=gcc&r1=1.429&r2=1.430
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-common.h.diff?cvsroot=gcc&r1=1.190&r2=1.191
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-decl.c.diff?cvsroot=gcc&r1=1.405&r2=1.406
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-tree.h.diff?cvsroot=gcc&r1=1.119&r2=1.120
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-typeck.c.diff?cvsroot=gcc&r1=1.244&r2=1.245
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ggc.h.diff?cvsroot=gcc&r1=1.55&r2=1.56
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/ChangeLog.diff?cvsroot=gcc&r1=1.3528&r2=1.3529
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/class.c.diff?cvsroot=gcc&r1=1.552&r2=1.553
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/cp-tree.h.diff?cvsroot=gcc&r1=1.878&r2=1.879
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/cp/search.c.diff?cvsroot=gcc&r1=1.275&r2=1.276

Comment 13 Andrew Pinski 2003-07-16 18:49:05 UTC
Only a 3.3 regression now.
Comment 14 Steven Bosscher 2003-07-25 10:09:20 UTC
Not a 3.4 bug
Comment 15 Andrew Pinski 2003-08-09 13:45:21 UTC
Submitted the 3.3 patch for comments: <http://gcc.gnu.org/ml/gcc-patches/2003-08/
msg00499.html>.
Comment 16 Mark Mitchell 2003-09-05 07:07:28 UTC
The patch is OK, please check it in.
Comment 17 CVS Commits 2003-09-05 14:33:13 UTC
Subject: Bug 10962

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-3_3-branch
Changes by:	pinskia@gcc.gnu.org	2003-09-05 14:33:07

Modified files:
	gcc            : ChangeLog c-decl.c 

Log message:
	2003-09-05  Andrew Pinski <pinskia@physics.uc.edu>
	
	PR c/10962
	* c-decl.c (field_decl_cmp): Add back function.
	(finish_struct): Sort fields if number greater than 15
	and no anymous structs/unions.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-3_3-branch&r1=1.16114.2.721&r2=1.16114.2.722
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-decl.c.diff?cvsroot=gcc&only_with_tag=gcc-3_3-branch&r1=1.356.2.12&r2=1.356.2.13

Comment 18 Andrew Pinski 2003-09-05 14:34:22 UTC
Fixed for 3.3.2 and 3.4.