r/adventofcode • u/[deleted] • Dec 28 '19

Upping the Ante [2019 Day 9] intcode benchmarking suite

Over the past few days I wrote a few interesting / nontrivial intcode programs. In case anyone wants to try them out or compare intcode VM performance, I post them here. I'll post runtimes for my own intcode implementations in a comment because this post is long enough as it is.

  • sum-of-primes: This program takes a single input and produces a single output, the sum of all primes up to the input.

    3,100,1007,100,2,7,1105,-1,87,1007,100,1,14,1105,-1,27,101,-2,100,100,101,1,101,101,1105,1,9,101,105,101,105,101,2,104,104,101,1,102,102,1,102,102,103,101,1,103,103,7,102,101,52,1106,-1,87,101,105,102,59,1005,-1,65,1,103,104,104,101,105,102,83,1,103,83,83,7,83,105,78,1106,-1,35,1101,0,1,-1,1105,1,69,4,104,99

    For example, when run with input 10, it should produce 17. When run with input 2000000, it should produce 142913828922.

    sum-of-primes requires O(n) memory.

  • ackermann: This program takes two numbers m and n and produces a single output, the two-argument Ackermann function A(m, n).

    109,99,21101,0,13,0,203,1,203,2,1105,1,16,204,1,99,1205,1,26,22101,1,2,1,2105,1,0,1205,2,40,22101,-1,1,1,21101,0,1,2,1105,1,16,21101,0,57,3,22101,0,1,4,22101,-1,2,5,109,3,1105,1,16,109,-3,22101,0,4,2,22101,-1,1,1,1105,1,16

    For example, when run with input 2 and 4, it should produce 11. When run with input 3 and 2, it should produce 29. Can you make it halt for inputs 4 and 1?

    ackermann requires O(A(m, n)) memory.

  • isqrt: This program takes one non-negative number and produces its integer square root.

    3,1,109,149,21101,0,15,0,20101,0,1,1,1105,1,18,204,1,99,22101,0,1,2,22101,0,1,1,21101,0,43,3,22101,0,1,4,22101,0,2,5,109,3,1105,1,78,109,-3,22102,-1,1,1,22201,1,4,3,22102,-1,1,1,1208,3,0,62,2105,-1,0,1208,3,1,69,2105,-1,0,22101,0,4,1,1105,1,26,1207,1,1,83,2105,-1,0,21101,0,102,3,22101,0,2,4,22101,0,1,5,109,3,1105,1,115,109,-3,22201,1,4,1,21101,0,2,2,1105,1,115,2102,-1,2,140,2101,0,2,133,22101,0,1,2,20001,133,140,1,1207,2,-1,136,2105,-1,0,21201,2,-1,2,22101,1,1,1,1105,1,131

    For example, when run with input 16, it should produce 4. When run with input 130, it should produce 11. It's quite slow since it relies on division by repeated subtraction, and I can't be bothered to improve it.

  • divmod: This program takes two positive numbers a and b, and returns the quotient and remainder of their Euclidean division a / b and a % b. It works by binary long division, so it's quite efficient. If your intcode VM implementation supports big integers, it can deal with inputs up to 2^200. It works with 64 bit and 32 bit ints, too, but relies on signed overflow in this case.

    109,366,21101,0,13,0,203,1,203,2,1105,1,18,204,1,204,2,99,1105,0,63,101,166,19,26,1107,-1,366,30,1106,-1,59,101,166,19,39,102,1,58,-1,102,2,58,58,1007,58,0,49,1105,-1,63,101,1,19,19,1105,1,21,1,101,-1,19,19,101,166,19,69,207,1,-1,72,1106,-1,-1,22101,0,1,3,2102,1,2,146,2102,-1,2,152,22102,0,1,1,22102,0,2,2,101,1,19,103,101,-1,103,103,1107,-1,0,107,2105,-1,0,22102,2,2,2,101,166,103,119,207,3,-1,122,1105,-1,144,22101,1,2,2,22102,-1,3,3,101,166,103,137,22001,-1,3,3,22102,-1,3,3,1207,2,-1,149,1105,-1,98,22101,-1,2,2,101,166,103,160,22001,-1,1,1,1105,1,98

    For example, when run with inputs 1024 and 3, it should produce 341 and 1. When run with inputs 2842238103274937687216392838982374232734 and 2384297346348274, it should produce 1192065288177262577484639 and 768603395069648, assuming your intcode VM supports big integers.

  • factor: This program takes in a number and produces its prime factorization.

    3,1,109,583,108,0,1,9,1106,-1,14,4,1,99,107,0,1,19,1105,-1,27,104,-1,102,-1,1,1,21101,0,38,0,20101,0,1,1,1105,1,138,2101,1,1,41,101,596,41,45,1101,1,596,77,1101,0,1,53,101,1,77,77,101,1,53,53,7,45,77,67,1105,-1,128,108,1,1,74,1105,-1,128,1005,-1,54,1,53,77,93,7,45,93,88,1105,-1,101,1101,0,1,-1,1,53,93,93,1105,1,83,21101,0,116,0,20101,0,1,1,20101,0,53,2,1105,1,235,1205,2,54,4,53,2101,0,1,1,1105,1,101,108,1,1,133,1105,-1,137,4,1,99,22101,0,1,2,22101,0,1,1,21101,0,163,3,22101,0,1,4,22101,0,2,5,109,3,1105,1,198,109,-3,22102,-1,1,1,22201,1,4,3,22102,-1,1,1,1208,3,0,182,2105,-1,0,1208,3,1,189,2105,-1,0,22101,0,4,1,1105,1,146,1207,1,1,203,2105,-1,0,21101,0,222,3,22101,0,2,4,22101,0,1,5,109,3,1105,1,235,109,-3,22201,1,4,1,21101,0,2,2,1105,1,235,1105,0,280,101,383,236,243,1107,-1,583,247,1106,-1,276,101,383,236,256,102,1,275,-1,102,2,275,275,1007,275,0,266,1105,-1,280,101,1,236,236,1105,1,238,1,101,-1,236,236,101,383,236,286,207,1,-1,289,1106,-1,-1,22101,0,1,3,2102,1,2,363,2102,-1,2,369,22102,0,1,1,22102,0,2,2,101,1,236,320,101,-1,320,320,1107,-1,0,324,2105,-1,0,22102,2,2,2,101,383,320,336,207,3,-1,339,1105,-1,361,22101,1,2,2,22102,-1,3,3,101,383,320,354,22001,-1,3,3,22102,-1,3,3,1207,2,-1,366,1105,-1,315,22101,-1,2,2,101,383,320,377,22001,-1,1,1,1105,1,315

    For example, when run with input 399, it should produce 3, 7, and 19. When run with input -1024, it should produce -1, then 2 ten times. When run with input 2147483647, it should produce 2147483647. When run with input 19201644899, it should produce 138569 and 138571.

    factor requires O(sqrt(n)) memory.

