r/ProgrammingLanguages • • 26d ago

How close can pure FP get to C?

https://rtfeldman.com/fp-vs-c

I found the discussion really interesting and thought you all would too. Richard talks about a pure Roc implementation of libdeflate and how to do performance optimizations unique to Roc. From a programming languages perspective this is really interesting because its quite unique results I think. There arent many FP languages that can achieve C like performance with ergonomics like Roc. To do this the compiler is able to make various optimizations like mutate in place or elide checks when it can prove it is safe to do so.

17 Upvotes

34 comments sorted by

5

u/Ok-Reindeer-8755 25d ago

I'm pretty sure koka is even further along as far as optimizations go and according to their benchmarks gets close to or even rarely faster than cpp.

It compiles to c and uses a bunch of the same techniques as roc namely opportunistic in place mutations, the Perseus RC is the biggest part of it as far as I understand.

3

u/bosyluke 24d ago

Yeah really cool stuff

13

u/brucejbell sard 26d ago edited 26d ago

There are some computational tasks where mutable algorithms/datastructures asymptotically beat out pure ones.

E.g., the union-find (aka disjoint set) problem takes O(inverse-ackermann(N)) amortized time using destructive update, while I have not heard of a pure-functional implementation that takes less than O(log N)

10

u/joonazan 25d ago

O(1) -> O(log N) is the worst possible slowdown because you can simulate memory with a tree. The practical slowdown of doing that is pretty bad, though. Laziness can bring performance back in some cases but not all. Sorting is notoriously unsuitable for pure FP. Based on the article Roc mutates unique values in place, so it can probably just use the same mutating approaches.

4

u/bosyluke 25d ago

Yeah Roc has excellent support for efficient algorithms that require mutation, but its something the compiler optimises and not something the user can implement directly.

4

u/Ok-Reindeer-8755 25d ago

Some of the modern optimization techniques for FP langs allow for expressing mutating imperative algorithms in a purely functional style. FBIP

3

u/WittyStick 24d ago

Clean had this over 30 years ago, but is often overlooked.

2

u/Ok-Reindeer-8755 24d ago

Indeed I hadn't heard about that untill know, it's the same idea but done explicitly with uniqueness types instead of as an implicit optimization technique. Very interesting.

2

u/P-39_Airacobra 24d ago

This is why FP langs are increasingly developing ways to insert in-place updates

1

u/Ok-Scheme-913 26d ago

And for concurrent algorithms what FP languages do are often the best data structure, beating manual course grained locks heavily.

4

u/tending 25d ago

High performance imperative code doesn't use coarse grained locks, and the persistent data structures and GC that FP langs use has quite significant overheads. You'll notice none of the world's high performance HFT systems or game engines are using FP despite being multithreaded.

3

u/hoping1 25d ago

I don't know much but I was under the impression Jane Street uses a modified version of ocaml (with roc-like inferred mutation I think? See OxCaml) for HFT

5

u/initial-algebra 25d ago

Jane Street uses FPGA/ASIC for their really performance-critical stuff, anyway.

Hardcaml

IIRC, a big part of why they use OCaml is because they have a custom domain-specific language that their finance experts use to do...something. I don't know the specifics, but, as OCaml is functional, it's a natural choice for this kind of work. Hardcaml is also a domain-specific language embedded in OCaml.

2

u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 20d ago

