10 ms·

In a sibling answer, steveklabnik suggests the Rust version was compiled without optimizations - https://news.ycombinator.com/item?id=11285569 https://news.ycom

by eddyb 11y ago

In a sibling answer, steveklabnik suggests the Rust version was compiled without optimizations - https://news.ycombinator.com/item?id=11285569 https://news.ycombinator.com/item?id=11285569 Could you try running both on the same machine? I'm curious if LuaJIT can still beat Rust if both have optimizations working. I know it can beat native code sometimes, which is pretty impressive (it finds common cases and specializes to them AFAIK, almost like "sufficiently advanced optimizing compiler" fairy tales).

Houshalter 11y ago
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.
chucksmash 11y ago
He diagnosed it correctly - I was running debug builds instead of release builds. Shaves 80% off my 20 sec runtime without including any of the other optimizations he shared.
- eddyb 11y ago
  The hashing optimization isn't necessary as using String at all is wasteful - my code ended up being simpler, but in the end the largest gain came from replacing u64 with u32 - see https://news.ycombinator.com/item?id=11290955 https://news.ycombinator.com/item?id=11290955.

by eddyb 11y ago

Houshalter 11y ago

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.

chucksmash 11y ago

He diagnosed it correctly - I was running debug builds instead of release builds. Shaves 80% off my 20 sec runtime without including any of the other optimizations he shared.

eddyb 11y ago
The hashing optimization isn't necessary as using String at all is wasteful - my code ended up being simpler, but in the end the largest gain came from replacing u64 with u32 - see https://news.ycombinator.com/item?id=11290955 https://news.ycombinator.com/item?id=11290955.