View mode: basic / threaded / horizontal-split · Log in · Help
February 01, 2005
Re: Example code: Expression templates in D
pragma wrote:

> I fully acknowledge that I am a complete idiot when it comes to "numerics
> programming".

Thanks for your honesty. Actually two years ago I would have had to say the
same, but I probably would not even have realized how little I knew. Since
then I worked two years on numerics for my diploma and now PhD thesis. It
took me some time to realize, that in high-performance numerics you have to
worry about completely other issues than in other fields of programming.

Generally, I see two major areas of interest for high-performance numerics
where D has the potential of surpassing all existing general purpose
languages. Neither of them stands in contrast with the philosophy of being
a "general purpose" language. Actually, I believe, if these issues are
dealt with correctly, many other areas of programming might benefit as
well:

-----------------
1) defining the language in a way that a compiler can efficiently optimize
2) support meta-programming as much as possible to allow writing libraries
that do intelligent decisions on the code that should be created.

Point 1) leads to multidimensional arrays and vectorized expressions. In
modern architectures, the performance of the code depends crucially on the
order of the individual machine code operations. Modern processors are
pipelined, do branch prediction, have sophisticated command set expansions
to deal with vectorized data (MMD extensions, etc.) and have several levels
of cache. In a language like C or Fortran 77, the programmer pretty much
specifies one command after the other what the program should do:
for(int i=0;i<MAX_I;i++)
for(int j=0;j<MAX_J;j++)
 A[i][j] = B[i][j]+C[i][j];
An intelligent compiler might be able to swap the order of some commands,
but it is very often not easy to decide whether the order can really safe
be changed without changing the overall semantics. Other languages (Fortran
95 and others) allow vectorized expressions:
A = B + C;
similar to the Array Operations described in the D specs. Here, the order of
execution is not specified. The compiler is free to pick one. For more
complicated expressions, the compiler might not be able to verify whether
the result depends on the order, but still, the programmer using such an
expression explicitely allows the compiler to choose the order of
execution. It is the responsibility of the programmer to make sure that the
order does not matter, but the whole syntax already makes this clear.
Inlike the for statements in C, the syntax of vectorized expressions should
be done in a way that the programmer does not even specify any order of the
single expressions, so he should have little reason to believe that the
compiler will stick to any order.

Understanding the issues of vectorized programming, it might be an idea to
read a bit about the design issues of Fortran 95 (or its predecessor High
Performance Fortran)

As I said, I believe that Array Operations in D are ill defined, but that is
a matter I will probably bring up again another time.

--------------
Point 2) is about expression templates. This is a technique only recently
developed in C++. Instead of trying to explain it here, I'll just give a
few links:

Blitz++ - a high-performance library based on expression templates in C++:
http://www.oonumerics.org/blitz/
Of special interest: several papers describing the background:
 http://www.oonumerics.org/blitz/papers/

Boost++ - A huge project making heavy use of advanced C++ techniques
http://www.boost.org/
uBlas - A subproject of boost++, dealing with numerics
http://www.boost.org/libs/numeric/ublas/doc/index.htm

There are several links starting at these pages. Just go through them.

A general remark: In C++, expression templates were only recently discovered
and exploited. The language was not really designed for them, so it is
rather complicated to design a library and use it. For that reason, only a
small number of experts deal with them. For D, on the other hand, I think
there could be a much greater future for them, since the template system is
designed a lot cleaner. It is not complete yet to support the full power of
C++ templates, but once this is done, expression templates will hopefully
be much easier to use than in C++.

So far for now, I have to leave. If there is interested in more discussion
on the topic, I'll be happy to join in.

Ciao,
Norbert
February 01, 2005
Re: Example code: Expression templates in D
In article <ctokv8$13pt$1@digitaldaemon.com>, Norbert Nemec says...
>
>...
>As I said, I believe that Array Operations in D are ill defined, but that is
>a matter I will probably bring up again another time.
>...
>Point 2) is about expression templates. This is a technique only recently
>developed in C++. Instead of trying to explain it here, I'll just give a
>few links:

Thank you for the kind words and the informative response!  

I've spent the last hour or two delving into expression templates and I cannot
believe my eyes.  I now understand how D's lack of template argument deduction
and implicit instancing stand directly in the way of implementing expression
templates.

From what I gather the tenents of Expression Templates read like an extreme
programming contest:

- Create a math library that supports all the major math expressions
(log,sin,etc) by using templates.
- Use solutions that do not copy or duplicate any term of an expression.  Any
solution should be as close to hand-coded as possible, while being machine
generated.
- The library should automatically unroll small loops and avoid needless
iteration.
- String parsers are not allowed.

The result is that adding three matricies in a single line (d = a + b + c)
should create no temporaries and only one loop.

I also now understand a (much, much) older post regarding aliasing, and how
implementing the 'restrict' keyword in D would assist the compiler in making
optimizations akin to Fortran (non-pointable vars = easier to optimize).

I think I'm starting to see the light.  I've particularily found anything by
Todd Veldhuizen to be particularily digestable, not to mention, packed with code
rather than mathematical expressions.  

