On Mon, Feb 2, 2009 at 3:11 PM, Chris Nicholson-Sauls <ibisbasenji@gmail.com> wrote:

> do we have any assurance that, were the functor
> class tagged as 'final', the call would cease to be virtual?

http://d.puremagic.com/issues/show_bug.cgi?id=1909

On Mon, Feb 2, 2009 at 3:11 PM, Chris Nicholson-Sauls <ibisbasenji@gmail.com> wrote:
>
> Or he's caching some very big/complex parameters in the code he's actually
> writing... maybe. That said: do we have any assurance that, were the functor
> class tagged as 'final', the call would cease to be virtual?  If so, then
> the only extra cost on the call is that of the hidden "this" sitting in ESI.
>  I still don't care for the memory allocation involved, personally, but if
> these are long-lived functors that may not be a major problem.  (Ie, if he
> calls foo(?,X) a million times, the cost of allocating one object is
> amortized into nearly nothing.)

Oh, I suppose I should also point out that if you made these functors' methods final, they wouldn't be able to implement interfaces, since interface implementations must be virtual.  So, at that point, you're using a final scope class - might as well use a struct anyway.

Jarrett Billingsley wrote:
> On Mon, Feb 2, 2009 at 3:11 PM, Chris Nicholson-Sauls
> <ibisbasenji@gmail.com> wrote:
>> Or he's caching some very big/complex parameters in the code he's actually
>> writing... maybe. That said: do we have any assurance that, were the functor
>> class tagged as 'final', the call would cease to be virtual?  If so, then
>> the only extra cost on the call is that of the hidden "this" sitting in ESI.
>>  I still don't care for the memory allocation involved, personally, but if
>> these are long-lived functors that may not be a major problem.  (Ie, if he
>> calls foo(?,X) a million times, the cost of allocating one object is
>> amortized into nearly nothing.)
> 
> Oh, I suppose I should also point out that if you made these functors'
> methods final, they wouldn't be able to implement interfaces, since
> interface implementations must be virtual.  So, at that point, you're
> using a final scope class - might as well use a struct anyway.

As far as I know, interface methods can still be final methods in a class. final methods are only disallowed to be overridden further. But it's perfectly fine to mark a method final, that overrides a method from a super class. final so to say only works in one direction.

Then the compiler can optimize calls, if they are statically known to be final. If not, it still has to do a vtable lookup on a method call, even if the actually called method is final.

So it can still make sense to use a class instead of a struct.

On Mon, Feb 2, 2009 at 3:37 PM, grauzone <none@example.net> wrote:

> As far as I know, interface methods can still be final methods in a class. final methods are only disallowed to be overridden further. But it's perfectly fine to mark a method final, that overrides a method from a super class. final so to say only works in one direction.

Sure, the method will be final, but it will still be virtual.  The way interfaces work is by basically giving you a slice of the vtable.

> Then the compiler can optimize calls, if they are statically known to be final. If not, it still has to do a vtable lookup on a method call, even if the actually called method is final.

The compiler can't optimize calls on interface references away.  The function that's using the interface reference only knows as much as the interface tells it.  If some class implements the interface and marks its implementation of the interface as final, it doesn't matter, since the method is not marked final in the interface (and can't be!).

Okay, so *if* the compiler inlined the call to the function that took the interface reference, *and* it was smart enough to recognize that that interface reference did not escape, *and* it was smart enough to realize that the interface really pointed to a class, *and* it knew that the implementation of the method was final, it could inline it. But that seems like an incredibly smart compiler and an incredibly rare situation.  I also don't believe in relying on optimizations that are not enforced, as it makes for nonportable code.

Daniel Keep wrote:
> 
> Lars Kyllingstad wrote:
>> [snip]
>> From a performance
>> perspective, however, it carries with it the overhead of an extra
>> function call, which I'm not sure I want.
>>
>> -Lars
> 
> You're worried about a second function call which could potentially be
> inlined, yet you're seemingly not worried about the overhead of virtual
> calls or heap allocations...

But that's the problem, you see. I don't know how expensive these operations are, hence my initial question(s). (This was also why I posted my question in D.learn.)

For instance, I didn't know (not sure I still do) what the cost is of frequent allocation/deallocation/access of stack memory vs. infrequent allocation/deallocation and frequent access of heap memory. From the replies I've got, it seems heap variables make for significantly slower code.

Nor was I sure, as you pointed out, how expensive a virtual function call is vs. an extra non-virtual function call.

I'm a physicist, not a computer scientist. :)

> Allow me to quote Donald Knuth:
> 
>> We should forget about small efficiencies, say about 97% of the time:
>> premature optimization is the root of all evil.
> 
> Unless you're doing something where you *know* you're going to need
> every last cycle, just go with whichever design works best.  Your
> response to Jarrett implies that you've already got a design in mind,
> and are just fishing for a magic "make it go faster button."

I want that button, yes. :)

But seriously, I am doing numerical computations, so performance is absolutely an issue. The main thing I wanted to know was, can I have both performance and usability, or do I have to choose? With Jarretts suggestion I can, to some degree, have both.

