View mode: basic / threaded / horizontal-split · Log in · Help
February 14, 2012
More specific instantiations
In D.learn there is an interesting thread ("Instance-specific unittests") about D idioms to use unittests in templated classes/structs:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=32490

A comment from Jonathan M Davis:

> And yes, this can be useful. The problem that you get into is when you _don't_ 
> want your test to be in each instantiation of the template. In that case, you 
> either end up having to use static if or move those unit tests out of the 
> template.

Time ago I have suggested the "static static" idea, an usage example:


auto foo(T)(T x) {
   static static arr = [1, 2, 3];
   return arr[x];
}


"static static" means that arr is not just static, but it's also created only once for all different instantiations of the foo function template. So there is only one arr (and the compiler/linker needs to work less to remove the copies).

A more complex idea (I have seen it in a Bjarne Stroustrup paper, here I have modified it a bit) is to use an attribute to specify a list of template argument types you are using in a declaration (the attribute name is made up on the spot, better names are possible):


auto foo(T)(T x) {
   @templated() static arr = [1, 2, 3];
   return arr[x];
}

class Bar(T, U, W) {
   @templated(T) void foo2() {}
}

@templated(T) means that foo2() is shared across the various instantiations of Bar that share the same U and W types, so it's a template of T only. This is useful as one tool to fight template bloat, and it has other purposes too (like avoiding some template instantiation errors, because you are asserting that foo2 does not need the types U and W to be fully defined correctly).

So if you use that attribute with no arguments, you have a unit test that is shared across all instantiations of the Spam template class, I think this solves Jonathan problem:

class Spam(T) {
   @templated() unittests {}
}

Bye,
bearophile
February 14, 2012
Re: More specific instantiations
On 14 February 2012 14:25, bearophile <bearophileHUGS@lycos.com> wrote:
> In D.learn there is an interesting thread ("Instance-specific unittests") about D idioms to use unittests in templated classes/structs:
> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.learn&article_id=32490
>
> A comment from Jonathan M Davis:
>
>> And yes, this can be useful. The problem that you get into is when you _don't_
>> want your test to be in each instantiation of the template. In that case, you
>> either end up having to use static if or move those unit tests out of the
>> template.
>
> Time ago I have suggested the "static static" idea, an usage example:
>
>
> auto foo(T)(T x) {
>    static static arr = [1, 2, 3];
>    return arr[x];
> }
>
>
> "static static" means that arr is not just static, but it's also created only once for all different instantiations of the foo function template. So there is only one arr (and the compiler/linker needs to work less to remove the copies).
>
> A more complex idea (I have seen it in a Bjarne Stroustrup paper, here I have modified it a bit) is to use an attribute to specify a list of template argument types you are using in a declaration (the attribute name is made up on the spot, better names are possible):
>
>
> auto foo(T)(T x) {
>    @templated() static arr = [1, 2, 3];
>    return arr[x];
> }
>
> class Bar(T, U, W) {
>    @templated(T) void foo2() {}
> }
>
> @templated(T) means that foo2() is shared across the various instantiations of Bar that share the same U and W types, so it's a template of T only. This is useful as one tool to fight template bloat, and it has other purposes too (like avoiding some template instantiation errors, because you are asserting that foo2 does not need the types U and W to be fully defined correctly).
>
> So if you use that attribute with no arguments, you have a unit test that is shared across all instantiations of the Spam template class, I think this solves Jonathan problem:
>
> class Spam(T) {
>    @templated() unittests {}
> }
>
> Bye,
> bearophile

With this:

class Bar(T, U, W) {
   @templated(T) void foo2() {}
}

I assume you mean that void foo2 is only templated across different
Ts, since that is how i read it. "foo2 is only dependent on T,
therefore do not duplicate for different values of U and W"

Other than that, this would be very useful, though I'm not sure about
how easy it is to implement. Better than doubling up a keyword, I
always found that confusing in C/C++ with its long long int and
similar constructs.