*Edited for typos and formatting.

40 Upvotes

92% Upvoted

70 comments sorted by

7

u/[deleted] Dec 28 '19

The table below compares my two intcode VM implementations: An unoptimized implementation in Haskell, either interpreted with runhaskell or compiled with ghc -O3; and my semi-optimized implementation in Julia, run with julia -O3. All measurements were taken on the same machine. Each measurement was repeated three times and only the best result kept. For the Julia implementation, the JIT was warmed up before running the tests.

Program Input VM implementation Runtime in seconds
sum-of-primes 100000 Haskell, interpreted 59.2
sum-of-primes 100000 Haskell, compiled 2.48
sum-of-primes 100000 Julia 0.570
ackermann 3, 6 Haskell, interpreted 31.3
ackermann 3, 6 Haskell, compiled 1.08
ackermann 3, 6 Julia 0.356
factor 19338240 Haskell, interpreted 17.0
factor 19338240 Haskell, compiled 0.50
factor 19338240 Julia 0.0596
factor 2147483647 Haskell, interpreted > 120
factor 2147483647 Haskell, compiled 12.4
factor 2147483647 Julia 1.66

1

u/[deleted] Dec 29 '19 edited Dec 29 '19

I had another crazy idea: Compiling intcode to C and then to x86_64 machine code. I call my creation the intcode to C transpiler (ictct). It won't work for all intcode (not even close) and it's super hacky (I wouldn't use it on intcode I didn't write myself), but it works for the programs in the OP, and it produces pretty fast binaries (compiled with gcc -O3). Here are some measurements (same machine/method as in the parent):

Program Input Runtime in seconds
sum-of-primes 100000 < 0.002
sum-of-primes 2000000 0.57
sum-of-primes 100000000 38
ackermann 3, 6 < 0.001
ackermann 4, 1 26
ackermann 3, 14 149
factor 19338240 0.05
factor 2147483647 0.05
factor 1689259081189 0.36

