Roll your own std::vector ???

[Joanna Carter [TeamB]]

"Peter Olcott" <[email protected]> a écrit dans le message de [email protected]...

| Both simultaneously without any tradeoffs if possible.

Hmmm, if I were you, I would download VS Express and see what it can achieve
before planning for failure

| (1) Where can I get this free copy?

http://msdn.microsoft.com/vstudio/express/default.aspx

| (2) This free copy probably is not licensed for commercial use, and even
if it
| is, would most likely be missing the code optimizers.

http://msdn.microsoft.com/vstudio/express/support/faq/

.... and i doubt whether the compiler would be specialised to be inefficient.

Joanna

 

[Peter Olcott]

"Peter Olcott" <[email protected]> a écrit dans le message de [email protected]...

| Systems programming is entirely different than applications programming.
When
| you are amortizing development costs over millions of users, you just
don't test
| something to see if its good enough. In this case you shoot for the
ballpark of
| as good as possible, right from the very beginning.

There is a well known anti-pattern called "Premature Optimisation", beware
of it, prove that something is too slow before wasting time and effort
trying to speed it up.

Yes, and I have found that I sometimes make this mistake, and must guard against
this mistake. On the other hand when the cost of development is to be amortized
against millions of users, one must provide a much better initial design than is
typical of most development.

If I as one programmer intend to make a product that is superior to the products
offered by the software giants, I can not just throw a few things together and
test them to see if they are good enough. The essential architecture must be
very good in every way, and it must be very good from the very beginning.

I intend to make the Borland Turbo Pascal 3.0 of my product category, (10 times
the quality for 1/10 the cost)

 

[Peter Olcott]

"Peter Olcott" <[email protected]> a écrit dans le message de [email protected]...

| Both simultaneously without any tradeoffs if possible.

Hmmm, if I were you, I would download VS Express and see what it can achieve
before planning for failure

| (1) Where can I get this free copy?

http://msdn.microsoft.com/vstudio/express/default.aspx

| (2) This free copy probably is not licensed for commercial use, and even
if it
| is, would most likely be missing the code optimizers.

http://msdn.microsoft.com/vstudio/express/support/faq/

... and i doubt whether the compiler would be specialised to be inefficient.

Lacking a code optimizer (as all of the cheaper versions of Visual Studio)
typically results in code that executes from 500% to twenty-fold slower. Writing
the code in C# .NET instead of C++ .NET often results in 500% slower code, since
the C++ optimizer has had many more years of fine-tuning it can produce superior
code.

 