James Miller
February 14, 2012
Re: More specific instantiations
> @templated(T) means that foo2() is shared across the various instantiations of Bar that share the same U and W types, so it's a template of T only. This is useful as one tool to fight template bloat, and it has other purposes too (like avoiding some template instantiation errors, because you are asserting that foo2 does not need the types U and W to be fully defined correctly).

I missed another potential usage.

This is a common D idiom, present in Phobos too:

struct Foo(T) {
   T xx;
}

Foo!T foo(T)(T x) {
   return Foo!T(x);
}

void main() {
   auto f = foo(5);
}


Maybe is replaceable with this, that avoids the need of a separate global function, I don't know if this is meaningful:

struct Foo(T) {
   T xx;

   @templated() static Foo!U opCall(U)(U x) {
       return Foo!U(x);
   }
}

void main() {
   auto f = Foo(5);
}

But Foo can't have a normal ctor, I think.

Bye,
bearophile
February 14, 2012
Re: More specific instantiations
On Monday, February 13, 2012 20:25:46 bearophile wrote:
> Time ago I have suggested the "static static" idea, an usage example:
[snip]

I would point out that two different instantiations of the same template have 
_nothing_ in common with one another. It's as if you instantiate a template 
with two different set of arguments, it's as if you copied and pasted the code 
and then adjusted it according to the arguments. As such, having a "static 
static" variable or function which is common to them makes no more sense than 
std.datetime.SysTime and std.container.RedBlackTree sharing a variable or 
function. They're completely separate. Thinking that two different 
instantiations of the same template are related is just going to cause you 
trouble.

- Jonathan M Davis
February 14, 2012
Re: More specific instantiations
Jonathan M Davis:

> I would point out that two different instantiations of the same template have 
> _nothing_ in common with one another.

Despite the optional presence of some static ifs, they share most of the algorithms. And sometimes if the algorithm doesn't change across template instantiations, then some values are the same across template instantiations.


> It's as if you instantiate a template 
> with two different set of arguments, it's as if you copied and pasted the code 
> and then adjusted it according to the arguments.

Often according to the types. So they share something important.


> As such, having a "static 
> static" variable or function which is common to them makes no more sense than 
> std.datetime.SysTime and std.container.RedBlackTree sharing a variable or 
> function. They're completely separate. Thinking that two different 
> instantiations of the same template are related is just going to cause you 
> trouble.

The following is a silly example, but it's clear.
If you implement a function template, like a shellSort(T)(T[] a), it's able to sort both an array of doubles and an array of ints. But the sequence of gaps it uses to sort items, like [1750 701 301 132 57 23 10 4 1] doesn't need to change between the int and double instantiation. The compiler is probably smart enough to put only one copy of such array in the binary, but I am not sure the compiler is able to remove it if such static variable is computed at run-time.

Any way, the post was mostly about the @templated() (and not much about the not so useful "static static" idea), that's useful when you define a class template or struct template on several template arguments, and some of its methods use only a subset of the template arguments.

Bye,
bearophile
February 14, 2012
Re: More specific instantiations
Am 14.02.2012, 13:32 Uhr, schrieb bearophile <bearophileHUGS@lycos.com>:

> Any way, the post was mostly about the @templated() (and not much about  
> the not so useful "static static" idea), that's useful when you define a  
> class template or struct template on several template arguments, and  
> some of its methods use only a subset of the template arguments.
>
> Bye,
> bearophile

I was thinking that "@templated(...)" isn't necessary, since it can be  
deduced naturally from the used symbols inside the function/template/etc.  
to the end that it would just be a compiler optimization.

1. Use all template arguments as usual (in this case of the struct/class)  
for generating the inner template (a method in this case)
2. While generating the method, keep track of used templated symbols from  
the outer scope.
3. For later reference, tag the generated method with template arguments  
introduced by the symbols from step 2.

This can yield sets like those for a struct with 3 template arguments and  
an imaginary method:
char, 5, int  // for "Foo!(char, 5, int)
char, 3, int  // for "Foo!(char, 3, int)
char, 1       // for "Foo!(char, 1, int)
The last case shows, that a "static if" inside the templated method caused  
the third argument to be ignored. The next time, the compiler sees the  
method template instantiated for (char, 1, ubyte), it will match this with  
the existing tag (char, 1).