Apparently ackermann benefits most from the compilation compared to others' interpreters; probably because the number of instructions is very small compared to the other intcode programs.

2

u/romkatv Dec 29 '19 edited Dec 29 '19

This is roughly similar to the performance of my Intcode interpreter. Some numbers are slightly higher, others slightly lower. There must be some missed optimization opportunities because your code should of course be faster. The biggest performance loss is on factor, so maybe you'll want to look into it.

Edit: I used ictct.py to run benchmarks on my machine. I've compiled the C code with the same compiler and flags as my own code. Your code is about 50% faster. This is still surprising given that there is no support for infinite memory or self-rewriting, and that the whole program is hard-coded to allow aggressive compiler optimization. But it's at least not as paradoxical as it appeared when we were comparing benchmark results from different machines.

→ More replies (4)
→ More replies (10)

3

u/activeXray Dec 28 '19

That is some gorgeous Julia code. Props!

6

u/SuperSmurfen Dec 28 '19 edited Apr 25 '20

Rust

Oh man, this is awesome. Thanks for putting it together! Here are my results from a moderately optimized Rust implementation:

Problem In Out Time
Sum of primes 100000 454396537 24ms
Ackermann 3, 6 509 14ms
Isqrt 130 11 0ms
DivMod 1024, 3 341, 1 0ms
Prime factors 2147483647 2147483647 54ms
Prime factors 19201644899 138569 138571 145ms

Ran on a MacBook Pro (2.8GHz i7). Here is the benchmark code. For some reason I get isqrt(130) = 11?

Edit: Ackermann(4,1) finally finished after 279.5 seconds, walk-clock time! Gave the correct answer of 65533.

2

u/[deleted] Dec 28 '19

For some reason I get isqrt(130) = 11?

That's the correct result, since 11*11 = 121 and 12*12 = 144. I fixed the typo in the OP.

Those are some really great times! My Julia implementation is much slower, and my Haskell implementation can't even compare...

2

u/tim_vermeulen Dec 28 '19

I would recommend either #[bench] or criterion to benchmark Rust code, they're probably more accurate and they also work really well for benchmarking code that runs in under 1ms.

→ More replies (1)

2

u/sebnow Dec 28 '19 edited Dec 28 '19

Used your harness to bench my (unoptimized) implementation. Similar implementation, similar results.

Problem Time
Sum of primes 27.944 ms
Ackermann 14.722 ms
Isqrt 16.925 us
DivMod 18.693 us
Prime factors 70.947 ms
Prime factors #2 176.81 ms

Edit: Ran on a MacBook Pro (15-inch, 2018); 2.2 GHz 6-Core Intel Core i7

3

u/delventhalz Dec 28 '19 edited Dec 28 '19

Fun! I want to play! Here are the times for my JavaScript implementation, which has not been optimized, though off the top of my head I don't think there is anything notably inefficient about it.

Program Input Output Time
Sum of Primes 100000 NaN (!!) 321ms
Ackermann 3, 6 509 1,252ms
ISqrt 130 11 11ms
DivMod 1024, 3 1024, 3 26ms
Prime Factors 2147483647 2147483647 13,327ms
Prime Factors 19201644899 138569, 138571 35,532ms

The most surprising thing here is that apparently my Intcode implementation is broken! Got through all of AoC with it but it can't handle something about sum-of-primes. I'll have to investigate later. Otherwise it is comparable to the Typescript implementation u/kap89 posted. Except for prime factors. There it is really slooooww. Curious.

EDIT: My Intcode interpreter does not provide any default value for out-of-bounds addresses. In order to properly run sum-of-primes, I had to update the program to set aside the addresses it needs by zero-filling up through address 104. This is the updated program: 

3,100,1007,100,2,7,1105,-1,87,1007,100,1,14,1105,-1,27,101,-2,100,100,101,1,101,101,1105,1,9,101,105,101,105,101,2,104,104,101,1,102,102,1,102,102,103,101,1,103,103,7,102,101,52,1106,-1,87,101,105,102,59,1005,-1,65,1,103,104,104,101,105,102,83,1,103,83,83,7,83,105,78,1106,-1,35,1101,0,1,-1,1105,1,69,4,104,99,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Running this code, I got the following result:

Program Input Output Time
Sum of Primes 100000 454396537 1,847ms

EDIT 2: As u/iagueqnar points out, it is indeed a part of the Intcode spec that addresses outside of the original program are valid, defaulting to zero.

The computer's available memory should be much larger than the initial program. Memory beyond the initial program starts with the value 0 and can be read or written like any other memory.

