"Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:cc5rm4$2juo$1@digitaldaemon.com...
> Walter wrote:
>
> What is needed is a "vector expression" that uses index notation. A few ideas, I'm shuffling around:
>
>         index i,j;   // declare i and j to be indices for a vector
expression
>         B[i,j] = sin(A[i,j]);
>         D[i,j] = A[i,j] + C[i];
>
> or
>
>         B[] = [i=0..10,j=0..10](sin(A[i,j]));
>         D[] = [i=0..10,j=0..10](A[i,j] + C[i]);
>
> In the second notation you could do really powerful things like:
>
>         real[8,8] E = [i=0..8,j=0..8]((i+j)%2); // initialize a
chess-board
>         real[8,8] F = [i=0..8,j=0..8](sin(i*j)); // initialize a 2D-sin
wave
>         real[8,8] G = [i=0..8,j=0..8]((i+j)%2 ? sin(i*j) : 0);
>                                     // initialize a masked sine-wave
>
> I'm not fully happy about the syntax yet. The ideas will probably just
need
> some time to ripen.
>

Now that would be really cool - and useful :) I agree that the syntax has got to be thought about more though... but I cannot think of any alterate notation that would be as effective and compact as what you have proposed, so I reckon you're heading in the right direction, at least!

"Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:cc5t00$2m4h$1@digitaldaemon.com...
> Knud Sørensen wrote:
>
> > On Sat, 03 Jul 2004 09:51:11 +0200, Norbert Nemec wrote:
> >
> >> Stephen Waits wrote:
> >>
> >>> My only suggestion is that these vector expressions be able to expand
to
> >>> handle non-trivial cases.  For example, think of calculating a vector cross product, or matrix multiplication, quaternion multiplication,
etc.
> >>
> >> I don't think, that would be a good idea: Plain vector operations cover *elementwise* operations. With a good concept, it should be possible to stay flexible and extensible enough, if this is put into the language.
> >
> > Einstein notation would give you all this and much more.
> > it would also give you powerful vectorization and avoid temporaries.
> >
> > agian I invite you to take a look at http://dlanguage.netunify.com/56
> >
> > and tell me what you think.
>
> See my other message about it. Just one point for clarification:
>
> Something like:
>         a[i,j] = sum(k){b[i,k]*c[k,j]};  // Pseudo-syntax!
> is called *index-notation* - this is exactly the core of my concept for
> vector operations. (I have no idea yet how to do aggregators like "sum",
> but they will definitely be needed) It was used in mathematics long before
> Einstein was born.
>
> The term "Einstein-Notation" on the other hand only refers to dropping the "sum" in the above expression, saying this sum is implicitly to be understood if one index appears twice. Einstein introduced that convention because he was lazy and because it really saves on writing in relativistic calculations. In contexts outside of relativity, geometry and linear algebra, this convention does not make much sense, though and actually
even
> gets in the way.
>
> Therefore: index-notation makes perfect sense in D, Einstein-notation
(i.e.
> summing over indices implicitly) would just be extremely confusing and counterproductive in many areas.
>

I'm with Norman on this... in a programming langauge there has to be as much expliciticity (is that a word??!?) and as little ambiguity as possible. I feel that Einstein notation would quickly get confusing because of the lack of explicit operation identifiers - methodology by context is a nice idea, but impractical for this I believe.

Also, wouldn't it have the side-effect of being more work for the compiler? Whereas index notation would not have that disadvantage.

"Norbert Nemec" <Norbert.Nemec@gmx.de> wrote in message news:cc5u5m$2nv8$1@digitaldaemon.com...
> Ivan Senji wrote:
>
> > Sounds great! But the syntax really shouldn't look like that,
> > the "[i=0..8,j=0..8]" part looks like an array litteral, even if they
> > aren't declared like this.
> >
> > When i think about it again , it could work like that if array litterals
> > had some
> > other syntax. :)
>
> For one, there are no array literals at all. There are array initializers, but that's something different.

Not now, but hopefully there will be in 2.0 :), they are mentioned in the future page.

