On Tue, 12 Aug 2008 04:23:55 +0400, bearophile <bearophileHUGS@lycos.com> wrote:

> bearophile:
>> But I don't understand why for example getValue() can be a CT function, while DoCheckMen() can't.
>

because the following code is wrong due to mixing of compile time and run-time constants:

template square(int a)
{
   const int foo = a * a;
}

int getSquare(int a)
{
    return square!(a); // you can't instantiate a template
    // with a variable (unless it is an alias, which is not a case)
}

> Anyway, even using those few small CT functions the compile time decreases from 1.81 s to about 0.91 s on my PC, and the memory used from about 42 MB to 32 MB, I don't know why.
>
> Bye,
> bearophile

That's because compiler doesn't have to instantiate all those hundreds of templates (and hold them in memory until exit).

I took a step forward and eliminated all the templates. Note that now the result is returned as a string due to a lack of compile time text output (it will be output once per template/fuction instance).

int numChildren(int men, int women) {
    return 100 - men - women;
}

bool isEven(int number) {
    return !(number & 1);
}

int getValue(int men, int women, int children) {
    return 3 * men + 2 * women + children / 2;
}

bool isOverflow(int men, int women = 0) {
    return getValue(men, women, 0) > 100;
}

char[] DoCheckMen(int men) {
    return CheckWomen(men, 0, 100 - men);
}

char[] itoa(int i)
{
    if (i < 10) {
        return "0123456789"[i..i+1];
    } else {
        return itoa(i / 10) ~ itoa(i % 10);
    }
}

char[] CheckSolution(int men, int women, int children) {
    if (isEven(children) && getValue(men,women,children) == 100) {
        return "Men:\t"~itoa(men)~"\tWomen:\t"~itoa(women)~"\tChildren:\t"~itoa(children)~"\n";
    } else {
        return "";
    }
}

char[] DoCheckWomen(int men, int women) {
    return CheckSolution(men, women, numChildren(men, women));
}

char[] CheckWomen(int men, int first, int last) {
    if (first == last) {
        return DoCheckWomen(men, first);
    }

    if (isOverflow(men, first)) {
        return "";
    }

    return DoCheckWomen(men, first) ~ CheckWomen(men, first+1, last);
}

char[] CheckMen(int first, int last) {
    if (first == last) {
        return DoCheckMen(first);
    }
    if (isOverflow(first)) {
        return "";
    }

    return DoCheckMen(first) ~ CheckMen(first+1, last);
}

const char[] solutios = CheckMen(0, 100);
pragma(msg, solutios);

Koroskin Denis:
>      return square!(a); // you can't instantiate a template
>      // with a variable (unless it is an alias, which is not a case)

Uhm... I think there can be ways to modify DMD to allow a better mixing of CT functions and templates.


> That's because compiler doesn't have to instantiate all those hundreds of templates (and hold them in memory until exit).

Now the compile time is around 0.06 s, way less.
Such difference is very interesting. A functional language (even an interpreted one) can probably execute the code relative to those templates in way less than the original 1.8 seconds (it amounts to almost 4 billion clock ticks, it's a lot of computations!).
I presume DMD somehow contains an almost complete interpreter of D language (with GC) plus a functional language interpreter for the templates that can probably be improved, plus the compiler itself, it sounds like a lot of complexity/stuff :-)


> Note that now the result is returned as a string due to a lack of compile time text output (it will be output once per template/fuction instance).

Good idea, I'll remember it.

Bye,
bearophile

On Tue, 12 Aug 2008 05:15:09 +0400, bearophile <bearophileHUGS@lycos.com> wrote:

> Koroskin Denis:
>>      return square!(a); // you can't instantiate a template
>>      // with a variable (unless it is an alias, which is not a case)
>
> Uhm... I think there can be ways to modify DMD to allow a better mixing of CT functions and templates.
>
>

Yes, I think it can be asked as an enhancement. As a result this function becomes Compile-Time evalualable only, so it will yield "Can not evaluate at run-time" if used with non-constant parameters. I like that bridge between functions and templates and it would reduce code complexity.

