10962 – [3.3 regression] lookup_field is a linear search on a linked list (can be slow if large struct) (original) (raw)

Description Drea 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 Drea 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 Drea Pinski 2003-05-25 18:17:37 UTC

I am working on this one.

Comment 3 Drea 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 Drea 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 Drea 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 Drea 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 Drea Pinski 2003-05-27 11:51:37 UTC

Created attachment 4088 [details] Patch for 3.4

ChangeLog (no tabs):

Comment 8 Drea 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 Drea Pinski 2003-06-02 00:19:29 UTC

Waiting on me getting my copyright assigment.

Comment 10 Drea Pinski 2003-06-04 14:10:13 UTC

suspended untill I get my copyright assignment on file.

Comment 11 Drea Pinski 2003-07-16 16:29:20 UTC

I just recieved cvs access will check in later today after class.

Comment 13 Drea 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 16 Mark Mitchell 2003-09-05 07:07:28 UTC

The patch is OK, please check it in.

Comment 18 Drea Pinski 2003-09-05 14:34:22 UTC

Fixed for 3.3.2 and 3.4.