Compare: Language Selection for Mathematical Research

This is a side-by-side comparison of programming languages, implementing a toy problem with similar characteristics to the combinatorial search that arises in my research. My immediate goal was to reconsider the language choices for my work.

Optimizing code in languages you do not know is an interesting form of tourism, only made possible by working with AI. Multiple agents were involved in this project. I am responsible line-by-line for the code in languages I seriously considered for adoption. Core algorithms are entirely mine, such as the "Loops" alternative to Tarjan union-find, or the mimimal implementation of parallel work stealing in OCaml and Scala.

This is a partial, public view of the project.

The Problem

We tally in parallel the cycle distributions of signed permutations (elements of the hyperoctahedral group B_n). For n=10 there are n! * 2^n = 3,715,891,200 signed permutations.

Results

Benchmarked on Apple M4 Max (12 performance cores), n=10, prefix=3. Every row below was measured in the same 24 hours on the same idle machine, 4 trials each.

Two algorithms are tested: Tarjan (tree-based union-find) and Loops (a simpler cycle-counting method).

Tarjan (tree-based union-find)

The classical Tarjan algorithm (Tarjan 1975) achieves O(m α(n)) only with both union-by-rank and path compression. We benchmark with neither: rank was empirically a wash at our small n; path compression turned out to be a universal cost in this round's experiment (see Key Insights). What runs is primitive tree-based union-find. The Tarjan name has become honorific.

Loops (simple algorithm, predictable access patterns)

I could imagine committing to any language on this list. Various other languages were considered, and dropped as impractical.

Reading the results

Score normalizes throughput so the fastest language averages 100. A score of 80 means 80% as fast as the leader.

Variance (±) estimates the smallest timing difference that has a 50% chance of being real rather than noise. Most languages cluster around ±0.05–0.15s. Chez and Kotlin Native are the most deterministic this round (±0.01s on both algorithms). Rust shows the widest spread (±0.22–0.24s).

Tarjan vs Loops are now closer in cost than before. Without path compression, Tarjan's hot loop is a clean walk up the parent chain — much like Loops's endpoint walk. C arrived late, took both crowns with fixed-size value structs, and forced a rematch: with the same idioms backported, C, C++, Rust and Zig now sit within 3% of each other on both algorithms — a plateau, not a podium. The variables that still separate them are compiler backends (LLVM schedules Tarjan's dependent loads better, GCC wins Loops's stores; the C and C++ run scripts choose per algorithm) and how much safety each language leaves switched on.

A caution about what these numbers measure. Attention has never been distributed evenly, and scrutiny has only ever made a language faster — no implementation here has been examined and gotten slower. So the table is partly a record of who was looked at last. The gap is not hypothetical: when the fixed-size-value-struct idiom that C shipped with was backported to the others, C++ and Rust each gained 10–14% and Go gained 8–10%, moving Go past four languages it had been sitting among. Every score is a lower bound, and the bound is tightest where the attention was highest. The mid tier — Kotlin, Scala, Julia, Nim — has not had that round.

Architecture

Each language implementation lives in source/{language}/ with the same structure:

source/{language}/
  src/         Source files
  run          Build and execute script

The code separates into two layers:

• Perms (coordination): Generates work parcels, distributes them across cores, combines results. Written for clarity in each language's idiomatic style.
• Worker (computation): The hot loops. Heap's algorithm for permutation generation, cycle counting via union-find or the Loops algorithm. Optimized aggressively — mutable arrays, zero allocation, explicit loops.

This separation is deliberate. Mathematical code should be readable at the coordination level and fast at the computation level.

Parallelism

Work is divided into parcels by permutation prefix, then distributed across cores. Most implementations use a short hand-rolled atomic work-stealing queue (Scala, OCaml, Lean 4, and others); a few use language-native parallel frameworks.

Benchmarks use 12 performance cores to ensure fair comparison across languages.

Running

just run scala 10 3 12    # Run Scala with n=10, prefix=3, 12 cores
just do scala             # Benchmark Scala (default: 4 iterations, n=10, both algorithms)
just do                   # Benchmark all default languages
just report               # Save timing reports
just show Tarjan 10       # Display Tarjan results for n=10

Key Insights

1. Allocation in hot loops is the primary performance killer. Top-tier performance requires eliminating allocation from the inner loops.

