Beating C with Futhark Running on GPU
futhark-lang.org
futhark-lang.org
[1]: https://xi-editor.io/docs/rope_science_01.html
[2]: https://raphlinus.github.io/personal/2018/04/25/gpu-unescapi...
I'm really interested in Futhark, though I haven't found a project where it would be make sense to use it. But I feel like it has the same potential to make GPU programming not feel overwhelming the same way Elm did with frontend work for me.
After seeing that it's possible to play crysis using software rendering on an AMD Rome cpu with 128 hw threads [1] - might this lead to some vindication for AMD sticking with opencl (assuming exposing such a cpu via opencl) - or is it just simpler to ignore that (in general and for futark) and just use regular threads for parallelizing aacross many cpu cores?
I guess it is possible to use OpenCL on the CPU as well, but it seems to be intended mostly for testing purposes. The Crysis software renderer uses threads: https://github.com/google/swiftshader/blob/master/src/Common...
What this article does show is that Futhark really does allow one to express this in a much simpler way than Haskell.
I hope I can assume that RHEL compiles their wc with at least -O.
True, maybe it's not about -O3 but about some factor in the unknown source code of the system wc. I did compile one version of wc with -O3 and it beat my system wc (Ubuntu) by 2x: https://news.ycombinator.com/item?id=21271951
(I had actually hoped Futhark would be slower sequentially, just so this wouldn't be the focus of the discussion!)
I used the "reference" source code linked from the original Haskell post, a BSD version hosted by Apple: https://opensource.apple.com/source/text_cmds/text_cmds-68/w...
It uses raw read() from a file descriptor and works with pipes as well. I think the only special handling for stdin vs. an actual file it has is calling fstat() if only the number of characters is requested, which shouldn't apply here.
So yes, this version does need to do more complicated I/O than a simple mmap(). And (broken record, but I'll stop after this) it's 2x as fast as my system's GNU wc (when compiled with -O3 vs. however the system wc was compiled).
> I had actually hoped Futhark would be slower sequentially
It might still turn out to be, if you see if you can get a faster C version of wc.
You definitely can, at least if you allow manually vectorized code.
On my system, with a 1.661GB file (256 times big.txt from the original Haskell post) GNU wc takes about 6.5s (real time), a stripped down version of Apple's implementation about 4.1s, and a single-threaded vectorized wc (written in C) only 0.27s. (These times are of course only with a hot cache. For reference, catting the same file to /dev/null takes about 0.18s.)
edit: corrected the time for the BSD-derived implementation
You're going to be intially page faulting every 4096 bytes if you mmap the file. The fact that you're accessing the mapped range sequentially in this case may help, I guess.
Compile and link with `-flto --march=native -O3` and you're good to go.
Would it be possible to use Futhark to rewrite the APL implementation instead of the Haskell one? That would make an interesting comparison.
Sadly, from what I can see, the APL version makes use of so-called nested arrays in the 'words' function, specifically arrays of strings (this is different from multidimensional arrays). Futhark does not directly support nested arrays. A rewrite of the APL implementation would require using a quite different algorithm (or a nontrivial encoding).
But my APL is a bit rusty, so I may be wrong.
My first attempt did some stuff with subtracting items in an array from their neighbor. Now with info I got from [mlochbaum](https://news.ycombinator.com/user?id=mlochbaum) I have another version that uses windowed reductions.
So those are three versions there; after that I just split it up just to see where that leads and that actually ends up feeling a lot like the Haskell / Futhark solution to me.
https://github.com/kwccoin/ABCDEFGHPPP
It is fun. I think I even try to use a micro version of cobol to do it. But the fastest is still c.
May be we can start one. Sadly no time to join.
(I think there is a web site that post many versions of the same program. It must have Wc. If not these should be there. )
I really like technologies like this and Sycl which aim to greatly simplify the process of writing GPU code. The important thing is that it can handle what you'd throw at it as if you were writing directly in Metal, Cuda, OpenCL, and I don't think that is the case (yet?) with Futhark.
But more importably, this benchmark is written as a composition of two reusable parts (a genetic algorithm that is parametric in its objective function, and a specific objective function that does option pricing) that are then put together in an efficient and automatic way by the compiler. You literally could not write it this way in OpenCL or CUDA (modulo extreme amounts of template metaprogramming in the latter). While you could certainly write a specialised GPU program that did exactly this calibration, and probably outperform Futhark, you would not be able to structure it as reusable components without significant performance loss. This, I think, is the main advantage of using a high-level language together with an optimising compiler.
[0]: https://github.com/diku-dk/futhark-benchmarks/tree/master/mi...
-- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
UNIX had very little to do with it, only very few people were lucky enough to have access to UNIX machines but untold 100's of thousands had access to PCs or 8 bit micros. The first time I saw a UNIX machine it was an Acorn 'Unicorn' and it was so far ahead of what I could afford that it might as well not exist.
It was just another programming language fighting for developer eyes.
On Windows and OS/2, although IBM and Microsoft decided to go with C for the underlying low level layers, C++ was the way to go for high level coding, C Set++, MFC. With Borland having Turbo Vision, OWL and VCL.
Macs were Object Pascal territory, and when MPW got C and C++ support, PowerPlant C++ framework was the way to go.
Epoch, BeOS and Symbian were also C++ territory.
MS-DOS games were also adopting C++ via Watcom and its DOS extender.
UNIX and the rise of FOSS, based on UNIX culture, were definitely the only reason.
And IMHO, at that time, before or around C++98, C++ didn't fix a single problem of C, but instead just added a lot of new ones (one could argue that this is still the case even today).
I was getting paid for teaching C++ on commercial training courses in 1990 - the C++ courses were probably the most popular after C and UNIX
> before or around C++98, C++ didn't fix a single problem of C
Of course it did, or why would people like me have transferred wholesale from C to C++?
C was never taught as such, as any student was expected to know it from their C++ classes.
The professor was a great teacher of what all the ways that C++ fixed C's problems, by providing his own data structures for strings, arrays, vectors, linked lists and hash tables, all with bounds checking enabled by default on his implementation.
Other issues that C++ fixed over C was having implicit conversions, a proper way to allocate memory (malloc() with sizeof, really?), ability to ensure valid pointers via references.
> malloc() with sizeof, really?
One tiny macro to solve 20% of all the problems people are whining about.
void _alloc_memory(void **ptr, size_t numElems, size_t elemSize)
{
size_t numBytes = safe_multiply(numElems, elemSize);
void *p = malloc(numBytes);
if (p == NULL)
fatal("OOM!\n");
*ptr = p;
}
#define ALLOC_MEMORY(ptr, numElems) _alloc_memory((ptr), (numElems), sizeof **(ptr))
int *myArray;
ALLOC_MEMORY(&myArray, 25);
Plus all C workarounds for "safe" code tend to fall apart when teams scale above 1 team member, as it keeps being proven by endless industry and academic reports.
Now Android NDK is Fortify enabled, with hardware tagging planned for all new ARM based models.
There is a difference between "explicit code" (which is mostly a good thing) and "boilerplate". It's saying what you mean vs saying what the platform requires you to say (or repeat, involuntarily). C definitely leads to the former, but not to the latter.
That said. It's a 1 line macro! You are being ridiculous. The amount of insanity we have to go through in so many other languages constantly, not just for setting a good base, is something completely different. It's not measured in handfuls of lines, but in number of hairs pulled out.
Compare:
#define ALLOC_MEMORY(ptr, numElems) _alloc_memory((ptr), (numElems), sizeof **(ptr))
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_vector.h
> for something that even Algol supports properly.
Probably with an allocation builtin, not allowing for custom allocators?
> supports properly.
There is nothing in this simple macro that isn't "proper". There are no ways it can break (although I still feel it would be nice to have expressions macros, not only token macros). The only requirement is you write it yourself. C in general doesn't like to give you canned things. It has made such mistakes in the past (see large parts of libc) and has actually learned from it.
> Plus all C workarounds for "safe" code tend to fall apart when teams scale above 1 team member, as it keeps being proven by endless industry and academic reports.
You could absolutely implement C with managed memory. It just wouldn't be a good idea. Use other languages if you want these tradeoffs.
Some of the most massive codebases in the world are C. (Often disguised as "C++ by experienced devs"). They are maintainable, protected investments, many decades old, and still in working order, precisely because a minimalistic language approach leads to modular APIs. It scales very well, and the "problem" might be mostly that the defect rate per line doesn't go down as the lines go up.
But the best feature of these codebases is that they exist, because C enables independent development of subsystems much better than the intertwingled messes and dead ends that most "statically-systematic" approaches lead to on non-trivial scales.
It's a huge boon that I don't have to think about rewriting interfaces using multiple inheritance or virtual inheritance or template insanity or SFINAE or unique_ptr or move semantics or rvalue references or static assertions or compile time evaluation, or the next fad around the corner, every 5 years.
ISO C doesn't offer full control over anything beyond the abstract memory model of the standard.
We all know that C is not without flaws. I would use other languages if there were good alternatives. For example, I liked some parts of Delphi, but it has too many show stoppers. For example, all local variables still have to be declared in the variables section before the function body, right? And are we still required to make type aliases to use pointer types in important places, such as function signatures?
C is special in that it is the only language that I've known that has a minimalistic attitude, resulting in a shitty language (every language is shit!) whose problems we can actually work around in practice.
Delphi is not Go, you can declare variables at the point of use nowadays.
Just like you can declare pointer types in function signatures, which would fail my code review, as those things tend to get out of hand.
Minimalist attitude leads to write only code bases, where it is impossible to maintain on long term projects with regular rotating team members, as it usually happens in most multinationals.
A workaround done today is a security exploit waiting to happen tomorrow.
Oh, it seems they introduced it in 2018, some time after I quit my 6-months Delphi stint. http://blog.marcocantu.com/blog/2018-october-inline-variable...
So, given the age of Delphi (and Pascal!), Go still has plenty of time to be quicker. Not sure what's missing from it, though.
Of course, I'm sure you knew all of that, and could have just mentioned it. But maybe you just want to convince people of unrealistic propositions, and claim that some obscure technologies were more practical than they really are.
> Just like C used to declare variables until C99.
1. C99 was 20 years ago, 19 years before Delphi.
2. What you say is wrong. You could declare variables at the start of any block since forever (I think it's standardized in C89).
3. What matters is compilers in practice, and I'm pretty sure they allowed you to declare variables anywhere, and also "for (int i..." (which is C99) since forever (as an extension).
> write only code bases
such as C++ code bases?
> regular rotating team members
I've just never seen that not becoming a mess
> A workaround done today is a security exploit waiting to happen tomorrow.
I'm still waiting for my code review. https://news.ycombinator.com/item?id=21290314 . For a start, where are my terrible workarounds?
Maybe it's just me, but I haven't seen this being a major problem in C. Most optimizations are local and fairly easy to reason about. C++ is a whole different story.
I might be in the minority, but to me, C is as high-level as we should go, for many many problems. If you really care about registers and SIMD stuff, then your concerns are architecture specific, and that's not really what C does well. What C does is mostly abstracting registers. Why blame it for that? The few places where you need SIMD, well, just insert architecture specific code there.
Is there a way to write portable code that can be better optimized?
That quote was true for some time but running into the limits of CPU clock gains for single threaded tasks all those optimizations are more than valid once more, and as you've no doubt noticed there is a veritable run on multi-core solutions embedded deeply in the languages, of which this article illustrates one special case using a co-processor.
C compilers are only speed monsters thanks to almost 50 years of research in optimizing C and C++ compiler backends.
Ok.
> C compilers are only speed monsters thanks to almost 50 years of research in optimizing C and C++ compiler backends.
Lots of those optimizations apply in one form or another to other languages as well.
And... so which is it? Are C compilers fast and the thing to beat or did that research go nowhere?
C is the speed benchmark because 'beating C' is what will get you a foot in the door. Being 'slower than C' is going to get your pet language booted out the door because:
- companies tend to compete on speed of execution
- the speed of the compiler itself is a major factor in turnaround time for the typical edit-compile-test cycle
- nobody cares about security until they've been bitten hard.
This is all very frustrating but it seems to - in my experience - accurately reflect priorities in lots of corporations. It is up to us to change that.
See the title: it is about the speed of execution, and it uses one technology 'GPU' to challenge another 'CPU' and yet the accent is on which language was used.
For CPUs, I'd like to introduce you to my good friend Fortran.
That's what I'm missing from these benchmarks - how does it fare against a handwritten, competent implementation in those languages?
That's fair, but it tells you nothing about the performance gap introduced by these high-level abstractions.
Futhark does not outperform expertly hand-optimised GPU code, but most of the GPU code found in the wild is hardly expertly hand-optimised. Futhark comes out on top surprisingly often, but can be solidly beaten for complex algorithms or clever implementations. See figure 8 in this paper for examples: https://futhark-lang.org/publications/ppopp19.pdf
If your application is better suited for GPUs of course it'll be faster than C on the cpu. GPU mining and AI training are done on the GPU for a reason, and they of course beat "C" on the cpu.
Fair enough about apples to oranges, but it was really distasteful to me that the top comment on this post was about how C is “unbeatable”, when the article clearly showed that Futhark was faster. And since we’re at the dawn of a new age of parallel computing, statements like that are absurd in general.
Barely...
It also mmaps in a whole 100 meg file. :P wc is not optimized to count as fast as possible, resource use be damned.
However, in practice, X-on-GPU where X is not Futhark is rare, because GPU programming is notoriously difficult and time-consuming. Futhark's purpose is to make high-performance data-parallel programming more accessible, even if you could potentially write a faster program yourself.
There are no empirical measurements that I know of, but I would not be surprised if it is a hundred times faster to write a Futhark program than the corresponding OpenCL program. CUDA fares a little better, but not by much. So even if your hand-written program might be twice as fast as Futhark, do you really have the time to write it in the first place? And if you later want to make a small change to its logic (say, adding another parallel loop on top), you may need to rework all of your optimisations from scratch.
> ispc compiles a C-based SPMD programming language to run on the SIMD units of CPUs and the Intel Xeon Phi™ architecture; it frequently provides a 3x or more speedup on CPUs with 4-wide vector SSE units and 5x-6x on CPUs with 8-wide AVX vector units, without any of the difficulty of writing intrinsics code. Parallelization across multiple cores is also supported by ispc, making it possible to write programs that achieve performance improvement that scales by both number of cores and vector unit size.
There is also an interesting story of its development (full with office politics drama :-P) written by its -then- main developer: https://pharr.org/matt/blog/2018/04/18/ispc-origins.html
Fortran scares people because it is often identified with FORTRAN77. I find very unfortunate that the concept of F (a modern simplified Fortran without the legacy features [1]) never took off, although I understand the reasons.