To that end, *anyone* interested in the topic should read the following:

http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html

It explains the topic blow-by-blow using how ET supports math, rather than how
math is mapped to ET.

- EricAnderton at yahoo
February 04, 2005
Re: Example code: Expression templates in D
"Norbert Nemec" <Norbert@Nemec-online.de> wrote in message
news:ctj46q$f52$1@digitaldaemon.com...
> Hi there,
>
> triggered by a message from Walter about implicit function template
> instantiation, I just sat down and wrote some example code for expression
> templates in D. The result is attached.
>
> Short summary: expression template programming is not yet possible in D.
> Many details show that the template mechanism in general is very promising
> compared to the C++, but implicit function template instantiation is such
a
> crucial feature for ET that the whole attempt is doomed.

I want to make this work (it's just beyond the scope of 1.0 at the moment).
February 04, 2005
Re: Example code: Expression templates in D
Walter wrote:

> I want to make this work (it's just beyond the scope of 1.0 at the
> moment).

That's a statement I can live with.

Actually, I have thought about the topic a little more considering whether
it might be possible to avoid the complexity of C++ implicit instantiation.

So far, my resolution is: No.

The power of C++ implicit instantiation comes from very sopisticated pattern
matching: The compiler can match any type like
MyTemplate<int,float,MyTemplate2<5,int> >
with a type pattern like
MyTemplate<T,U,MyTemplate2<N,T> >
while also matching up T with int, U with float and N with 5

The D compiler already does a little bit of pattern matching as well, but it
is by far not as flexible and it is not possible yet to retrieve the
matched parts:

template(T,U: T[5])

already needs some intelligence, but by far not as much, and it is in
general not possible to do anything like

template(T,U: T[N])

where N is retrieved from the type given for U.

Any attempt to avoid the complexity of the C++ behaviour that I could think
of so far resulted in severly limited power. I doubt, that a way can be
found around it.
February 04, 2005
Idea (Was: Example code: Expression templates in D)
Norbert Nemec wrote:
> Walter wrote:
>>I want to make this work (it's just beyond the scope of 1.0 at the
>>moment).
> 
> That's a statement I can live with.
> 
> Actually, I have thought about the topic a little more considering whether
> it might be possible to avoid the complexity of C++ implicit instantiation.
....
> Any attempt to avoid the complexity of the C++ behaviour that I could think
> of so far resulted in severly limited power. I doubt, that a way can be
> found around it.

Just a thought, but:

Ideally, we'd have this separated from the rest of D development, for a 
while. D1.0 would be unhampered by this, and this could go on 
essentially irrespective of "daily issues" in D development. This is, 
after all, on a separate conceptual level. Later, when this produces a 
superior template system, then it would be imported to D. (Be it then 
D2.0, D1.5 or, hopefully D1.1)

In this project, Norbert could lead the template language development. 
The practical side, i.e. testing the concepts with real code, could be 
implemented by others with a preprosessor. Ideally that would take any D 
source, but only transform the constructs relevant to this.

The preprocessor could be written in Perl, DMDscript, or D itself, 
pretty quickly. I assume it wouldn't even need to properly parse D in 
it's entirety, just the relevant parts. To speed up writing (and 
rewriting totally different versions of) the preprocessor, we might even 
decide to have in-comment special markers, or whatever other extras in 
the input sources. It is, afer all, a language lab, not a production 
environment.

