Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Turing Beat C++ in Performance?!?!
Index -> Programming, C++ -> C++ Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
keyboardwalker




PostPosted: Fri Feb 28, 2014 7:57 pm   Post subject: Turing Beat C++ in Performance?!?!

WARNING A TEXT FILE WITH THE GENERATED PRIME NUMBERS WILL BE SAVED IN A .txt FILE ON YOUR COMPUTER AFTER RUNNING EITHER OF THESE

I've created an algorithm for finding the prime numbers between 1 and the number held by NUMNUMS in Turing and C++. I'm not sure as to why C++'s performance is slower than Turing's. I have a feeling that it has something to do with using vectors in the C++ version. Is there anyway to improve C++'s performance and why is this happening?

Turing:

const NUMNUMS := 1000000
var Nums : array 1 .. NUMNUMS of boolean

for i : 1 .. NUMNUMS
    Nums (i) := true
end for
Nums (1) := false
for i : 2 .. NUMNUMS
    if Nums (i) then
        for ii : i + i .. NUMNUMS by i
            Nums (ii) := false
        end for
    end if
end for
var streamnum : int
open : streamnum , "theNums.txt", put
for i : 1 .. NUMNUMS
    if Nums (i) then
        put : streamnum, i
    end if
end for
close (streamnum)
put Time.Elapsed




c++:


#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>

int main () {

        using namespace std;
        ofstream myfile;
        const int NUMNUMS = 1000000;
        clock_t t;
        // "Time stamps"
        int t1, t2;

        t = clock();

        t1 = clock();
        cout << "Initializing\n";

        vector <bool> Nums(NUMNUMS, true);
        Nums[1] = false;

        cout << "Done Initializing it took " << clock () - t1 << " ms" << endl;
        cout << "Deriving Prime Numbers\n";

        t1 = clock ();
        for (int i = 2 ; i < NUMNUMS; i ++)
        {
                if (Nums[i])
                {
                        for (int ii = i + i; ii < NUMNUMS; ii += i)
                        {
                                Nums [ii] = false;
                        }
                }
        }

        cout << "Done Algorithm took " << clock() - t1 << " ms" << endl;
        cout << "Saving\n";

        t1 = clock ();
        myfile.open ("theNums.txt");
        for (int i = 2 ; i < NUMNUMS; i ++)
        {
                if (Nums[i])
                {
                        myfile << i << endl;
                }
        }

        myfile.close();
        cout << "Done Saving. It took: "  << clock() - t1 << " ms" << endl;
        cout << "The entire program took "  << clock() - t << " ms" << endl;
        return 0;
}

Sponsor
Sponsor
Sponsor
sponsor
Insectoid




PostPosted: Fri Feb 28, 2014 8:29 pm   Post subject: RE:Turing Beat C++ in Performance?!?!

It's cheating to use a basic type in one language and a comparatively much slower class in the other. Try rewriting the c++ code to use an array instead of a vector. C++ will have also used much less ram and produce a much smaller program.
keyboardwalker




PostPosted: Fri Feb 28, 2014 9:12 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

Insectoid @ Fri Feb 28, 2014 8:29 pm wrote:
It's cheating to use a basic type in one language and a comparatively much slower class in the other. Try rewriting the c++ code to use an array instead of a vector. C++ will have also used much less ram and produce a much smaller program.

Agreed, but I haven't been able to make an array of 1 billion elements in C++ like I have in Turing. That's why I used vectors instead of arrays. Unless I don't know the full capabilities of arrays in C++. Which is quite likely.
Dreadnought




PostPosted: Fri Feb 28, 2014 9:20 pm   Post subject: Re: Turing Beat C++ in Performance?!?!

You can't allocate large arrays on the stack in C++, but the heap is a different story.

code:
bool[] MyBoolArray = new bool[NumElements];


EDIT: or you can do it ala C
code:
bool[] MyBoolArray = (bool)malloc(NumElements * sizeof(bool));


Remember that if your arrays are really large, catching bad_alloc expections or checking for null might be a good idea.
Insectoid




PostPosted: Fri Feb 28, 2014 9:25 pm   Post subject: RE:Turing Beat C++ in Performance?!?!

c++ can't make a 1 billion element array, but your code only tests up to 1 million and c++ can handle that just fine.
keyboardwalker




PostPosted: Fri Feb 28, 2014 10:14 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

