February 01, 2005
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
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
"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
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

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
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
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
"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
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
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.