422,764 Members | 1,289 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 422,764 IT Pros & Developers. It's quick & easy.

Shootout (fannkuch)

P: n/a
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<ig****@yahoo.comwrote:
>Why don't you go through all...
This time I am going to demonstrate a very serious problem with the
shootout site.

The algorithms used by C, C++, and D are BETTER than the Java
versions! What the heck? In some cases Java version is so bad that
it's 10 times slower.

Let's start over again. We go through the list one by one.

You have this version of Java for fannkuch

http://shootout.alioth.debian.org/gp...lang=java&id=2

I wrote a different version (algorithm used by Heiner Marxen)

http://pastebin.com/f41c2ef6f

When n = 11

0m10.165s -client (old version)
0m6.064s -client (this new version)

4 seconds faster...

Let's compare it now with C++ version

http://shootout.alioth.debian.org/gp...&lang=gpp&id=2

g++ -pipe -O3 -fomit-frame-pointer fannkuch.cpp -o fannkuch.exe
jc -inline+ fannkuch (java native compiler)

N 9 10 11
g++ 0.115s 0.442s 4.542s
java 0.206s 0.596s 5.970s (-client)
jet 0.310s 4.355s 4.355s

I used -client since it's faster than -server in this case. Jet in
this case beats g++ with n = 11. With n = 12, difference is even
bigger 1m1.187s v 0m56.697s

Jun 27 '08 #1
Share this Question
Share on Google+
37 Replies


P: n/a
On Mon, 05 May 2008 01:54:16 -0500, Razii <ty******@hotmail.com>
wrote:
>N 9 10 11
g++ 0.115s 0.442s 4.542s
java 0.206s 0.596s 5.970s (-client)
jet 0.310s 4.355s 4.355s
>With n = 12, difference is even bigger 1m1.187s v 0m56.697s
To make it also work with gcj, I had to make slight changes (use print
instead of printf), so the new version is this
http://pastebin.com/f630a1d8a

N 9 10 11 12
gcj 0.110s 0.398s 4.026s 54.037s (on Ubuntu)

That's even faster than Jet

I used both -fno-bounds-check AND -fno-store-check, something that you
never seem to do.
Jun 27 '08 #2

P: n/a
On Mon, 05 May 2008 04:03:34 -0500, Razii <ty******@hotmail.com>
wrote:
>>N 9 10 11
g++ 0.115s 0.442s 4.542s
java 0.206s 0.596s 5.970s (-client)
jet 0.310s 4.355s 4.355s
typo: that should have been 0.591s with n=10 for Jet

Jun 27 '08 #3

P: n/a
Razii <ty******@hotmail.comwrites:
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<ig****@yahoo.comwrote:
>>Why don't you go through all...

This time I am going to demonstrate a very serious problem with the
shootout site.
Why don't you go demonstrate it to someone who gives a damn? This kind
of language evangelism (aka pissing contest) is just infantile. Give it
a rest already.

*plonk*

sherm--

--
My blog: http://shermspace.blogspot.com
Cocoa programming in Perl: http://camelbones.sourceforge.net
Jun 27 '08 #4

P: n/a
On May 5, 8:54*am, Razii <tynkf...@hotmail.comwrote:
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy

<igo...@yahoo.comwrote:
Why don't you go through all...

This time I am going to demonstrate a very serious problem with the
shootout site.

The algorithms used by C, C++, and D are BETTER than the Java
versions! What the heck? In some cases Java version is so bad that
it's 10 times slower.
Well, I wouldn't be to serious about shootout site,
as programs compared are trivial and results vary on
setup and machine. You can conclude only that
on particular machine, with particular
os, with particular setup, results are as they
are. You can't conclude that results will
be in same proportion on anything else.
For example on my computer both c and c++ versions
show same execution time (gcc 4.2.3).
That should be that way as both are basically same.
C++ version uses vector instead of raw array and
also swaps with std function instead of doing it manually.
But that costs 30% in performance according to site.
Interesting is that following version of c++ program
shows 10% increase in performance relative to both c and c++ version
on the site on my computer ;)
I only use next_permutation instead of algorithm showed
in benchmark, and populate arrays in range of 1..n,
instead of 0..n-1.
What isn't clear to me is why flips are not performed
when permutation array has maximum value for last
element?

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