Insectoid @ Fri Feb 28, 2014 9:25 pm wrote:
c++ can't make a 1 billion element array, but your code only tests up to 1 million and c++ can handle that just fine.

It's only 1 Million because it would take several minutes to calculate the prime numbers between 1 and 1 Billion. I wrote it in C++ to try and reduce this processing time but it appears that it vectors aren't the way to go in this case.
DemonWasp




PostPosted: Fri Feb 28, 2014 10:38 pm   Post subject: RE:Turing Beat C++ in Performance?!?!

The part that makes the C++ version take forever is the endl, which forces the output stream to flush every time you add one. To avoid that, use the \n escape character.

You still need to make sure that the stream gets flushed eventually, but closing it will also do that (which is what happens in Turing).

With this change, the C++ version handily outruns the Turing version. I ran the Turing version on Windows and the C++ version on Linux in a virtual machine, and the C++ version was still more than 10x faster. The numbers output are incorrect (it looks like you are outputting microseconds and calling them milliseconds).

The problem is not with vectors, which are widely used and perform well enough for most tasks (though there are many solutions where they are less convenient than other types).

Edit: see the documentation at http://en.cppreference.com/w/cpp/io/manip/endl
keyboardwalker




PostPosted: Sat Mar 01, 2014 12:39 am   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

DemonWasp @ Fri Feb 28, 2014 10:38 pm wrote:
The part that makes the C++ version take forever is the endl, which forces the output stream to flush every time you add one. To avoid that, use the \n escape character.

You still need to make sure that the stream gets flushed eventually, but closing it will also do that (which is what happens in Turing).

With this change, the C++ version handily outruns the Turing version. I ran the Turing version on Windows and the C++ version on Linux in a virtual machine, and the C++ version was still more than 10x faster. The numbers output are incorrect (it looks like you are outputting microseconds and calling them milliseconds).

The problem is not with vectors, which are widely used and perform well enough for most tasks (though there are many solutions where they are less convenient than other types).

Edit: see the documentation at http://en.cppreference.com/w/cpp/io/manip/endl


Your suggestion made a huge difference to saving speeds. As for the timing I think it was close if not the correct time in the C++ but I have calculated it differently now. I'm fairly sure that the times are correct and in milliseconds. You can check the references to see what I mean or to correct me again :p. I implemented arrays and there was a huge performance increase. Here's the updated version. Thank you to everyone who made suggestions.

c++:


#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>

int main () {

        using namespace std;
        ofstream myfile;
        const int NUMNUMS = 1000000;
        clock_t t;
        int t1;
        t = clock();
        t1 = clock();

        cout << "Initializing\n";

        bool *Nums = new bool[NUMNUMS];
        for (int i = 0; i < NUMNUMS; i ++)
        {
                Nums[i] = true;
        }


        //vector <bool> Nums(NUMNUMS, true);
        Nums[1] = false;

        cout << "Done Initializing it took " << (float)(clock () - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "Deriving Prime Numbers\n";

        t1 = clock ();

        for (int i = 2 ; i < NUMNUMS; i ++)
        {
                if (Nums[i])
                {
                        for (int ii = i + i; ii < NUMNUMS; ii += i)
                        {
                                Nums [ii] = false;
                        }
                }
        }

        cout << "Done. Algorithm took: " << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "Saving\n";

        t1 = clock ();
        myfile.open ("theNums1.txt");
        for (int i = 2 ; i < NUMNUMS; i ++)
        {
                if (Nums[i])
                {
                        myfile << i << "\n";
                }
        }

        myfile.close();

        cout << "Done Saving. It took: "  << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "The entire program took "  << (float)(clock() - t)/CLOCKS_PER_SEC * 1000 << " ms" << endl;

        delete [] Nums;

        cout << "Press any key";
        cin.get();
        return 0;
}

Sponsor
Sponsor
Sponsor
sponsor
linuxp




PostPosted: Sat Mar 01, 2014 2:24 pm   Post subject: RE:Turing Beat C++ in Performance?!?!

The problem is vector<bool>

In c++ vector<bool> is a specialized version of vector.

normal vector<type> is just a plain array of
[type,type,type]

vector<bool> is a memory optimized container.
each bool takes 1 bit instead of 1 byte.

The result is 1/8 memory but longer operation time.

if you need a normal array of bool
use vector<char> or bool[]
DemonWasp




PostPosted: Sat Mar 01, 2014 2:54 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

linuxp @ Sat Mar 01, 2014 2:24 pm wrote:
The problem is vector<bool>


No, the problem he was having is because endl unexpectedly flushes the output stream. The operations on vector<bool> aren't that much slower than standard.
nullptr




PostPosted: Sat Mar 01, 2014 9:52 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i)
{
        Nums [ii] = false;
}

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.
keyboardwalker