2. Path compression doesn't pay at small n. Removing it sped up every implementation — Lean by 2.7×, others by 5–25%. Tarjan's amortized α(n) bound is asymptotic; at chain length ≤ 24 the compression writes cost more than they save. The benchmark's "Tarjan" is now honorific — no rank, no compression — primitive tree-based union-find.

3. Simple parallel patterns work well. A short atomic work-stealing queue is competitive with language-native parallel frameworks. Where both were built and raced — Go's ticket dispenser against a channel worker pool — they tied within noise, because 720 parcels of 25ms each leave nothing for dispatch to win.

4. The top JIT tier is readable. F#, Kotlin, and Scala 3 deliver competitive performance with concise, expressive code.

5. Where the data lives beats how it is written. Every language that moved its relations array from a heap allocation into inline fixed-size storage gained: C++ and Rust 10–14%, Go 8–10%. The wins were large enough, and uniform enough, that a language's position here mostly records whether anyone has performed that surgery on it yet.

6. The price of memory safety varies by two orders of magnitude, and the data layout sets it. On inline arrays with a compile-time length, Go's bounds checks became unmeasurable — a build with checks disabled is no faster. On the same loops Rust pays ~10%, and Zig's ReleaseSafe 11–22% while also checking overflow and narrowing casts. Swift, the one implementation built on a reference type, paid 160% for the dynamic exclusivity enforcement a class requires — until it became a struct.

7. Reference types are a performance liability, not a style preference. Swift's implementation silently depended on the optimizer eliminating those exclusivity checks. One compiler release withdrew the favour and the benchmark ran 3.9× slower overnight, with no source change. Value types make the same guarantee statically, for free, and cannot regress this way.

Conclusion

I love Ruby for scripting but it doesn't scale or perform well for math research. I've searched for compiled or typed Ruby, e.g. Crystal, and I've been left unmoved.

I'm an old Haskell programmer, coming from SML then OCaml. F# is not quite OCaml, with an impressive jit, and .NET rusty bedsprings poking through. I've been through Lisp, Scheme, Clojure, Erlang, Idris. All of these functional choices left me uncertain for various reasons.

My bias against Java was so extreme that I ignored Scala completely, only taking another look after being puzzled by its featured status in the Zed editor. I saw a native compiler so I gave it a try. Of course, the JVM jit is faster.

Kotlin arrived later as the obvious second JVM comparison; it runs neck-and-neck with Scala but doesn't displace it. Kotlin could be a pragmatic choice, but it is a regression in expressiveness from Scala 3 for mathematical work. Clojure also targets the JVM but is too slow to consider. It lands ~40× behind the pace setters.

It is hard to shed prejudices about how code should look, even if learning to see clearly past convention is the only good reason to be a mathematician. I'm already quite sure how I will die: I'll read another article on Hacker News about a new programming language where I see nothing new, and I'll read that they included {}; to make C programmers comfortable. I'll have a massive stroke.

Haskell abstracts on two axes simultaneously. A single traverse f xs works across every traversable container — list, tree, map, custom data type — and every applicative effect — failure, IO, accumulation, validation. OCaml requires per-container code or explicit functor passing for each combination. Scala has the machinery via type classes, but the ceremony discourages casual use. For research code that constantly composes operations across structures-with-effects, that double-axis abstraction is the load-bearing argument for Haskell.

Scala can appear to win this comparison study. At the same time, this comparison raises the wrong questions. Especially with the advent of AI, the right question is which language supports the highest level architectural thought, and at the same time is suitable for real work. I'm the bottleneck, not my computer processing power. One could say Haskell hits that abstract-yet-practical sweet spot, and I knew this before starting this comparison project. I needed to know if there was a different answer.

In college my choices were FORTRAN on punched cards on a single IBM 1130 that served the entire school, and an APL timesharing terminal. I was able to write mathematical code in college using APL that would have been out of reach in FORTRAN. Later, the company providing the timesharing called to ask who was this kid, and hired me for the summer. I could write reporting software in a morning that their client's FORTRAN shop would take months to even start. APL radicalized me; expressive power is the whole ball game.

In my dreams I only code in Lean 4. When I began this project, AI really struggled to use Lean as a general purpose programming language, unable to navigate a training corpus largely focused on proof. That has changed. Lean benchmarks as the slowest language in my comparison, but it is also by far the most expressive. For general purpose programming, one could use dependent types or verify program correctness, but this is optional. Lean 4 is young and under active development, and is by far the most interesting language to learn. I believe that I am choosing Lean for my research, in part to keep my interest engaged as I work.