[Bug c/10962] New: lookup_field is a linear search on a linked list (can be slow if large struct)

[Bug c/10962] New: lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962

           Summary: lookup_field is a linear search on a linked list (can be
                    slow if large struct)
           Product: gcc
           Version: 3.4
            Status: NEW
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pinskia@physics.uc.edu
                CC: gcc-bugs@gcc.gnu.org
 GCC build triplet: powerpc-apple-darwin6.6
  GCC host triplet: powerpc-apple-darwin6.6
GCC target triplet: powerpc-apple-darwin6.6

According to the comments of lookup_field, it seems that TYPE_LANG_SPECIFIC should 
have the sorted list for a binary search.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia@physics.uc.edu  2003-05-24 02:44 -------
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.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|0000-00-00 00:00:00         |2003-05-25 18:17:37
               date|                            |


------- Additional Comments From pinskia@physics.uc.edu  2003-05-25 18:17 -------
I am working on this one.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned@gcc.gnu.org      |pinskia@physics.uc.edu
             Status|ASSIGNED                    |NEW





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2003-05-25 18:17:37         |2003-05-25 21:17:38
               date|                            |





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia@physics.uc.edu  2003-05-26 02:43 -------
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).



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.4                         |3.3.1





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia@physics.uc.edu  2003-05-26 03:09 -------
Only problem with the patch is that it does not work with pch, I will fix that.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia@physics.uc.edu  2003-05-26 03:41 -------
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.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pinskia@physics.uc.edu      |unassigned@gcc.gnu.org
             Status|ASSIGNED                    |NEW





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2003-05-25 21:17:38         |2003-05-27 11:41:29
               date|                            |





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned@gcc.gnu.org      |pinskia@physics.uc.edu
             Status|ASSIGNED                    |NEW





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [Regression 2.95.2-3.4] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2003-05-27 11:41:29         |2003-05-27 11:42:09
               date|                            |





------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [3.3/3.4 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia@physics.uc.edu  2003-06-02 00:19 -------
Waiting on me getting my copyright assigment.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [3.3/3.4 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |SUSPENDED


------- Additional Comments From pinskia@physics.uc.edu  2003-06-04 14:10 -------
suspended untill I get my copyright assignment on file.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug c/10962] [3.3/3.4 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at physics dot uc dot edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia at physics dot uc dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.3.1                       |3.3.2

[Bug c/10962] [3.3/3.4 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|SUSPENDED                   |NEW
   Last reconfirmed|2003-05-27 11:42:09         |2003-07-16 16:29:20
               date|                            |


------- Additional Comments From pinskia at gcc dot gnu dot org  2003-07-16 16:29 -------
I just recieved cvs access will check in later today after class.

[Bug c/10962] [3.3/3.4 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[cvs-commit at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From cvs-commit at gcc dot gnu dot org  2003-07-16 18:46 -------
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

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at physics dot uc dot edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia at physics dot uc dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[3.3/3.4 regression]        |[3.3 regression]
                   |lookup_field is a linear    |lookup_field is a linear
                   |search on a linked list (can|search on a linked list (can
                   |be slow if large struct)    |be slow if large struct)


------- Additional Comments From pinskia at physics dot uc dot edu  2003-07-16 18:49 -------
Only a 3.3 regression now.

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[steven at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|3.4                         |3.3


------- Additional Comments From steven at gcc dot gnu dot org  2003-07-25 10:09 -------
Not a 3.4 bug

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


------- Additional Comments From pinskia at gcc dot gnu dot org  2003-09-05 14:34 -------
Fixed for 3.3.2 and 3.4.

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[cvs-commit at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From cvs-commit at gcc dot gnu dot org  2003-09-05 14:33 -------
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

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[mmitchel at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org


------- Additional Comments From mmitchel at gcc dot gnu dot org  2003-09-05 07:07 -------
The patch is OK, please check it in.

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962


pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2003-07-16 16:29:20         |2003-08-17 23:04:21
               date|                            |

[Bug c/10962] [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct)

[pinskia at gcc dot gnu dot org]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10962



------- Additional Comments From pinskia at gcc dot gnu dot org  2003-08-09 13:45 -------
Submitted the 3.3 patch for comments: <http://gcc.gnu.org/ml/gcc-patches/2003-08/
msg00499.html>.