New Multi-Threaded Pi Program - Faster than SuperPi and PiFast

[poke349]

Arr, I'm not happy with the topic, but while reading through Agner Fog's recent thoughts on Intel compiler and software, it seems that the reason why the GNU compiler was slower than Intel compiler is that the GNU compiler has sub-par performance in Windows environment compared to Linux environment. Since most of the code is in C, the GCC should actually be faster than Intel C compiler, while Intel may be slightly ahead with their C++ compiler.

Here's the actual quote:

So, if there's ever going to be linux version compiled with GCC, it could potentially mean that there might be some performance gain for AMD users.

I finally got Linux to boot reliably on both my workstation and my laptop.

I also have the Intel compiler installed, but I haven't figured out how to use it yet so I'm using GCC for now.

So I'm working on it. Ran into some unexpected portability issues with the fpos_t type (among other things). So I'm sorting it out right now.

[Calmatory]

Sounds great. Do you have any clue how much of a work is it to solve the issues and have a binary compiled?

[poke349]

Sounds great. Do you have any clue how much of a work is it to solve the issues and have a binary compiled?

Dunno yet...


I realized that my "mock" Linux version (compiled within Windows) was not compiling because I made so many changes to the interface since the last time I tested it.

So to bypass the temporary fpos_t problems, I'm back in Windows on MSVS right now, but Advanced Swap mode is crashing in my "mock" linux version.

Right now, there's a few big differences between the Windows and my Linux versions:
1. WinAPI threads vs. OpenMP
2. WinAPI raw I/O vs. Standard C++ fread/fwrite
3. Performance timers enabled in Windows, disabled in Linux. (use clock_t and time.h instead)
4. __cpuid enabled for Windows, but disabled in Linux for GCC
5. Benchmark validation disabled in Linux.

But I've narrowed down the problem to the I/O. I'm compiling a modified Windows version that uses the Standard C++ fread/fwrite (everything else kept the same), and it's still crashing in Advanced Swap Mode...

So there's definitely something wrong with my Standard C++ fread/fwrite implementation of the I/O library... still debugging it...




EDIT:
I just tested a modified Windows version using OpenMP and WinAPI I/O. And everything works fine.
So at least I know that I haven't broken the OpenMP implementation of the program.

Once I can get this "mock" Linux version to work again, I'll boot back up into Ubuntu and try to compile it in Linux.

[Calmatory]

By performance timers do you mean getting the time delta from the start of the run and the end of the run? If so, don't use ctime/time.h for gathering the elapsed time, it is inaccurate. Instead, you have to use <sys/time.h> in linux to gather the elapsed time.

The way how it works:

#include <iostream>
#include <sys/time.h>


void init_timer(timeval &tv) {
    /* Update tv to the current time */
    gettimeofday(&tv, 0);
};

unsigned int get_time(timeval &start, timeval &end) {
    /* Update end to current time, at this point start should be updated earlier by init_timer() */
    gettimeofday(&end, 0);
    /* Calculate the difference in microseconds(tv_usec) and convert it to milliseconds, do the same to seconds(tv_sec) */
    return (end.tv_usec-start.tv_usec)/1000 + (end.tv_sec-start.tv_sec)*1000;
};

int main() {

    timeval tv_start;
    timeval tv_end;

    init_timer(tv_start);
    /* Do something */
    std::cout << get_time(tv_start, tv_end) << std::endl;
    return 0;
};

timeval structure and gettimeofday(timeval &) gives microsecond accuracy, which is then truncated to milliseconds which should be precise enough. At least has been for my use.

The good thing about sys/time.h is that it is part of C POSIX library, so it should work with any POSIX compicant operating systems.

[poke349]

By performance timers do you mean getting the time delta from the start of the run and the end of the run? If so, don't use ctime/time.h for gathering the elapsed time, it is inaccurate. Instead, you have to use <sys/time.h> in linux to gather the elapsed time.

The way how it works:

#include <iostream>
#include <sys/time.h>


void init_timer(timeval &tv) {
    /* Update tv to the current time */
    gettimeofday(&tv, 0);
};