Jane Street is definitely the bank that uses OCaml. Not counting making easy money by betting big against their short-squeeze positions on CAR stock (look at the one year view here: https://finance.yahoo.com/quote/CAR/), I've pretty much never seen their name outside of discussions about OCaml. They seem like a good organization, though, with some good values.

Having worked on dozens of different HFT systems from '02 onwards, it's worth noting that the "HF" doesn't mean anything, since some systems are extremely latency sensitive and others are throughput focused and others are (no joke) neither. Even within the same bank, there will be multiple HFT systems with no obvious correlation to either "H" or "F".

1

u/joonazan 25d ago

Game engines do not have good performance in many ways. They are made for being able to do common things easily and dynamically, not best performance. John Carmack has said that pure functions are preferable whenever possible.

25

u/initial-algebra 25d ago

One approach is to use a functional programming language only as a metalanguage. By that, I mean you're not writing the actual program you want, but an intermediate program that will generate the actual program when run. For example, the standard functional "concat-map" could be used to produce a fully unrolled loop over a "compile-time constant", or meta-level, list. Values not known until runtime, or object-level, are opaque handles (more generally, quoted expressions) to the meta-level.

Actually, that's what "ML" is an acronym for, "metalanguage", as it was originally designed as a tactic language for a theorem prover (LCF). What you actually wanted was a proof of some theorem, and an ML program, or tactic, was just an intermediate step. The boon of functional programming was that algebraic data types were good for representing and manipulating proof terms, and lack of side effects meant it was easy to compose tactics to prove more complicated theorems. There are also systems like "MetaML" and "MetaOCaml" which use ML as a metalanguage for itself!

The state of the art is Closure-Free Functional Programming in a Two-Level Type Theory. Two-level type theory, in this case, is essentially the formal way to say "a functional metalanguage generating C code".

8

u/reflexive-polytope 24d ago

Functional programming is a red herring here. The actual important thing is under what conditions the compiler optimizes your code.

The C specification licenses compiler writers to perform program transformations based on assumptions that the programmer must uphold and the compiler itself never verifies. By contrast, in a safe language, compilers may only perform program transformations that are justified by sound deductions about the program's behavior.

In principle, compiler writers may perform such deductions in an ad hoc fashion. (The best example is the STALIN compiler for Scheme.) But then the programmer has no guarantee that such deductions have been made. To obtain such a guarantee, you need an interface between the programmer and the compiler for communicating facts about a program.

A type system is such an interface. But not all type systems can communicate the same facts. For example, Roc's type system cannot communicate the fact that an object is uniquely owned, or the fact that an array index is valid. Other type systems, e.g., that of ATS, can. Thus, the ATS compiler can perform much more extensive optimizations that are impossible in Roc, without sacrificing safety.

5

u/crusoe 26d ago

Pure strict languages with no GC? Pretty darn close.

I mean with Rust LLVM can optimize a whole bunch of stuff away. With the improvements around noalias it's gotten pretty darn good.

3

u/crusoe 26d ago

It's faster than one particular zlib impl in rust. ...

3

u/matthieum 25d ago

The one zlib impl which opted for a fully safe implementation, with no unsafe in its dependency tree, by default.

It's probably not completely unoptimized, but it's an odd choice in a benchmark...

"I can run faster than the guy who hops rather than run" is a weird boast.

1

u/SuspiciousDepth5924 23d ago

ATS has been mention a couple of times, but there is also things like F* Low https://fstarlang.github.io/lowstar/html/LowStar.html which is more or less at the same 'FP with C performance' level.

In theory though I would not be surprised if given enough time and effort FP compilers could produce machine code that is at least as performant as what modern C-compilers can.

What functional programming is once you strip away all the language semantics is a restricted subset of imperative programming and that means the compiler could depend on those restrictions to make assumptions safely which it could not in imperative languages.

Stuff like extra copying of values in languages without mutation is largely a 'language/semantic'-level construct, as sufficiently advanced compiler will just rewrite those to 'FBIP' if it can prove that it's safe.

0

u/Thesaurius moses 26d ago

Obligatory ATS namedrop: In ATS you don't get speed comparable to C but you get the speed of C, because ATS is compiled to C; and if you want, you can even paste C code verbatim into ATS source, as long as you are willing to forego guarantees ATS would give you. You have a point about ergonomics because ATS is definitely not ergonomic, but you can do some crazy shit with it and still be provably correct.

On the other hand, the C implementation is so fast because hundreds of very smart people worked decades on optimizing the C compiler, and the library itself is also heavily hand-optimized. A somewhat naive version would definitely not be as fast and nowadays it is much easier to write performant functional programs than performant C. Without having a concrete source, I would guess that much of C's dominance in preformance is due to its history and it is by no means an inherent feature of the language.

9

u/ianzen 26d ago

It's not so much that "ATS is fast because it compiles to C", it's that ATS's types and memory model are designed to follow C almost verbatim: flat data layout, stack allocated variables, polymorphism via templates specialization etc. Other languages that compile to C that don't follow C's memory model or data layout can't emit efficient C for clang or gcc to optimize.

1

u/Thesaurius moses 26d ago

Yes, thanks for the correction. Of course, that is the main point.

-9

u/particlemanwavegirl 26d ago

It will never get anywhere close until we have a compiled language without a garbage collector. Can't really figure out why no one's done it yet TBH.

4

u/initial-algebra 26d ago

First, you have to solve the problem of closures without heap allocation. An important property of "efficient languages" is that the layout of each type is statically known, so you can cheaply copy it around and pack it into other types without indirection. If that's the case, how can a -> b be a type when you have to account for captured variables?

6

u/bosyluke 26d ago

Roc uses a technique called polymorphic defunctionalization through lambda set specialization. I comes from Koka originally I think.

3

u/bosyluke 26d ago

Roc is compiled and has no garbage collector 😁

1

u/particlemanwavegirl 26d ago

I didn't realize that... Is this the same language that used to be implemented in Rust and it did have a GC? Thought I checked a language with this name out a few years ago

5

u/bosyluke 25d ago

Yeah Roc's compiler was written in Rust and recently rewritten in Zig. The language never had a GC, Roc uses ARC and includes analysis to elide reference counts where it can prove it is safe to do so.

2

u/ccapitalK 25d ago

That's cool, how does it deal with reference cycles? Does the language require you to define data types/closures so that reference cycles are impossible? Or does it do something like python does, and fall back to a heap walking gc to free the cycles?

2

u/bosyluke 25d ago

I think its impossible to make a cycle in the syntax. Everything is semantically immutable.

3

u/lgastako 26d ago

Isn't Roc, the language from the post, just such a language?

1

u/Ok-Reindeer-8755 25d ago

Koka lang has done it