[Jon Skeet [C# MVP]]

No. Arrays are always reference types, even if they're arrays of value
types. The difference is that if you have an array of a reference type
(eg String[]) each element of the array is a *reference* to a string,
not the string data itself. If you have an array of a value type
(eg int[]) then each element of the array is a value directly.

So it look like if I want to avoid the huge overhead of boxing and unboxing that
value types have, I must comprise all of my (hand-rolled std::vector like)
arrays of value type which can include elemental types such as int, char,
double, and also composite types such as struct, but not composite types such as
class. Is this right ???

Yes, pretty much. I'd take a bit longer learning the basics of the
language before going too much further with a performance-critical
project, however: using a language you're unfamiliar with, you're
always likely to do things the way you're familiar with rather than the
idiomatic way to start with.

 

[Jon Skeet [C# MVP]]

Lacking a code optimizer (as all of the cheaper versions of Visual Studio)
typically results in code that executes from 500% to twenty-fold slower.

The C# compiler is part of the framework, not part of Visual Studio
itself. Likewise, the JIT compiler (which is where most of the
optimisations occur) is part of the CLR itself.

Don't assume that just because cheap/free versions of other editions of
Visual Studio had weaker compilers means the same is true for VS.NET.

Writing the code in C# .NET instead of C++ .NET often results in 500%
slower code, since the C++ optimizer has had many more years of
fine-tuning it can produce superior code.

Care to produce evidence for this "often" statement? It can happen,
certainly - but in my experience most of the time, C# will end up
"roughly" the same speed as C++ (eg within 20% of the C++ performance,
and sometimes faster than the C++).

 

[Joanna Carter [TeamB]]

"Peter Olcott" <[email protected]> a écrit dans le message de [email protected]...

| Lacking a code optimizer (as all of the cheaper versions of Visual Studio)
| typically results in code that executes from 500% to twenty-fold slower.
Writing
| the code in C# .NET instead of C++ .NET often results in 500% slower code,
since
| the C++ optimizer has had many more years of fine-tuning it can produce
superior
| code.

AFAICT, no version of Visual Studio has an optimiser. Optimisation of .NET
code is usually done by the runtime, platform/cpu specific JITter.

You quote a possible 500% difference in performance, yet you still haven't
actually tried your particular algorithm. Do yourself a favour, end your own
speculation, and get yourself the free version, which will give just the
same end IL code as the pro versions.

Coming from a Delphi background, this native vs .NET speed argument has
cropped up often in the Borland fora. Always, the naysayers were basing
their opinions on rumour and gossip, not on actual evaluations of .NET code
which, on many occasions, turns out to be faster than native code.

It is true that .NET may be slow on the very first execution of a particular
piece of code, but after that first JIT compilation, subsequent executions
turn out to be as fast, if not faster than standard native code. This is
mainly because, once compiled and cached, .NET code *is* native code. What
is more the JIT compiler optimises according to the platform the program
runs on.

Stop prevaricating and let us know what you think of the real C# compiler,
not your theoretical one )

Joanna

 

[Samuel R. Neff]

So you're saying you haven't done any testing to see if boxing is
producing any noticable performance effect and you are prematurely
optimizing based on assumptions with no real-world profiling or
testing.

Thanks for confirming exactly what I asked.

Sam

 

[Peter Olcott]

The C# compiler is part of the framework, not part of Visual Studio
itself. Likewise, the JIT compiler (which is where most of the
optimisations occur) is part of the CLR itself.

Don't assume that just because cheap/free versions of other editions of
Visual Studio had weaker compilers means the same is true for VS.NET.


Care to produce evidence for this "often" statement? It can happen,
certainly - but in my experience most of the time, C# will end up
"roughly" the same speed as C++ (eg within 20% of the C++ performance,
and sometimes faster than the C++).

http://www.tommti-systems.de/go.htm...ain-Dateien/reviews/languages/benchmarks.html

This is from published benchmarks and Microsoft's own recommendations. At least
much of optimization, and possibly most of optimization must occur before the
jitter ever sees the code. This is because much semantic information is lost
after the code has been initially translated, thus there is less of a basis for
semantically equivalent transformations.

 

[Peter Olcott]

"Peter Olcott" <[email protected]> a écrit dans le message de [email protected]...

| Lacking a code optimizer (as all of the cheaper versions of Visual Studio)
| typically results in code that executes from 500% to twenty-fold slower.
Writing
| the code in C# .NET instead of C++ .NET often results in 500% slower code,
since
| the C++ optimizer has had many more years of fine-tuning it can produce
superior
| code.

AFAICT, no version of Visual Studio has an optimiser. Optimisation of .NET
code is usually done by the runtime, platform/cpu specific JITter.

That would directly contradict Microsoft's published recommendation of using C++
for maximum .NET performance, thus I would expect that you are simply wrong on
this point.

You quote a possible 500% difference in performance, yet you still haven't
actually tried your particular algorithm. Do yourself a favour, end your own
speculation, and get yourself the free version, which will give just the
same end IL code as the pro versions.

C++ .NET also has a smaller learning curve for me than C# .NET.

Coming from a Delphi background, this native vs .NET speed argument has
cropped up often in the Borland fora. Always, the naysayers were basing
their opinions on rumour and gossip, not on actual evaluations of .NET code
which, on many occasions, turns out to be faster than native code.

http://www.tommti-systems.de/go.htm...ain-Dateien/reviews/languages/benchmarks.html
http://www.osnews.com/img/5602/results.jpg

The above shows a big difference between native code and .NET code on the first
link.
The second link shows a big difference between .NET code across different
language compilers.

 

[Peter Olcott]

I don't have the time to learn something to see if it is worth learning, I must
accomplish at least 40 hours worth of work, every day (notice that I did not say
every week, I must accomplish 60% more work than there are hours in a day).

 

[Lucian Wischik]

http://www.tommti-systems.de/go.htm...ain-Dateien/reviews/languages/benchmarks.html
http://www.osnews.com/img/5602/results.jpg
The above shows a big difference between native code and .NET code on the first
link.

???

The link shows C# to be within a factor between 1 and 2 for pretty
much everything. The only outlier is "list", but it's a bad benchmark:
the c++ version uses vector<int>, and the c# uses ArrayList, but as
we've discussed in this thread it should instead use List<int>.

 

[Peter Olcott]

???

The link shows C# to be within a factor between 1 and 2 for pretty
much everything. The only outlier is "list", but it's a bad benchmark:
the c++ version uses vector<int>, and the c# uses ArrayList, but as
we've discussed in this thread it should instead use List<int>.

But then that is my whole point in a prior thread. Generics were not available
when this benchmark was created, and thus the drastic boxing and unboxing
overhead becomes quite apparent.

 

[Jon Skeet [C# MVP]]

http://www.tommti-systems.de/go.html?http://www.tommti-systems.de/
main-Dateien/reviews/languages/benchmarks.html

This is from published benchmarks and Microsoft's own recommendations.

a) That's .NET 1.1 - it would be interesting to see the .NET 2.0
results
b) I haven't looked at the code yet, but the fact that Java is
significantly faster in a couple of the benchmarks suggests there's
further room for optimisation
c) There's only *one* test where C# is five times slower than C++ - so
surely you can accept that your statement that .NET "typically" results
in code that executes 5-20x slower is a gross exaggeration. Do you
usually regard one in fourteen as "typical"?

At least
much of optimization, and possibly most of optimization must occur before the
jitter ever sees the code.

No, I believe the JIT does most of the optimisation, actually.

This is because much semantic information is lost after the code has
been initially translated, thus there is less of a basis for
semantically equivalent transformations.

If you decompile some C#, you can get back to something very close to
the original - so very little information is being lost, leaving the
JIT with plenty of room for optimisation.

 

[Lucian Wischik]

a) That's .NET 1.1 - it would be interesting to see the .NET 2.0
results
b) I haven't looked at the code yet, but the fact that Java is
significantly faster in a couple of the benchmarks suggests there's
further room for optimisation