>> That's because compiler doesn't have to instantiate all those hundreds of
>> templates (and hold them in memory until exit).
>
> Now the compile time is around 0.06 s, way less.
> Such difference is very interesting. A functional language (even an interpreted one) can probably execute the code relative to those templates in way less than the original 1.8 seconds (it amounts to almost 4 billion clock ticks, it's a lot of computations!).
> I presume DMD somehow contains an almost complete interpreter of D language (with GC) plus a functional language interpreter for the templates that can probably be improved, plus the compiler itself, it sounds like a lot of complexity/stuff :-)
>
>

Yes, it is. And Walter writes it on his own :(

>> Note that now the
>> result is returned as a string due to a lack of compile time text output
>> (it will be output once per template/fuction instance).
>
> Good idea, I'll remember it.
>
> Bye,
> bearophile

Koroskin Denis:
> Yes, it is. And Walter writes it on his own :(

I think there can be ways to reduce such complexity (and add a compile-time GC).

I think in a short time LLVM will become good enough as backend for D (what are the practical problems left that make this adoption possible? In my benchmarks (all the Shootout C benchmarks) LLMV isn't efficient as GCC yet, but it's probably already more efficient than the backend of DMD so that's not a problem, and it's open source), what I mean it can become the backend for the official D compiler developed by Walter (and the D community). (side question: can the front-end for LLMV be written in D? I hope so).

Does Walter oppose moving to develop with this back-end? I think it will lead to solve some of the main current problems in the D development process (such switch can be aligned to a switch to phobos+tango too).

Bye,
bearophile

On Tue, 12 Aug 2008 15:45:15 +0400, bearophile <bearophileHUGS@lycos.com> wrote:

> Koroskin Denis:
>> Yes, it is. And Walter writes it on his own :(
>
> I think there can be ways to reduce such complexity (and add a compile-time GC).
>
> I think in a short time LLVM will become good enough as backend for D (what are the practical problems left that make this adoption possible? In my benchmarks (all the Shootout C benchmarks) LLMV isn't efficient as GCC yet, but it's probably already more efficient than the backend of DMD so that's not a problem, and it's open source), what I mean it can become the backend for the official D compiler developed by Walter (and the D community). (side question: can the front-end for LLMV be written in D? I hope so).
>
> Does Walter oppose moving to develop with this back-end? I think it will lead to solve some of the main current problems in the D development process (such switch can be aligned to a switch to phobos+tango too).
>
> Bye,
> bearophile

Nice idea. IIRC, Walter isn't going to replace its own backend to (or even look at) GCC because of the GPL license. However, LLVM has a BSD-like license and that could be an option.

It still lacks some features, but it evolves *daily* unlike DMD backend. For example, chances are we won't ever get a native x86_64 codegen from DM backend, but we will get it with LLVM eventually (very soon, hopefully).

Koroskin Denis wrote:
> On Tue, 12 Aug 2008 15:45:15 +0400, bearophile <bearophileHUGS@lycos.com> wrote:
> 
>> Koroskin Denis:
>>> Yes, it is. And Walter writes it on his own :(
>>
>> I think there can be ways to reduce such complexity (and add a compile-time GC).
>>
>> I think in a short time LLVM will become good enough as backend for D (what are the practical problems left that make this adoption possible? In my benchmarks (all the Shootout C benchmarks) LLMV isn't efficient as GCC yet, but it's probably already more efficient than the backend of DMD so that's not a problem, and it's open source), what I mean it can become the backend for the official D compiler developed by Walter (and the D community). (side question: can the front-end for LLMV be written in D? I hope so).
>>
>> Does Walter oppose moving to develop with this back-end? I think it will lead to solve some of the main current problems in the D development process (such switch can be aligned to a switch to phobos+tango too).
>>
>> Bye,
>> bearophile
> 
> Nice idea. IIRC, Walter isn't going to replace its own backend to (or even look at) GCC because of the GPL license. However, LLVM has a BSD-like license and that could be an option.

There are other issues. If Walter only ever looks at his own code, he's safe from any infringement issues (at least reasonably so). Of course, just using the internal representation from LLVM, and its public APIs, won't have any real affect.

Also, moving dmd to llvm would kill dmc.

> It still lacks some features, but it evolves *daily* unlike DMD backend. For example, chances are we won't ever get a native x86_64 codegen from DM backend, but we will get it with LLVM eventually (very soon, hopefully).

I agree completely with this. I'd rather be using llvmdc right now, but I couldn't get it to work.