Name: rmT116609 Date: 07/15/2003


FULL PRODUCT VERSION :
java version "1.4.2"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2-b28)
Java HotSpot(TM) Client VM (build 1.4.2-b28, mixed mode)

FULL OS VERSION :
Microsoft Windows 2000 [Version 5.00.2195]

EXTRA RELEVANT SYSTEM CONFIGURATION :
P4 1800 1Gmem

A DESCRIPTION OF THE PROBLEM :
When an interface extends from many other interfaces the javac compiler will take very long to compile. I tested several versions of the JDK with a certain set of files. These are the compile times:

  j2sdk1.4.0_04 5204 ms
  j2sdk1.4.1_02 13703 ms
  j2sdk1.4.1_03 13954 ms
  j2sdk1.4.2 15641 ms

When the number of extending interfaces is increased the compile time increases exponentially (or at least much worse then linear).

You may argue that so many extending interfaces is not a real life example, but our product generates java source files that use such constructs. We encounter unexceptable build times that are 2-3 times slower then with 1.4.0.

It is interesting that running the compiler under -verbose shows that the '[checking ...]' phase is the culprit.

THE TEST-SET:
The above numbers were gathered with a plain invocation of javac with 100m heap size. There were 2 packages: one with 120 interfaces with 10 methods each and one with 120 interfaces that extend all 120 interfaces from the first package and define 10 additional methods.

I have build a testset-generator that will generate and compile the above testset in all sorts of combinations. I am more then happy to supply this generator if that would help (just mail me).

I used the generator to generates the following table of compile times (in ms):

--------------------------------------
#interfaces 1.4.1_02 1.4.2
        1.4.0 1.4.1_03
--------------------------------------
20 1156 1313 1109 1140
21 1234 1125 1141 1141
22 1266 1140 1203 1203
23 1250 1188 1203 1250
24 1266 1172 1171 1250
25 1297 1235 1375 1250
26 1328 1187 1297 1453
27 1781 1594 1453 1375
28 1375 1422 1344 1563
29 1500 6453 1766 1453
30 1625 1406 1765 1844
31 1984 1344 1375 1500
32 1828 1735 2125 1703
33 1469 1453 1468 1500
34 1515 1438 1516 1609
35 1766 1453 1516 1610
36 1579 1688 1546 1875
37 1593 1594 1625 1859
38 1687 1844 2000 1968
39 2047 2156 2282 2438
40 2797 2578 2093 2000
41 1875 2016 1890 2156
42 1797 1797 1859 2016
43 1797 1891 2093 2078
44 1813 1968 2157 2219
45 1828 2078 1984 3016
46 2203 2500 2422 2672
47 2297 2282 2140 2547
48 2079 2250 2219 2578
49 2031 2219 2844 2531
50 2172 2407 2375 2515
51 2094 2359 2484 2735
52 2281 2594 2938 2812
53 2219 2625 2625 2781
54 2204 2594 2719 2937
55 2218 2781 2891 2953
56 2188 2766 2875 3047
57 2422 2953 3000 3125
58 2312 2906 3078 3234
59 2407 3156 3547 3969
60 2297 3141 3438 3407
61 2266 3141 3032 3328
62 2532 3312 3203 3656
63 2422 3500 3672 3453
64 2391 3266 3515 4329
65 2546 3766 4281 4156
66 2985 3547 3859 3968
67 2500 3672 3953 4157
68 2609 4172 3750 4109
69 2625 4219 3922 4219
70 2578 4281 4172 4656
71 3297 5281 4390 5015
72 3547 4562 5375 6312
73 3562 4422 4375 5265
74 2782 4641 4907 5484
75 2813 4672 4813 5234
76 3531 4781 4828 6094
77 3250 4844 4860 5422
78 3015 4953 5047 6703
79 3204 5485 5219 6078
80 3594 5437 5547 6125
81 3891 5437 6093 6140
82 3031 5672 5907 6640
83 3203 6000 5688 7469
84 3782 6938 6015 6907
85 3563 7860 6703 7062
86 3359 6172 6343 8500
87 3438 6485 6329 7156
88 3797 6609 6656 7640
89 3515 6594 6656 7547
90 3453 7000 7203 7641
91 3766 7031 7016 8500
92 3813 7156 7250 8313
93 3641 7672 7688 8688
94 3750 7672 7578 9250
95 3891 7938 7687 8829
96 4375 8250 8235 9297
97 4031 8516 8594 9562
98 4156 8343 8532 9578
99 4031 9343 8828 9906
100 4266 9281 9422 10063
101 4437 9469 9437 10609
102 4282 9829 9500 10937
103 4375 9797 9579 11000
104 4360 10047 10453 11328
105 4563 11031 10234 11750
106 4953 10593 10218 11562
107 4937 10922 10625 12109
108 4672 10734 11079 12578
109 5172 10890 11031 12359
110 4953 11328 11047 12906
111 4484 11484 11687 13094
112 4734 12093 12062 13109
113 4828 12359 11718 14204
114 5141 12470 12235 13626
115 4923 12970 14126 14016
116 5157 12563 12625 14313
117 5265 12735 13344 15282
118 5407 13126 13297 15516
119 5359 13672 13251 15251
120 5204 13703 13954 15641
121 5484 13875 13688 17266
122 5485 14969 14423 17016
123 5923 14688 14719 16673
124 6828 14750 15078 17219
125 5719 15875 15938 17313
126 5938 15688 15282 17875
127 5891 16266 16203 18469
128 6204 15985 16344 18797
129 6015 17469 16657 19329
130 5843 16704 16688 19282
131 5953 16984 17376 20094
132 6828 18375 22000 22734
133 6656 43313 18344 20953
134 6688 19515 18375 21860
135 6953 19422 19156 21828
136 6672 19438 19469 22891
137 8656 20375 19594 22609
138 6688 20984 20110 22953
139 7359 20563 20969 24703
--------------------------------------

When you graph these numbers you can see the exponential behaviour.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
As described above: compile a testset with 1.4.0 compiler and with 1.4.2 compiler and compare time used.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The 1.4.0 and 1.4.2 compiler should show compile times that are equivalent or the 1.4.2 compiler should have improved behaviour.
ACTUAL -
The 1.4.0 compiler shows linear behaviour while the 1.4.2 compiler shows exponential behaviour

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
The complete testset would be too large.

Ad-hoc testset description:

 in Package a (containing a total of 120 files):
   interface xyzzy_$i { <FOR $i = 0 TO 120>
     void xyzzy_$i_method_$j(); <FOR $j = j TO 10>
   }

 in Package b (containing a total of 120 files):
   interface xyzzy_$i extends <FOR $i = 0 TO 120>
         a.xyzzy_$k { <FOR $k = 0 TO 120>
     void plugh_$i_method_$j(); <FOR $j = j TO 10>
   }

---------- END SOURCE ----------
(Incident Review ID: 189487)
======================================================================