Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15504 > unrolled thread

The container abstraction and parallel programming

Back to article view | Back to comp.lang.c

Contents

  The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:02 +0100
    Re: The container abstraction and parallel programming blp@cs.stanford.edu (Ben Pfaff) - 2012-01-06 15:08 -0800
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:27 +0100
        Re: The container abstraction and parallel programming blp@cs.stanford.edu (Ben Pfaff) - 2012-01-06 15:30 -0800
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 00:41 +0100
    Re: The container abstraction and parallel programming Kaz Kylheku <kaz@kylheku.com> - 2012-01-07 00:04 +0000
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:06 +0100
      Re: The container abstraction and parallel programming Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-01-08 03:42 -0800
    Re: The container abstraction and parallel programming Ian Collins <ian-news@hotmail.com> - 2012-01-07 13:50 +1300
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:31 +0100
        Re: The container abstraction and parallel programming Ian Collins <ian-news@hotmail.com> - 2012-01-07 22:03 +1300
        Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 07:39 -0600
          Re: The container abstraction and parallel programming Gene <gene.ressler@gmail.com> - 2012-01-07 09:27 -0800
            Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-08 11:37 -0600
              Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 18:42 +0100
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:48 +0100
            Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 11:16 +0000
            Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-08 11:52 -0600
              Re: The container abstraction and parallel programming Keith Thompson <kst-u@mib.org> - 2012-01-08 14:17 -0800
                Re: The container abstraction and parallel programming pete <pfiland@mindspring.com> - 2012-01-08 22:08 -0500
                Re: The container abstraction and parallel programming Stephen Sprunk <stephen@sprunk.org> - 2012-01-09 11:07 -0600
                  Re: The container abstraction and parallel programming Keith Thompson <kst-u@mib.org> - 2012-01-09 14:55 -0800
              Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-09 00:22 +0100
            Re: The container abstraction and parallel programming Nobody <nobody@nowhere.com> - 2012-01-09 14:19 +0000
              Re: The container abstraction and parallel programming Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-09 16:40 +0000
              Re: The container abstraction and parallel programming Kaz Kylheku <kaz@kylheku.com> - 2012-01-09 17:53 +0000
              Re: The container abstraction and parallel programming Gene <gene.ressler@gmail.com> - 2012-01-10 16:58 -0800
    Re: The container abstraction and parallel programming Robert Wessel <robertwessel2@yahoo.com> - 2012-01-07 01:28 -0600
    Re: The container abstraction and parallel programming Jens Gustedt <jens.gustedt@loria.fr> - 2012-01-07 09:39 +0100
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-07 09:54 +0100
        Re: The container abstraction and parallel programming Jens Gustedt <jens.gustedt@loria.fr> - 2012-01-07 11:36 +0100
    Re: The container abstraction and parallel programming Gareth Owen <gwowen@gmail.com> - 2012-01-08 08:08 +0000
      Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:41 +0100
        Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:53 +0100
        Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 11:59 +0100
        Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 11:05 +0000
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-08 12:29 +0100
            Re: The container abstraction and parallel programming ec429 <ec429@cam.ac.uk> - 2012-01-08 13:35 +0000
        Re: The container abstraction and parallel programming gwowen <gwowen@gmail.com> - 2012-01-09 01:09 -0800
        Re: The container abstraction and parallel programming Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-26 09:23 -0800
          Re: The container abstraction and parallel programming jacob navia <jacob@spamsink.net> - 2012-01-26 23:41 +0100
            Re: The container abstraction and parallel programming Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-07 16:18 -0800

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#15646

On 08-Jan-12 16:17, Keith Thompson wrote:
> Stephen Sprunk <stephen@sprunk.org> writes:
>> On 08-Jan-12 04:48, jacob navia wrote:
> [...]
>>> If I write:
>>>
>>>     c = (a+b)/2;
>>>     if (c&1) fn(1);
>>>
>>> You could deduce that c must be of integer type isn't it?
>>
>> Um, no.  It could be any arithmetic type.
> 
> "c&1" is valid only if c is of some integer type.

I stand corrected.  Still, there are obvious problems with expecting the
compiler to deduce the type of undeclared variables.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#15666

