On Sunday, 13 January 2013 at 10:24:17 UTC, Jonathan M Davis wrote:
> On Sunday, January 13, 2013 04:58:16 Chad J wrote:
>> On 01/13/2013 02:28 AM, Jonathan M Davis wrote:
>> > I really should ask Andrei why he made length require O(log n) instead
>> > O(1)...
>> > 
>> > - Jonathan M Davis
>> 
>> Are there cases where it can't be O(1)?
>
> Most definitely. Take a doubly linked list for example. Either length can be
> O(1) and splicing is then O(n), or length is O(n) and splicing is then O(1).
> That's because if you want to keep track of the length, you have to count the
> number of elements being spliced in. For instance, it's a relatively common
> mistake in C++ to use std::List's size function and compare it with 0 to see
> whether the list is empty, because size is O(n). The correct thing to do is to
> call empty and check its result.
>
> You _could_ make std::list's size function be O(1), but that would mean that
> splicing becomes O(n), which C++98 definitely did not do (though I hear that
> C++11 made the interesting choice of changing how std::list works so that size
> is O(1) and splicing is O(n); I don't know if that's good or not).
>
> std.container.slist and std.container.dlist don't define length precisely
> because it can't be O(1) given their design.
>
> - Jonathan M Davis

Yes, size is now "o(1)" in C++11.

However, splice's complexity remains "o(1)" if the list spliced from/to is the same. It only degenerates to "o(N)" if they are not the same list.

Also, note that with the old implementation, while length was "O(N)", most implementations could still cache the result it to give "0(1)" access, and only invalidate the cache when splicing with another list.

But enough off topic here I guess ;)

On Saturday, 12 January 2013 at 05:44:00 UTC, Walter Bright wrote:
> No problem. I think it's great that you're the champion for LDC.
> Having 3 robust compilers for D is only a win, and I don't think having 3 takes away from D at all.

I precisely did *not* want to drag LDC into this discussion, but I guess it was unavoidable given that I talked about it in the first part of my post, and of course because I'm the one maintaining it right now.

So, just to clarify, I took up LDC development mainly because it produces significantly faster code for some of my projects, and it would have been a shame to let it die from a marketing point of view. If I had lots of spare time (which I don't have right now) I'd certainly try to help out with a D-based compiler project instead. So it's not like I'm overly attached to LDC, emotionally – resurrecting it just seemed like the most viable short-term solution.

But yes, you are right, having 3 robust compilers for D would certainly be a good thing for D. But unfortunately, I think it would be quite a stretch to say that we have even a single such one right now.

To elaborate – and again, please don't take this as a personal attack –, every time this discussion comes up you seem to resort to the »diversity is good« cliché without ever actually responding to the arguments other people bring up. You want to stick to the DMC backend? Fine, that's your good right, but wouldn't it only be fair to share your reasons with the other people who are investing considerable amounts of work and time in »your« language?

As a note aside, I think this point is much deeper than it might appear at first. Sociology is not exactly my field, so I don't know what current research has to say about this, but at least to me it seems obvious that a healthy culture of communication is essential for the success of any non-trivial open source project. Even if it would be short-sighted to claim that all disputes can be resolved by a good technical discussion, it seems to go a long way towards reaching a consensus in most cases; and many engineers/scientists/hackers seem to regard it as the norm. On the other hand, it seems like failure to communicate the reasons behind a given decision is one of the most effective ways to cause (potential) contributors to turn away, looking for a more promising project to throw their spare time at. And to be honest, I think some of the most unfortunate events in the history of D can be directly traced back to such communication failures (I hope it is obvious what I'm alluding to here?).

But let's return to the particular topic I brought up. To recap, my impression is that several large players in the industry have started to pool their efforts regarding compiler development, as spending the ever-increasing amount of work needed to come up with their own state-of-the-art optimizer is no longer justified by the potential advantages this would offer over their competitors – maybe quite similar to the almost universal success of Linux in the OS domain.

So, in short, even if the DMC backend was technically superior to every other solution out there right now, I would be hard-pressed to make an argument for preferring it over a more widely used solution like LLVM because of this. I cannot see how putting work into a custom backend could realistically help to make D more attractive compared to other languages, so the current situation seems like a case of making things unnecessarily hard for ourselves.

Of course, as with any open source project, it would be foolish to try and tell you what to spend your time on. But I would really be interested in your long-term vision for D(MD), because as noted before I can't see any signs that the expectations at a compiler backend will drop in the future (more and more vector units in processors, the rise of ARM, ...), and even when neglecting the platform support issue, I'm not sure how good an offer D would still be if its main implementation started to perform significantly worse than common C++ compilers.

