Really shouldn't waste the effort in replying, but this post is so full of FUD ... Puhhhleez ! I will, however, not pollute this decent topic further by pointing out exactly how much fallacy is involved. Instead, I'll try to assume it's an offbeat attempt at humor.

"Berin Loritsch" <bloritsch@d-haven.org> wrote in message news:cf8c0q$qnr$1@digitaldaemon.com...
> I would be careful with this.  Something I have found with Java IO Streams is that buffering can backfire--and if there is no way to turn it off then the developer is stuck.  Let me give an example:
>
> In a web environment you need to handle as many requests as you can at one time.  This is key to scalability.  Initial testing might suggest that using a BufferedInputStream for file IO would speed up the request/response time on the server.  Then later, when you are doing load testing, you find that the extra KB or so of RAM taken up by the buffer is adding up quickly and your system starts falling apart at the seams due to the heavy load on the memory system.
>
> This is something I have been bitten by in the past.  I would be surprised to find it only limited to Java.  The solution to use unbuffered IO or even a greatly reduced buffer size helped the scalability of the webapp.

Stratus wrote:

> Really shouldn't waste the effort in replying, but this post is so full of
> FUD ... Puhhhleez ! I will, however, not pollute this decent topic further
> by pointing out exactly how much fallacy is involved. Instead, I'll try to
> assume it's an offbeat attempt at humor.

Actually, it is an anecdote of history.

> 
> "Berin Loritsch" <bloritsch@d-haven.org> wrote in message
> news:cf8c0q$qnr$1@digitaldaemon.com...
> 
>>I would be careful with this.  Something I have found with Java IO
>>Streams is that buffering can backfire--and if there is no way to
>>turn it off then the developer is stuck.  Let me give an example:
>>
>>In a web environment you need to handle as many requests as you can
>>at one time.  This is key to scalability.  Initial testing might
>>suggest that using a BufferedInputStream for file IO would speed up
>>the request/response time on the server.  Then later, when you are
>>doing load testing, you find that the extra KB or so of RAM taken
>>up by the buffer is adding up quickly and your system starts falling
>>apart at the seams due to the heavy load on the memory system.
>>
>>This is something I have been bitten by in the past.  I would be
>>surprised to find it only limited to Java.  The solution to use
>>unbuffered IO or even a greatly reduced buffer size helped the
>>scalability of the webapp.
> 
> 
> 

Berin Loritsch wrote:

> Stratus wrote:
> 
>> Really shouldn't waste the effort in replying, but this post is so full of
>> FUD ... Puhhhleez ! I will, however, not pollute this decent topic further
>> by pointing out exactly how much fallacy is involved. Instead, I'll try to
>> assume it's an offbeat attempt at humor.
> 
> 
> Actually, it is an anecdote of history.
> 

Besides whats wrong with supplying both an UnbufferedFile and a
BufferedFile?  You have the flexibility when you need it.  I assume
you don't want to take the time to discover how little falacy is
involved.  Or how that particular premature optmization bit me.

Berin Loritsch wrote:

> Ben Hinkle wrote:
> <snip>
> 
>> Have you tried using a BufferedFile? The default File is unbuffered. There
>> are a number of posters who think the default File should be buffered and
>> I'm starting to agree - just because people seem to assume it is buffered.
> 
> 
> I would be careful with this.  Something I have found with Java IO
> Streams is that buffering can backfire--and if there is no way to
> turn it off then the developer is stuck.  Let me give an example:

I read "the default File should be buffered" to mean both are allowed and it's the developer's choice.

Just because one is given a preferential name doesn't mean that the other isn't allowed.

No need for alarm. ;)

-- 
Justin (a/k/a jcc7)
http://jcc_7.tripod.com/d/

In article <cf8b1l$qb0$1@digitaldaemon.com>, Ben Hinkle says...
>
>Have you tried using a BufferedFile? The default File is unbuffered. There are a number of posters who think the default File should be buffered and I'm starting to agree - just because people seem to assume it is buffered.
>

Here is that along with a similiar Java version. Thanks for the tip on
BufferedFile().

;----------
D version:

import std.string;
import std.stream;
import std.outbuffer;