Okay, here are my results for that benchmark:

c++ using vector: 28 seconds
C#.net1 using ArrayList: 19.3 seconds
C#.net2 using ArrayList: 19.5 seconds
C#.net2 using List<int>: 19.1 seconds
Also, VS2005 and Visual C# Express were identical in speed.

Of those 19 seconds, 6 of them are spent building a 10,000 element
list by repeatedly inserting a new member at the front, 10 of them are
spent clearing two 10,000 element lists by repeatedly removing the
element at the front, and the rest of the work is O(n) rather than
O(n^2).

So this benchmark is basically just doing memcpy() on a 40k block of
memory, repeatedly. It says nothing about the relative cost of boxing
or unboxing. That's why the generics are no faster than the ArrayList.

I don't know why I'm getting the exact opposite resoluts from that
webpage -- I'm getting a moderately slower c++vector, whereas the
webpage gets an extremely slower c#.net1. Obviously one of us has a
typo somewhere! I also don't know why ArrayList should be any faster
than c++vector.

Here, I've distilled out the essence (O^n2) of that anomalous
benchmark:

// c++ version
//
int main()
{ int t = GetTickCount();
for (int j=0; j<100; j++)
{ vector<int> v;
for (int i=0; i<10000; i++) v.push_back(i);
vector<int> v2 = v;
vector<int> v3;
for (int i=0; i<10000; i++) v3.insert(v3.begin(),i);
while (!v.empty()) v.erase(v.begin());
while (!v2.empty()) v2.erase(v2.begin());
printf(".");
}
printf("\nTime: %i\n",(int)(GetTickCount()-t));
return 0;
}


// c# version
//
static void Main(string[] args)
{ DateTime startTime = DateTime.Now;
for(int j=0; j<100; j++)
{ ArrayList v = new ArrayList();
for (int i=0; i<10000; i++) v.Insert(v.Count, i);
ArrayList v2 = new ArrayList(v);
ArrayList v3 = new ArrayList();
for (int i=0; i<10000; i++) v3.Insert(0,i);
while (v2.Count>0) v2.RemoveAt(0);
while (v3.Count>0) v3.RemoveAt(0);
Console.Write(".");
}
Console.WriteLine("\nVector elapsed time: " +
DateTime.Now.Subtract(startTime).TotalMilliseconds + " ms");
}

 

[Samuel R. Neff]

If you don't have time to learn new things you're really in the wrong
business.

Sam

 

[Peter Olcott]

a) That's .NET 1.1 - it would be interesting to see the .NET 2.0
results
b) I haven't looked at the code yet, but the fact that Java is
significantly faster in a couple of the benchmarks suggests there's
further room for optimisation
c) There's only *one* test where C# is five times slower than C++ - so
surely you can accept that your statement that .NET "typically" results
in code that executes 5-20x slower is a gross exaggeration. Do you
usually regard one in fourteen as "typical"?

Since I always use the construct where C# did 500% worse, and good programming
practice would require always using such a construct, then C# is often (if not
typically) 500% slower. As it turns out, the solution derived from this thread
directly addresses this specific problem. The Boxing and UnBoxing of ArrayList
simply costs way too much.

No, I believe the JIT does most of the optimisation, actually.


If you decompile some C#, you can get back to something very close to
the original - so very little information is being lost, leaving the
JIT with plenty of room for optimization.

That is not the way that compiler optimization works. Too much semantic
information is lost after it has been translated into the intermediate code for
much optimization to be applied. I posted another benchmark across the different
..NET languages, there was a substantial difference.

 