> Apart from that, it's just a first idea. The exact syntax of course has to be fit into the language much cleaner.
>
> In general, I'm not really sure, whether I like the idea of using brackets for both array literals and array indexing. Maybe, using braces for both array and struct literals might be a better idea. But that again might collide with block delimiters. It really is a pity that we have only three kinds of paired delimiters to choose from. :-(

It really is a pity, but i don't think using [] for array literals and
indexing
is a bad thing as long as it is made  unambiguous.

On Sat, 03 Jul 2004 11:07:50 +0200, Norbert Nemec wrote:

> Knud Sørensen wrote:
> 
>> On Sat, 03 Jul 2004 09:51:11 +0200, Norbert Nemec wrote:
>> 
>>> Stephen Waits wrote:
>>> 
>>>> My only suggestion is that these vector expressions be able to expand to handle non-trivial cases.  For example, think of calculating a vector cross product, or matrix multiplication, quaternion multiplication, etc.
>>> 
>>> I don't think, that would be a good idea: Plain vector operations cover *elementwise* operations. With a good concept, it should be possible to stay flexible and extensible enough, if this is put into the language.
>> 
>> Einstein notation would give you all this and much more.
>> it would also give you powerful vectorization and avoid temporaries.
>> 
>> agian I invite you to take a look at http://dlanguage.netunify.com/56
>> 
>> and tell me what you think.
> 
> See my other message about it. Just one point for clarification:

Yes, we did post replys to each other at the same time.


> Something like:
>         a[i,j] = sum(k){b[i,k]*c[k,j]};  // Pseudo-syntax!
> is called *index-notation* - this is exactly the core of my concept for
> vector operations. (I have no idea yet how to do aggregators like "sum",
> but they will definitely be needed) It was used in mathematics long before
> Einstein was born.
> 

Yes, but how would you implement this sum aggregator on an expression
like

 # B[i,j] = A[k,i]*C[k,l]*A[l,j]; // B=A^T*C*A;

without devectorization.

What Einstein-Notation says that we can drop the sum
because the order of the sums don't matter.
It is in fact a vectorization of multi summations.


> The term "Einstein-Notation" on the other hand only refers to dropping the "sum" in the above expression, saying this sum is implicitly to be understood if one index appears twice. Einstein introduced that convention because he was lazy and because it really saves on writing in relativistic calculations. In contexts outside of relativity, geometry and linear algebra, this convention does not make much sense, though and actually even gets in the way.
> 
> Therefore: index-notation makes perfect sense in D, Einstein-notation (i.e. summing over indices implicitly) would just be extremely confusing and counterproductive in many areas.

Can you give an example of an vectorization which get extremely confusing and counterproductive in Einstein notation.


What about making a vectorization notation shootout.
It could be a wiki page where one could post vectorization problems,
an we could post solutions in different notations.

Then when enough different problems/solutions where posted it would be easier to compare the notations.

Knud

Knud Sørensen wrote:

>> Something like:
>>         a[i,j] = sum(k){b[i,k]*c[k,j]};  // Pseudo-syntax!
>> is called *index-notation* - this is exactly the core of my concept for
>> vector operations. (I have no idea yet how to do aggregators like "sum",
>> but they will definitely be needed) It was used in mathematics long
>> before Einstein was born.
>> 
> 
> Yes, but how would you implement this sum aggregator on an expression
> like
> 
>  # B[i,j] = A[k,i]*C[k,l]*A[l,j]; // B=A^T*C*A;
> 
> without devectorization.

Simple:

        B[i,j] = sum(k){sum(l){A[k,i]*C[k,l]*A[l,j]}};

or, equivalently:

        B[i,j] = sum(k){A[k,i]*sum(l){C[k,l]*A[l,j]}};
        B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]*A[l,j]}};
        B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]}*A[l,j]};
        B[i,j] = sum(l){A[l,j]*sum(k){A[k,i]*C[k,l]}};
        B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]*A[l,j]}};

> What Einstein-Notation says that we can drop the sum
> because the order of the sums don't matter.
> It is in fact a vectorization of multi summations.

This is wrong. It is a general fact that you can switch the order of the sums and that you can pull out factors that do not depend on the summation index. Einstein notation is only possible because of this fact. But for every Einstein expression, you can simply put in the summation signs in some appropriate position.

Really: Einstein notation is *always* just a shorthand for an explicit summation.