PostPosted: Sun Mar 02, 2014 6:36 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

nullptr @ Sat Mar 01, 2014 9:52 pm wrote:
Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i)
{
        Nums [ii] = false;
}

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.

Do you really mean i * i (i^2) or do you mean i*2 instead of i + i. If you actually meant i * i could you please elaborate?
nullptr




PostPosted: Sun Mar 02, 2014 8:18 pm   Post subject: Re: RE:Turing Beat C++ in Performance?!?!

keyboardwalker @ Sun Mar 02, 2014 6:36 pm wrote:
nullptr @ Sat Mar 01, 2014 9:52 pm wrote:
Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i)
{
        Nums [ii] = false;
}

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.

Do you really mean i * i (i^2) or do you mean i*2 instead of i + i. If you actually meant i * i could you please elaborate?

Yep, I meant i^2. Here's my proof: suppose we have found a prime N, and that every number divisible by a prime less than N has already been marked as composite. Suppose there is a composite number X which is less than N^2, but is divisible by N. X must have some prime factor other than N, since it is less than N^2. Furthermore, that factor must be less than N, or else X would be greater than N^2. But every number divisible by a prime less than N has already been marked as composite! Therefore this algorithm will not leave any composite numbers divisible by N without marking them. We are allowed to assume that every number divisible by a prime less than N has already been marked because, for N=2, there are no primes less than N, and for any N, this assumption still holds true for the next prime after N.
Panphobia




PostPosted: Sun Mar 02, 2014 8:22 pm   Post subject: RE:Turing Beat C++ in Performance?!?!

Thats the sieve of eratosthenes,
code:

    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i; i * j <= N; j++) {
                isPrime[i * j] = false;
            }
        }
    }
There is my code for it, where N is your NUMNUMS, I am pretty sure this is more efficient, but not completely Razz.
keyboardwalker




PostPosted: Sun Mar 02, 2014 10:05 pm   Post subject: Re: Turing Beat C++ in Performance?!?!

c++:


#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>

int main () {

        using namespace std;
        ofstream myfile;
        const int NUMNUMS = 1000000;
        clock_t t;
        int t1;
        t = clock();
        t1 = clock();

        cout << "Initializing\n";
        bool *Nums = new bool[NUMNUMS];
        for (int i = 0; i < NUMNUMS; i ++)
        {
                Nums[i] = true;
        }


        //vector <bool> Nums(NUMNUMS, true);
        Nums[1] = false;

        cout << "Done Initializing it took " << (float)(clock () - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "Deriving Prime Numbers\n";

        t1 = clock ();
        for (int i = 4 ; i < NUMNUMS; i += 2)
        {
                Nums [i] = false;
        }
        for (int i = 3 ; i * i < NUMNUMS; i += 2)
        {
                if (Nums[i])
                {
                        for (int j = i * i; j < NUMNUMS; j += i * 2)
                        {
                                Nums [j] = false;
                        }
                }
        }
       
        cout << "Done. Algorithm took: " << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "Saving\n";

        t1 = clock ();
        myfile << 2 << "\n";
        for (int i = 3 ; i < NUMNUMS; i += 2)
        {
                if (Nums[i])
                {
                        myfile << i << "\n";
                }
        }

        myfile.close();

        cout << "Done Saving. It took: "  << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;
        cout << "The entire program took "  << (float)(clock() - t)/CLOCKS_PER_SEC * 1000 << " ms" << endl;

        delete [] Nums;

        cout << "Press any key";
        cin.get();
        return 0;
}


These are great suggestions and I made one more improvement to the sieve.

I can do this j += i * 2 since an odd number (all primes except for 2) multiplied an even number of times is always an even number and therefore a factor of 2 and not a prime number. i * (i + 1) is not a prime number such that i is a prime number greater than 2.

I didn't see this in the optimized version of http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I wonder why.
Display posts from previous:   
   Index -> Programming, C++ -> C++ Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 15 Posts ]
Jump to:   


Style:  
Search: