Java vs C++ speed (IO & Sorting)

[Jerry Coffin]

[ ... ]

And post the c++ GMP version. Where is the documentation? It took me
about 10 minutes to come up with the idea, look up BigInteger class on
the web, write few lines, and post it here.

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html

And I am not even Java expert. That's not what I do for living. Not
kidding. Maybe took even less than 10 minutes.

Writing the basic idea of it in C++ took me about 2 minutes (at most).
Formatting the timing output and such to match yours reasonably well
took longer, because I had to look back and forth between my editor and
what you'd done.

It's been 8 hours and no one has yet posted the c++ version. Why? How
come? Because it's much harder. You need to download GMP, find how it
works, even it works, and then you can't be sure your version will
work on say, Mac.

Post the C++ version. Where is it?

The C++ version has been posted. As for taking 8 hours: well, some of us
have jobs....

 

[Alberto Bignotti]

This code look simply and in my opinion in clean than java version.
We can say it's equivalent in complexity.
The performance look very different.

Razii, please stop trolling comp.lang.c++.
As someone said, "Mine is bigger than yours" games are juvenile,
uninteresting, and a waste of time.

Bye.

[ ... ]

Exactly. There is no network, no threads, no bignum. No GUI. Nothing
really. And by the way, bignum is important. You can't do cryptology
without bignum.

Yes, you can do cryptology without bignum. In fact, you can do it quite
nicely. There are a few symmetric ciphers that use big numbers, but
bignums only come into heavy use for public-key ciphers.

In any case, the fact that something isn't in the standard library
hardly means that it doesn't exist.

Anyway, if you have GMP bignum library, can you post the c++ version
of java that I posted?

I haven't used GMP much, but with the library I normally use (NTL) it
would look something like this:

#include <NTL/zz.h>
#include <fstream>
#include <time.h>
#include <iostream>

int main() {
int bits = 1000;
std:fstream out("prime.txt");

clock_t start = clock();
for (int i=0; i<10; i++)
out << NTL::RandomPrime_ZZ(bits) << "\n\n";
clock_t end = clock();

std::cout << "Time to generate ten "
<< bits
<< " bit prime numbers: "
<< float(end-start)/CLOCKS_PER_SEC
<< " Seconds\n";
return 0;
}

The result on my machine:

Time to generate ten 1000 bit prime numbers: 5.906 Seconds
...
Later,
Jerry.

The universe is a figment of its own imagination.

 

[Razii]

This code look simply and in my opinion in clean than java version.
We can say it's equivalent in complexity.
The performance look very different.

He did 10 numbers rather than 11 and is on faster computer. Goes to
show you are not the brightest bulb here.

 

[Razii]

Nearly all. 500 ms is half a second, and nearly everybody seems to be
able to perceive that. When it's expected, they aren't necessarily
bothered a great deal by a 500 ms delay, but almost everybody perceives
it nonetheless.

You can't have your cake and eat it too. If they can perceive 500 ms,
then the can perceive the difference between downloading 1.5 kb file
and 90 kb file, especially on the dial up.

 

[Razii]

Yes, you can do cryptology without bignum. In fact, you can do it quite
nicely. There are a few symmetric ciphers that use big numbers, but
bignums only come into heavy use for public-key ciphers.

For most Internet based encryptions, passwords, logins, banks, you
need big numbers (i.e Asymmetrical encryption) to transfer symmetric
keys. C++ standard library doesn't have it. Nor does it have threads
and network, and that's a problem and reason why c++ lost much of it's
ground to other languages online.

 

[Michael.Boehnisch]

Hi!

The atmosphere in this whole thread is already beyond my usual "ok-
thats-it-i-am-out" threshold. There is nothing wrong with heated
discussion, I enjoy it. It would be nice, though, if everybody came
back to civilized manners here. Childishly pointing out irrelevant
typos in example code goes nowhere, neither do insults or wild
accusations. The original post was provocative but not rude - and he
has a valid point in comparing *aspects* of Java performance to C++
performance.
Please remember, programming languages are tools, not holy sacraments.

'Nuff said, back to business:

On Thu, 20 Mar 2008 05:08:08 -0700 (PDT), peter koch

FileWriter fstream = new FileWriter("prime.txt");
BufferedWriter fout = new BufferedWriter(fstream);
PrintWriter out = new PrintWriter (fout);

The C++ equivalent to this bread-and-butter fragment is:

std:fstream fstream( "prime.txt" );

No need to explicitly construct three objects. IMHO, Java is overdoing
interface separation here a little bit. I am sure, though, most
serious Java programmers will have wrappers for stuff like this in
their private utility and code snippet collection. I am doing this for
C and C++ for twenty years already - my personal toolbox is nearly
800 classes of reusable code already, saves me lots of time in
projects i am doing.

BigInteger bigInteger;

Arbitrary length integer math is not part of the "standard" C++
library, but there are plenty of widely adopted packages that offer
such functions and its not really hard to implement.

bigInteger = BigInteger.probablePrime(bits,new Random());

I do not think this example does you very well. probablePrime() is a
*very* special purpose function of use maybe for cryptographic
algorithm implementations. Traditionally, the standard libraries for C
and C++ try to restrict themselves to functions of wide applicability
and leave rare needs to independent, non-standardized third-party
packages. This is a matter of style, not programming language powers.
probablePrime() is limited in use since there is no guarantee the
numbers it generates are *really* prime. In use cases where I have to
rely vitaly on the prime number property, I cannot accept that e.g. 1
out of 1,000,000 generated numbers is pseudo-prime only.
The implementation of a function like this is not super difficult also
- take any arbitrary length integer package, generate some random
numbers in a loop and check for primality property e.g. by Rabin's
probabilistic test ten times. I'll sketch the C++ code out for, maybe
in a private email conversation, if you're really interested.

Here is what it does: it generates ten 1000 bit prime numbers and
writes them to a file. (1000 bit means an integer with 301 digits in
it)

No, it doesn't - it generates ten 1000 bit numbers that are *likely*
to be prime. They are good candidates for a more thorough checking
with a deterministic method. This will need extra code and takes way
more CPU time, though. It's not a trivial task to do it efficiently in
any programming language.

Pleas show us the greatestness and simplicity of c++ standard library.
The out file (prime.txt) must look something like this with ten 100
bit prime numbers