> Can you give an example of an vectorization which
> get extremely confusing and counterproductive in Einstein notation.

        D[i] = sum(l){A[l,i]*B[l,i]*C[l,i]};
        D[i,j] = A[i,j]*B[i,j]; // no summation here - just elementwise
                                // multiplication

As said before: these do not make sense for matrices (in the linear algebra meaning), but for general arrays, they may be perfectly sensible.

> What about making a vectorization notation shootout.
> It could be a wiki page where one could post vectorization problems,
> an we could post solutions in different notations.

I don't think that would lead very far. What would be needed is a complete concept for arrays and vectorization. Notation only follows from this concept. If there are several competing concepts we can start discussing. So far, I don't even have a full concept myself. This really is not the time for discussing notation.

On Sat, 03 Jul 2004 18:45:10 +0200, Norbert Nemec wrote:

> Knud Sørensen wrote:
> 
>>> Something like:
>>>         a[i,j] = sum(k){b[i,k]*c[k,j]};  // Pseudo-syntax!
>>> is called *index-notation* - this is exactly the core of my concept for
>>> vector operations. (I have no idea yet how to do aggregators like "sum",
>>> but they will definitely be needed) It was used in mathematics long
>>> before Einstein was born.
>>> 
>> 
>> Yes, but how would you implement this sum aggregator on an expression
>> like
>> 
>>  # B[i,j] = A[k,i]*C[k,l]*A[l,j]; // B=A^T*C*A;
>> 
>> without devectorization.
> 
> Simple:
> 
>         B[i,j] = sum(k){sum(l){A[k,i]*C[k,l]*A[l,j]}};
> 
> or, equivalently:
> 
>         B[i,j] = sum(k){A[k,i]*sum(l){C[k,l]*A[l,j]}};
>         B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]*A[l,j]}};
>         B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]}*A[l,j]};
>         B[i,j] = sum(l){A[l,j]*sum(k){A[k,i]*C[k,l]}};
>         B[i,j] = sum(l){sum(k){A[k,i]*C[k,l]*A[l,j]}};
> 

My question where not about notation but about implimention.

My fear is that the implimention would do the devectorization.


>> What Einstein-Notation says that we can drop the sum
>> because the order of the sums don't matter.
>> It is in fact a vectorization of multi summations.
> 
> This is wrong. It is a general fact that you can switch the order of the sums and that you can pull out factors that do not depend on the summation index. Einstein notation is only possible because of this fact. But for every Einstein expression, you can simply put in the summation signs in some appropriate position.
> 
> Really: Einstein notation is *always* just a shorthand for an explicit summation.
> 
>> Can you give an example of an vectorization which
>> get extremely confusing and counterproductive in Einstein notation.
> 
>         D[i] = sum(l){A[l,i]*B[l,i]*C[l,i]};
>         D[i,j] = A[i,j]*B[i,j]; // no summation here - just elementwise
>                                 // multiplication

With Einstein notation you would write

 # D[i] = A[l,i]*B[l,i]*C[l,i];

 Index l is a free index in a multiplication, so there is a summation.

 # D[i,j] = A[i,j]*B[i,j];

 There is no free index, so the is no summation.

A free index is a index which is only defined on the right hand side.

> As said before: these do not make sense for matrices (in the linear algebra meaning), but for general arrays, they may be perfectly sensible.
> 
>> What about making a vectorization notation shootout.
>> It could be a wiki page where one could post vectorization problems,
>> an we could post solutions in different notations.
> 
> I don't think that would lead very far. What would be needed is a complete concept for arrays and vectorization. Notation only follows from this concept. If there are several competing concepts we can start discussing. So far, I don't even have a full concept myself. This really is not the time for discussing notation.

Yes, but how do you know that the concept is complete.
If you don't have a set of problems to compare it with ??

It is also better to have the problems first or
else one tend to find problems which fit nice into
the concept, instead of a concept that fits the actual problems.

Knud Sørensen wrote:

> My question where not about notation but
> about implemention.
> 
> My fear is that the implemention would do the devectorization.

That depends on how much effort your put into the optimization. Vector expressions are just a means to *allow* the compiler to optimize. Of course, once this is given, a lot of effort and research has to be put into the implementation to really squeeze out that performance.