struct Inc{
int operator()(){ return i_++; }
Inc(int i=1):i_(i){}
int i_;
};
int fannkuch(int n, ostream &o) {
if (n < 1) return 0;
vector<intperm(n),flips(n);
generate(perm.begin(),perm.end(),Inc());
int dispcount=0, maxFlips=0;
do
{
if(dispcount++<30)
{
copy(perm.begin(),perm.end(),ostream_iterator<int> (o));
o<<'\n';
}
if (!(perm[0]==1 || perm[n-1]==n)) // ?? why
{
copy(perm.begin(),perm.end(),flips.begin());
int nflips=0;
while(flips[0]!=1)
{
reverse(flips.begin(),flips.begin()+flips[0]);
++nflips;
}
if(nflips>maxFlips)maxFlips=nflips;
}
}while(next_permutation(perm.begin(),perm.end()));
return maxFlips;
}
int main(int argc, const char **argv) {
int n = (argc>1) ? atoi(argv[1]) : 0;
cout << "Pfannkuchen(" << n << ") = "
<< fannkuch(n, cout) << '\n';
return 0;
}

Greetings, Branimir.

Jun 27 '08 #5

P: n/a
On Mon, 05 May 2008 05:47:08 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>*plonk*
Jun 27 '08 #6

P: n/a
On Mon, 05 May 2008 05:47:08 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>Why don't you go demonstrate it to someone who gives a damn?
<PLONKK>

Jun 27 '08 #7

P: n/a
Another opportunity to use the "Ignore Thread" feature in
"Right Click Watch Ignore" extensions for Thunderbird.

--
Andrea Francia
http://www.andreafrancia.it/
Jun 27 '08 #8

P: n/a
On May 5, 3:10 am, Branimir Maksimovic <bm...@hotmail.comwrote:
On May 5, 8:54 am, Razii <tynkf...@hotmail.comwrote:
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<igo...@yahoo.comwrote:
>Why don't you go through all...
This time I am going to demonstrate a very serious problem with the
shootoutsite.
The algorithms used by C, C++, and D are BETTER than the Java
versions! What the heck? In some cases Java version is so bad that
it's 10 times slower.

The FAQ gives instructions on how to contribute better programs

http://shootout.alioth.debian.org/gp4/faq.php#play
Well, I wouldn't be to serious aboutshootoutsite,
as programs compared are trivial and results vary on
setup and machine. You can conclude only that
on particular machine, with particular
os, with particular setup, results are as they
are. You can't conclude that results will
be in same proportion on anything else.

Performance measurements are brittle.

For example on my computer both c and c++ versions
show same execution time (gcc 4.2.3).
That should be that way as both are basically same.
C++ version uses vector instead of raw array and
also swaps with std function instead of doing it manually.
But that costs 30% in performance according to site.
Interesting is that following version of c++ program
shows 10% increase in performance relative to both c and c++ version
on the site on my computer ;)
I only use next_permutation instead of algorithm showed
in benchmark, and populate arrays in range of 1..n,
instead of 0..n-1.
What isn't clear to me is why flips are not performed
when permutation array has maximum value for last
element?

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

struct Inc{
int operator()(){ return i_++; }
Inc(int i=1):i_(i){}
int i_;};

int fannkuch(int n, ostream &o) {
if (n < 1) return 0;
vector<intperm(n),flips(n);
generate(perm.begin(),perm.end(),Inc());
int dispcount=0, maxFlips=0;
do
{
if(dispcount++<30)
{
copy(perm.begin(),perm.end(),ostream_iterator<int> (o));
o<<'\n';
}
if (!(perm[0]==1 || perm[n-1]==n)) // ?? why
{
copy(perm.begin(),perm.end(),flips.begin());
int nflips=0;
while(flips[0]!=1)
{
reverse(flips.begin(),flips.begin()+flips[0]);
++nflips;
}
if(nflips>maxFlips)maxFlips=nflips;
}
}while(next_permutation(perm.begin(),perm.end()));
return maxFlips;

}