Stephen Sprunk <stephen@sprunk.org> writes:
> On 08-Jan-12 16:17, Keith Thompson wrote:
>> Stephen Sprunk <stephen@sprunk.org> writes:
>>> On 08-Jan-12 04:48, jacob navia wrote:
>> [...]
>>>> If I write:
>>>>
>>>>     c = (a+b)/2;
>>>>     if (c&1) fn(1);
>>>>
>>>> You could deduce that c must be of integer type isn't it?
>>>
>>> Um, no.  It could be any arithmetic type.
>> 
>> "c&1" is valid only if c is of some integer type.
>
> I stand corrected.  Still, there are obvious problems with expecting the
> compiler to deduce the type of undeclared variables.

For example, that conforming C compilers don't do that.  (For some
other languages, it probably makes perfect sense.)

Looking upthread, I see that it was intended as an example of the
kind of inference a C compiler *shouldn't* do, in the context of
whether compilers should infer that they can use SIMD.  I'm not
going to get into that particular debate, other than to observe
that it's not a perfect analogy.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#15598

Le 08/01/12 18:52, Stephen Sprunk a écrit :
> On 08-Jan-12 04:48, jacob navia wrote:
>> If I write:
>>
>>      c = (a+b)/2;
>>      if (c&1) fn(1);
>>
>> You could deduce that c must be of integer type isn't it?
>
> Um, no.  It could be any arithmetic type.
>

c&1 implies c is an integer since all other floating types do not
support that operation.

It could be char/short/int/long/long long/, and by reading more
code the compiler could even differentiate among them.

[toc] | [prev] | [next] | [standalone]

#15635

On Sun, 08 Jan 2012 11:48:28 +0100, jacob navia wrote:

> gcc will vectorize this:
> 
> void doADD(double *L, double *R, double *result,size_t n)
> {
>       for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
> }

Doesn't it require "restrict"?

I would expect vectorisation to produce the wrong result if result
overlaps either L or R.

[toc] | [prev] | [next] | [standalone]

#15645

Nobody <nobody@nowhere.com> writes:

> On Sun, 08 Jan 2012 11:48:28 +0100, jacob navia wrote:
>
>> gcc will vectorize this:
>> 
>> void doADD(double *L, double *R, double *result,size_t n)
>> {
>>       for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
>> }
>
> Doesn't it require "restrict"?

Yes.

> I would expect vectorisation to produce the wrong result if result
> overlaps either L or R.

A simple test shows that different code is generated with and without
the restrict keyword.  If I lie to the compiler (i.e. I use restrict but
pass pointers to overlapping data) the code does indeed give the "wrong"
result (at optimisation level -O3 but not at -O2).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15647

On 2012-01-09, Nobody <nobody@nowhere.com> wrote:
> On Sun, 08 Jan 2012 11:48:28 +0100, jacob navia wrote:
>
>> gcc will vectorize this:
>> 
>> void doADD(double *L, double *R, double *result,size_t n)
>> {
>>       for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
>> }
>
> Doesn't it require "restrict"?

No; the compiler could spit out two versions of the code along with a
run-time overlap check.

[toc] | [prev] | [next] | [standalone]

#15722

On Jan 9, 9:19 am, Nobody <nob...@nowhere.com> wrote:
> On Sun, 08 Jan 2012 11:48:28 +0100, jacob navia wrote:
> > gcc will vectorize this:
>
> > void doADD(double *L, double *R, double *result,size_t n)
> > {
> >       for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
> > }
>
> Doesn't it require "restrict"?
>
> I would expect vectorisation to produce the wrong result if result
> overlaps either L or R.

Likely true if compiled as a function, but with gcc -O3 this will be
inlined then vectorized.  At least that was my experience.

[toc] | [prev] | [next] | [standalone]

#15523

On Sat, 07 Jan 2012 00:02:07 +0100, jacob navia <jacob@spamsink.net>
wrote:

>Today, more than 10 years tafter Intel introduced the first SIMD 
>instructions it is still not possible to use those instructions to do 
>SIMD programming when you use C and two mainstream compilers like gcc or 
>MSVC.
>
> From the C side there is absolutely no support for this type of 
>programming, even though plain arrays could do the trick obviously.
>
>
>The container abstraction, specifically the valarray container, could be 
>used to *mean* SIMD using operator overloading.
>
>The use case could be
>
>ValArray operator+(ValArray left,ValArray right);
>
>This would allow an operation like adding two arrays element-wise
>to be performed using SIMD instructions.
>
>
>Obviously, the usual "optimizations" can be added to those
>basic operations so that
>	
>         ValArray a,b,c,d;
>
>	a = b+c+d;
>
>doesn't have to produce an intermediate array but can be "compiled"
>by an overloaded assignment operator to generate
>
>	a[i] = b[i]+c[i]+d[i];
>
>as is done in C++. Each overloaded operator returns a token operator
>containing information about its arguments, and the overloaded 
>assignment operator compiles correct element-wise code by reparsing
>the generated tree.
>
>To prepare for this, the C Containers library proposes the ValArray
>container, for each of the basic types (char, short, int, long long and 
>size_t).
>
>In the sample implementation there is a generic module that
>allows to generate code for ANY type, also those being left out like
>long (since it is always either equal to int or equal to long long in
>all implementations I know of). The type size_t was added to be able
>to correctly index any sequantial container with a ValArray of size_t's.
>
>The code proposed NOW is plain serial code, but can (and should) be
>replaced in more sophisticated implementations than the sample 
>implementation to do SIMD programming, one of the most basic forms
>of parallelism, already available in plain hardware since already 10 
>years...
>
>Obviously the four basic operations should be there, but other kinds of 
>array operations could be interesting like
>
>o REDUCE Apply binary operation to each element and the running total:
>	REDUCE + 1 2 3 4 5  --> 1+2+3+4+5 = 15
>
>         You apply operator + to the identity element for "+" and to the
>         first element: 0+1 --> 1
>         You apply the operator + to the second element and the result
>         of the last operation: 1+2-->3
>	ETC until the last element is reached.
>
>o EXPAND Apply binary operation producing a ValArray of same length
>         containing the intermediate results:
>         EXPAND + 1 2 3 4 5 --> 1 3 6 10 15
>
>
>o SELECT  Apply boolean vector to ValArray selecting all elements that
>           correspond to 1 and eliminate those with zeros.
>
>	SELECT 1 1 0 1 0 0 / 10 20 30 40 50 60 --> 10 20 40
>
>o EXTEND Apply boolean vector to ValArray leaving all elements with 1
>          and introducing the zero or blank (for character arrays) at the
>          zero positions:
>
>          EXTEND 1 1 0 1 0 0 / 10 20 40 --> 10 20 0 40 0 0
>
>The idea is to select a set of operations that makes it easy to work 
>with arrays as objects of operations instead of working with scalar data.
>
>What new operations should be in the set?
>How could those operations be incoporated into mainstream C?


There are a number of vector libraries, some fairly standard (BLAS,
LAPACK, etc.), which can be used from C.  Rather than reinventing this
from scratch, it would probably be useful to see where those are and
build from there.  BLAS, in particular, sounds like it would cover
much of what you're trying to do, and it has a free* standard and
reference implementation.  Then there are a fair number of CPU
optimized implementations of BLAS available under various license
terms (for example, for x86, Intel implements BLAS as part of MKL**,
which can be used not only with ICC, but with MSVC and GCC, among
others).


*I've not looked at the BLAS license in detail, but it's at least
approximately free in the beer sense

**MKL also provides several other libraries, including an alternate
(and somewhat simpler) vector library.

[toc] | [prev] | [next] | [standalone]

#15528

Am 01/07/2012 12:02 AM, schrieb jacob navia:
> How could those operations be incoporated into mainstream C?

macros and _Generic

Jens

[toc] | [prev] | [next] | [standalone]

#15529

Le 07/01/12 09:39, Jens Gustedt a écrit :
> Am 01/07/2012 12:02 AM, schrieb jacob navia:
>> How could those operations be incoporated into mainstream C?
>
> macros and _Generic
>
> Jens

Hi Jens

"macros and _Generic"... can you maybe elaborate a bit?
That was far to cryptic for my small brain.

:-)

[toc] | [prev] | [next] | [standalone]

#15536

Salut Jacob,

Am 01/07/2012 09:54 AM, schrieb jacob navia:
> Le 07/01/12 09:39, Jens Gustedt a écrit :
>> macros and _Generic