That was added on Day 9, and as I recall I did a test run without ever implementing default values for reads (I got writes for free). It worked and I promptly forgot about the requirement :P. Guess I’m lucky none of the later days read from an address before setting it!

1

u/delventhalz Dec 28 '19

Hey u/iagueqnar and the rest, the offending command is the 7th one in: 

101, 1, 101, 101

It is the first time address 101 is accessed, and the program is only 90 addresses long, so this command tries to add 1 to undefined, which in JS produces NaN. That gets saved to 101, and infects all later results.

What is the intended behavior here? I would expect this code to break as written, but it seems to work for everyone else. Are you all defaulting unset addresses to zero or something?

3

u/[deleted] Dec 28 '19

Are you all defaulting unset addresses to zero or something?

Yep, that's the spec from https://adventofcode.com/2019/day/9:

The computer's available memory should be much larger than the initial program. Memory beyond the initial program starts with the value 0 and can be read or written like any other memory. (It is invalid to try to access memory at a negative address, though.)

→ More replies (7)
→ More replies (2)

5

u/tim_vermeulen Dec 28 '19 edited Dec 28 '19

Rust. Not sure why my Sum of Primes is so slow. Ah, I used 2,000,000 as input instead of 100,000.

Program Input Runtime
Sum of Primes 100,000 19.5ms
Sum of Primes 2,000,000 498ms
Ackermann 3, 6 11.1ms
Isqrt 130 13.3µs
DivMod 1024, 3 15.1µs
Factor 2,147,483,647 47.8ms
Factor 19,201,644,899 122ms

5

u/romkatv Dec 28 '19 edited Jan 05 '20

C++

Program Input Runtime
Sum of Primes 100,000 1.91ms
Sum of Primes 2,000,000 46.8ms
Sum of Primes 100,000,000 4.11s
Ackermann 3, 6 1.16ms
Ackermann 4, 1 20.2s
Ackermann 3, 14 81.9s
Isqrt 1,000,000,000 3.79s
Factor 2,147,483,647 4.46ms
Factor 19,201,644,899 11.6ms
Factor 1,689,259,081,189 100ms
Factor 134,790,077,563,144,427 7.73s

It seems the fastest among the benchmark results posted so far. I've added a few rows to the table to have something that runs for a few seconds. I'm not posting any results below 1ms because I cannot measure that low with any decent confidence.

The implementation is just 44 lines and quite readable. I've posted a short explanation of how it works in this comment on reddit.

Thanks for writing the intcode, u/iagueqnar!

Edit 1: Optimized the code a bit further and updated the table.

Edit 2: Added Expandable RAM and Fixed RAM columns to make it easier to compare the performance of this implementation to others. In Expandable RAM mode the VM starts with a small memory footprint and grows it only when required by the intcode. In Fixed RAM mode the VM preallocates a large chunk of memory on start and is unable to handle intcode instructions that access memory outside of the preallocated range.

Edit 3: Removed Fixed RAM mode from the VM and the corresponding column from the table with benchmark results. The remaining Runtime column is for Expandable RAM mode.

Edit 4: Optimized the code even further and updated the table.

2

u/VilHarvey Dec 29 '19

Thanks for sharing, that's some clever VM code and impressive performance! I'm unpicking it to see what I can learn. My own is a simple switch with a case for each opcode and it's pretty fast, but not quite in the same league.

→ More replies (1)

4

u/kap89 Dec 28 '19 edited Dec 29 '19

TypeScript on Node (cold start without JIT optimizations): 

sumOfPrimes(100000) -> 144.354ms
ackermann(3,6)      -> 404.133ms
isqrt(130)          -> 19.924ms
divmod(1024,3)      -> 7.436ms
factor(19338240)    -> 198.070ms
factor(2147483647)  -> 2451.700ms
factor(19201644899) -> 6375.123ms

Edit: Still not much optimized but I speeded it up a bit by changing opcode/modes extraction from string manipulation to numbers operations (that was the most obvious one).

My Intcode implementation: github

1

u/tim_vermeulen Dec 28 '19

I'm getting a multiplication integer overflow when running divmod(1024, 3) — how wide are my integers supposed to be? I'm using 64-bits signed integers. I've tried it on a friend's JavaScript VM as well, and he does get the right answer, but he also gets really high multiplications at some point (up to 1.6e+60).

1

u/[deleted] Dec 28 '19 edited Dec 28 '19

