Hello all,

A surprise today when tweaking some code.

I have a function which takes as input an array of values (the values are a custom struct).  So, in pseudocode, it's something like this:

    struct MyStruct
    {
        size_t x;
        size_t y;
        double z;
    }

    void foo(MyStruct[] input)
    {
        ...
    }

Since the input isn't modified, I thought I'd tag it as const[1]:

    void foo(const MyStruct[] input) { ... }

... but this turned out to noticeably slow down the program.  (Noticeably as in, a 25-second as opposed to 23-second running time, consistently observed on repeated trials of different code versions.)

I'm surprised by this as I would have thought if anything tagging a variable as const would if anything have increased the speed, or at worst left it the same as before.

Can anyone explain why?  It's no big deal, but I'm curious.

Thanks and best wishes,

    -- Joe

-------
[1] Actually I originally tried marking it as immutable, but it turns out that's a stronger condition that doesn't just apply to what happens _inside_ the function.

On Fri, 27 Apr 2012 11:12:07 -0400, Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> wrote:

> Hello all,
>
> A surprise today when tweaking some code.
>
> I have a function which takes as input an array of values (the values are a custom struct).  So, in pseudocode, it's something like this:
>
>      struct MyStruct
>      {
>          size_t x;
>          size_t y;
>          double z;
>      }
>
>      void foo(MyStruct[] input)
>      {
>          ...
>      }
>
> Since the input isn't modified, I thought I'd tag it as const[1]:
>
>      void foo(const MyStruct[] input) { ... }
>
> ... but this turned out to noticeably slow down the program.  (Noticeably as in, a 25-second as opposed to 23-second running time, consistently observed on repeated trials of different code versions.)
>
> I'm surprised by this as I would have thought if anything tagging a variable as const would if anything have increased the speed, or at worst left it the same as before.
>
> Can anyone explain why?  It's no big deal, but I'm curious.

const should not affect code generation *at all*, except for name mangling (const MyStruct is a different type from MyStruct), and generating an extra TypeInfo for const MyStruct and const MyStruct[].  Const is purely a compile-time concept.

This cannot account for an extra 2 seconds.  Something else is happening.

Without more of your code, nobody can give a definitive answer except it is not supposed to affect it.

-Steve

On 27/04/12 17:18, Steven Schveighoffer wrote:
> const should not affect code generation *at all*, except for name mangling
> (const MyStruct is a different type from MyStruct), and generating an extra
> TypeInfo for const MyStruct and const MyStruct[]. Const is purely a compile-time
> concept.
>
> This cannot account for an extra 2 seconds. Something else is happening.
>
> Without more of your code, nobody can give a definitive answer except it is not
> supposed to affect it.

The code is here: https://github.com/WebDrake/Dregs/

... and the particular file concerned is
https://github.com/WebDrake/Dregs/blob/master/dregs/codetermine.d

You'll see that there are about 8 different functions in there which receive as input an array of type Rating!(UserID, ObjectID, Reputation)[].  These were the inputs I was marking as const.

On Fri, 27 Apr 2012 11:33:39 -0400, Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> wrote:

> On 27/04/12 17:18, Steven Schveighoffer wrote:
>> const should not affect code generation *at all*, except for name mangling
>> (const MyStruct is a different type from MyStruct), and generating an extra
>> TypeInfo for const MyStruct and const MyStruct[]. Const is purely a compile-time
>> concept.
>>
>> This cannot account for an extra 2 seconds. Something else is happening.
>>
>> Without more of your code, nobody can give a definitive answer except it is not
>> supposed to affect it.
>
> The code is here: https://github.com/WebDrake/Dregs/
>
> ... and the particular file concerned is
> https://github.com/WebDrake/Dregs/blob/master/dregs/codetermine.d
>
> You'll see that there are about 8 different functions in there which receive as input an array of type Rating!(UserID, ObjectID, Reputation)[].  These were the inputs I was marking as const.

Hm.. you have marked all your functions pure as well.  I don't think this will affect anything in the current implementation, but it might.  However, I'd expect the opposite (const version is faster) if anything.

-Steve

On 27/04/12 18:02, Steven Schveighoffer wrote:
> Hm.. you have marked all your functions pure as well. I don't think this will
> affect anything in the current implementation, but it might. However, I'd expect
> the opposite (const version is faster) if anything.

Yes, me too, hence confusion.