> "macros and _Generic"... can you maybe elaborate a bit?
> That was far to cryptic for my small brain.

probably a bit too terse, yes :)

what I meant is that you need a type generic interface for these things,
not necessarily a language extension

the idea would be to write a whole bunch of type specific functions that
cover the different cases (different primitive types, different
operations). Then you can put a type generic glue arround that by using
macros and the brand new _Generic from C11. This only would give you
function like syntax but would make it easily usable.

Then, after some time there could perhaps be some convergence on the
functionalities and one could think of adding keywords and/or operator
support.

I don't know how far you are for your compiler for implementing _Generic
(if you attacked it at all). Gcc already has equivalent features that
are usable and that I am currently using to implement the set of type
generic atomic_... interfaces of C11. I think the interface complexity
of that is about the same as what would be necessary for vector
operations. (BTW thinking about it, _Pragma can also be quite handy when
programming such things.)

Cheers
Jens

[toc] | [prev] | [next] | [standalone]

#15570

jacob navia <jacob@spamsink.net> writes:

> Today, more than 10 years tafter Intel introduced the first SIMD
> instructions it is still not possible to use those instructions to do
> SIMD programming when you use C and two mainstream compilers like gcc
> or MSVC.

Nonsense.  As well as the builtins already mentioned, GCC has
-ftree-vectorize which uses these SIMD instructions automatically when
the compiler can deduce that the aliasing rules allow it. Dot product
and matrix multiplication get a sizeable speed up when you use it.  
The 'restrict' keyword helps a lot, also

[toc] | [prev] | [next] | [standalone]

#15573

Le 08/01/12 09:08, Gareth Owen a écrit :
> jacob navia<jacob@spamsink.net>  writes:
>
>> Today, more than 10 years tafter Intel introduced the first SIMD
>> instructions it is still not possible to use those instructions to do
>> SIMD programming when you use C and two mainstream compilers like gcc
>> or MSVC.
>
> Nonsense.  As well as the builtins already mentioned, GCC has
> -ftree-vectorize which uses these SIMD instructions automatically when
> the compiler can deduce that the aliasing rules allow it. Dot product
> and matrix multiplication get a sizeable speed up when you use it.
> The 'restrict' keyword helps a lot, also

Nonsense, gcc doesn't have a real vectorizer. For instance:

void doADD(double *L, double *R, double *result,size_t n)
{
      for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
}

This is exactly the same program as

void doADD(double *L, double *R, double *result,size_t n)
{
      for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
}

But NO option (including -ftree-vectorize, as you suggest) will
convince gcc to use the parallel instructions in the first case.

Only Intel has a more stable version of a vectorizer, since
only Intel can afford to pay dozens of computer scientists
dozens of years full time to build it.

Gcc has invested a considerable effort and the results are
not very good, as you can see.

But of course, why make simple when you can do complicated?

Why is not possible that  the PROGRAMMER declares a special
data type that should be used in SIMD programming?

That was the main argument of my post and nobody has given a sensible
answer to it. Most of the answer are like yours:

"Nonsense. gcc can do it automatically"

[toc] | [prev] | [next] | [standalone]

#15575

Le 08/01/12 11:41, jacob navia a écrit :
> void doADD(double *L, double *R, double *result,size_t n)
> {
> for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
> }
>

that should have been:

for(size_t i=0; i<n;i++) result[n-i-1]=L[n-i-1]+R[n-i-1];

The results are the same for gcc with following options:

gcc -O3 -c -S -std=c99 -ftree-vectorize maybe.c

inner loop:
         movsd   -8(%rdi), %xmm0
         addsd   -8(%rsi), %xmm0
         movsd   %xmm0, -8(%rax)

movsd = MOVe Scalar Double precision

[toc] | [prev] | [next] | [standalone]

#15576

Le 08/01/12 11:41, jacob navia a écrit :
>
If you change the starting index to something Other than zero
the vectorization fails

> void doADD(double *L, double *R, double *result,size_t n)
> {
> for(size_t i=1; i<n;i++) result[i]=L[i]+R[i];
> }

[toc] | [prev] | [next] | [standalone]

#15577