To summarize: Although there is quite a lot of promising development going on in the language space right now, I still think D has an excellent offer to make, otherwise I would left the camp long ago. But it doesn't seem wise to intentionally weaken our position in the arena by spending considerable amounts of manpower on solving a problem from the ground up for which there is already a free off-the-shelf solution that would get us at least 95% there – and the fact that our resources are limited is precisely what you seem to neglect when reciting the »diversity is good« mantra.


> For example, LDC doesn't work with VS, and so would have cost
> us the possible design win at Remedy.

In view of the above, I'm not sure how much weight this argument could carry, but I don't think it is valid in the first place: If our reference compiler was backed by LLVM, you could have just added CV8 support to it like you did for DMD. By the way, the other thing missing from LLVM regarding VS compatibility is SEH support, but DMD doesn't implement that either (LLVM actually supports EH on MinGW right now, so the implementation could likely have been re-used as a workaround, just like you did for DMD).


David

On 1/13/2013 3:10 PM, David Nadlinger wrote:
> To elaborate – and again, please don't take this as a personal attack –, every
> time this discussion comes up you seem to resort to the »diversity is good«
> cliché

Being a cliche doesn't make it invalid.

> without ever actually responding to the arguments other people bring up.
> You want to stick to the DMC backend? Fine, that's your good right, but wouldn't
> it only be fair to share your reasons with the other people who are investing
> considerable amounts of work and time in »your« language?

It's long ceased to be my language. It's a group creation.

Anyhow, I like using the dmc backend because:

1. I can completely control the user experience.

2. I can fix a problem where it should be fixed, rather than working around it.

3. I understand it completely, and so I can reasonably quickly add in things that some other back end may not support.

4. It's fast.

5. I don't run any risk of "you stole X's ideas when you worked on X's back end."

6. I enjoy working on it.


> So, in short, even if the DMC backend was technically superior to every other
> solution out there right now, I would be hard-pressed to make an argument for
> preferring it over a more widely used solution like LLVM because of this. I
> cannot see how putting work into a custom backend could realistically help to
> make D more attractive compared to other languages, so the current situation
> seems like a case of making things unnecessarily hard for ourselves.

This assumes that the existence of dmd takes away from ldc. I don't believe it does. Ldc doesn't need me.

> To summarize: Although there is quite a lot of promising development going on in
> the language space right now, I still think D has an excellent offer to make,
> otherwise I would left the camp long ago. But it doesn't seem wise to
> intentionally weaken our position in the arena by spending considerable amounts
> of manpower on solving a problem from the ground up for which there is already a
> free off-the-shelf solution that would get us at least 95% there – and the fact
> that our resources are limited is precisely what you seem to neglect when
> reciting the »diversity is good« mantra.

I'm not convinced that the effort to keep up with llvm in order to work with it is actually less time.


>> For example, LDC doesn't work with VS, and so would have cost
>> us the possible design win at Remedy.
>
> In view of the above, I'm not sure how much weight this argument could carry,
> but I don't think it is valid in the first place: If our reference compiler was
> backed by LLVM, you could have just added CV8 support to it like you did for
> DMD.

The thing is, I don't see how that would have saved time. It would have been more time - I already had CV4 support in dmd, so I had a head start on CV8. There were also a number of wacky things about Mscoff64 - how to integrate them into LLVM would have required a thorough knowledge of it on my part, and *then* I'd still have to implement it. There were also the MS64 ABI changes, which consumed a considerable amount of time. If that is not in LLVM, I would have been in for a world of effort and would have had to do some considerable surgery on it.

> By the way, the other thing missing from LLVM regarding VS compatibility is
> SEH support, but DMD doesn't implement that either (LLVM actually supports EH on
> MinGW right now, so the implementation could likely have been re-used as a
> workaround, just like you did for DMD).

I think that underestimates what all is necessary to be ABI and format compatible with VC64. SEH is only a small part of it. For example,

1. Win64 ABI, which is fundamentally different from any other platform
2. Making it compatible with and use VC++'s runtime
3. Generating MsCoff 64.
4. Adding the wacky pdata and xdata sections
5. Learning the completely undocumented CV8 format, then implementing it

Doing this all requires a fairly comprehensive understanding of the innards of the back end. If LLVM is lacking one or more of 1..5, then I wouldn't be surprised a bit if it took me considerably *longer* to do it for LLVM, and then I'd have to sell my changes to the LLVM group. (If they don't buy it, then I'm stuck with a fork I have to maintain myself. Ugh.)

