5 ms·

I don't know how to Rust, but you are welcome to try it. LuaJIT is amazingly fast. It shouldn't be faster than native code in general, but it's still not orders

I don't know how to Rust, but you are welcome to try it. LuaJIT is amazingly fast. It shouldn't be faster than native code in general, but it's still not orders of magnitude behind like interpreted languages are. As I understand it, JITs can sometimes do better by doing statistics on code paths and optimizing them. And of course, it takes 0 seconds to compile, if you factor in that time : )

eddyb 11y ago
LuaJIT 2.0.4: 3.67user 0.01system 0:03.68elapsed 99%CPU rustc 1.9.0-nightly (74b886ab1 2016-03-13) (-C opt-level=3): 5.18user 0.00system 0:05.20elapsed 99%CPU Switching to BTreeMap gives me: 4.36user 0.00system 0:04.38elapsed 99%CPU Using u8 as the key (last_digit0*10 + last_digit1) instead of a string: 4.18user 0.00system 0:04.18elapsed 99%CPU I tried preallocating the vector of primes and it didn't help, strangely enough. Replacing the floating-point sqrt with squaring in the comparison does bring it a bit lower: 4.04user 0.00system 0:04.05elapsed 99%CPU I don't know how to bring that number lower without using a sieve, perf reports that most of the time is spent in: 86,31 │ div %rbx I've also just noticed that the Lua and the Rust code don't give the same results, but I can't easily tell why. Oh! The largest prime is 0x00ec4bab, so they can be stored as u32. Final Rust result: 2.33user 0.00system 0:02.33elapsed 99%CPU Code: https://gist.github.com/eddyb/51a92fa2edf20d6e23fe https://gist.github.com/eddyb/51a92fa2edf20d6e23fe
- Houshalter 11y ago
  Nice. I suppose I should try optimizing the Lua code some more. There are some nasty branches in there that might slow it down. The Lua code is not exactly identical to the rust code. I test all numbers less than n, as opposed to counting n primes. I set n so it got slightly more primes than the rust code though.

5 ms·

I don't know how to Rust, but you are welcome to try it. LuaJIT is amazingly fast. It shouldn't be faster than native code in general, but it's still not orders

by Houshalter 11y ago

eddyb 11y ago
LuaJIT 2.0.4: 3.67user 0.01system 0:03.68elapsed 99%CPU rustc 1.9.0-nightly (74b886ab1 2016-03-13) (-C opt-level=3): 5.18user 0.00system 0:05.20elapsed 99%CPU Switching to BTreeMap gives me: 4.36user 0.00system 0:04.38elapsed 99%CPU Using u8 as the key (last_digit0*10 + last_digit1) instead of a string: 4.18user 0.00system 0:04.18elapsed 99%CPU I tried preallocating the vector of primes and it didn't help, strangely enough. Replacing the floating-point sqrt with squaring in the comparison does bring it a bit lower: 4.04user 0.00system 0:04.05elapsed 99%CPU I don't know how to bring that number lower without using a sieve, perf reports that most of the time is spent in: 86,31 │ div %rbx I've also just noticed that the Lua and the Rust code don't give the same results, but I can't easily tell why. Oh! The largest prime is 0x00ec4bab, so they can be stored as u32. Final Rust result: 2.33user 0.00system 0:02.33elapsed 99%CPU Code: https://gist.github.com/eddyb/51a92fa2edf20d6e23fe https://gist.github.com/eddyb/51a92fa2edf20d6e23fe
- Houshalter 11y ago
  Nice. I suppose I should try optimizing the Lua code some more. There are some nasty branches in there that might slow it down. The Lua code is not exactly identical to the rust code. I test all numbers less than n, as opposed to counting n primes. I set n so it got slightly more primes than the rust code though.