unsigned int get_time(timeval &start, timeval &end) {
    /* Update end to current time, at this point start should be updated earlier by init_timer() */
    gettimeofday(&end, 0);
    /* Calculate the difference in microseconds(tv_usec) and convert it to milliseconds, do the same to seconds(tv_sec) */
    return (end.tv_usec-start.tv_usec)/1000 + (end.tv_sec-start.tv_sec)*1000;
};

int main() {

    timeval tv_start;
    timeval tv_end;

    init_timer(tv_start);
    /* Do something */
    std::cout << get_time(tv_start, tv_end) << std::endl;
    return 0;
};

timeval structure and gettimeofday(timeval &) gives microsecond accuracy, which is then truncated to milliseconds which should be precise enough. At least has been for my use.

Oh, cool. I didn't know about that.
The performance counter that I use is this:
http://msdn.microsoft.com/en-us/libr...8VS.85%29.aspx

Which I think is a wrapper on top of the "rdtsc" instruction.


Lemme get the program to work first, then I'll deal with the little things like this.

At the time I did the "mock" linux version (more than a year ago ), I realized that the performance counters couldn't be accessed portably, so I did a combination of clock() and time.h.
If the duration was shorter than a certain cutoff, it uses clock(), if it was too long it uses time.h. (I made a single struct that had both variables in it.)
In the Windows version, the struct only contains a single 64-bit integer which is the Windows performance counter.

Which makes me wonder if I had actually thought of the clock_t overflow problem before... But that was nearly 2 years ago... lol
Only one small thing amoung 300,000 lines of code I've written... Even I don't remember everything I did... lol


And hey!!! I got the mock linux version to work again!
Man do I love ram drives!!!
btw, this is on my laptop. I recently jacked a 4GB stick from my mom to get this up to 8GB... sooo nice
(Yes I got permission from her and no she does not need 6GB of ram for word-processing...)
(click to enlarge)


I'm probably gonna head out for a while first (lunch and other things).
Then I'll try to finish sorting out all the MSVS and GCC incompatibilities...

But I start my 1 week drive back to school in Illinois on Sunday, so I won't be able to get any work done during that time.



So far it looks like the big things are:
fpos_t - 64-bit integer in Windows, struct in Linux
I've been casting back and forth between fpos_t and a 64-bit integer in my code as a way to jump to a part of the file.
It looks that all of that needs to be dumped into a wrapper function with two versions for Windows and Linux...

errno_t - this doesn't seem to exist in GCC...


I'm surprised at not getting any ascii/Unicode conflicts...
y-cruncher works almost exclusively in unicode especially with filepaths and I know UNIX doesn't like unicode filepaths...

[poke349]

Looks like this fpos_t problem is very serious.
There's no portable way to do large file access so I'm gonna have to write my own file API with a Windows and Linux implementation...

Furthermore, the Linux implementation is not going to compile in Windows at all so it's gonna be tough getting the whole thing together.

So I don't think it's gonna be ready anytime soon...

[poke349]

The fpos_t problem didn't turn out as bad as I thought.

So I got it to compile and run correctly... sort of...

(click to enlarge)





It computes correctly, but it looks like printf() is borked.
wprintf() seems to work. Did the terminal somehow default to some Unicode setting and disable ascii printf()?

The program uses both printf() and wprintf().
The ymo_print() function you see eventually calls wprintf(). So everything that is printed with ymo_print() seems to work fine...


Also, the validation file is messed up. Somehow ubuntu didn't write the 2-byte unicode header into the file so it opens up as crap...


Anyone got any ideas on where/what I screwed up?

[Calmatory]

Nice. The problem with printf seems strange. Are you printing newline after each call to printf?

Edit: Arr, nvm. I am too used working with C++ and std::cout for printing. Seems that printf doesn't care about newlines.

[Alpha]

Congrats Poke for the share of the 5 trillion world record! i just caught that on engadget and feel dumb as you posted it when it happened just a page back!

[poke349]