On 08/01/12 10:41, jacob navia wrote:
> Nonsense, gcc doesn't have a real vectorizer. For instance:
>
> void doADD(double *L, double *R, double *result,size_t n)
> {
> for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
> }
>
> This is exactly the same program as
>
> void doADD(double *L, double *R, double *result,size_t n)
> {
> for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
> }
Actually, those programs aren't "exactly the same", due to the lack of 
the aforementioned "restrict" keyword.  For instance:
  double array[3]={0,1,2};
  doADD(array+1, array+1, array, 2);
In the first case you will get array={8,4,2}; in the second, array={2,4,2}.
In general, the correct approach to parallel programming is giving the 
compiler as few constraints as possible.  This can sometimes be achieved 
with 'restrict', but not much can be done in procedural languages unless 
they have some explicit means of telling the compiler that normal order 
constraints can be relaxed (which would be a /much/ more useful 
extension to C than processor-specific vectorisation primitives, since 
the latter would reduce the portable glory of C to the provincial 
insularity of assembler (not that assembler isn't valuable in 
appropriate circumstances, of course!)).  In C as it stands, the 
canonical way to do this is by means of threads (at least in C11; '99 
and its predecessors don't mention threaded execution, but many 
implementations support it).  SIMD has its uses, of course; but unless 
your code is perversely written (and so long as you have used 'restrict' 
where appropriate) the compiler knows better than you do.  Besides, your 
time as a programmer is worth enough that you generally shouldn't be 
expending it on non-portable performance hacks unless you /know/ your 
code will be run a very large number of times.  YAGNI.
If you really want to write strongly parallelisable programs (rather 
than merely hand-optimising with a few vector ops that probably don't 
gain you much anyway) try a functional language, such as LISP - with a 
properly designed data-flow model parallel processing becomes something 
that the implementation can do transparently.

I think you just don't like gcc, because you know (and don't want to 
admit to yourself) that it's better than yours.
-e
-- 
'sane', adj.: see 'unimaginative'
   on the web - http://jttlov.no-ip.org

[toc] | [prev] | [next] | [standalone]

#15579

Le 08/01/12 12:05, ec429 a écrit :
> On 08/01/12 10:41, jacob navia wrote:
> Actually, those programs aren't "exactly the same", due to the lack of
> the aforementioned "restrict" keyword. For instance:
> double array[3]={0,1,2};
> doADD(array+1, array+1, array, 2);

Adding the "restrict" keyword doesn't change anything.


> In general, the correct approach to parallel programming is giving the
> compiler as few constraints as possible. This can sometimes be achieved
> with 'restrict', but not much can be done in procedural languages unless
> they have some explicit means of telling the compiler that normal order
> constraints can be relaxed (which would be a /much/ more useful
> extension to C than processor-specific vectorisation primitives, since
> the latter would reduce the portable glory of C to the provincial
> insularity of assembler (not that assembler isn't valuable in
> appropriate circumstances, of course!)).


Well, thanks a lot. It is EXACTLY what I proposed in the message that 
started this discussion. We should have a way to tell the compiler
to use SIMD operations in a special object that we declare as SIMD.

> In C as it stands, the
> canonical way to do this is by means of threads (at least in C11; '99
> and its predecessors don't mention threaded execution, but many
> implementations support it). SIMD has its uses, of course; but unless
> your code is perversely written (and so long as you have used 'restrict'
> where appropriate) the compiler knows better than you do. Besides, your
> time as a programmer is worth enough that you generally shouldn't be
> expending it on non-portable performance hacks unless you /know/ your
> code will be run a very large number of times. YAGNI.

1) Using threads to make SIMD is not possible. The overhead of thread
    creation and maintenance is impossible high.

2) Your remarks about "The compiler knows better" have no connection
    with reality. Gcc, that is a highly advanced compiler, is unable
    to do SIMD reliably, as I proved. It suffices a small change and
    the whole thing COLLAPSES.

3) Your remarks about avoiding performance hacks are welcome since it is
    exactly what I was saying: we need a portable way of using SIMD that
    is supported by the language.


> If you really want to write strongly parallelisable programs (rather
> than merely hand-optimising with a few vector ops that probably don't
> gain you much anyway) try a functional language, such as LISP - with a
> properly designed data-flow model parallel processing becomes something
> that the implementation can do transparently.
>

Well, I am using C, and I do not see how LISP would be useful in this 
context since it would need the same extensions that you would need in 
C. Lisp is NOT SIMD per se.

