I don't know much about this topic, but this post is mostly in question form.

Are dynamic casts pure? I have compiled the following small program with LDC:


version (Tango)
    import tango.stdc.stdio: printf;
else version (D1)
    import std.c.stdio: printf;
else
    import core.stdc.stdio: printf;

class A { int a; }

void main() {
    Object o = new A();
    A a = cast(A)o;
    a.a = 10;
    printf("%d %d\n", a.a, cast(A)o);
}


LDC based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009) ldc -O5 -release -inline -output-s dyncast_test.d

The asm it produces shows two calls to _d_dynamic_cast:

_Dmain:
    pushl   %esi
    subl    $16, %esp
    movl    $_D5cast51A7__ClassZ, (%esp)
    call    _d_allocclass
    movl    %eax, %esi
    movl    $_D5cast51A6__vtblZ, (%esi)
    movl    $0, 4(%esi)
    movl    $0, 8(%esi)
    movl    %esi, (%esp)
    movl    $_D5cast51A7__ClassZ, 4(%esp)
    call    _d_dynamic_cast
    movl    $10, 8(%eax)
    movl    %esi, (%esp)
    movl    $_D5cast51A7__ClassZ, 4(%esp)
    call    _d_dynamic_cast
    movl    %eax, 8(%esp)
    movl    $10, 4(%esp)
    movl    $.str1, (%esp)
    call    printf
    xorl    %eax, %eax
    addl    $16, %esp
    popl    %esi
    ret $8


If the dynamic cast are pure the compiler can call it only once here (LLVM already has two functions attributes for pure functions).

(Related: can the code that performs the dynamic casts be in some situations inlined by LDC?)

Bye,
bearophile

bearophile wrote:
> I don't know much about this topic, but this post is mostly in question form.
> 
> Are dynamic casts pure? I have compiled the following small program with LDC:
> 
> 
> version (Tango)
>     import tango.stdc.stdio: printf;
> else version (D1)
>     import std.c.stdio: printf;
> else
>     import core.stdc.stdio: printf;
> 
> class A { int a; }
> 
> void main() {
>     Object o = new A();
>     A a = cast(A)o;
>     a.a = 10;
>     printf("%d %d\n", a.a, cast(A)o);
> }
> 
> 
> LDC based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009)
> ldc -O5 -release -inline -output-s dyncast_test.d
> 
> The asm it produces shows two calls to _d_dynamic_cast:
> 
> [snip]
> 
> If the dynamic cast are pure the compiler can call it only once here (LLVM already has two functions attributes for pure functions).
> 
> (Related: can the code that performs the dynamic casts be in some situations inlined by LDC?)
> 
> Bye,
> bearophile

One cast for the assignment to a and one cast for the call to printf.

I would say the casts are pure to a certain level, they don't always return the same value to the same input because they return references. They do however perform the exact same code path for the same inputs. So it should be possible to inline them.

Take a look at the _d_dynamic_cast implementation of my runtime:

Object _d_dynamic_cast(in Object p, in ClassInfo ci) {
	uint offset = void;
	return p && _d_isbaseof2(p.classinfo, ci, offset) ?
		cast(Object)(*cast(void**)&p + offset) : null;
}

You can clearly see all there is to a dynamic cast is simply adjusting the pointer to the object's virtual table. So a compiler knowing the source and destination offset of the vtable can easily inline the code for such a cast.

An interface dynamic cast is similar but the interface reference has to be converted into an object reference first and then passed to _d_dynamic cast.

Maybe you could open a ticket in bugzilla about this?

Jeremie

Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.

bearophile Wrote:

> I don't know much about this topic, but this post is mostly in question form.
> 
> Are dynamic casts pure? I have compiled the following small program with LDC:
> 
> 
> version (Tango)
>     import tango.stdc.stdio: printf;
> else version (D1)
>     import std.c.stdio: printf;
> else
>     import core.stdc.stdio: printf;
> 
> class A { int a; }
> 
> void main() {
>     Object o = new A();
>     A a = cast(A)o;
>     a.a = 10;
>     printf("%d %d\n", a.a, cast(A)o);
> }
> 
> 
> LDC based on DMD v1.045 and llvm 2.6 (Thu Sep 10 23:50:27 2009) ldc -O5 -release -inline -output-s dyncast_test.d
> 
> The asm it produces shows two calls to _d_dynamic_cast:
> 
> _Dmain:
>     pushl   %esi
>     subl    $16, %esp
>     movl    $_D5cast51A7__ClassZ, (%esp)
>     call    _d_allocclass
>     movl    %eax, %esi
>     movl    $_D5cast51A6__vtblZ, (%esi)
>     movl    $0, 4(%esi)
>     movl    $0, 8(%esi)
>     movl    %esi, (%esp)
>     movl    $_D5cast51A7__ClassZ, 4(%esp)
>     call    _d_dynamic_cast
>     movl    $10, 8(%eax)
>     movl    %esi, (%esp)
>     movl    $_D5cast51A7__ClassZ, 4(%esp)
>     call    _d_dynamic_cast
>     movl    %eax, 8(%esp)
>     movl    $10, 4(%esp)
>     movl    $.str1, (%esp)
>     call    printf
>     xorl    %eax, %eax
>     addl    $16, %esp
>     popl    %esi
>     ret $8
> 
> 
> If the dynamic cast are pure the compiler can call it only once here (LLVM already has two functions attributes for pure functions).
> 
> (Related: can the code that performs the dynamic casts be in some situations inlined by LDC?)
> 
> Bye,
> bearophile