To illustrate that I have this struct here:

struct Foo(U, V, W) {
  W idx;
  union {
    U[] arr;
    U noarr;
  }
  U bar() {
    static if (V == 1) {
      return noarr;
    } else {
      return arr[idx];     // idx of templated type 'W' is introduced
    }
  }
  W get_idx() {            // uses only symbols of type 'W'
    return idx;            // no need to template on 'U' & 'V'
  }
}
February 14, 2012
Re: More specific instantiations
On 02/14/2012 03:36 PM, Marco Leise wrote:
> Am 14.02.2012, 13:32 Uhr, schrieb bearophile <bearophileHUGS@lycos.com>:
>
>> Any way, the post was mostly about the @templated() (and not much
>> about the not so useful "static static" idea), that's useful when you
>> define a class template or struct template on several template
>> arguments, and some of its methods use only a subset of the template
>> arguments.
>>
>> Bye,
>> bearophile
>
> I was thinking that "@templated(...)" isn't necessary, since it can be
> deduced naturally from the used symbols inside the
> function/template/etc. to the end that it would just be a compiler
> optimization.
>
> 1. Use all template arguments as usual (in this case of the
> struct/class) for generating the inner template (a method in this case)
> 2. While generating the method, keep track of used templated symbols
> from the outer scope.
> 3. For later reference, tag the generated method with template arguments
> introduced by the symbols from step 2.
>
> This can yield sets like those for a struct with 3 template arguments
> and an imaginary method:
> char, 5, int // for "Foo!(char, 5, int)
> char, 3, int // for "Foo!(char, 3, int)
> char, 1 // for "Foo!(char, 1, int)
> The last case shows, that a "static if" inside the templated method
> caused the third argument to be ignored. The next time, the compiler
> sees the method template instantiated for (char, 1, ubyte), it will
> match this with the existing tag (char, 1).
>
> To illustrate that I have this struct here:
>
> struct Foo(U, V, W) {
> W idx;
> union {
> U[] arr;
> U noarr;
> }
> U bar() {
> static if (V == 1) {
> return noarr;
> } else {
> return arr[idx]; // idx of templated type 'W' is introduced
> }
> }
> W get_idx() { // uses only symbols of type 'W'
> return idx; // no need to template on 'U' & 'V'
> }
> }

It cannot be a compiler optimization because it potentially changes the 
semantics of the code:

template T(U, V, W){
    @templated(W) W idx;
}

void main(){
    T!(int,double,long).idx = 1;
    assert(T!(double,int,long).idx == 1);
}
February 14, 2012
Re: More specific instantiations
Am 14.02.2012, 15:46 Uhr, schrieb Timon Gehr <timon.gehr@gmx.ch>:

> It cannot be a compiler optimization because it potentially changes the  
> semantics of the code:
>
> template T(U, V, W){
>      @templated(W) W idx;
> }
>
> void main(){
>      T!(int,double,long).idx = 1;
>      assert(T!(double,int,long).idx == 1);
> }

Ah right, I was a bit off-topic then: @templated removes duplicate static  
data (if desired) whereas the code gen optimization removes duplicate code  
(automatically). Can we make this distinction at least, or did I miss  
something else? The initial post by bearophile was about both - code and  
data, and I argue that the compiler can figure out which code/methods are  
duplicates, which would be preferred over doing it manually.

These uses would remain:

template T(U, V, W) {
    @templated(W) W idx;
}

struct Foo(U, V, W) {
    void bar() { // one method per W
        @templated(W) static W value;
    }
    void foobar() { // one method per U, V, W
        static W value;
    }
}

while this would be invalid:

struct Foo(U, V, W) {
    @templated(W) void bar() {
        static W value;
    }
}

The reasons are that it could duplicate a safe compiler optimization if  
used on methods and I think @templated is easier to understand if it only  
applies to static data.

-- Marco
Top | Discussion index | About this forum | D home