> I think you just don't like gcc, because you know (and don't want to
> admit to yourself) that it's better than yours.


I have never denied that gcc generates better code than lcc.
In my posting I spoke of two mainstream compilers like gcc and MSVC
That is all. And what I said was right: they aren't able to use SIMD
programming in a useful way.

But you do not like what I say (and you do not want to admit it
to yourself) because I am NOT using gcc and even have the audacity of
trying to build a different compiler!

You see?

If you get to personal attacks or suppositions we just can't discuss.
Everything becomes a stupid war of "gcc is the best and you are wrong
because you use another compiler"

[toc] | [prev] | [next] | [standalone]

#15583

On 08/01/12 11:29, jacob navia wrote:
> Le 08/01/12 12:05, ec429 a écrit :
>> Actually, those programs aren't "exactly the same", due to the lack of
>> the aforementioned "restrict" keyword. For instance:
>> double array[3]={0,1,2};
>> doADD(array+1, array+1, array, 2);
>
> Adding the "restrict" keyword doesn't change anything.
This is patently false.  Adding the "restrict" keyword certainly changes 
the program (from the perspective of the C standard) since it promises 
to the compiler that the pointers will not be aliased, thereby making 
optimisations (such as SIMD) legal (they otherwise would not be).
> Well, thanks a lot. It is EXACTLY what I proposed in the message that
> started this discussion. We should have a way to tell the compiler
> to use SIMD operations in a special object that we declare as SIMD.
No, you have missed the point.  You don't tell the compiler to "use SIMD 
instructions"; you tell the compiler that it /may/ operate on these data 
in any order since the operators are commutative, nothing is aliased, 
&c.; if the target platform has SIMD instructions the compiler may 
choose to use them.  I cannot stress enough that this is the compiler's job.
Mixing container abstractions with compiler internals, as your OP seems 
to propose, is a pathway to infinite pain; instead, your containers 
library (if such a thing be even necessary) should be written in a 
manner susceptible to optimisation by SIMD-aware compilers - namely, it 
should make full use of the restrict keyword, and handle arrays simply 
where possible; also, data dependencies should be carefully controlled. 
  (Data dependencies limit all reordering)
If, after doing this, you find that the compiler does not use SIMD 
instructions, you patch the compiler (in as general a way as possible). 
  You do _not_ patch the language.
> 1) Using threads to make SIMD is not possible. The overhead of thread
> creation and maintenance is impossible high.
I wasn't suggesting using threads for SIMD; I was merely discussing 
parallelisation in general terms.
> 2) Your remarks about "The compiler knows better" have no connection
> with reality. Gcc, that is a highly advanced compiler, is unable
> to do SIMD reliably, as I proved. It suffices a small change and
> the whole thing COLLAPSES.
Ok, I'll clarify.  The compiler *in principle* knows better, and if it 
gets it wrong, you patch the compiler; you don't patch the language.
> 3) Your remarks about avoiding performance hacks are welcome since it is
> exactly what I was saying: we need a portable way of using SIMD that
> is supported by the language.
"Using SIMD" in your code is a performance hack.  /Making the use of 
SIMD by the compiler possible/ in your code is portable, and avoids 
performance hacks.
> Well, I am using C, and I do not see how LISP would be useful in this
> context since it would need the same extensions that you would need in
> C. Lisp is NOT SIMD per se.
Lisp is inherently parallel; one entirely valid model of execution is to 
consider every cons as being executed in parallel, blocking on its data 
dependencies from its car and cdr.  This is why functional languages 
often incorporate monads, because I/O happens to need to be serial.
A sufficiently intelligent LISP compiler could compile (reduce), 
(expand), (select), and (extend) to appropriate SIMD instructions if the 
target platform has them.  But this is c.l.c, not c.l.lisp.
> I have never denied that gcc generates better code than lcc.
> In my posting I spoke of two mainstream compilers like gcc and MSVC
> That is all. And what I said was right: they aren't able to use SIMD
> programming in a useful way.
I suspect your definition of "useful" is isomorphic to "anything 
mainstream compilers don't do".  As other posters have explained, gcc 
can indeed use SIMD in a useful way, but only where sufficient promises 
have been made to it (like "restrict") for such use not to be a 
violation of the C standard.  Since it's good practice to make those 
promises wherever you can (even if you don't foresee an immediate 
benefit - just the documentation effect of const and restrict justifies 
their use), I don't see what you're complaining about.
> But you do not like what I say (and you do not want to admit it
> to yourself) because I am NOT using gcc and even have the audacity of
> trying to build a different compiler!
I laud your efforts to build a compiler; I'm impressed that you are able 
to do so.  But that doesn't necessarily mean that ideas you have for the 
extension of the language are good ones.
> If you get to personal attacks or suppositions we just can't discuss.
> Everything becomes a stupid war of "gcc is the best and you are wrong
> because you use another compiler"
I'm not a High Priest of the One True Way (tm) of gcc. rather my gold 
standard is The Standard.  Its extension or emendation is justified only 
when it can be shown to have failed.  On SIMD it has not done so.
gcc may currently use less SIMD than it could.  That is a problem to be 
solved by work on gcc, or by creating a better compiler that matches 
gcc's good qualities while avoiding its bad habits.  It is not a problem 
to be solved by adding non-portable incompatible extensions to the 
language, particularly when the language already provides sufficient 
recourse.
-e
-- 
'sane', adj.: see 'unimaginative'
   on the web - http://jttlov.no-ip.org