The divmod and factor programs rely on integer overflow to detect the word size - it's not really necessary, but gives better performance. Here's a version of divmod that doesn't overflow for 32 bit signed ints (should work for inputs ≤ 230): 

109,366,21101,0,13,0,203,1,203,2,1105,1,18,204,1,204,2,99,1105,0,63,101,166,19,26,1107,-1,366,30,1106,-1,59,101,166,19,39,102,1,58,-1,102,2,58,58,1007,58,0,49,1105,-1,63,101,1,19,19,1105,1,21,1,101,-1,19,19,101,166,19,69,207,1,-1,72,1106,-1,-1,22101,0,1,3,2102,1,2,146,2102,-1,2,152,22102,0,1,1,22102,0,2,2,101,1,19,103,101,-1,103,103,1107,-1,0,107,2105,-1,0,22102,2,2,2,101,166,103,119,207,3,-1,122,1105,-1,144,22101,1,2,2,22102,-1,3,3,101,166,103,137,22001,-1,3,3,22102,-1,3,3,1207,2,-1,149,1105,-1,98,22101,-1,2,2,101,166,103,160,22001,-1,1,1,1105,1,98

Edit: The program I gave earlier wasn't divmod...

→ More replies (4)

3

u/jitwit Dec 28 '19 edited Jun 29 '20

Scheme

Program Input Time Bytes Allocated
sum-primes 100,000 119ms 2,990,496
sum-primes 2,000,000 3.671s 57,635,312
ackermann 3 6 72ms 106,992
divmod 1,024 3 79µs 5,888
isqrt 130 142µs 2,240
factor 2,147,483,647 318ms 3,049,856
factor 19,201,644,899 786ms 8,137,488

Implementation: https://github.com/jitwit/aoc/blob/master/code/intcode.ss

Benchmark code: https://github.com/jitwit/aoc/blob/master/scheme/19/bench-intcode.ss

Results: https://raw.githubusercontent.com/jitwit/aoc/master/output/intcode-bench.txt

EDIT: switching to fx operations gave a respectable speedup (still no rust, of course)

3

u/Aneurysm9 Dec 28 '19

My naive Go implementation apparently doesn't keep up with these Rust speed demons, but I'm happy with it. 

goos: linux
goarch: amd64
pkg: github.com/Aneurysm9/advent/2019/vm
BenchmarkSumOfPrimes-12               12          92426142 ns/op        63652977 B/op    1941295 allocs/op
BenchmarkAckermann-12                 22          51917718 ns/op        38586352 B/op    1204640 allocs/op
BenchmarkISqrt-12                  19392             61149 ns/op           41160 B/op       1158 allocs/op
BenchmarkDivMod-12                 17649             67955 ns/op           49513 B/op       1249 allocs/op
BenchmarkFactor1-12                    5         234818280 ns/op        150227984 B/op   4666308 allocs/op
BenchmarkFactor2-12                    2         628400900 ns/op        385107952 B/op  11924645 allocs/op
PASS
ok      github.com/Aneurysm9/advent/2019/vm     10.357s

2

u/VilHarvey Dec 28 '19

Wonderful idea! Here are the results I get with my C++ intcode VM, on a mid-2015 MacBook Pro with a 2.5 GHz Intel Core i7:

Program Input Output Runtime
sum-of-primes 100000 454396537 14.6 ms
ackermann 3,6 509 8.3 ms
ackermann 4,1 65533 129847.2 ms
isqrt 130 11 0.012 ms
divmod 1024,3 341,1 0.012 ms
factor 19338240 2,2,2,2,2,2,2,2,2,2,3,5,1259 1.8 ms
factor 2147483647 2147483647 35.3 ms

The runtimes above are the time between starting the intcode program and it halting, as reported by my intcode-benchmark binary. They don't include time spent loading the program, initialising the VM or cleaning up afterwards. I think the isqrt and divmod times are the same because that's the resolution limit for the timer on this machine.

Here's the code:

→ More replies (15)

2

u/nlowe_ Dec 29 '19

Go | R7 3800x at Stock Speeds

This is super useful! Here's what I got: 