On Sunday, 13 January 2013 at 23:57:48 UTC, Walter Bright wrote:
> On 1/13/2013 3:10 PM, David Nadlinger wrote:
>> To elaborate – and again, please don't take this as a personal attack –, every
>> time this discussion comes up you seem to resort to the »diversity is good«
>> cliché
>
> Being a cliche doesn't make it invalid.

You conveniently ended your citation before the »without ever actually responding to the arguments other people bring up« part.

>> You want to stick to the DMC backend? Fine, that's your good right, but wouldn't
>> it only be fair to share your reasons with the other people who are investing
>> considerable amounts of work and time in »your« language?
>
> It's long ceased to be my language. It's a group creation.
>
> Anyhow, I like using the dmc backend because:

Let me reply specifically focusing on LLVM:

> 1. I can completely control the user experience.

You can do this with LLVM as well, as you can modify its source at will. Let me also note that this means that *only you* can fix certain parts of the user experience (see for example the Optlink issues).

And besides, to be brutally honest, there has not been too much good feedback about the DMD toolchain so far, apart from compilation speeds, has there? The reason for this might of course be that users just expect a D compiler to work just like every other C/C++ compiler, but I can't see how having a potentially bigger degree of control would have helped much so far.

> 2. I can fix a problem where it should be fixed, rather than working around it.

You can do this with LLVM as well – after all, that's precisely the point of open source software. And additionally, it has the big advantage that other people can fix problems in it too, and in many cases, the LLVM people will even do the work for you.

> 3. I understand it completely, and so I can reasonably quickly add in things that some other back end may not support.

LLVM is reasonably well documented and has many useful debugging and visualization features, so I'm sure you would find your way around it quickly if you wanted to.

> 4. It's fast.

No objection there. But let me note that its weak(er) optimizer might get it disqualified as far as release builds go before this argument even counts.

> 5. I don't run any risk of "you stole X's ideas when you worked on X's back end."

You can use any code from LLVM under a BSD-like license. Would this be too restrictive? I am not a lawyer, but I'm reasonably certain it would even allow you to just take the whole LLVM code base and sell it as a closed-source package.

> 6. I enjoy working on it.

Fair enough, and all too understandable given that it's your creation! But to put it bluntly, it's a hassle for almost everybody else working on the compiler, so a project you want to attract other contributors to might not be the best environment to pursue this »hobby«.

>> So, in short, even if the DMC backend was technically superior to every other
>> solution out there right now, I would be hard-pressed to make an argument for
>> preferring it over a more widely used solution like LLVM because of this. I
>> cannot see how putting work into a custom backend could realistically help to
>> make D more attractive compared to other languages, so the current situation
>> seems like a case of making things unnecessarily hard for ourselves.
>
> This assumes that the existence of dmd takes away from ldc. I don't believe it does. Ldc doesn't need me.

Why are you even bringing up LDC here? My last post must have been very unclear in this regard? But of course, LDC does need you – after all, it uses the DMD frontend!

My entire point is that *D* needs you and your expertise: Having a veteran compiler writer on board is just about the best thing that can happen to a language effort; just because of your experience you are infinitely more productive in some areas than most of us other contributors are. What I'm trying to say is that if you want D to succeed, which I assume you do, spending (part of) your time on writing a custom backend might not be the best idea: First, you could have spent that time working on things that help to sell the language, and second, doing so actually makes life *harder* for other contributors.

>> To summarize: Although there is quite a lot of promising development going on in
>> the language space right now, I still think D has an excellent offer to make,
>> otherwise I would left the camp long ago. But it doesn't seem wise to
>> intentionally weaken our position in the arena by spending considerable amounts
>> of manpower on solving a problem from the ground up for which there is already a
>> free off-the-shelf solution that would get us at least 95% there – and the fact
>> that our resources are limited is precisely what you seem to neglect when
>> reciting the »diversity is good« mantra.
>
> I'm not convinced that the effort to keep up with llvm in order to work with it is actually less time.

Less time than what? Developing a code generator that matches theirs? You are certainly a very capable compiler engineer, but LLVM has quite a few bright minds working on it as well, full-time. I honestly don't see how »keeping up with LLVM« could be more time-consuming than replicating all of their work. Maybe you can elaborate on what exactly you meant?

But for what it's worth, Kai and I have had no problems with keeping LDC up to date with the latest LLVM version for the last few upstream releases, and we both can't spend too much time on LDC, so this likely wouldn't be a big issue for you either.

