[cfe-dev] Syntactic order of CXXBaseOrMemberInitializers

[Marshall Clow]

On May 20, 2010, at 11:23 AM, Douglas Gregor wrote:

> 
> On May 20, 2010, at 10:26 AM, Abramo Bagnara wrote:
> 
>> Il 20/05/2010 18:52, Douglas Gregor ha scritto:
>>> 
>>> 
>>> Sent from my iPhone
>>> 
>>> On May 19, 2010, at 4:40 AM, Abramo Bagnara <abramo.bagnara at gmail.com> wrote:
>>> 
>>>> 
>>>> As currently the initializers are reordered to match member order in
>>>> record declaration there is no easy way for an AST consumer to know in
>>>> which order the initializers were written in the source file.
>>> 
>>> Originally, I had imagined that we would compare based on source locations, and perhaps add an "implicit" bit for implicitly-generated initializers. Does that not work?
>> 
>> We thought the same, but the fact that a sorting algorithm lead to a
>> worst case of O(n*log(n)) or O(n*2) calls to non trivial source location
>> comparison has worried us.
> 
> It seems highly unlikely that N will grow large enough for this to ever matter, since N should only include explicitly-written base classes. 

Several years ago, I reported a performance problem with Metrowerks compiler.
I was defining several hundred traits classes; and the compiler would keep the machine (a PowerPC) pegged for about 90 seconds compiling that file.

I sent this to the Metrowerks folks, and rather sheepishly got a response a couple of days later:
	"Oops. That was an N^2 loop. Try this new version; it's an log(N) version"

and the file compiled in about three seconds with the new compiler.

My (uninformed) opinion is to try to avoid the N^2 algorithm; because users write the damndest code. ;-)

-- Marshall