This is not a good basis. I am certain, in some obscure corner of the
standard C++ library I'd be able to find something that is not
directly available in the Java library and needs a custom
implementation to reproduce. I admit, the Java library is *huge*. But
I also like the "99-1" approach of the C++ library (99% of all
problems is covered by 1% of library function candidates . Personal
preference, nothing I'd put in good/bad categories.

best,

Michael

 

[Tim Smith]

Back to see if anything has changed

(downloaded whatever is latest version from sun.java.com)

Your C++ code won't even compile, since ostream_iterator is not defined.
You need to add "#include <iterator>" to get that. Also, your time
calculation of off by 6 orders of magnitude on my system. The clock
function counts CLOCKS_PER_SEC times per second, not once per second.

Time for reading, sorting, writing: 359 ms (Java)
Time for reading, sorting, writing: 375 ms (Java)
Time for reading, sorting, writing: 375 ms (Java)

Visual C++ express and command I used was cl IOSort.cpp /O2

Time for reading, sorting, writing: 375 ms (c++)
Time for reading, sorting, writing: 390 ms (c++)
Time for reading, sorting, writing: 359 ms (c++)

The question still is (7 years later), where is great speed advantage
you guys were claiming for c++?

With your C++ code fixed so it compiles and reports the correct time,
here are my results (iMac with 2 GHz Intel Core Duo), for three runs:

Java: 485, 469, 502
C++: 181, 182, 192
Perl: 328, 269, 292

Perl code:

#!/usr/bin/perl
use strict;
use Time::HiRes qw{gettimeofday};

open IN, "bible.txt" or die "There is no God!\n";
my $start = gettimeofday;
my @bible = <IN>;
close IN;
my @sorted_bible = sort @bible;
open OUT, ">sorted.txt";
print OUT foreach @sorted_bible;
close OUT;
my $finish = gettimeofday;
my $took = 1000*($finish - $start);
print $took, " ms\n";

 

[Bo Persson]

I like how you start the time _after_ allocations and
initializations for Java, but _before_ them in C++.
Also, clock has granularity has big as my toe. I've seen it skew as
much as a second on some machines. There are several pages on Google
on how to do _REAL_ performance time measurements. It gets even
worse on multi-core systems.

It doesn't really matter, as most of the time is in the IO. On my
machine, reading and writing takes 125 ms, everything else 25 ms. It
is the 25 we are actually benchmarking!


Bo Persson

 

[Razii]

The performance look very different.

I cut and pasted his version .....

and only changed I made was to for loop. Changed it to (int i=0;
i<=10; i++)

Time to generate ten 1000 bit prime numbers: 11 Seconds
Time to generate ten 1000 bit prime numbers: 11 Seconds
Time to generate ten 1000 bit prime numbers: 10.969 Seconds
Time to generate ten 1000 bit prime numbers: 11.078 Seconds

the compiler options were
/O2 /Oi /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D
"UNICODE" /FD /EHsc /MD /Gy /Fo"Release\\" /Fd"Release\vc90.pdb" /W3
/nologo /c /Zi /TP /errorReportrompt

/I "C:\WinNTL-5_4_2\include"

As you see, not much faster than the java version I posted

Time for generating ten 1000 bit prime numbers 10203 ms
Time for generating ten 1000 bit prime numbers 17031 ms
Time for generating ten 1000 bit prime numbers 10172 ms
Time for generating ten 1000 bit prime numbers 11859 ms

And guess what? I had to download NTL. Search for it. Waste a lot of
time figuring it out. Compile it as NTL.lib and only then was able to
use it.

What a waste a time. And performance difference? ZERO

 

[dave_mikesell]

It's not silly. Bignum doesn't exist in c++. Period. If you don't have
something in standard library, that means there is no guarantee that
you can port your code once you use that library. Same problem with
networking and threads. And when you switch third party libraries,
that means you will have to learn the new library all over again.

ACE (threads, sockets, IPC, etc.) is available on (the following from
the ACE website):

Windows (i.e., WinNT 3.5.x, 4.x, 2000, Embedded NT, XP, Win95/98, and
WinCE using MSVC++, Borland C++ Builder, and IBM's Visual Age on 32-
and 64-bit Intel and Alpha platforms), Mac OS X, most versions of UNIX
(e.g., Solaris on SPARC and Intel, SGI IRIX 5.x and 6.x, DG/UX, HP-UX
10.x, and 11.x, Tru64UNIX 3.x and 4.x, AIX 3.x, 4.x, 5.x, DG/UX,
UnixWare, SCO, and freely available UNIX implementations, such as
Debian Linux 2.x, RedHat Linux 5.2, 6.x, 7.x, 8x, and 9.x, as well as
the various Enterprise editions, SUSE Linux 8.1 and 9.2, Timesys
Linux, FreeBSD, and NetBSD), real-time operating systems (e.g.,
LynxOS, VxWorks, ChorusOS, QnX Neutrino, RTEMS, OS9, and PSoS),
OpenVMS, MVS OpenEdition, and CRAY UNICOS.

 

[dave_mikesell]

Java: 485, 469, 502
C++: 181, 182, 192
Perl: 328, 269, 292

Interpreted Perl whipped your Java version? Beware, you are about to
incur the Wrath of Razii!

 

[Razii]

I do not think this example does you very well. probablePrime() is a
*very* special purpose function of use maybe for cryptographic
algorithm implementations.

Not true. You need a large prime number fo RSA. That's very commonly
used on the web to encrypt data.

in fact p (prime) x q (prime) = n (and n should be 2048 bits) so
you definitely need big prime numbers. Also, Diffie-Hellman key
exchange uses big prime numbers.

Millions of computers (including your above gmail account that you are
using), use some kind of encryption when you login with your password.

probablePrime() is limited in use since there is no guarantee the
numbers it generates are *really* prime.

http://java.sun.com/j2se/1.4.2/docs...ger.html#probablePrime(int, java.util.Random)

"Returns a positive BigInteger that is probably prime, with the
specified bitLength. The probability that a BigInteger returned by
this method is composite does not exceed 2^(-100)."

The probability that the number you get would be composite is lower
than winning several (10?) power ball lottery consecutively every
week.

No, it doesn't - it generates ten 1000 bit numbers that are *likely*
to be prime. They are good candidates for a more thorough checking
with a deterministic method.

That's exactly the point! If it was easy to check and factor the
number as composite, you won't be able to use it in encryption!
However, the probability that the number is prime is good enough that
you can use it to generate asymmetric keys.

 

[Razii]

With your C++ code fixed so it compiles and reports the correct time,
here are my results (iMac with 2 GHz Intel Core Duo), for three runs:

Java: 485, 469, 502
C++: 181, 182, 192
Perl: 328, 269, 292

What JVM did you use?

 

[Lasse Reichstein Nielsen]

For most Internet based encryptions, passwords, logins, banks, you
need big numbers (i.e Asymmetrical encryption) to transfer symmetric
keys. C++ standard library doesn't have it. Nor does it have threads
and network, and that's a problem and reason why c++ lost much of it's
ground to other languages online.

If you need encryption, you should *not* implement it yourself.
You should use an encryption library, or better yet, a protocol library
that includes the encryption, since you shouldn't implement security
protocols yourself either.

With security, there is no "small" mistakes. Any mistake can
completely break security for the implementation. It takes trained
professionals to write something that I would trust. That, and peer
review by other trained professionals.

An existing bignum-library might not have the properties needed for
security (e.g., wiping the memory where the key resides when you are
done using it). You'll have to check whether the properties of the
bignum library you use is compatible with your needs, which are more
than just the ability to multiply numbers. Using the standard library
would only make sense if the requirements you need are part of the
documented features of the library, i.e., it's likely to also hold
for later versions.

Security just isn't like normal programming.
/L

 

[Razii]

Razii, please stop trolling comp.lang.c++.
As someone said, "Mine is bigger than yours" games are juvenile,

If you have nothing to contribute, stop whining and cluttering the
thread. You also seem to be obsessed with penises and size. Please
stop trolling if you have nothing to say.

 

[Razii]

Interpreted Perl whipped your Java version? Beware, you are about to
incur the Wrath of Razii!

Perl is especially good with text processing, given it was originally
developed for text manipulation.

 

[zionztp]

Hello, i read the first post and i tought it would be interesting to
try this, im not an expert so i will only post the compilers info and
the test results i obtained using the code provided.

C++ test:

g++ -v:
Reading specs from /usr/lib/gcc/i486-slackware-linux/4.1.2/specs
Target: i486-slackware-linux
Configured with: ../gcc-4.1.2/configure --prefix=/usr --enable-shared
--enable-languages=ada,c,c++,fortran,java,objc --enable-threads=posix
--enable-__cxa_atexit --disable-checking --with-gnu-ld --verbose --
with-arch=i486 --target=i486-slackware-linux --host=i486-slackware-
linux
Thread model: posix
gcc version 4.1.2

g++ -O2 sort.cpp
../a.out

bible.txt: 98ms (5 runs avg)
10x bible.txt: 1583ms (5 runs avg)

-------------------------------------------------------------

Java test:

java -version:
java version "1.6.0_02"
Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
Java HotSpot(TM) Client VM (build 1.6.0_02-b05, mixed mode, sharing)

javac -version:
javac 1.6.0_02

javac -O IOSort.java
java IOSort ( -Xmx128m added for 10x bible test)

bible.txt: 318ms (5 runs avg)
10x bible.txt: 3227ms (5 runs avg)

Im not sure if i used the right optimization flags to compile the java
program so if its wrong please tell me how i should compile it, since
i expected to obtain similar results.

 

[Razii]

Im not sure if i used the right optimization flags to compile the java
program so if its wrong please tell me how i should compile it, since
i expected to obtain similar results.

I guess your g++ compiler is just better than my VC++ compiler for
this test

 

[Mark Space]

Java has never impeded anyone's ability in my direct experience to
create what I call clean abstraction layers, or for that matter, to
create clean, useful, maintainable code that does what its sponsors want
with acceptable performance on time and on budget. I've known quite a
few Java programmers, too.

Mostly I'm interested in the perceptions of the folks claiming that C++
is better. I'm sure that Java is fine, but I'd like to hear what the
other side has to say. So far they haven't deigned to respond....

 

[Michael.Boehnisch]

Not true. You need a large prime number fo RSA. That's very commonly
used on the web to encrypt data.

That's what I was saying. I mentioned cryptography as an area where
the function is useful. However, I feel it rather belongs into the
package providing RSA, not into the standard library.

http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#pro...)

"Returns a positive BigInteger that is probably prime, with the
specified bitLength. The probability that a BigInteger returned by
this method is composite does not exceed 2^(-100)."

The probability that the number you get would be composite is lower
than winning several (10?) power ball lottery consecutively every
week.

You are right. My math is a little outdated - I assumed the original
Rabin test that did not work for the Carmichael numbers and therefore
had a relatively high false positive rate. The current Java
implementation uses the improved Miller-Rabin test, not suffering from
this flaw anymore.

best,

Michael