A simple (and correct) implementation would be to just turn the vector expression into a loop. There would already be some gain compared to traditional loop-programming, since this vectorization can be threaded through function calls, avoiding unnecessary temporary copies of the data.

More sophisticated implementations could go a lot further, sorting the commands for optimal cache/pipeline usage, or maybe even distributed execution.

A language never is fast or slow by itself, but different languages make it easier or harder for the compiler to optimize the code.

>>> What Einstein-Notation says that we can drop the sum
>>> because the order of the sums don't matter.
>>> It is in fact a vectorization of multi summations.
>> 
>> This is wrong. It is a general fact that you can switch the order of the sums and that you can pull out factors that do not depend on the summation index. Einstein notation is only possible because of this fact. But for every Einstein expression, you can simply put in the summation signs in some appropriate position.
>> 
>> Really: Einstein notation is *always* just a shorthand for an explicit summation.
>> 
>>> Can you give an example of an vectorization which
>>> get extremely confusing and counterproductive in Einstein notation.
>> 
>>         D[i] = sum(l){A[l,i]*B[l,i]*C[l,i]};
>>         D[i,j] = A[i,j]*B[i,j]; // no summation here - just elementwise
>>                                 // multiplication
> 
> With Einstein notation you would write
> 
>  # D[i] = A[l,i]*B[l,i]*C[l,i];
> 
>  Index l is a free index in a multiplication, so there is a summation.

But here you will still have to say that l is a index at all. As it stands, it is just an undeclared variable name.

So you can either construct some syntax like

        index l;
        D[i] = A[l,i]*B[l,i]*C[l,i];

or stick with simply do some syntax like:
        D[i] = sum(l){A[l,i]*B[l,i]*C[l,i]};

Which is much more descriptive.

B.t.w: one other example where you will run into trouble:

        D[i] = sin(A[l,i]*B[l,i]);

Now: should that implicit summation happen inside or outside the sine? How about:

        D[i] = sin(A[l,i])*sin(B[l,i]);

And, what about other accumulators? There should be at least an accumulative "product", as well as "and" and "or" as primitives. (Maybe others as commodity: "mean" or "stdev" etc.)

> A free index is a index which is only defined on the right hand side.

I understand pretty well, but I still don't think that would be a good idea in a programming language.

> Yes, but how do you know that the concept is complete.
> If you don't have a set of problems to compare it with ??

I'm not talking of "complete" in some mathematical sense. In this context I would call a "complete" concept one that can be written down in a form that is fit for the language specs. The behavior has to be clearly defined not only for examples but for the general case.

> It is also better to have the problems first or
> else one tend to find problems which fit nice into
> the concept, instead of a concept that fits the actual problems.

Sometimes, it might yet be the other way around. A good programming language does not only solve problems but it inspires you to solve problems you would never have thought of before.

Anyway: in this case, my ideas came from thinking about a very real problem. Vectorization is the key to performance on modern hardware. C++ specialists went through the pains of writing the boost++ library to solve this problem. I think it is worth thinking about ways of doing better in D.

Furthermore: I've been using Matlab for my numerics work lately and I've come to see how much a powerful array mechanism helps in programming. Some of my recent ideas were certainly inspired by Matlab's strengths, others by its weaknesses.

Norbert Nemec wrote:

> Hi there,
> 
> just a few words about this nights thoughts. This is probably post-1.0, but
> it should already be considered now in order to avoid steps in the wrong
> direction.
> 
> For high-performance numerics, vectorization of array operations is
> absolutely crucial. Currently, I know of several approaches to this problem
> in different languages:
> 
> * HPF (High-Performance-Fortran) has powerful vector expression capabilities
> built in. AFAIK, these are always limited to one routine, i.e. you cannot
> spread vectorization across routines. This makes it mostly impossible to
> extend the existing set of vector operations.
> 
> * Some very promising languages (e.g. Single-Assignment-C:
> http://www.sac-home.org) take the step to purely functional languages, or
> even purely declarative languages, where the compiler can optimize much
> more aggressively than in imperative languages.

I very much think this is the solution for the simple reason that it centers around giving the compiler more information, as opposed to pushing the burden onto programmers.

Something that comes to mind is taking advantage of D's foreach and letting the optimizer be a bit more aggressive.  The symbol 'foreach' already connotes the concept of doing a bunch of stuff in some unspecified order, so it's a good choice.  For instance, given something like this,

    // not quite legal because of foreach
    float[4][] sourcePixels, destPixels;
    float[] alpha;
    foreach(float[4] src, inout float[4] dest, float a; sourcePixels, destPixels, alpha) {
        foreach(float s, inout float d; src, dest) {
            d = s * a + d * (1 - a);
        }
    }

it's easy for both people and machines to see that, for the innermost loop, that no iteration depends on the result of any other iteration. So, hypothetically, the compiler could do things like break the expression up a bit,

    d *= (1 - a); d += s * a;

then break those sub-expressions into two separate loops.  From there, a decision to unroll or vectorize could be made.

I think, though, that if it were this easy, it would have been done by now, so it might be best to ignore everything I just said. :)

 -- andy

Norbert Nemec wrote:
> Stephen Waits wrote:
> 
>>My only suggestion is that these vector expressions be able to expand to
>>handle non-trivial cases.  For example, think of calculating a vector
>>cross product, or matrix multiplication, quaternion multiplication, etc.
> 
> I don't think, that would be a good idea: Plain vector operations cover
> *elementwise* operations. With a good concept, it should be possible to
> stay flexible and extensible enough, if this is put into the language.
> 
> The operations you are suggesting go far beyond that in complexity. Of

Sorry, I wasn't suggesting that these operations be built into the language; only that the language allow enough flexibility so that we may code such optimizations without sacrificing so much performance.

I shall research the geometric algebra you mention.

We generally just use quaternions for character animation, and possibly camera animation.

--Steve

Well, I did think about using foreach for the concept of vectorization - anyhow: even though the specs are not very specific about this, foreach loops seem to have a defined order of execution. Just looking at the way opApply is implemented makes the whole thing more like a fancy notation for a good old loop. Trying to integrate this with the concept of vectorization seems more like mixing two different things into one.

It is true that we should avoid new language concepts wherever existing ones can be extended, but it would be equally bad to try to force new meanings into existing concepts where they do not fit.



Andy Friesen wrote:

> Norbert Nemec wrote:
> 
>> Hi there,
>> 
>> just a few words about this nights thoughts. This is probably post-1.0, but it should already be considered now in order to avoid steps in the wrong direction.
>> 
>> For high-performance numerics, vectorization of array operations is absolutely crucial. Currently, I know of several approaches to this problem in different languages:
>> 
>> * HPF (High-Performance-Fortran) has powerful vector expression capabilities built in. AFAIK, these are always limited to one routine, i.e. you cannot spread vectorization across routines. This makes it mostly impossible to extend the existing set of vector operations.
>> 
>> * Some very promising languages (e.g. Single-Assignment-C: http://www.sac-home.org) take the step to purely functional languages, or even purely declarative languages, where the compiler can optimize much more aggressively than in imperative languages.
> 
> I very much think this is the solution for the simple reason that it centers around giving the compiler more information, as opposed to pushing the burden onto programmers.
> 
> Something that comes to mind is taking advantage of D's foreach and letting the optimizer be a bit more aggressive.  The symbol 'foreach' already connotes the concept of doing a bunch of stuff in some unspecified order, so it's a good choice.  For instance, given something like this,
> 
>      // not quite legal because of foreach
>      float[4][] sourcePixels, destPixels;
>      float[] alpha;
>      foreach(float[4] src, inout float[4] dest, float a; sourcePixels,
> destPixels, alpha) {
>          foreach(float s, inout float d; src, dest) {
>              d = s * a + d * (1 - a);
>          }
>      }
> 
> it's easy for both people and machines to see that, for the innermost loop, that no iteration depends on the result of any other iteration. So, hypothetically, the compiler could do things like break the expression up a bit,
> 
>      d *= (1 - a); d += s * a;
> 
> then break those sub-expressions into two separate loops.  From there, a decision to unroll or vectorize could be made.
> 
> I think, though, that if it were this easy, it would have been done by now, so it might be best to ignore everything I just said. :)
> 
>   -- andy