int main()
{
char[] input;
OutBuffer output = new OutBuffer();

output.write("<TABLE><TR><TD>\n");
BufferedFile f = new BufferedFile("some_large_file",FileMode.In);
while(!f.eof()) {
input = f.readLine();
output.write(input);
output.write("</TD><TD>\n");
}
f.close();

output.write("</TD></TR></TABLE>\n");

printf("output length: %d\n",output.toString().length);
return(0);
}
;---
output length: 6944735
real    0m0.767s
user    0m0.710s
sys     0m0.060s

;;-----------------------

Java version:

import java.io.*;
import java.util.*;
import java.text.*;

public class html {
public static void main(String[] args)
{
String input;
StringBuffer output = new StringBuffer();

output.append("<TABLE><TR><TD>\n");
try {
FileReader f = new FileReader("some_large_file");
BufferedReader in = new BufferedReader(f);
while ((input = in.readLine()) != null) {
output.append(input);
output.append("</TD><TD>\n");
}
f.close();
} catch (IOException e) {
System.err.println(e);
return;
}

output.append("</TD></TR></TABLE>\n");

System.out.println("output length: " + output.toString().length());
}
}
;---
# /usr/java/j2sdk1.4.2_05/bin/javac html.java
# time /usr/java/j2sdk1.4.2_05/bin/java -server html
output length: 6944735
real    0m1.881s
user    0m0.780s
sys     0m0.050s

Howabout introducing a special keyword so that you could mark variables that will not alias?

I suggest this because the alias detection is very costly to do. During the compilation it is impossible (just imagine an array of pointers/objects that is filled runtime). During runtime you need to do it all the time for it to be effective - always when utilizing two variables of the same kind, or taken to the extreme: when accessing two memory locations.

For example:

void mangle(inout int a, inout int b)
{
  b += a + 5;
  a += b;
}

generates something like in pseudo-risc-asm:

// calculate b+a+5
mov reg1, a // reg1 <- a
mov reg2, b
add reg2, reg2, 5 // reg1 <- reg1 + 5
add reg2, reg2, reg1
// store b
mov b, reg2
// calculate a+b
mov reg1, a
add reg1, reg1, reg2
// store a
mov a, reg1

in this example there are one unnecessary read and one store, if the values do not alias. The b needs to be stored in the first statement because the value of a would be changed if they aliased. Similarly, we need to read the value a again in the latter statement because we don't know if the variables aliased or not.

If you know that these variables will never ever alias, you can touch them with noalias keyword which will tell the compiler that it can perform some optimizations.

void mangle(inout noalias int a, inout noalias int b)
{
  b += a + 5;
  a += b;
}

that would generate:

// calculate b+a+5
mov reg1, a
mov reg2, b
add reg2, reg2, 5
add reg2, reg2, reg1
// calculate a+b
add reg1, reg1, reg2
// store both a and b
mov a, reg1
mov b, reg2

Now the two memory accesses in the between are removed and the algorithm would run faster. With more complex algorithms the benefits get even bigger as more stuff could be stored in the registers.

This syntax might be familiar for some of you from compiler called VectorC. (http://www.codeplay.com/)

To sum it up:

Automatic alias detection is a very hard task to do - it will involve complex data flow analysis compile-time and tedious checking run-time.
In compile-time, the optimizations must be safe. If there is a change that variables might alias, they are expected to alias. This reduces the changes to optimize while the calculation time is huge (compare for example to inline-optimizations). It works on local variables though (which will be optimized anyway). Run-time checks bloat the code so that the benefits will vanish. And what would happen in variables alias? Exception thrown?

But manually aiding the compiler is very easy to implement and can be efficient. Instead of introducing new keyword it could be done with the compiler extensions that D supports (this is a compiler design problem, after all). There is still risk of human error, but then again if you need to optimize your code, you should know what you are doing.

-- texmex/sampsa lehtonen



On Sun, 1 Aug 2004 13:46:35 +0000 (UTC), Dave <Dave_member@pathlink.com> wrote:

>
> I'm very new to D (literally as of yesterday), but am very impressed with what
> I'm seeing so far.
>
> Being that I want this language to succeed and an important part of that will be
> performance potential over C, I'm curious - how does/will D deal with the
> pointer 'aliasing problem' that plagues C and C++ compiler developers?
>
> From what little I've seen so far, it seems that this same problem has been
> 'forced' on D by it's backward compatability with C libraries and C/C++ -like
> support for pointers.
>
> IMHO, any language that seeks to replace C/C++ should do it's best to avoid this
> problem, or at least discourage code that introduces it.
>
>

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

Duh!

I should have read all the messages in the thread before posting... never mind.

I think that function parameters should be considered to alias, at least in the regular builds. In the optimized versions (release), they could be expected not to alias... But then again, this might have weird side effects, where debug code works as expected and optimized doesn't.

At least it would be good idea to have option for "safe-compile". Coupled with compiler extensions for noalias/alias it could prove powerful.

-- texmex/sampsa lehtonen

On Tue, 10 Aug 2004 16:09:57 +0300, Sampsa Lehtonen <snlehton@cc.hut.fi> wrote:

> Howabout introducing a special keyword so that you could mark variables that will not alias?



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

In article <opscip3stw35qbu1@macray>, Sampsa Lehtonen says...
>
>Duh!
>
>I should have read all the messages in the thread before posting... never mind.
>
<snip>

Thanks for posting - your example helped clarify the 'cost' of aliasing on performance, and why.

Below is a simple example of what I'm talking about and why I think this issue is important to consider.

#include <cstdio>
// This sample is in C++ because it can demonstrate the large
//  performance difference with an Intel C++ compiler switch.
//  Think of '&' as 'inout' in D
void foo(int& ri, int& rj)
{
// ri and rj are not related as used and are operated on separately.
//  But the C/C++ spec. says thecompiler has to assume that they may
//  reference the same var., so this code cannot be optimized aggressively.
for(int idx = 0; idx < 10000000; idx++) { ri++; rj++; }
}

void bar(int& ri, int& rj, int& rk)
{
// Same here - successive calls passing around references (very common,
//  especially in OOP code) only exaserbates the issue.
foo(ri,rj);
for(int idx = 0; idx < 10000; idx++) { ri = rj % 10; rk += rj - rk; }
}

int main()
{
int i = 0, j = 0, k = 0;
for(int idx = 0; idx < 1000; idx++) bar(i,j,k);
printf("i = %d, j = %d, k = %d\n",i,j,k);
}

# icc -O3 -static t_alias.cpp -o t_alias
# icc -O3 -fno-alias -static t_alias.cpp -o t_alias_opt

# time t_alias
i = 8, j = 1410065408, k = 1410065408
real    0m17.371s
user    0m17.310s
sys     0m0.010s

# time t_alias_opt
i = 8, j = 1410065408, k = 1410065408
real    0m2.414s
user    0m2.410s
sys     0m0.000s

It's apparent this can make a very large difference in peformance, yet the results and code are identical.

Considering methods calling methods calling methods, etc... The end-results can be pretty large.

The magnitude of this result actually surprised me also, and I knew it was a problem.

The whole concern is that more often than not, the aliasing 'de-optimization' effects common, often used, correctly used code because C/C++ compilers allow aliasing.

My proposal would be something along the lines of changing out/inout function/method params to 'noalias' by default, if a compile-time or even debug run-time check could be done.

How about this for a proposal:
- 'noalias' for out/inout params limited to primitive types, structs and arrays
of primitive types.
- pointers left as-is for C compatibility, and so code like the above could be
done if the side effects of param1 and param2 referencing the same variable are
desired.
- For primitive type params (not pointers to prim. types), warn on passing of a
de-referenced pointer. For example:
int i;
int* j = &i;
foo(i,*j); //Compiler warning: de-referenced ptr. passed inout.

Among others I'm sure, that leaves this case in D:

class X {
int i;
}

int main()
{
X x = new X();
x.i = 10;
Y y = x;        // y is now a reference to x in D
foo(x.i,y.i);
}

Anyone think of a solution for that?? Maybe that would be a case for a debug runtime check. Or could the compiler reasonably check for this at compile time?

Something like the above would probably satisfy the numerics crowd along with many other applications of inout params., because often the most performance sensitive code (i.e.: passed params used in tight loops) deals with primitive types.

They added the 'restrict' keyword in C, and I guess many lib. function calls are being re-written to use it. Even functions like fopen are being changed:

/* C89: */
fopen(const char *path, const char *mode);
// C99:
fopen(const char * restrict path, const char * restrict mode);

The difference can be that large I guess. Who would've thought fopen()? It's used a lot but usually not in tight loops..

Think of UI code passing primitive types around. Think of the inards of a lot of templates using native types. Think of socket calls de/serializing structs.

Just about anything called in functions passing around references used repetitively can be effected in a big way by aliasing.

As for your mention of aliasing within arrays, I believe the spec. already prohibits some 'overlapping' for slicing, so that takes care of part of your concern for native type arrays, I think.

- Dave

Dave schrieb:

> Doh! CTFA (Check the fargin' Archives). Sorry, and thanks for the responses and
> pointers to the archives.

No problem. It just takes time and threads get forgotten, because the
newsgroup grows too fast for anyone to follow.

> Here are some from back a while.. Can anyone tell me if the non-overlapping
> array prohibition is still part of the spec.?

As far as i know, it is with whole-array operations (they are not
implemented yet iirc). It is not specified in which order the elements
would be processed, and thus they must be unaliased...

I don't think it holds true of functions in general. One solution might
be a sort-of unoverlapping assert, which would be standard and both keep
us safe and enable optimizations. BTW, asserts usually do enable
optimizations in D - in release mode, their true-ness is assumed for
optimization, although the assert code itself is left out.

Even if it's not there, the whole array operations would probably carry
the bulk of performance optimization by utilizing the SIMD units.

The check itself is technically very simple and doesn't consume time,
since arrays are pointer&length and one only has to check their
overlapping. Since C doesn't have a concept of an array, i hardly
imagine how such a check could be done.

> http://www.digitalmars.com/drn-bin/wwwnews?D/348
> http://www.digitalmars.com/drn-bin/wwwnews?D/1926
> http://www.digitalmars.com/drn-bin/wwwnews?D/18534
> http://www.digitalmars.com/drn-bin/wwwnews?D/18543
> http://www.digitalmars.com/drn-bin/wwwnews?D/17971

Phew, you do some investigation work. :)

> The following deal with exactly what my original post had in mind:
> 
> http://www.digitalmars.com/drn-bin/wwwnews?D/28260, to qoute Walter: 
> 
> "Historically, adding in special keywords for such optimizations has not worked
> out well. That's why I was thinking of making it implicit for D function
> parameters."
> 
> I AGREE - let's do that (make it implicit, but warn in debug mode), or is it too
> late?

No, i don't think things like that are late. The compiler doesn't look
like it's approaching the spec very soon, and code gets broken every now
and then.

> http://www.digitalmars.com/drn-bin/wwwnews?D/28377, to qoute Walter again:
> 
> "I think it would be better to have the compiler assume they are not aliased
> (since that is by far the usual case) and have to say when they are not aliased.
> Also, a runtime check that they really are not aliased might be appropriate in
> debug mode."
> 
> I, again, wholeheartedly AGREE.

Hmmm... And what would one do when one is willing to accept aliased
arrays? And is there any necessity in this case anyway?

What i see in front of my eyes, is a function, which inputs 2 arrays and outputs a new one. I understand that there should be no aliasing if it was to output in one of the inputs, but aliasing between the inputs would be OK if the output is a new array.

You mention Fortran doesn't have the problem. How does Fortran deal with aliasing?

If i remember correctly, Sather has some way to identify possible aliasing hazards statically, and allow aliasing if nothing speaks against it, though i might be wrong - perhaps it was just planned. Sather is a whole-program compiler. D is geared towards whole-program compilation, but should also work without it. C++ is too weak for all that.

> I'm with Drew here: http://www.digitalmars.com/drn-bin/wwwnews?D/28904
> 
> What is the state of this as far as D goes?
> 
> God Bless you Walter, I can see you put a lot of thought into memory layout for
> and vectorizing of arrays and such, and also the aliasing issue.
> 
> Hopefully these ideas (non-overlapping arrays and implicit no-alias with debug
> warning) have stood the test of time and v1 implementation so far. Because if
> they do, I think it covers a lot of the issue for not only HPC code, but also
> many other things now-a-days, like writing high-throughput socket code, database
> engines, AI engines, speech synthesis, etc., etc., etc...
> 
> It seems like Walter wants to give both us and compiler implementors a great
> high-performance base to work with..
> 
> Not only that, but consider this: In these days of cool, productive and decent
> performance interpreted languages like Perl, Python, etc. not to mention Java,
> many people are just not going to switch just because of excellent new features
> (most people think "their" language has enough features - after all, they've
> been able to "get by with it so-far").
> 
> Now, if you give them:
> 
> - High-performance on the order Fortran,
> - Intuitive (implicit aliasing like C is NOT intuitive to most people using
> Perl, VB, Java, etc. and therefore is the source of a lot of bugs to them),
> - True OOP language with all the features of D,
> 
> THAT in total is a great reason to switch.
> 
> How about the compiler developers?? Many of them would quit en-masse if you told
> them they had to implement C++ all over again, except with MORE features ;)
> 
> Thanks for all of the pointers to the archived messages.
> 
> - Dave
> 
> In article <ceoed5$1btb$1@digitaldaemon.com>, Ben Hinkle says...
> 
>>Not a stupid question at all. See previous threads, for example http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/5274
>>Norbet and Walter (and probably others) had a nice discussion about future
>>possibilities. Walter doesn't like "restrict" much either.
>>
>>Dave wrote:
>>
>>
>>>Was this that stupid of a question or what? Seriously..
> 
> 
> 

I inadvertently skewed the results when I caused an overflow by bumping the loop count up to make the test run for a decent amt. of time.

If you change the loop in both foo() and bar() to 1000000 iterations, the
relative difference is even larger (>7x compared to >10x):

# time t_alias_opt # no-alias
i = 0, j = 1000000000, k = 1000000000
real    0m1.010s
user    0m1.000s
sys     0m0.000s

# time t_alias # alias
i = 0, j = 1000000000, k = 1000000000
real    0m11.287s
user    0m10.810s
sys     0m0.020s

BTW - Just to be clear, my intention is /not/ to suggest a compiler switch for D like the demonstration C/C++ compiler has.

Thanks,

- Dave

In article <cfaq4t$2v67$1@digitaldaemon.com>, Dave says...
>
>Below is a simple example of what I'm talking about and why I think this issue is important to consider.
>
>#include <cstdio>
>// This sample is in C++ because it can demonstrate the large
>//  performance difference with an Intel C++ compiler switch.
>//  Think of '&' as 'inout' in D
>void foo(int& ri, int& rj)
>{
>// ri and rj are not related as used and are operated on separately.
>//  But the C/C++ spec. says thecompiler has to assume that they may
>//  reference the same var., so this code cannot be optimized aggressively.
>for(int idx = 0; idx < 10000000; idx++) { ri++; rj++; }
>}
>
>void bar(int& ri, int& rj, int& rk)
>{
>// Same here - successive calls passing around references (very common,
>//  especially in OOP code) only exaserbates the issue.
>foo(ri,rj);
>for(int idx = 0; idx < 10000; idx++) { ri = rj % 10; rk += rj - rk; }
>}
>
>int main()
>{
>int i = 0, j = 0, k = 0;
>for(int idx = 0; idx < 1000; idx++) bar(i,j,k);
>printf("i = %d, j = %d, k = %d\n",i,j,k);
>}
>
># icc -O3 -static t_alias.cpp -o t_alias
># icc -O3 -fno-alias -static t_alias.cpp -o t_alias_opt
>
># time t_alias
>i = 8, j = 1410065408, k = 1410065408
>real    0m17.371s
>user    0m17.310s
>sys     0m0.010s
>
># time t_alias_opt
>i = 8, j = 1410065408, k = 1410065408
>real    0m2.414s
>user    0m2.410s
>sys     0m0.000s
>
>It's apparent this can make a very large difference in peformance, yet the results and code are identical.