I have to say I'm somewhat confused about whether the pure markings are really accurate.  The reputation() modifies the reputationUser_ and reputationObject_ internal arrays and hence the returned values of reputationUser() and reputationObject().  It's true that for a given input to reputation(), the outcome will always be the same, but there's nevertheless mutability involved: if I pass one input to reputation(), and then another, the reputationObject() and ...User() outputs will change as a result.

I suppose it's a kind of weak purity, but I'm not too happy with it.  I suppose I could get reputation() to _return_ reputationObject and reputationUser instead of having them called via functions; but I'd be worried it would slow everything down substantially.

Background to this piece of code: it's a D rewrite of some C++ I wrote a couple of years back as part of a research project.  I took quite a lot of time to make the C++ as efficient as possible, so this is a nice test case to see if I can get D to produce similar efficiency while having much more elegantly-written code.  It's also just a nice way to learn to be "D-ish", working on a problem that I already understand well.

Currently the D code is MUCH more elegant and easy to read than the C++, and runs about 2 seconds slower for the test case implemented here (so on my machine, C++ does it in about 21s as opposed to D's 23), with that difference scaling with problem size.  It's a tolerable difference, though it would be nice to see if I can close the gap.

On Fri, 27 Apr 2012 12:37:41 -0400, Joseph Rushton Wakeling <joseph.wakeling@webdrake.net> wrote:

> I have to say I'm somewhat confused about whether the pure markings are really accurate.  The reputation() modifies the reputationUser_ and reputationObject_ internal arrays and hence the returned values of reputationUser() and reputationObject().  It's true that for a given input to reputation(), the outcome will always be the same, but there's nevertheless mutability involved: if I pass one input to reputation(), and then another, the reputationObject() and ...User() outputs will change as a result.

weak purity, I think, is one of the most revolutionary ideas to come from D.  Essentially, we get compiler-checked pure functions that can be written imperatively instead of functionally.

If the function is weakly pure, then it cannot be optimized based on purity, so I don't think there is any way marking it pure *hurts*.

-Steve

On 27/04/12 18:37, Joseph Rushton Wakeling wrote:
> I suppose I could get reputation() to _return_ reputationObject and
> reputationUser instead of having them called via functions; but I'd be worried
> it would slow everything down substantially.

... well what do I know.  I tweaked it to do just that, and it runs at exactly the same speed.
https://github.com/WebDrake/Dregs/commit/9926094645118ecf03c3bedd57f923b02e2bb7fc

On Friday, April 27, 2012 11:18:26 Steven Schveighoffer wrote:
> const should not affect code generation *at all*, except for name mangling (const MyStruct is a different type from MyStruct), and generating an extra TypeInfo for const MyStruct and const MyStruct[]. Const is purely a compile-time concept.

Thanks to the fact that const is transitive and that it's illegal to cast it away to use mutation, const _can_ affect code optimizations, but I don't know exactly under what circumstances it does in the current compiler.

Still, like you, if anything, I'd expect const to be faster rather than slower if there's any speed difference. So, what's happening is a bit weird, and I have no idea what's going on.

- Jonathan M Davis

On 27/04/12 19:08, Steven Schveighoffer wrote:
> weak purity, I think, is one of the most revolutionary ideas to come from D.
> Essentially, we get compiler-checked pure functions that can be written
> imperatively instead of functionally.

I do agree with that; it's a very attractive aspect of D that a function or object can be internally imperative but pure as far as the outside world is concerned.  Seeing that documented in Andrei's writings was another "Wow!" moment for me about D. :-)

What concerned me here was that the way my reputation() function was set up actually did change the public state of the object, which to my mind isn't even weakly pure.  But I just wrote a fix which, contrary to my fears, didn't affect the speed of the program.

> If the function is weakly pure, then it cannot be optimized based on purity, so
> I don't think there is any way marking it pure *hurts*.

I was more concerned that the compiler wasn't identifying what to me was a violation of purity.  I'm fairly sure I can also find a way to make some of those "nothrow" functions throw an error ...

On 27/04/12 19:23, Jonathan M Davis wrote:
> Thanks to the fact that const is transitive and that it's illegal to cast it
> away to use mutation, const _can_ affect code optimizations, but I don't know
> exactly under what circumstances it does in the current compiler.

I should add that I'm using GDC 4.6.3 here, not DMD.  I just checked with the latter and don't see any speed difference with const/non-const.  But the DMD compiled code runs about 20s slower in total anyway, so ... ;-)

> Still, like you, if anything, I'd expect const to be faster rather than slower
> if there's any speed difference. So, what's happening is a bit weird, and I
> have no idea what's going on.

Yup. :-\