int main(int argc, const char **argv) {
int n = (argc>1) ? atoi(argv[1]) : 0;
cout << "Pfannkuchen(" << n << ") = "
<< fannkuch(n, cout) << '\n';
return 0;

}

Greetings, Branimir.
Jun 27 '08 #9

P: n/a
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<ig****@yahoo.comwrote:
>Why don't you go through all...
Let's continue with a NEW thread then, just for our friend Sherman
Pendley

You have java version for partialsums

http://shootout.alioth.debian.org/gp...lang=java&id=2

my version based on D
http://pastebin.ca/1008251

For N = 2,500,000

4.472s (yours -server)
3.493s (mine -server)

It's one second faster.

2.598s (g++)
3.307s (jet)

1.880s (gcj on Ubuntu 64bit). However, g++ was even faster on 64-bit

Jun 27 '08 #10

P: n/a
On Mon, 5 May 2008 08:27:23 -0700 (PDT), Isaac Gouy <ig****@yahoo.com>
wrote:
>The FAQ gives instructions on how to contribute better programs

http://shootout.alioth.debian.org/gp4/faq.php#play
It's right here

http://pastebin.ca/1008316111

but to make you happy, I will post it to the site too.
Jun 27 '08 #11

P: n/a
On Mon, 05 May 2008 09:54:29 -0700, Razii <gj******@gmail.comwrote:
On Wed, 30 Apr 2008 08:00:38 -0700 (PDT), Isaac Gouy
<ig****@yahoo.comwrote:
>Why don't you go through all...

Let's continue with a NEW thread then, just for our friend Sherman
Pendley
As if we needed any more evidence that you're just a troll.
I find it amazing that there are still people who can be suckered in by
this troll. Is there really anyone left who _really_ thinks that whatever
he has to say is worthwhile enough to justify his rude, cross-posting,
subject-changing trollish behavior? Or that anything you might post in
reply will have any positive effect whatsoever on what the troll thinks or
does?

"Razii" will go away when everyone is able to resist the urge to feed his
egomaniacal desires and stops replying to his posts, and not a moment
before. There is no resolution other than to just stop responding.
Jun 27 '08 #12

P: n/a
Peter Duniho wrote:
"Razii" will go away when everyone is able to resist the urge to feed
his egomaniacal desires and stops replying to his posts, and not a
moment before. There is no resolution other than to just stop responding.
I think that these two groups are so crowded that there will be always
someone that want to feeds the troll.

I think that the only solution is black list the thread.

I blacklisted the original thread on my client but when I changed the
news server this has stopped working.

--
Andrea Francia
alias rm='trash' #use trash command instead of removing
rm -Rfv file #put the file in the KDE trashcan
http://www.andreafrancia.it/trash
Jun 27 '08 #13

P: n/a

"Razii" <gj******@gmail.comwrote in message
news:hk********************************@4ax.com...

<...>
Let's continue with a NEW thread then
Ah... The troll spammer who keeps changing his email address because he
knows everybody killfiles him strikes again.

Yawn....... zzzzzzzzzh... plonk! ( no 99 )

regards
Andy Little

Jun 27 '08 #14

P: n/a
On Mon, 05 May 2008 10:11:39 -0700, "Peter Duniho"
<Np*********@nnowslpianmk.comwrote:
>As if we needed any more evidence that you're just a troll.
<PLONK>
Jun 27 '08 #15