>>> For example, LDC doesn't work with VS, and so would have cost
>>> us the possible design win at Remedy.
>>
>> In view of the above, I'm not sure how much weight this argument could carry,
>> but I don't think it is valid in the first place: If our reference compiler was
>> backed by LLVM, you could have just added CV8 support to it like you did for
>> DMD.
>
> The thing is, I don't see how that would have saved time. It would have been more time - I already had CV4 support in dmd, so I had a head start on CV8. There were also a number of wacky things about Mscoff64 - how to integrate them into LLVM would have required a thorough knowledge of it on my part, and *then* I'd still have to implement it. There were also the MS64 ABI changes, which consumed a considerable amount of time. If that is not in LLVM, I would have been in for a world of effort and would have had to do some considerable surgery on it.

If I'm not mistaken, most of the related work for LLVM was done by the end of 2011.

>> By the way, the other thing missing from LLVM regarding VS compatibility is
>> SEH support, but DMD doesn't implement that either (LLVM actually supports EH on
>> MinGW right now, so the implementation could likely have been re-used as a
>> workaround, just like you did for DMD).
>
> I think that underestimates what all is necessary to be ABI and format compatible with VC64. SEH is only a small part of it.
>
> For example,
>
> 1. Win64 ABI, which is fundamentally different from any other platform
> 2. Making it compatible with and use VC++'s runtime
> 3. Generating MsCoff 64.
> 4. Adding the wacky pdata and xdata sections

I was not just blindly guessing in my last post. LLVM supports directly emitting 64 bit COFF, and as far as I know the code for writing out the RUNTIME_FUNCTION/UNWIND_INFO instances is functional.

> 5. Learning the completely undocumented CV8 format, then implementing it
>
> Doing this all requires a fairly comprehensive understanding of the innards of the back end. If LLVM is lacking one or more of 1..5, then I wouldn't be surprised a bit if it took me considerably *longer* to do it for LLVM, and then I'd have to sell my changes to the LLVM group. (If they don't buy it, then I'm stuck with a fork I have to maintain myself. Ugh.)

Given the modular design of LLVM, maintaining a fork probably wouldn't even be too bad; many companies using it e.g. have their own private backends. That being said, the LLVM folks are generally very open with accepting contributions into the main tree (except for 32 bit SEH support, where the Apple people are afraid of issues regarding that notorious Borland patent).

But note that I didn't even want to convince you that implementing a given new feature (such as CV8) for LLVM would take you _less_ time than for your own backend. I'm just saying that I would expect it to take a comparable amount of time, and even if it might take you some time to get familiar with the LLVM internals at first, I'm sure that initial cost would quickly be offset by the fact that you don't have to write *everything* on your own. I wonder if there is another production-grade backend out there that is maintained by a single person?

David

On 1/13/2013 6:07 PM, David Nadlinger wrote:
>> 1. I can completely control the user experience.
>
> You can do this with LLVM as well, as you can modify its source at will. Let me
> also note that this means that *only you* can fix certain parts of the user
> experience (see for example the Optlink issues).

I don't really want to get into a long back-and-forth thing where we just keep repeating our statements.

But as for optlink, I would have happily turned it over to anyone who expressed interest in working on it. I'd also put it on github if anyone wanted to look at it.

On 1/14/13, Walter Bright <newshound2@digitalmars.com> wrote:
> But as for optlink, I would have happily turned it over to anyone who
> expressed
> interest in working on it. I'd also put it on github if anyone wanted to
> look at it.

What's the state of Optlink, have you finished the transition to C? IIRC we've asked for this years ago.

On 1/14/13, Walter Bright <newshound2@digitalmars.com> wrote:
> I'd also put it on github if anyone wanted to look at it.

Anyway don't tease, put it online! :p

On 1/13/2013 6:40 PM, Andrej Mitrovic wrote:
> On 1/14/13, Walter Bright <newshound2@digitalmars.com> wrote:
>> I'd also put it on github if anyone wanted to look at it.
>
> Anyway don't tease, put it online! :p
>

Have fun!

https://github.com/DigitalMars/optlink

On Monday, 14 January 2013 at 02:24:38 UTC, Walter Bright wrote:
> I don't really want to get into a long back-and-forth thing where we just keep repeating our statements.

Neither do I. You listed your reasons for sticking with the DMC backend, and I tried to outline how I would judge things differently and why. I guess discussions generally work like this. :)

Anyway, thanks for responding to my post in the first place. I very much appreciate that, as I don't think you ever commented on the topic in the last few years in any detail at all, at least as far as the public forums are concerned.

David

On 1/14/13, Walter Bright <newshound2@digitalmars.com> wrote:
> Have fun!
> https://github.com/DigitalMars/optlink

Cool! Can you tell us how this code is licensed?