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.

* C++ has expression templates which allow to resolve the vectorization of expression to be done via meta-programming. This allows utmost flexibility, but is very clumsy to use, and what is even more problematic: it can never be tuned as closely to the processor as a good optimizing compiler can.

For D, I already have some ideas how these problems could be overcome,
finding a way in the middle.
-> Full support by the language
-> Simple to use
-> Simple to extend
-> compatible with the (mostly) imperative environment of D

Core idea is, to drop the current concept of array expressions in favor of a more flexible basic concept of vector expressions, using index notation. (I'm not sure about the syntax yet, so I cannot give conclusive details) The functionality of the current (specified but not implemented) array expressions could then simply be implemented in the library without performance penalty.

The other pillar on which the whole idea rests is slice assignment. Thinking about the matter for some time, I think, it might not be a good idea to make slice assignments overloadable at the moment.

Having opIndex and opIndexAssign is a nice, unproblematic thing: as soon as you index an array, you break vectorization anyway, so any fully user-defined array may perform just as good as native arrays. Handling slices though, is tightly coupled with vectorizing code. Once, we know how vector expressions really work, we may find some way to offer a overloadable opSlice and maybe even opSliceAssign. Until then, we should better leave slicing to the native arrays as we have them and not do any rash decisions trying to force multidimensional slicing into the language without having multidimensional arrays. Even the existing opSlice should probably be dropped for now. It certainly is easier to reintroduce later when we realize that it fits in than to remove it if it collides with the rest of the vectorization/slicing concept.

OK, so far for now. Actually, this post mostly means that the matters are postponed further, but it also means that I'm still actively thinking about them.

Ciao,
Nobbi

In article <cc2un6$11gc$1@digitaldaemon.com>, Norbert Nemec says...
>
>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.

Let me throw out a thought here.   How would you feel about
an explicit vectorblock keyword?  Inside a vectorblock the
compiler has a restricted/exteneded subset of the language that
can be aggressively optimized for vector operatons.

What I worry about is that we may hurt the general expressiveness of the language if we put too many restrictions just for vector operations.  I am already annoyed that I can't do things like a[4..12] = a[3..11]. But inside a vectorblock you can make assumptions about array aliasing and other things. The compiler would insert code in debug mode to check these assuptions at the begining of the block.

It's beginning to sound like my project (in C though) called brook
http://brook.sf.net/
still has a lot of work to become useful on cpu's or on clusters...but similar idea...:-)

Patrick Down wrote:
> In article <cc2un6$11gc$1@digitaldaemon.com>, Norbert Nemec says...
> 
>>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.
> 
> 
> Let me throw out a thought here.   How would you feel about
> an explicit vectorblock keyword?  Inside a vectorblock the
> compiler has a restricted/exteneded subset of the language that
> can be aggressively optimized for vector operatons.
> 
> What I worry about is that we may hurt the general expressiveness
> of the language if we put too many restrictions just for vector
> operations.  I am already annoyed that I can't do things like
> a[4..12] = a[3..11]. But inside a vectorblock you can make assumptions about array aliasing and other things. The compiler would insert code in debug mode to check these assuptions at the
> begining of the block.    
> 
> 
> 
> 
> 

Patrick Down wrote:

> In article <cc2un6$11gc$1@digitaldaemon.com>, Norbert Nemec says...
>>
>>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.
> 
> Let me throw out a thought here.   How would you feel about
> an explicit vectorblock keyword?  Inside a vectorblock the
> compiler has a restricted/exteneded subset of the language that
> can be aggressively optimized for vector operatons.
> 
> What I worry about is that we may hurt the general expressiveness of the language if we put too many restrictions just for vector operations.  I am already annoyed that I can't do things like a[4..12] = a[3..11]. But inside a vectorblock you can make assumptions about array aliasing and other things. The compiler would insert code in debug mode to check these assuptions at the begining of the block.


First: of course, D is a general purpose language. Trading general usefulness for qualities in some special area is, of course, not an option.

Second: I don't really like the idea of splitting the language into different "modes". Once you start splitting, the parts will begin to drift apart and in the end you have a mess of different languages.

Conclusion: Of course, vector operations should not restrict the language, but they should still be built into the language with the optimum combination of performance and practicability.


Now your example: You are stating a vector-expression. One possible definition for a vector expression is that the order of execution of the individual parts is not defined. The effect of this is, that your statement is not an error (the compiler cannot detect it), but the outcome is not defined.

Some possible ideas that you might have had to solve the problem would be:

* either define a fixed order of execution in some arbitrary way by the language specs - this would be just cause confusion without solving the problem. (Suddenly a[3..11] = a[4..12] would be correct, but a[4..12] = a[3..11] would be incorrect!)

* ask for enough intelligence in the compiler to choose the right order - I'm pretty sure this is impossible since aliasing cannot be detected at compile time. Your example seems simple enough, but the general case would be a mess to sort out.

* introduce temporary copies wherever aliasing might be possible - this would mean *lots* of overhead that does not only hurt high-performance computing but everyone.

There might be other approaches, but I doubt there is a simple solution.

Of course, all of this has to be investigated more closely, but I don't think anyone would come up with a good solution that allows statements like yours.


Ciao,
Nobbi

I am pretty interested in the future improvements of
D's arrays, so can you please explain (in a couple of words)
what is vectorization (or point me to some place where i could
find out more).

As for array operations:
The only thing that is currently implemented is
int[] x= new int[100]; x[]=3;
and this maybe even isn't an array operation?

But the way i see this feature is like just another way of writing
a loop on the elements of the array.
For example
z[] = x[]+b[];
i see as:
for(int i=0;iyz.length;i++)
    z[i]=x[i]+b[i];

So i think this feature could be more general by maybe introducing a new syntax to say explicitly "for every element of the array" for example:

int[] x,y,z;
z[#] = x[#]+y[#];
And this would mean mathematically speaking z[i]=x[i]+y[i];

We could even do something like:
int func(int x);
func(z[#]); //call func with every z[i], z[i] is int and func takes
int so everything is ok :)

Access to the index would be even greater.
z[#(int index1)] = 5*index1-3;

or even
int[10][10] multidim;

multidim[#(int i)][#(int j)] = i*j+1; //some matrix initialization
or
multidim[#(int i)] = z;
//meaning "for every posible first index assign to multidim[i] = z"

Quite possible many of the things i said are even impossible to implement or maybe useless, but i do beleive array operations could be made very powerfull and usefull feature (maybe not even in this direction but in some other)

Norbert, tell me if i am totally crazy :)

Ivan Senji wrote:

> I am pretty interested in the future improvements of
> D's arrays, so can you please explain (in a couple of words)
> what is vectorization (or point me to some place where i could
> find out more)
...
> Norbert, tell me if i am totally crazy :)

No, your thoughts go pretty much the right direction. But as you can see yourself, it really is difficult to find a syntax that is powerful, clean, simple and extensible. As always in programming language design, you want to have the simple things simple and the complex ones possible.

I have not yet come up with a complete concept for the syntax, but there are some ideas for most pieces already.

One of the core ideas is that you would need two different ways for writing
vector expressions. Index-free like in
        a[] = b[1..3] + c[2..4];
for the simple cases. Here you would need to slice all the operands into the
right shape and then add then. An alternative way to specify the same thing
would be something like:

        a[] = [i=1..3](b[i] + c[i+1]);

This is, of course, much more flexible, also allowing complicated computation inside the vector statement. In the end, you could of course combine both ways wildly.

One important detail is, that vectorization should be possible across function calls. That is, if you write and use something like

int[] myfunc(int[] a,int[] b) {
        return a + b;
}

the language should be defined in a way that allows the compiler to inline this without breaking vectorization. (i.e. without creating intermediate temporary arrays)

Norbert Nemec wrote:
> OK, so far for now. Actually, this post mostly means that the matters are
> postponed further, but it also means that I'm still actively thinking about
> them.

Great post Norbert..

I'd _LOVE_ to see something like this brought into the language.  It opens up an avenue for D in the scientific and real-time-3D area which, IMO, does not currently exist.

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.

What I desire is some of the performance of Boost, without the HORRID ugliness.  In C++ this is accomplished through template expressions, and template meta-programming, all which sounds fun - but in practice it is just awful to work with.  This is all an effort to escape from TEMPORARY OBJECT HELL.. it's an especially hellish hell.

Optimization opportunities that compilers like Codeplay's take advantage of would elevate this language WAY up there IMO..  I believe this language CAN be built to make this easier on compilers, WITHOUT compromising the general purpose goals.

Ideally, something like:

	Vector3 a, b, c;
	c = 2.0 * a + b;

Should reduce and be inlined to something like:

	<vectorizable>
	c[0] = 2.0 * a[0] + b[0];
	c[1] = 2.0 * a[1] + b[1];
	c[2] = 2.0 * a[2] + b[2];
	</vectorizable>

Or, a bigger, more complicated example:

	Vector3  a, b, c;
	Matrix33 m;

	c = m * a.Cross(b);

becomes:

	<vectorizable>
	c[0] =
	   a[0]*(b[1]*m[0,2] - b[2]*m[0,1]) +
	   a[1]*(b[2]*m[0,0] - b[0]*m[0,2]) +
	   a[2]*(b[0]*m[0,1] - b[1]*m[0,0]);

	c[1] =
	   a[0]*(b[1]*m[1,2] - b[2]*m[1,1]) +
	   a[1]*(b[2]*m[1,0] - b[0]*m[1,2]) +
	   a[2]*(b[0]*m[1,1] - b[1]*m[1,0]);

	c[2] =
	   a[0]*(b[1]*m[2,2] - b[2]*m[2,1]) +
	   a[1]*(b[2]*m[2,0] - b[0]*m[2,2]) +
	   a[2]*(b[0]*m[2,1] - b[1]*m[2,0]);
	</vectorizable>


--Steve

PS - Your other post (below) about aliasing is also very important.  In game development, aliasing is one of our worst enemies.

On Fri, 2 Jul 2004 16:24:06 +0000 (UTC), Patrick Down <Patrick_member@pathlink.com> wrote:

> In article <cc2un6$11gc$1@digitaldaemon.com>, Norbert Nemec says...
>>
>> 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.
>
> Let me throw out a thought here.   How would you feel about
> an explicit vectorblock keyword?  Inside a vectorblock the
> compiler has a restricted/exteneded subset of the language that
> can be aggressively optimized for vector operatons.
>
> What I worry about is that we may hurt the general expressiveness
> of the language if we put too many restrictions just for vector
> operations.  I am already annoyed that I can't do things like
> a[4..12] = a[3..11]. But inside a vectorblock you can make
> assumptions about array aliasing and other things. The compiler
> would insert code in debug mode to check these assuptions at the
> begining of the block.

What do you want a[4..12] = a[3..11] to do exactly?

It looks to me like you want to basically do a

memmove(&a[4],&a[3],typeof(a[0]).sizeof * 8);

or is it supposed to do something else?

Regan

-- 
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

Take a look at my array suggestions at http://dlanguage.netunify.com/56

feel free to add to the wiki.

Knud

Why can't we make the current array operations serve this purpose?