Except the intermediate values are stack-allocated in Rust and C as well. This article claims that stack-allocated data is faster than heap-allocated as well, which is dubious without further clarification. malloc is indeed slower than pushing to the stack, and the stack will almost certainly be in cache, but this program is small enough that its working set will always be in cache so there should be minimal difference.

I’m curious what the modular function is doing in Rust - the C implementation just uses a simple (n % 2) == 0 while the Rust code does ((n % 2) + 2) % 2 and it’s not clear why.

I can’t wait for “faster than rust” to be the new meme.

eliminating all heap allocations

Rust isn’t heap allocating anything.

Something the other comments aren’t touching on is that what’s slow about functional programming has nothing to do with a collatz function. These are just integers, so the types will always be copied in and out of registers instead of mutated (probably, depends on what the compiler feels like doing). What’s slow about ‘functional programming’ is when you have larger datatypes and you choose to make an entirely new one instead of an old one. What’s slow is when the idiomatic datastructure is the linked list which wreaks havoc on your cache, or other tree based persistent datastructures. What’s slow is the abuse of dynamically dispatched first class functions, which compilers go to great lengths to avoid but is sometimes unavoidable.

The only way to make functional programming fast, as a paradigm, is to really commit to linear/affine types (like BOTH Rust and ATS have, actually), so the compiler has enough information to determine that it can reuse the memory space.

I’m a secret Standard ML fan and I’ve been using Rust since late mid 2014 so of course I like ATS. :) I just find the “point” of the article pretty misleading.

Never heard of ATS, and it’s not linked to in the post. Here it is:

http://www.ats-lang.org

ATS is a statically typed programming language that unifies implementation with formal specification. It is equipped with a highly expressive type system rooted in the framework Applied Type System, which gives the language its name. In particular, both dependent types and linear types are available in ATS.

How was the C function tested? With/without -O2 makes a difference, and using unsigned integers also makes a difference.

collatz_c, linux/amd64, gcc 6.3.0 without optimizations:

0000000000000000 <collatz_c>:
   0:	55                   	push   %rbp
   1:	48 89 e5             	mov    %rsp,%rbp
   4:	89 7d ec             	mov    %edi,-0x14(%rbp)
   7:	c7 45 fc 00 00 00 00 	movl   $0x0,-0x4(%rbp)
   e:	eb 2e                	jmp    3e <collatz_c+0x3e>
  10:	8b 45 ec             	mov    -0x14(%rbp),%eax
  13:	83 e0 01             	and    $0x1,%eax
  16:	85 c0                	test   %eax,%eax
  18:	75 11                	jne    2b <collatz_c+0x2b>
  1a:	8b 45 ec             	mov    -0x14(%rbp),%eax
  1d:	89 c2                	mov    %eax,%edx
  1f:	c1 ea 1f             	shr    $0x1f,%edx
  22:	01 d0                	add    %edx,%eax
  24:	d1 f8                	sar    %eax
  26:	89 45 ec             	mov    %eax,-0x14(%rbp)
  29:	eb 0f                	jmp    3a <collatz_c+0x3a>
  2b:	8b 55 ec             	mov    -0x14(%rbp),%edx
  2e:	89 d0                	mov    %edx,%eax
  30:	01 c0                	add    %eax,%eax
  32:	01 d0                	add    %edx,%eax
  34:	83 c0 01             	add    $0x1,%eax
  37:	89 45 ec             	mov    %eax,-0x14(%rbp)
  3a:	83 45 fc 01          	addl   $0x1,-0x4(%rbp)
  3e:	83 7d ec 01          	cmpl   $0x1,-0x14(%rbp)
  42:	75 cc                	jne    10 <collatz_c+0x10>
  44:	8b 45 fc             	mov    -0x4(%rbp),%eax
  47:	5d                   	pop    %rbp
  48:	c3                   	retq   

collatz_c, linux/amd64, gcc 6.3.0, -O2:

0000000000000000 <collatz_c>:
   0:	31 c0                	xor    %eax,%eax
   2:	83 ff 01             	cmp    $0x1,%edi
   5:	75 1a                	jne    21 <collatz_c+0x21>
   7:	eb 2c                	jmp    35 <collatz_c+0x35>
   9:	0f 1f 80 00 00 00 00 	nopl   0x0(%rax)
  10:	89 fa                	mov    %edi,%edx
  12:	83 c0 01             	add    $0x1,%eax
  15:	c1 ea 1f             	shr    $0x1f,%edx
  18:	01 d7                	add    %edx,%edi
  1a:	d1 ff                	sar    %edi
  1c:	83 ff 01             	cmp    $0x1,%edi
  1f:	74 12                	je     33 <collatz_c+0x33>
  21:	40 f6 c7 01          	test   $0x1,%dil
  25:	74 e9                	je     10 <collatz_c+0x10>
  27:	8d 7c 7f 01          	lea    0x1(%rdi,%rdi,2),%edi
  2b:	83 c0 01             	add    $0x1,%eax
  2e:	83 ff 01             	cmp    $0x1,%edi
  31:	75 ee                	jne    21 <collatz_c+0x21>
  33:	f3 c3                	repz retq 
  35:	f3 c3                	repz retq 

collatz_c, linux/amd64, gcc 6.3.0, -O2, s/int/unsigned int/:

0000000000000000 <collatz_c>:
   0:	31 c0                	xor    %eax,%eax
   2:	83 ff 01             	cmp    $0x1,%edi
   5:	74 23                	je     2a <collatz_c+0x2a>
   7:	66 0f 1f 84 00 00 00 	nopw   0x0(%rax,%rax,1)
   e:	00 00 
  10:	89 fa                	mov    %edi,%edx
  12:	8d 4c 7f 01          	lea    0x1(%rdi,%rdi,2),%ecx
  16:	d1 ea                	shr    %edx
  18:	83 e7 01             	and    $0x1,%edi
  1b:	0f 45 d1             	cmovne %ecx,%edx
  1e:	83 c0 01             	add    $0x1,%eax
  21:	83 fa 01             	cmp    $0x1,%edx
  24:	89 d7                	mov    %edx,%edi
  26:	75 e8                	jne    10 <collatz_c+0x10>
  28:	f3 c3                	repz retq 
  2a:	f3 c3                	repz retq

I was trying to get this to run on my machine, but I was running into issues on Arch Linux (something having to do with Stack and Cabal? I’m not a Haskell guy). One thing I noticed was that there’s no --release flag on the cargo command - the optimizations for Rust really do make a difference. Could someone add that argument to shake.hs and see what the speeds look like?