[toc] | [prev] | [next] | [standalone]

#15609

On Jan 8, 10:41 am, jacob navia <ja...@spamsink.net> wrote:
> Nonsense, gcc doesn't have a real vectorizer. For instance:

It doesn't have a *perfect* vectorizer.

> But NO option (including -ftree-vectorize, as you suggest) will
> convince gcc to use the parallel instructions in the first case.

Yes, you can confuse vectorizers.  You can also confuse optimizers.

Do you think I can't obfuscate trivial code so badly that lcc can't
optimize it?
Does that mean lcc doesn't have a real optimizer?

Of course it doesn't mean that.  By writing clear C I've got a
measurable out of GCC's imperfect vectorizer, and no semantic
arguments will ever prevent that from being true.

> That was the main argument of my post and nobody has given a sensible answer to it.
> Most of the answer are like yours:

No one has agreed with you, certainly. That means one of two things:
i) You're wrong
ii) Everyone else is wrong.

[toc] | [prev] | [next] | [standalone]

#16263

jacob navia <jacob@spamsink.net> writes:

> Le 08/01/12 09:08, Gareth Owen a @C3{A9}crit :
>> jacob navia<jacob@spamsink.net>  writes:
>>
>>> Today, more than 10 years tafter Intel introduced the first SIMD
>>> instructions it is still not possible to use those instructions to do
>>> SIMD programming when you use C and two mainstream compilers like gcc
>>> or MSVC.
>>
>> Nonsense.  As well as the builtins already mentioned, GCC has
>> -ftree-vectorize which uses these SIMD instructions automatically when
>> the compiler can deduce that the aliasing rules allow it. Dot product
>> and matrix multiplication get a sizeable speed up when you use it.
>> The 'restrict' keyword helps a lot, also
>
> Nonsense, gcc doesn't have a real vectorizer. For instance:
>
> void doADD(double *L, double *R, double *result,size_t n)
> {
>      for(size_t i=0; i<n;i++) result[n-i]=L[n-i]+R[n-i];
> }
>
> This is exactly the same program as
>
> void doADD(double *L, double *R, double *result,size_t n)
> {
>      for(size_t i=0; i<n;i++) result[i]=L[i]+R[i];
> }
>
> But NO option (including -ftree-vectorize, as you suggest) will
> convince gcc to use the parallel instructions in the first case.
>
> Only Intel has a more stable version of a vectorizer, since
> only Intel can afford to pay dozens of computer scientists
> dozens of years full time to build it.
>
> Gcc has invested a considerable effort and the results are
> not very good, as you can see.
>
> But of course, why make simple when you can do complicated?
>
> Why is not possible that  the PROGRAMMER declares a special
> data type that should be used in SIMD programming?
>
> That was the main argument of my post and nobody has given a sensible
> answer to it.  [snip]

The problem is, no one other than yourself finds your argument
persuasive, let alone convincing.  Does that give you any sort
of pause or prompt any further reflection?

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web