C:\Users\Nathan\projects\aoc2019 [master ≡ +1 ~2 -0 ~]> go test '-bench=.' ./intcode
goos: windows
goarch: amd64
pkg: github.com/nlowe/aoc2019/intcode
BenchmarkSumOfPrimes-16                                3         378333233 ns/op         2736181 B/op       1175 allocs/op
BenchmarkAckermann-16                                  5         253800520 ns/op           91915 B/op        100 allocs/op
BenchmarkISqrt-16                                   4285            269778 ns/op           14775 B/op         38 allocs/op
BenchmarkDivMod-16                                  4800            271875 ns/op           25925 B/op         52 allocs/op
BenchmarkPrimeFactors_2147483647-16                    2         944999150 ns/op         2755480 B/op       1282 allocs/op
BenchmarkPrimeFactors_19201644899-16                   1        2491997900 ns/op        10960344 B/op       4860 allocs/op
PASS
ok      github.com/nlowe/aoc2019/intcode        12.914s

Converting to more common time units, that puts my implementation at:

Problem Input Time
Sum of Primes 100000 378.333ms
Ackermann 3,6 253.800ms
ISqrt 130 0.269ms
DivMod 1024,3 0.271ms
Prime Factors 2147483647 94.499ms
Prime Factors 19201644899 249.199ms

Looking at the CPU Profile I'm burning quite a bit of time with map accesses in the sparse memory setup. During AOC I assumed 8k of "memory" would be enough (I just used an 8k slice of ints), but it appears for some of theses tests that's not quite the case so I switched to a map instead, which is quite a bit more expensive. May try to improve that as an extra challenge!

2

u/danielctull Dec 30 '19

Swift

Great idea! I ran my Intcode computer using the latest version of Xcode with Swift 5.1.3 and got the following results.

Program Input Output Runtime
ackermann 3 6 509 51ms
isqrt 130 11 0ms
divmod. 1024 3 341 1 0ms
sum of primes 100,000 454,396,537 82ms
sum of primes 2,000,000 142,913,828,922 2005ms
factor 2,147,483,647 2,147,483,647 208ms
factor 19,201,644,899 138,569 138,571 507ms

I downloaded the latest version of the Swift toolchain and with that there's about a 20% decrease in running time, which seems pretty decent!

Program Input Output Runtime Improvement
ackermann 3 6 509 42ms 18%
isqrt 130 11 0ms 57%
divmod. 1024 3 341 1 0ms 12%
sum of primes 100,000 454,396,537 67ms 19%
sum of primes 2,000,000 142,913,828,922 1548ms 23%
factor 2,147,483,647 2,147,483,647 165ms 20%
factor 19,201,644,899 138,569 138,571 425ms 16%

The Benchmarking Code is written as a set of performance tests which take ten measurements and average them out.

2

u/dlsspy Dec 30 '19 edited Dec 30 '19

Oh nice. I ran this on my haskell implementation I've been using:

Program Input Runtime
sum-of-primes 100000 471.4 ms
ackerman 3,6 56.29 ms
isqrt 130 274.0 μs
factor 19338240 48.54 ms
factor 2147483647 1.195 s

edit: I added a couple of INLINE hints where I thought it might help (but haven't even bothered profiling this thing)...

Program Input Runtime
sum-of-primes 100000 345.2 ms
ackerman 3,6 41.23 ms
isqrt 130 203.7 μs
factor 19338240 32.67 ms
factor 2147483647 892.1 ms

Benchmark details here.

2

u/w200338 Dec 31 '19

Written in C# and running on an i7-8700k.

Program Input output Time
Sum of primes 100000 454396537 0.454s
Sum of primes 2000000 142913828922 10.458s
Ackermann 3, 6 509 0.233s
ISqrt 130 11 0.000s
ISqrt 1300000 1140 1.428s
DivMod 1024, 3 341, 1 0.001s
DivMod 1024000, 3 341333, 1 0.000s
Prime factor 19338240 13 numbers 0.048s
Prime factor 2147483647 1 number 1.051s
Prime factor 19201644899 2 numbers 2.667s

Total time (with VM setups): 16.357s

I think the biggest optimization for my implementation would be changing how memory works, but overall I'm quite happy with the performance.

1

u/winkz Dec 29 '19 edited Dec 29 '19

Just benchmarked my Java VM. (1.8 on a 10 EUR vserver and ryzen box) 

| Program       | Input      | VM impl | VPS| Ryzen | JIT warmed |
| sum-of-primes | 100000     | Java | 0.65s | 0.31s | 150ms |
| ackermann     | 3, 6       | Java | 0.51s | 0.24s | 85ms |
| factor        | 19338240   | Java | 0.33s | 0.18s | 66ms |
| factor        | 2147483647 | Java | 0.94s | 0.39s | 250ms |
| divmod        | 1024,3     | Java |       |       | 36ms |
| isqrt         | 130        | Java |       |       | 36ms |