Calling Futhark from C and Haskell | Hacker News Reader

Calling Futhark from C and Haskell

futhark-lang.org

88 pointsAthas15 comments

It's nice seeing Futhark on here. I prefer my array languages to be more like APL or J, but perhaps this is better for longer code. I know it is easier for the compiler to put on the GPU I guess?

The biggest issue with compiling APL and J is the presence of dynamic types (and other dynamic behaviour). For the subset of APL can that can be resolved statically, I don't see why they should be particularly difficult (Co-dfns[0] seems to be making good progress). To handle anywhere near full APL, you probably need some complicated JIT compiler, unfortunately.

[0]: https://github.com/arcfide/Co-dfns

Big follower of Aaron's work even though I don't use it. He gave two recent talks at Dyalog 17' last week. Both worth at least flipping through the slides.

Hooray! I've been playing with Futhark from time to time (and it's lovely).

I have eagerly been awaiting this development! This is great!

I write much of my code in Rust these days and being able to generate plain C entrypoints to my Futhark functions will allow me to bridge both worlds :)

That's good to hear! You will probably encounter some limitations due to the missing support for error recovery. When you do, we'd very much like to hear from you, to get an understanding of what a proper solution should look like.

For example, we probably should not handle "catastrophic" errors like GPU/compiler bugs the same way we handle "incidental" errors like bounds check failures. The former might well poison the entire context, while the latter should permit subsequent entry points to work.

I have a question regarding the new library generation: is this also supported by futhark-c (or are there plans to support this down the line)?

I'd like to be able to fall back to CPU execution when OpenCL is not available on a platform. I realize this means I will need to reduce the problem set significantly, but it would be nice to be able to run a small demo on unsupported platforms as well.

Yes, both futhark-c and futhark-opencl use the exact same infrastructure.

Chuckled at relevant favicon

https://futhark-lang.org/performance.html

Good eye! Sanic sped

I love the integration C and Haskell. And of course Python. Looking forward to play with it soon!

I'd like to see "efficient string sorting" as one of the examples, as it is structurally very different from most vector operations, yet it can be parallelized very well.

It's a little tricky to implement irregular algorithms in Futhark, but I'd like to give it a try. Do you know of a nice data-parallel algorithm for string sorting?

That would be cool! Radix-sort is an algorithm that is both simple and it can be parallelized [1].

There's also a sorting-contest [2], perhaps it can bring some more inspiration.

[1] https://en.wikipedia.org/wiki/Radix_sort

[2] http://sortbenchmark.org/

We already have both a radix sort[0] and a bitonic merge sort[1]. They perform alright - nothing world-shaking, but fine. I was more interested in whether string sorting has some particularly clever algorithms.

[0]: https://github.com/diku-dk/futhark/blob/master/futlib/radix_...

[1]: https://github.com/diku-dk/futhark/blob/master/futlib/merge_...

Nice to see that you have radix-sorting covered!

I'm not aware of sorting algorithms that use "clever" tricks; the challenge with sorting seems to be in the low-level optimization (e.g. making sure that no unnecessary data-copying takes place).

If you are looking for a challenge, then you could try sorting arbitrary length strings (more difficult since the comparison operator is of non-constant time). Or do something like the Burrows-Wheeler transform [1], where you sort all rotations of a very large string. This is actually a very useful operation for building a large search index [2]. Many people in e.g. bioinformatics would be very interested in a fast solution.

[1] https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...

[2] https://en.wikipedia.org/wiki/FM-index

Reply on news.ycombinator.com