"there is no way proper C code can be slower than those languages."

  -- http://www.reddit.com/r/programming/comments/1s5ze3/benchmarking_d_vs_go_vs_erlang_vs_c_for_mqtt/cduwwoy

comes up now and then. I think it's incorrect, D has many inherent advantages in generating code over C:

1. D knows when data is immutable. C has to always make worst case assumptions, and assume indirectly accessed data mutates.

2. D knows when functions are pure. C has to make worst case assumptions.

3. Function inlining has generally been shown to be of tremendous value in optimization. D has access to all the source code in the program, or at least as much as you're willing to show it, and can inline across modules. C cannot inline functions unless they appear in the same module or in .h files. It's a rare practice to push many functions into .h files. Of course, there are now linkers that can do whole program optimization for C, but those are kind of herculean efforts to work around that C limitation of being able to see only one module at a time.

4. C strings are 0-terminated, D strings have a length property. The former has major negative performance consequences:

    a. lots of strlen()'s are necessary

    b. using substrings usually requires a malloc/copy/free sequence

5. CTFE can push a lot of computation to compile time rather than run time. This has had spectacular positive performance consequences for things like regex. C has no CTFE ability.

6. D's array slicing coupled with GC means that many malloc/copy/free's normally done in C are unnecessary in D.

7. D's "final switch" enables more efficient switch code generation, because the default doesn't have to be considered.

On Friday, 6 December 2013 at 22:20:19 UTC, Walter Bright wrote:
>
> "there is no way proper C code can be slower than those languages."
>
>   -- http://www.reddit.com/r/programming/comments/1s5ze3/benchmarking_d_vs_go_vs_erlang_vs_c_for_mqtt/cduwwoy
>
> comes up now and then. I think it's incorrect, D has many inherent advantages in generating code over C:
>
> 1. D knows when data is immutable. C has to always make worst case assumptions, and assume indirectly accessed data mutates.
>
> 2. D knows when functions are pure. C has to make worst case assumptions.
>
> 3. Function inlining has generally been shown to be of tremendous value in optimization. D has access to all the source code in the program, or at least as much as you're willing to show it, and can inline across modules. C cannot inline functions unless they appear in the same module or in .h files. It's a rare practice to push many functions into .h files. Of course, there are now linkers that can do whole program optimization for C, but those are kind of herculean efforts to work around that C limitation of being able to see only one module at a time.
>
> 4. C strings are 0-terminated, D strings have a length property. The former has major negative performance consequences:
>
>     a. lots of strlen()'s are necessary
>
>     b. using substrings usually requires a malloc/copy/free sequence
>
> 5. CTFE can push a lot of computation to compile time rather than run time. This has had spectacular positive performance consequences for things like regex. C has no CTFE ability.
>
> 6. D's array slicing coupled with GC means that many malloc/copy/free's normally done in C are unnecessary in D.
>
> 7. D's "final switch" enables more efficient switch code generation, because the default doesn't have to be considered.

You can add generic programming.

Walter Bright:

> comes up now and then. I think it's incorrect, D has many inherent advantages in generating code over C:

I think in your list you have missed the point 8, that is templates allow for data specialization, or for specialization based on compile-time values.

The common example of the first is the C sort() function compared to the type specialized one.

An example for the second is code for the kD-tree that is specialized on the dimension (coordinate) to slice on:
http://rosettacode.org/wiki/K-d_tree#D

As you see the cyclic selection of the coordinate nextSplit is assigned to an enum:

struct KdTree(size_t k, F) {
    KdNode!(k, F)* n;
    Orthotope!(k, F) bounds;