This would essentially free Walter to concentrate on current issues. (Of 
course Walter'd be around in this too, but you know what I mean.) And 
the project could go meandering on, free to try even the most 
controversial things. Once we get a working (and proven and tested!!!) 
template syntax, we could use it for a while in "d-developers-only" 
projects, to see if it actually works in real life.

We might even have a number of alternative syntaxes examined at the same 
time!!

A good template system being both urgent and important, I feel this is 
the least we could do right now.
February 04, 2005
Re: Idea (Was: Example code: Expression templates in D)
Georg Wrede wrote:

> Just a thought, but:
> 
> Ideally, we'd have this separated from the rest of D development, for a
> while. D1.0 would be unhampered by this, and this could go on
> essentially irrespective of "daily issues" in D development. This is,
> after all, on a separate conceptual level. Later, when this produces a
> superior template system, then it would be imported to D. (Be it then
> D2.0, D1.5 or, hopefully D1.1)

Nice idea. However currently, I really don't have much resources left over
for that. (Actually - I'm already spending much more time on reading and
writing in this list than I should...)

I still have the plan to at write down the design of the most central
features that I have in mind for future D development. If it becomes clear
that a prototype implementation can be done in a preprocessor, that
certainly is an option. Anyhow, I believe that most ideas what I have in
mind would demands very detailed analysis of the sourcecode for a
preprocessor.

In any case: I cannot promise when I find the time to write on the design
papers. Discussing an implementation does not make sense before that.

Of course, if anybody wants to experiment, you are always welcome to start.
I'll certainly join in the discussion and it might actually force me to
finally sit down and write down clean concepts.
February 04, 2005
Re: Idea (Was: Example code: Expression templates in D)
Norbert Nemec wrote:
> Georg Wrede wrote:
>>Ideally, we'd have this separated from the rest of D development,
>>for a while. D1.0 would be unhampered by this, and this could go on
>>essentially irrespective of "daily issues" in D development.
...
> Of course, if anybody wants to experiment, you are always welcome
> to start. I'll certainly join in the discussion and it might
> actually force me to finally sit down and write down clean concepts.

Good. This was excactly what I'd hoped for!

> Anyhow, I believe that most ideas what I have in
> mind would demands very detailed analysis of the 
> sourcecode for a preprocessor.

Hmm. Does that contradict with D having a context free grammar?
February 04, 2005
Re: Example code: Expression templates in D
"Norbert Nemec" <Norbert@Nemec-online.de> wrote in message
news:ctvj6q$248a$1@digitaldaemon.com...
> The power of C++ implicit instantiation comes from very sopisticated
pattern
> matching: The compiler can match any type like
>  MyTemplate<int,float,MyTemplate2<5,int> >
> with a type pattern like
>  MyTemplate<T,U,MyTemplate2<N,T> >
> while also matching up T with int, U with float and N with 5

So can D. D will do all the pattern matching C++ will, it just won't do
implicit instantiation. The above examples are explicit instantiation, which
should work fine with D.

> The D compiler already does a little bit of pattern matching as well, but
it
> is by far not as flexible and it is not possible yet to retrieve the
> matched parts:
>
>  template(T,U: T[5])
>
> already needs some intelligence, but by far not as much, and it is in
> general not possible to do anything like
>
>  template(T,U: T[N])
>
> where N is retrieved from the type given for U.

The following does work:

template foo(T,N,U:T[N])
{
   T t;
   N n;
   U u;
}

alias foo!(int,char,int[char]) bar;
February 07, 2005
Re: Idea (Was: Example code: Expression templates in D)
Georg Wrede wrote:

> 
> Norbert Nemec wrote:
>> Georg Wrede wrote:
>>>Ideally, we'd have this separated from the rest of D development,
>>>for a while. D1.0 would be unhampered by this, and this could go on
>>>essentially irrespective of "daily issues" in D development.
> ...
>  > Of course, if anybody wants to experiment, you are always welcome
>  > to start. I'll certainly join in the discussion and it might
>  > actually force me to finally sit down and write down clean concepts.
> 
> Good. This was excactly what I'd hoped for!
> 
>> Anyhow, I believe that most ideas what I have in
>> mind would demands very detailed analysis of the
>  > sourcecode for a preprocessor.
> 
> Hmm. Does that contradict with D having a context free grammar?

No, but you simply need more than grammar to preprocess implicit
instantiation. Basically, the precompiler would have to understand all the
types used in D, which goes far beyond simply parsing the code.
February 08, 2005
Re: Example code: Expression templates in D
Walter wrote:

> "Norbert Nemec" <Norbert@Nemec-online.de> wrote in message
> news:ctvj6q$248a$1@digitaldaemon.com...
>> The power of C++ implicit instantiation comes from very sopisticated
> pattern
>> matching: The compiler can match any type like
>>  MyTemplate<int,float,MyTemplate2<5,int> >
>> with a type pattern like
>>  MyTemplate<T,U,MyTemplate2<N,T> >
>> while also matching up T with int, U with float and N with 5
> 
> So can D. D will do all the pattern matching C++ will, it just won't do
> implicit instantiation. The above examples are explicit instantiation,
> which should work fine with D.

I guess, I did not make my point clear enough: as I believe, the pattern
matching in C++ is fundamentally more powerful that that in D. To
illustrate, it is the simplest way to imagine what implicit instantiation
might look like in D without demanding more intelligence of the compiler. 

The first idea that comes to mind would be the rule that, if 'mytemplate' is
the name of a template containing exactly one function with the name
'mytemplate', the call
mytemplate(a,b,c)
is automatically translated into
mytemplate!(typeof(a),typeof(b),typeof(c))(a,b,c)

This was my first idea when I thought about the topic. It would be trivial
to implement and provide some kind of 'implicit instantiation'. It can make
full use of D's pattern matching mechanism, as it will automatically select
the appropriate specialization based on the types of the arguments.

However, it becomes immediately clear that this is less powerful than C++.
The template parameters could only be types and they would have to match
one-by-one with the arguments of the encapsulated function. C++, on the
other hand allows the template parameters to be used as placeholders in
arbitrary places of the function arguments:

template<int M,int N>
Vector<M> dot(Matrix<M,N> a,Vector<N> b)
{
 Vector<M> res;
 for(int m=M;m--;) {
     double r = 0.0;    
     for(int n=N;n--;)
  r += a[m,n]*b[n]
     res[m] = r;
 }
 return res;
}

Here, the compiler actually does a complete patter matching on the pair
(Matrix<$M,$N>,Vector<$N>)
and keeps the integers matched by $M and $N for later use.

Furthermore, the compiler matches not only one pattern, but compares several
patterns and selects the one that fits "best" (if you do partial
specialization)


This goes several steps beyond the current power of D.
1 2 3
Top | Discussion index | About this forum | D home