P: n/a
Andrea Francia wrote:
Another opportunity to use the "Ignore Thread" feature in
"Right Click Watch Ignore" extensions for Thunderbird.
I just use `K'. Keyboard shortcuts really are fun.

Anyone up for if `Subject' contains `Razii' -`Ignore Thread'?

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Jun 27 '08 #16

P: n/a
Lew
Razii wrote:
On Mon, 05 May 2008 10:11:39 -0700, "Peter Duniho"
<Np*********@nnowslpianmk.comwrote:
>As if we needed any more evidence that you're just a troll.

<PLONK>
plonk

--
Lew
Jun 27 '08 #17

P: n/a

"Razi" <fg***@gmail.comwrote in message
news:r4********************************@4ax.com...
On Mon, 5 May 2008 08:27:23 -0700 (PDT), Isaac Gouy <ig****@yahoo.com>
wrote:
>>The FAQ gives instructions on how to contribute better programs

http://shootout.alioth.debian.org/gp4/faq.php#play

Well, I have been around but wasting my time on this bogus shootout
site.
Why don't you set up your own shootout website then and show us all how it
should be done.

Meanwhile f*ck off ... and stick to one email.

Plonk.

regards
Andy Little


Jun 27 '08 #18

P: n/a
On Wed, 21 May 2008 09:36:14 +0100, "kwikius"
<an**@servocomm.freeserve.co.ukwrote:
>Why don't you set up your own shootout website then and show us all how it
should be done.
That's a good suggestion and should be considered.

Jun 27 '08 #19

P: n/a
Razi<fg***@gmail.comwrites:

Changing your address just to get out of killfiles and back in people's
faces to say "neener neener, you can't shut me up" is infantile. But then,
so is this whole "my language has bigger gametes than yours" debate that
you keep trying to start, so I suppose childish behavior is to be expected
from you.

Go play, or something - the adults are trying to have a conversation here.

*plonk*

sherm--

--
My blog: http://shermspace.blogspot.com
Cocoa programming in Perl: http://camelbones.sourceforge.net
Jun 27 '08 #20

P: n/a
On Wed, 21 May 2008 12:21:59 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>Changing your address just to get out of killfiles and back in people's
faces to say "neener neener, you can't shut me up" is infantile.
I might set a bot just for this purpose. It will change the email
automatically with every post. As long as I see any ad hominem post
directed at me, such as yours, I am planning to use it.
>Go play, or something - the adults are trying to have a conversation here.
My threads generate the most replies (i.e. conversations). Most of
the posts on the group are spam.
Jun 27 '08 #21

P: n/a
On Wed, 21 May 2008 08:01:45 -0700 (PDT), Isaac Gouy
<ig****@yahoo.comwrote:
>contribute a program that reads 82 chars at a time.
Now it's 82 chars at a time from read "line by lines"? In any case,
isn't this just a simple fix?

changing this line byte[] line = new byte[65536];
to byte[] line = new byte[82];

and now System.in.read(line)

can't read more than 82 bytes at a times.

Jun 27 '08 #22

P: n/a
Razii <jd**@gmail.comwrites:
On Wed, 21 May 2008 12:21:59 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>>Changing your address just to get out of killfiles and back in people's
faces to say "neener neener, you can't shut me up" is infantile.

I might set a bot just for this purpose. It will change the email
automatically with every post. As long as I see any ad hominem post
directed at me, such as yours, I am planning to use it.
Go for it.

Continuing your infantile behavior would only prove me correct. And now
that you've admitted that your continuing abuse of netiquette is intentional,
it won't be difficult to get your access cancelled.

sherm--

--
My blog: http://shermspace.blogspot.com
Cocoa programming in Perl: http://camelbones.sourceforge.net
Jun 27 '08 #23

P: n/a
On Wed, 21 May 2008 14:17:44 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>Go for it.

Continuing your infantile behavior would only prove me correct. And now
that you've admitted that your continuing abuse of netiquette is intentional,
it won't be difficult to get your access cancelled.
LOL @ netiquette :) There is no such thing. How many times do I need
to explain how USENET works?

Go ahead and try getting my access canceled for posting on unmoderated
newsgroup.

Jun 27 '08 #24

P: n/a
On Wed, 21 May 2008 22:20:13 +0200, Michael DOUBEZ
<mi************@free.frwrote:
>For all you know, he/she may actually be 12 years old.
Or it could be that Sherman Pendley is 12? How do you know he isn't?
>cross posting (as I am doing now since I don't know on which group you are).
Almost everyone who respond to all my threads religiously (I wonder
why?) apparently are in c++ group. There was one from java group. I
forgot his name, Lew or whatever. I plonked that moron a long time
ago.

Jun 27 '08 #25

P: n/a
Raz
On Wed, 21 May 2008 01:05:21 -0500, Razi<fg***@gmail.comwrote:
>I submitted a twice faster "partialsums" but it was put in
"interesting alternative" section, even though it follows all
benchmark rules.

http://shootout.alioth.debian.org/gp...lsums&lang=all

Basically, I discovered that trig functions are much faster in C++.
That's because the x86 family of processors return incorrect results
for sin and cos at the accuracy that Java requires. If the angle is
not within the range of +45 to -45 degrees, java doesn't use hardware
for sin and cos; the number is calculated in software.

The solution is pretty simple (as suggested by Jeff's Gems wiki
article). Use something like following to reduce te angle to be within
+45 to -45 degrees before calling Math.sin and Math.cos. For million
of sin & cos calls, this would be 6 to 7 times faster.

class FastMath
{
public static final double PI = Math.PI;
public static final double TWOPI = PI * 2;
public static final double HalfPI = PI / 2;
public static final double OneFourthPI = PI / 4;

/* This forces the trig functiosn to stay * within
* the safe area on the x86 processor *(-45 degrees to +45 degrees)
* The results may be very slightly off from * what the Math
* and StrictMath trig functions * give due to rounding in
* the angle reduction * but it will be very very close. */

public static double reduceSinAngle(double radians)
{
radians %= TWOPI;
if (Math.abs(radians)>PI)
{
radians = radians-(TWOPI);
}
if (Math.abs(radians)>HalfPI)
{
radians = PI - radians;
}
return radians;
}
public static double sin (double radians)
{
radians = reduceSinAngle(radians);
if (Math.abs(radians)<=OneFourthPI)
{
return Math.sin(radians);
}
else
{
return Math.cos(HalfPI-radians);
}
}
public static double cos (double radians)
{
return sin (radians+HalfPI);
}
}
Jun 27 '08 #26

P: n/a
Razii <oe***@gmail.comwrites:
On Wed, 21 May 2008 14:17:44 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>>Go for it.

Continuing your infantile behavior would only prove me correct. And now
that you've admitted that your continuing abuse of netiquette is intentional,
it won't be difficult to get your access cancelled.

LOL @ netiquette :) There is no such thing. How many times do I need
to explain how USENET works?
None. I know how it works. There are two fundamental principles on usenet:
You have the right to say whatever you want to, but *I* have the right to
ignore you if *I* want to.

What you are doing is called nymshifting, and when it's done to escape
being plonked it's expressly forbidden by any reputable ISP, because a) the
plonking doesn't interfere with your usenet "rights," and b) the nymshifting
*does* interfere with everyone else's right to ignore you.
Go ahead and try getting my access canceled
Your threat to create a bot for the express purpose of disrupting this group
is definitely something any reasonable ISP would take notice of, if you carry
it out. And I guarantee you, if you do, I won't be the only one complaining
to your ISP about it.

sherm--

--
My blog: http://shermspace.blogspot.com
Cocoa programming in Perl: http://camelbones.sourceforge.net
Jun 27 '08 #27

P: n/a
Michael DOUBEZ <mi************@free.frwrites:
Just let him be. Ignore him
I'm trying to. I've killfiled three of his sock puppets already. That's
why his constant nym-shifting is pissing me off - he won't *let* anyone
ignore him.

sherm--

--
My blog: http://shermspace.blogspot.com
Cocoa programming in Perl: http://camelbones.sourceforge.net
Jun 27 '08 #28

P: n/a
On Wed, 21 May 2008 18:14:36 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>I'm trying to. I've killfiled three of his sock puppets already. That's
why his constant nym-shifting is pissing me off - he won't *let* anyone
ignore him.
You pathetic moron, that's not what Michael DOUBEZ meant. He said
don't respond to my posts if you are grown up. You obviously aren't.
You have proven yourself to be a 12-years old.
Jun 27 '08 #29

P: n/a

"Razii" <fg***@gmail.comwrote in message
news:so********************************@4ax.com...
Almost everyone who respond to all my threads religiously (I wonder
why?) apparently are in c++ group. There was one from java group. I
forgot his name, Lew or whatever. I plonked that moron a long time
ago.
And your C++ question is ... ?

regards
Andy Little
Jun 27 '08 #30

P: n/a
Razii wrote:
On Wed, 21 May 2008 12:21:59 -0400, Sherman Pendley
<sp******@dot-app.orgwrote:
>Changing your address just to get out of killfiles and back in people's
faces to say "neener neener, you can't shut me up" is infantile.

I might set a bot just for this purpose. It will change the email
automatically with every post. As long as I see any ad hominem post
directed at me, such as yours, I am planning to use it.
Why do you think that it is OK for you to attack others and
not OK for others to attack you ????

(accuse a benchmark site to take money to flaw the results is
an attack)
>Go play, or something - the adults are trying to have a conversation here.

My threads generate the most replies (i.e. conversations). Most of
the posts on the group are spam.
quantity != quality

and there are plenty of on-topic threads.

Arne
Jun 27 '08 #31

P: n/a
On Wed, 21 May 2008 19:34:47 -0400, Arne Vajhøj <ar**@vajhoej.dk>
wrote:
>Why do you think that it is OK for you to attack others and
not OK for others to attack you ????
Most often (in 99% of cases), I am just responding in kind. Some
people have never gotten into a flamewar with me despite long threads.
This was the second time that Sherman Pendley posted in my thread and
insulted me. Did I ever post to his thread? No. Did I ever randomly
start responding to his posts? No. I don't even know/remember the guy.
Perhaps he posts from java group which I don't read. If you inject
yourself in my thread with the goal of flamewars and/or to disrespect
me, you are very welcome. I don't mind. I will respond in kind. That's
all.

Jun 27 '08 #32

P: n/a
On May 22, 1:10*am, Razii <bj...@gmail.comwrote:
On Wed, 21 May 2008 19:34:47 -0400, Arne Vajhøj <a...@vajhoej.dk>
wrote:
Why do you think that it is OK for you to attack others and
not OK for others to attack you ????

Most often (in 99% of cases), I am just responding in kind. Some
people have never gotten into a flamewar with me despite long threads.
This was the second time that Sherman Pendley posted in my thread and
insulted me.
And your C++ question is ?

regards
Andy Little

Jun 27 '08 #33

P: n/a
On Wed, 21 May 2008 17:16:57 -0700 (PDT), kwikius
<an**@servocomm.freeserve.co.ukwrote:
>And your C++ question is ?
Here we a clear example of what a real troll looks like.

Keep it up, by the way. Every reply counts in making the thread
bigger.
Jun 27 '08 #34

P: n/a

"Raz" <rt*****@gmail.comwrote in message
news:7k********************************@4ax.com...

<...>
Basically, I discovered that trig functions are much faster in C++.
And your C++ question is ...?

regards
Andy Little
Jun 27 '08 #35

P: n/a
On Thu, 22 May 2008 02:13:28 +0100, "kwikius"
<an**@servocomm.freeserve.co.ukwrote:
>Basically, I discovered that trig functions are much faster in C++.

And your C++ question is ...?
How do I play default Windows sounds?

Jun 27 '08 #36

P: n/a
kwikius wrote:
>
"Raz" <rt*****@gmail.comwrote in message
news:7k********************************@4ax.com...

<...>
Basically, I discovered that trig functions are much faster in C++.

And your C++ question is ...?
Please stop feeding the troll.


Brian
Jun 27 '08 #37

P: n/a
On 22 May 2008 18:56:46 GMT, "Default User" <de***********@yahoo.com>
wrote:
>Please stop feeding the troll.
You are right. Everyone please add the troll kwikius to your ignore
list and stop feeding him.
Jun 27 '08 #38

This discussion thread is closed

Replies have been disabled for this discussion.