    // Constructs a KdTree from a list of points...
    this(Point!(k, F)[] pts, in Orthotope!(k, F) bounds_) pure {
        static KdNode!(k, F)* nk2(size_t split)(Point!(k, F)[] exset)
        pure {
...
            enum nextSplit = (split + 1) % d.length;//cycle coordinates



> 2. D knows when functions are pure. C has to make worst case assumptions.

Perhaps D purity were designed for usefulness, code correctness, etc. but not to help compilers. I remember some recent discussions in this newsgroup by developers of GDC that explained why the guarantees D offers over C can't lead to true improvements in the generated code. If this is true then perhaps D has some features that weren't designed in hindsight of what back-ends really need to optimize better.


On this whole subject I remember that pointers in Fortan are regarded as so dis-empowered that the Fortran compiler is able to optimize their usage better than any pointers in usual C programs, even C99 programs that use the "restrict" keyword.


There are also situations where D is slower than D: when D can't prove that an array will be accessed in bounds [*]. And when a D compiler because of separate compilation can't de-virtualize a virtual class method call.

Bye,
bearophile

[*] I will have to say more on this topic in few days.

> Perhaps D purity were designed for usefulness,

I meant "was".


> There are also situations where D is slower than D:

I meant "than C" :-)

Bye,
bearophile

On 12/6/2013 2:40 PM, bearophile wrote:
> I think in your list you have missed the point 8, that is templates allow for
> data specialization, or for specialization based on compile-time values.
>
> The common example of the first is the C sort() function compared to the type
> specialized one.

That's a good example.


>> 2. D knows when functions are pure. C has to make worst case assumptions.
>
> Perhaps D purity were designed for usefulness, code correctness, etc. but not to
> help compilers. I remember some recent discussions in this newsgroup by
> developers of GDC that explained why the guarantees D offers over C can't lead
> to true improvements in the generated code. If this is true then perhaps D has
> some features that weren't designed in hindsight of what back-ends really need
> to optimize better.

dmd can and does remove multiple calls to strongly pure functions with the same arguments.


> There are also situations where D is slower than D: when D can't prove that an
> array will be accessed in bounds [*].

In the cases where D cannot, can C? Nope. C doesn't even know what an array is. Can any other language? Nope.


> And when a D compiler because of separate compilation can't de-virtualize a virtual class method call.

Can C devirtualize function calls? Nope.

On Friday, 6 December 2013 at 22:20:19 UTC, Walter Bright wrote:
>
> "there is no way proper C code can be slower than those languages."
>
>   -- http://www.reddit.com/r/programming/comments/1s5ze3/benchmarking_d_vs_go_vs_erlang_vs_c_for_mqtt/cduwwoy
>
> comes up now and then. I think it's incorrect, D has many inherent advantages in generating code over C:

What surprises me most is claim that D can 'hypothetically' generate more efficient code comparing with C, especially taking into account current situation with code generation and optimization.

The claim about inherent advantages implies that code generation is not good now. If it can be so efficient, why it is not the case? And if in practice it is worse, than who cares that 'in theory' code can be better?

I believe that most of your points are either insignificant (like array length - it is carried together with pointer almost everywhere in C) or provide some marginal advantage. Such advantages are offset by:

- huge runtime library
- constant runtime lib invocation and allocation stuff on heap
- horrible mangling (see http://forum.dlang.org/thread/mailman.207.1369611513.13711.digitalmars-d@puremagic.com examples from hall of D mangling, mangling is so big, that forum software goes astray)
- phobos snowball - one invocation of some function in standard library leads to dozens template instantiations and invocations of pretty much stuff

Am 06.12.2013 23:40, schrieb bearophile:
> Walter Bright:
>
>> comes up now and then. I think it's incorrect, D has many inherent
>> advantages in generating code over C:
>
> I think in your list you have missed the point 8, that is templates
> allow for data specialization, or for specialization based on
> compile-time values.
>
> The common example of the first is the C sort() function compared to the
> type specialized one.
>
> An example for the second is code for the kD-tree that is specialized on
> the dimension (coordinate) to slice on:
> http://rosettacode.org/wiki/K-d_tree#D
>
> As you see the cyclic selection of the coordinate nextSplit is assigned
> to an enum:
>
> struct KdTree(size_t k, F) {
>      KdNode!(k, F)* n;
>      Orthotope!(k, F) bounds;
>
>      // Constructs a KdTree from a list of points...
>      this(Point!(k, F)[] pts, in Orthotope!(k, F) bounds_) pure {
>          static KdNode!(k, F)* nk2(size_t split)(Point!(k, F)[] exset)
>          pure {
> ...
>              enum nextSplit = (split + 1) % d.length;//cycle coordinates
>
>
>
>> 2. D knows when functions are pure. C has to make worst case assumptions.
>
> Perhaps D purity were designed for usefulness, code correctness, etc.
> but not to help compilers. I remember some recent discussions in this
> newsgroup by developers of GDC that explained why the guarantees D
> offers over C can't lead to true improvements in the generated code. If
> this is true then perhaps D has some features that weren't designed in
> hindsight of what back-ends really need to optimize better.
>
>
> On this whole subject I remember that pointers in Fortan are regarded as
> so dis-empowered that the Fortran compiler is able to optimize their
> usage better than any pointers in usual C programs, even C99 programs
> that use the "restrict" keyword.
>
>
> There are also situations where D is slower than D: when D can't prove
> that an array will be accessed in bounds [*]. And when a D compiler
> because of separate compilation can't de-virtualize a virtual class
> method call.
>
> Bye,
> bearophile
>
> [*] I will have to say more on this topic in few days.


That is why most safe systems programming language compilers allow disabling bounds checking. :)

Back in the MS-DOS days, I made use of {$R-} sections if I really needed the few ms gained by disabling bounds checking in Turbo Pascal.

--
Paulo

On Friday, 6 December 2013 at 22:52:46 UTC, Walter Bright wrote:
> On 12/6/2013 2:40 PM, bearophile wrote:
>> I think in your list you have missed the point 8, that is templates allow for
>> data specialization, or for specialization based on compile-time values.
>>
>> The common example of the first is the C sort() function compared to the type
>> specialized one.
>
> That's a good example.
>
>
>>> 2. D knows when functions are pure. C has to make worst case assumptions.
>>
>> Perhaps D purity were designed for usefulness, code correctness, etc. but not to
>> help compilers. I remember some recent discussions in this newsgroup by
>> developers of GDC that explained why the guarantees D offers over C can't lead
>> to true improvements in the generated code. If this is true then perhaps D has
>> some features that weren't designed in hindsight of what back-ends really need
>> to optimize better.
>
> dmd can and does remove multiple calls to strongly pure functions with the same arguments.

and what about holes in immutable, pure and rest type system?

>
>> There are also situations where D is slower than D: when D can't prove that an
>> array will be accessed in bounds [*].
>
> In the cases where D cannot, can C? Nope. C doesn't even know what an array is. Can any other language? Nope.
>
>
>> And when a D compiler because of separate compilation can't de-virtualize a virtual class method call.
>
> Can C devirtualize function calls? Nope.

C doesn't have virtual functions. By the way, does D devirtualize them? AFAIK it doesn't either, but I do remember spec page was talking about it (this is so Dish - advertize optimization trick in spec and do not implement it).

07-Dec-2013 02:20, Walter Bright пишет:
>
> "there is no way proper C code can be slower than those languages."

> 3. Function inlining has generally been shown to be of tremendous value
> in optimization. D has access to all the source code in the program, or
> at least as much as you're willing to show it, and can inline across
> modules.

Uh-oh. I'd avoid advertising this particular point until after a critical bug is fixed:
https://d.puremagic.com/issues/show_bug.cgi?id=10985
Applies to all 3 compilers.

Otherwise - it's spot on. D has many ways to be typically "faster then Cee" ;)

-- 
Dmitry Olshansky

On 12/6/2013 3:02 PM, Maxim Fomin wrote:
> What surprises me most is claim that D can 'hypothetically' generate more
> efficient code comparing with C, especially taking into account current
> situation with code generation and optimization.
>
> The claim about inherent advantages implies that code generation is not good
> now. If it can be so efficient, why it is not the case? And if in practice it is
> worse, than who cares that 'in theory' code can be better?

You can write D code in "C style" and you'll get C results. To get performance advantages from D code, you'll need to write in a structurally different way (as Andrei pointed out).

Looking through Phobos, there is a lot of code that is not written to take advantage of D's strengths. An apt one discussed here recently is the std.path.buildPath, which is written in "C style", as in allocating memory for its result.

A structural D style version would accept a range for its output, and the range need not allocate memory. This would be fundamentally faster than the typical C approach.

This pattern is repeated a lot in Phobos code.


> I believe that most of your points are either insignificant (like array length -
> it is carried together with pointer almost everywhere in C)

I see a lot of C code that does strlen() over and over. I think Tango's XML parser showed what can be done in D versus any known C implementation. It took maximal advantage of D's slicing abilities to avoid copying.

Dmitry's regex also showed huge gains over C regex implementations.

> or provide some marginal advantage.

Even a marginal advantage is a counter example to the claim "there is no way proper C code can be slower than those languages."

> Such advantages are offset by:
>
> - huge runtime library

C has a huge runtime library, too, it's just that you normally don't notice it because it's not statically linked in. Be that as it may, 2.064 substantially reduced the size of "hello world" programs.

> - constant runtime lib invocation and allocation stuff on heap

This is, as I mentioned, a problem with writing C style code in Phobos.

> - horrible mangling (see
> http://forum.dlang.org/thread/mailman.207.1369611513.13711.digitalmars-d@puremagic.com
> examples from hall of D mangling, mangling is so big, that forum software goes
> astray)

Long mangling is not an inherent language characteristic, as that thread suggests improvements.

> - phobos snowball - one invocation of some function in standard library leads to
> dozens template instantiations and invocations of pretty much stuff

True enough, but does that lead to non-performant code? 2.064 cuts that down quite a bit anyway, and I think we can make more improvements in this regard.