Jason House wrote:
> Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.

What if the GC just happens to re-use that address for a different object?

Daniel Keep wrote:
> 
> Jason House wrote:
>> Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.
> 
> What if the GC just happens to re-use that address for a different object?

I don't know about druntime's GC but I used to have this issue with my own GC. I would cast an object to an interface type which would make its only reference point to a different 16bytes block, remember that bit fields in the GC are aligned to 16bytes, and the allocation had therefore no more reachable pointers, or so the GC thought.

What fixed it was to adjust the scan phase and align found pointers to the block size of its corresponding allocation. That way the GC won't reuse the address of reachable objects no matter what interface or subclass they are casted to.

Daniel Keep:
>What if the GC just happens to re-use that address for a different object?<

I don't understand. Can you explain me an example where this problem may happen?

Bye,
bearophile

Daniel Keep Wrote:

> 
> 
> Jason House wrote:
> > Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.
> 
> What if the GC just happens to re-use that address for a different object?


I was thinking of that and tried to be careful with my wording. I guess I failed. Memoization can't occur, exactly for the reason you indicate. I was trying to say that for the life of an object, the type and type info is immutable. Since a dynamic cast only uses that immutable state, the return value does not change over the lifetime of the object. This could be used for optimizations above and beyond simple purity.

On Tue, Sep 22, 2009 at 8:40 AM, bearophile <bearophileHUGS@lycos.com> wrote:
> Daniel Keep:
>>What if the GC just happens to re-use that address for a different object?<
>
> I don't understand. Can you explain me an example where this problem may happen?
>
> Bye,
> bearophile
>

Object is allocated at 0x10001000, that object is collected, its memory is put back on the freelist, another object of the same size is allocated, and that block of memory is used again, allocating a new object at 0x10001000.

On Tue, 22 Sep 2009 05:24:11 -0400, Daniel Keep <daniel.keep.lists@gmail.com> wrote:

>
>
> Jason House wrote:
>> Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.
>
> What if the GC just happens to re-use that address for a different object?

That's only if memoization is used.

I think what Jason said is correct -- you can view dynamic cast as taking 2 arguments, one is the reference which is simply echoed as the return value, and one is the classinfo, which is an immutable argument that causes a decision to be made.

In fact, you could use memoization on a dynamic cast subfunction that memoizes on the target type and the classinfo of the source, regardless of the reference value, and returns an offset to add to the return value.

It's pretty easy for the compiler to prove that o has not be reassigned, so even without memoization, the compiler can logically assume that the result from the first dynamic cast can be reused.  I think this is the major optimization for pure functions anyways, not memoization.

-Steve

On Tue, Sep 22, 2009 at 1:19 PM, Steven Schveighoffer <schveiguy@yahoo.com> wrote:
> On Tue, 22 Sep 2009 05:24:11 -0400, Daniel Keep <daniel.keep.lists@gmail.com> wrote:
>
>>
>>
>> Jason House wrote:
>>>
>>> Dynamic casts are pure. They don't use global state, and have the same output for the same reference as input. Interestingly, dynamic cast results are independent of intervening mutable calls... So there's even greater opportunity for optimization.
>>
>> What if the GC just happens to re-use that address for a different object?
>
> That's only if memoization is used.
>
> I think what Jason said is correct -- you can view dynamic cast as taking 2 arguments, one is the reference which is simply echoed as the return value, and one is the classinfo, which is an immutable argument that causes a decision to be made.
>
> In fact, you could use memoization on a dynamic cast subfunction that memoizes on the target type and the classinfo of the source, regardless of the reference value, and returns an offset to add to the return value.
>
> It's pretty easy for the compiler to prove that o has not be reassigned, so even without memoization, the compiler can logically assume that the result from the first dynamic cast can be reused.  I think this is the major optimization for pure functions anyways, not memoization.

Or you could - I dunno - cache the result of the dynamic cast in a local, since doing multiple dynamic casts is terrible style anyway.

Just saying. ;)