Nice. The problem with printf seems strange. Are you printing newline after each call to printf?

Edit: Arr, nvm. I am too used working with C++ and std::cout for printing. Seems that printf doesn't care about newlines.

Doesn't look like and easy problem to fix. printf() works fine until the first wprintf, then it gets all screwed up...
A couple my friends just flew over from Chicago and will be helping me drive my car back to Illinois so I won't be able to work on anything for the next week and a half...

Congrats Poke for the share of the 5 trillion world record! i just caught that on engadget and feel dumb as you posted it when it happened just a page back!

Thanks... Though I'm starting to worry about my website's bandwidth.
Usually my daily access log is only 300 - 500k.

August 5th: 14.9 MB
August 6th: 90.8 MB

And I think there's a pretty hefty penalty for going over the limit...
I'm not so sure what will happen if the Digg effect sets in... I might go broke if they charge a per GB rate once you go over the limit...

[Calmatory]

Could you try to make a simple test case to reproduce the problem? Since I can't reproduce the problem by using few printf and wprintf calls. Then again, my C is very weak so there could be something I haven't understood fully.

Edit: F this. I'll get a proper C book and start studying it now.

[poke349]

Could you try to make a simple test case to reproduce the problem? Since I can't reproduce the problem by using few printf and wprintf calls. Then again, my C is very weak so there could be something I haven't understood fully.

Edit: F this. I'll get a proper C book and start studying it now.

The case that's already failing for me is the one in the screenshot.

wprintf(L"Hello World! unicode");
print(L"Hello World! ascii");

The second printf() fails.
But I don't know if some of my compiler options have done anything.

btw, I'll be on the road for a next week an a half, so I won't have much internet access.

[Calmatory]

Right. It indeed seems to fail for me too. Wouldn't it be possible to use wprintf all the time though?

[poke349]

Right. It indeed seems to fail for me too. Wouldn't it be possible to use wprintf all the time though?

Yeah, that's probably what I'm gonna end up doing.

[[XC] gomeler]

Glad to hear you are making some progress on this. Sadly I'm not a C/C++ dev, I just dabble in scripting for work. Hopefully you guys can get it working on Linux so I can have a little fun

[poke349]

So I finally got all the static printing to work. I had to change some 500 printfs...

But now the dynamic prints are messed up. (The dynamic ones are the ones that keep overwriting the status - like when the % is incremented.)

A bigger problem is that the clock() is all messed up as well.
When multi-threading is disabled, it seems to work fine. But when multi-threading is enabled, it consistently gives the same inflated (and incorrect) time. I have no idea why.

(click to enlarge)

[Calmatory]

I'm afraid that to to dynamic printing, you need to use (* = n for linux, pd for windows) *curses library(It comes with the linux distribution, <ncurses.h>). It's pretty straightforward to write wrapper functions for it to manage stuff like dynamic printf().

as far as I've understood, clock() measures the execution time of a process. When it is run on multiple threads, it adds up the total execution time of those threads. I am not sure about this though. Try dividing the time with some constant related to the number of threads.

Glad to hear you are making some progress on this. Sadly I'm not a C/C++ dev, I just dabble in scripting for work.

Nothing stops you from becoming one though. Just grab a book and have a try.

[poke349]

I'm afraid that to to dynamic printing, you need to use (* = n for linux, pd for windows) *curses library(It comes with the linux distribution, <ncurses.h>). It's pretty straightforward to write wrapper functions for it to manage stuff like dynamic printf().

as far as I've understood, clock() measures the execution time of a process. When it is run on multiple threads, it adds up the total execution time of those threads. I am not sure about this though. Try dividing the time with some constant related to the number of threads.


Nothing stops you from becoming one though. Just grab a book and have a try.

Interesting. That means I can use clock() to determine the CPU utilization.

So actually, which clock function should I use as a wall clock?
And I don't really understand what you mean by "*" for dynamic printing.
(Right now, I'm using "\r" and a bunch of spaces to clear the line before I print over it. This doesn't always work in Linux.)


EDIT:

Here's a checklist of things left to fix before I can release it:

Required:

• Fix all the fpos_t problems. - Done
• Get the program to compile. - Done
• Fix the printf() problems. - Done
• Fix the messed up validation files. - Not Started
• Fix the timers. - Not Started
• Fix the dynamic printing. - Not Started

There will probably be more problems as I go on. But these are what I know need to be fixed for now.


Optional: (I haven't started any of these, but I will release an Alpha build of the Linux version before I start these anyway.)

• Linux implementation for reading the hardware (processor, frequency, memory, etc...)
• See which compiler (GCC or ICC) compiles faster code, and if needed, re-tune all the performance-critical code.
• Raw I/Os for maximum efficiency in the swap modes.
• Linux implementation of the validation and cheat-detection.
• "pthread.h" implementation of the multi-threading library to bypass OpenMP overhead.
• Add color to the console? (if this is even possible in Linux)

[Calmatory]

What I meant is that you'd probably have to use ncurses library with Linux and pdcurses library with Windows. They are equivalent(but newer) implementations of older UNIX curses library. It is pretty easy to build whole GUIs with *curses though, so I would definitely take a look at it. Too bad I have no experience with widecharacters so I can't say anything about *curses support for it.

Be careful with clock() though, it isn't very reliable afaik. I'll need to test it myself again.

[poke349]

yeah... I swear the dynamic print junk that I'm seeing is a bug in Linux.
I've looked up the definition of what printing "\r" does and I'm pretty sure what I'm doing right now should work...

I suppose the printf()/wprintf() failure thing is also a bug in Linux... (unless I missed some spec somewhere saying that you cannot mix the two...)

I'll have to take a look at the "curses" library and modify my print functions to use it for Linux... Looks like I can add color back in as well.

As for the timers... It looks like I'm gonna need to write my own timer object and migrate the entire program to it...
Especially seeing how Windows and Linux defines clock() differently... meh...

[Calmatory]

It's not a bug, it's a feature. (Most probably due to strict limitations due to actual terminal emulating)

As far as my exprience goes, you need to use \n to actually make the printf to print anything in linux. An ugly workaround would be to fiddle with \b, but it's not neat. Edit2: http://c-faq.com/osdep/baton.html -- So calling fflush() does the trick, no \n needed.

Regarding non-wide and wide character output: http://bytes.com/topic/c/answers/852...intf-glibc-bug
It seems that the standard defines it to work the way it does with Linux.

Edit: I'm not sure if you've read this but it sums up the clock() differences under Linux and Windows pretty well: http://stackoverflow.com/questions/5...-work-properly

[poke349]

Looks like sticking "fflush(stdout);" to the end of my print function solved the dynamic print problem completely... lol

I've also finished making my timer object and have just started migrating the program to it. So the first thing I did was replace the global computation timer with the new one...

And just as expected, it looks like the Linux version is a bit slower than the Windows version. I'll have more details soon, but I think the major reason is that OpenMP has a lot more overhead than WinAPI threads.
I guess the other reason is that all the code has been tuned to compile well on ICC and VSC...

There's still a lot more timers I need to switch to the new one before it's ready.

[Calmatory]

Great to hear.

Try not to call any printing functions while inside a loop, they seem to be quite expensive.
What kind of flags are you using with GCC? Which version of GCC is it? (g++ -v).

How much do you have C++ code sticked in?

[poke349]

Expensive yes, but there aren't too many of them - certainly not within any thing performance critical.

I'm booted into Windows right now so I can't check which version it is.
The options I'm using right now are:

g++ "x64 SSE3 - Linux.cpp" -msse3 -fopenmp -O2

I haven't actually checked through all the code yet, but I think the only C++ I'm using is a couple of "cin"s. Which isn't much. But I'll try to get rid of it later once I fix up all the important things first.

[Calmatory]

Have you tried compiling with the -O3? Or even -Os? Though, -Os optimizes for size, I've seen it being somewhere around -O2 and faster most of the time. Could be that in a big codebase as yc has, it could even help.

But well yeah, the speed shouldn't be that important yet.