[Peter Olcott]

Okay, here are my results for that benchmark:

c++ using vector: 28 seconds
C#.net1 using ArrayList: 19.3 seconds
C#.net2 using ArrayList: 19.5 seconds
C#.net2 using List<int>: 19.1 seconds
Also, VS2005 and Visual C# Express were identical in speed.

Obviously something has changed. Did you use the same version of .NET ???
Also it might be that the compiler did much worse on std::vector rather than did
much better on ArrayList. You might try this test with different levels of
optimization, in some cases the optimizer might be eliminating some of the
steps.

Of those 19 seconds, 6 of them are spent building a 10,000 element
list by repeatedly inserting a new member at the front, 10 of them are
spent clearing two 10,000 element lists by repeatedly removing the
element at the front, and the rest of the work is O(n) rather than
O(n^2).

So this benchmark is basically just doing memcpy() on a 40k block of
memory, repeatedly. It says nothing about the relative cost of boxing
or unboxing. That's why the generics are no faster than the ArrayList.

I don't know why I'm getting the exact opposite resoluts from that
webpage -- I'm getting a moderately slower c++vector, whereas the
webpage gets an extremely slower c#.net1. Obviously one of us has a
typo somewhere! I also don't know why ArrayList should be any faster
than c++vector.

Here, I've distilled out the essence (O^n2) of that anomalous
benchmark:

// c++ version
//
int main()
{ int t = GetTickCount();
for (int j=0; j<100; j++)
{ vector<int> v;
for (int i=0; i<10000; i++) v.push_back(i);
vector<int> v2 = v;
vector<int> v3;
for (int i=0; i<10000; i++) v3.insert(v3.begin(),i);
while (!v.empty()) v.erase(v.begin());
while (!v2.empty()) v2.erase(v2.begin());
printf(".");
}
printf("\nTime: %i\n",(int)(GetTickCount()-t));
return 0;
}


// c# version
//
static void Main(string[] args)
{ DateTime startTime = DateTime.Now;
for(int j=0; j<100; j++)
{ ArrayList v = new ArrayList();
for (int i=0; i<10000; i++) v.Insert(v.Count, i);
ArrayList v2 = new ArrayList(v);
ArrayList v3 = new ArrayList();
for (int i=0; i<10000; i++) v3.Insert(0,i);
while (v2.Count>0) v2.RemoveAt(0);
while (v3.Count>0) v3.RemoveAt(0);
Console.Write(".");
}
Console.WriteLine("\nVector elapsed time: " +
DateTime.Now.Subtract(startTime).TotalMilliseconds + " ms");
}

 

[Peter Olcott]

If you don't have time to learn new things you're really in the wrong
business.

Sam

I did not say that I don't have time to learn new things. I said I don't have
time to learn new things to see if they are worth learning. Spending six months
learning something that ends up proving to be useless would bankrupt me at this
particular stage of my venture.

 

[Lucian Wischik]

That is not the way that compiler optimization works. Too much semantic
information is lost after it has been translated into the intermediate code for
much optimization to be applied. I posted another benchmark across the different
.NET languages, there was a substantial difference.

Peter, that's incorrect. Have you ever looked at the IL? It really has
lost very little information. That's why e.g. Microsoft's code
analysis FxCop is able to run and give useful results on IL.

http://www.osnews.com/img/5602/results.jpg

This was the benchmark you posted. It did not show what you claimed.
It showed both .net languages to have identical performance, except
that the VB version used a slower IO library.

Since I always use the construct where C# did 500% worse, and good programming
practice would require always using such a construct, then C# is often (if not
typically) 500% slower. As it turns out, the solution derived from this thread
directly addresses this specific problem. The Boxing and UnBoxing of ArrayList
simply costs way too much.

The 500% you quote was a benchmark that did NOT test the performance
of boxing and unboxing. The construct it used was an O(n^2) operation
where an O(n) operation was appropriate. If this is a construct you
use often, then I suggest you fix your code!

 

[Lucian Wischik]

Obviously something has changed. Did you use the same version of .NET ???
Also it might be that the compiler did much worse on std::vector rather than did
much better on ArrayList. You might try this test with different levels of
optimization

I tested it on VS2003 and VS2005. I did the c++ version with
optimizations for speed, and profile-guided optimization.

In any case, the c++ runs just as fast with optimizations turned on as
with them turned off. That's because the benchmark is testing how fast
the library can copy a 40k block of memory (as it removes or inserts
the head element from a 10,000 element vector). This is sure as
anything going to be a ready-provided small machine code library
routine, e.g. memcpy, and outside the realm of compiler optimizations.