> Believe me, if Walter had invented such a thing, he wouldn't be wasting
> his time putting up with us; he'd be too busy smoking $100 bills from
> the comfort of his SPACE FORTRESS.  :D

What are you implying, that he wouldn't make it open-source? :)

> In any case, I'm willing to bet that if there *are* inefficiencies
> you're not going to know exactly where until you've written the code,
> anyway.  :P
> 
> If classes work, and make for an elegant design, go for it.
> 
>   -- Daniel

Jarrett Billingsley wrote:
> On Mon, Feb 2, 2009 at 1:27 PM, grauzone <none@example.net> wrote:
>> Why not use scope to allocate the class on the stack?
>> For everything else, I agree with Donald Knuth (if he really said that...)
> 
> That's fine too, and would fit in with his needs to implement
> interfaces.  But again, if he's worried about caching some parameters
> but not worried about the overhead of virtual calls.. something's off.

You're assuming too much programming knowledge and carelessness on my part. I merely wanted to know if the second solution would be significantly slower than the first one. Caching of the parameters would be a bonus, as would caching of additional output and the ability to use interfaces.

-Lars

I agree. Of course using an interface to call a method always requires a virtual method call. It's even slower than a virtual method call, because it needs to convert the interface reference into an object reference.

But he still could call the method in question directly. Implementing an interface can be useful to enforce a contract. You can't do that with structs.

Code compiled in debug mode (or was it not-release mode) also calls the code to check the invariant, even if you didn't define one. I guess this can make calling struct methods much faster than object methods.

On Mon, Feb 2, 2009 at 4:55 PM, grauzone <none@example.net> wrote:
> I agree. Of course using an interface to call a method always requires a virtual method call. It's even slower than a virtual method call, because it needs to convert the interface reference into an object reference.
>
> But he still could call the method in question directly. Implementing an interface can be useful to enforce a contract. You can't do that with structs.

What's the point of implementing an interface unless you plan on passing instances of that class to something that expects an interface reference?  ;)

> Code compiled in debug mode (or was it not-release mode) also calls the code to check the invariant, even if you didn't define one. I guess this can make calling struct methods much faster than object methods.

Invariants (as well as in/out contracts and assertions) are turned off in release mode.  FWIW, struct methods also do an "assert(this !is null);" in debug mode, so they're sort of doing an invariant check. But struct methods are never virtual, so yes, they will in general be faster.

Lars Kyllingstad:
> I merely wanted to know if the second solution would be significantly slower than the first one.<

No amount of theory can replace actual timings of your code snippets :-)
(It's often true the other way too, practice doesn't replace theory. But here there isn't too much theory, so lot of practice suffices if you don't know the theory).

Bye,
bearophile

Lars Kyllingstad wrote:
> Daniel Keep wrote:
>>
>> Lars Kyllingstad wrote:
>>> [snip]
>>> From a performance
>>> perspective, however, it carries with it the overhead of an extra
>>> function call, which I'm not sure I want.
>>>
>>> -Lars
>>
>> You're worried about a second function call which could potentially be
>> inlined, yet you're seemingly not worried about the overhead of virtual
>> calls or heap allocations...
> 
> But that's the problem, you see. I don't know how expensive these operations are, hence my initial question(s). (This was also why I posted my question in D.learn.)
> 
> For instance, I didn't know (not sure I still do) what the cost is of frequent allocation/deallocation/access of stack memory vs. infrequent allocation/deallocation and frequent access of heap memory. From the replies I've got, it seems heap variables make for significantly slower code.

Allocating stack memory is very cheap, because essentially the only thing that has to be done is to offset a stack pointer.  Some stack variables are even optimized away if only used as temporaries (that is, their value is retained in a register until it isn't needed) and for short durations.

Allocating heap memory, on the other hand, is expensive for two reasons.  The first, is that the heap may have to grow, which means negotiating more memory from the operating system, which means switching the CPU back and forth between modes, sometimes several iterations.  Of course, this doesn't happen on every allocation, or even very often if you're careful.  The second reason, is that before every allocation the garbage collector will perform a collection run.  This can actually be disabled (at least in theory) if you plan on doing several allocations in a short period of time, and thereafter re-enabled.

For the latter case, see Phobos 'std.gc' or Tango 'tango.core.Memory'.

Once you have memory allocated, the cost of access is generally about the same, except that the stack is more likely to be cached by the CPU.  (Since it is inevitably accessed often.)

> Nor was I sure, as you pointed out, how expensive a virtual function call is vs. an extra non-virtual function call.

It adds an additional step.  You start with an index into the object's vtable (a list of pointers) rather than the function's actual address. Its essentially the same as the difference between assigning to an 'int**' versus an 'int*'.

> I'm a physicist, not a computer scientist. :)
> 

Which is a good thing, since D could use more experience from non-programmers who need to program.  That's a demographic that occasionally (but never completely!) gets forgotten.  I'm not exactly a thirty-years guru, myself.

-- Chris Nicholson-Sauls