Fast Output From Loop (c++)

[monkey56657]

Hello.

I am quite new to c++ but am working on translating a prime generator I have made over from c#.

I have everything working well but have found that c# can output to file faster than c++ (by around 10%). This is once the 'working out' is done.

Here is the c++ code that I am currently using:

FILE * handle = fopen("primes.dat", "w");

ostringstream buffer; buffer << 2 << ' ';

for (int x = 3; x < upper_primes; x += 2)
{
    if (!test_primes[x])
    {			
		if (buffer.tellp() > 4194304)
		{
			fputs(buffer.str().c_str(), handle);
			
			buffer.str("");
		}
		
		buffer << x << ' ';
    }
}

fputs(buffer.str().c_str(), handle);

fclose(handle);

As you can see it outputs to file every 4MB. I have tried a few variations from 1KB up to 4MB all with similar results.

I have also tried using ofstream directly rather than ostringstream and fputs. They offer very little performance difference.

So my question is simply.. for a loop that outputs millions of numbers (originally as type int) each followed by a space can you suggest a faster way to output the list?

FULL SOURCE CODE

Once I can fine tune this I will have to work on the multi-threading for the processing. My first attempt at that made it slower (I need to keep the threads for re-using rather than creating new ones every loop) .. but thats another matter.

Thanks in advance :)

Jonathan .

[Salem]

The snail and the tortoise

How about beginning with the fact that your approach to testing primes is horribly inefficient?

[Ancient Dragon]

Already gave you a couple suggestions here

[monkey56657]

How about beginning with the fact that your approach to testing primes is horribly inefficient?

If you care to suggest a faster method then please do. On my machine this is generating all primes from 1 to 100,000,000 in around 4 seconds. My method isn't what you usually find on the web but I find that it does the job a lot faster than anything else i've found online. The result is a ~50MB file.

Already gave you a couple suggestions here

Thanks I will look into fprintf method. The ofstream I already have tried it wasn't any faster. I never even asked my question at that other website but regardless thanks for your reply.

[monkey56657]

Thanks I will look into fprintf method.

Unfortunately this only increased the output time. Any more suggestions ?

[Salem]

Observe how this does NOT check 9
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

That's the most famous algorithm out there, and it should be quicker than yours.
Odd that you missed it in your "research"

[monkey56657]

Observe how this does NOT check 9
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

That's the most famous algorithm out there, and it should be quicker than yours.
Odd that you missed it in your "research"

Marking all multiples of 3, 5, 7 etc. and the rest are then primes. I get the idea. My method was based on that and is infact faster.

If you check the full source code you will see:

static bool test_primes[upper_primes];

const int square_root = (int) sqrt((double) num_primes) + 1;

for (int x = 3; x < square_root; x += 2)
{
	if (!test_primes[x])
	{
		const int up_limit = (num_primes / x) + 1;
	
		for (int mx = x; mx < up_limit; mx += 2)
		{
			test_primes[(mx * x)] = true;
		}	
	}
}

1. An array to mark of the multiples
2. Work out the square root
3. Loop through from 3 to square root marking multiples (missing out those that aren't primes themselves)

4. Output as shown in the already presented code.

Test it for yourself.