7 ms·

Sometimes, rewriting in another language works

56 points by espadrine 5y ago

darksaints 5y ago
The comments about V8 don't resonate with me. Sure, V8 is pretty damn fast for a Javascript VM, but that's a really low bar considering how utterly unoptimizable Javascript is. Overall, I have a lot of trouble believing that javascript would be a reasonable contender here compared to Julia. Language semantics matter.
adgjlsfhk1 5y ago
The problem with the Julia version is just that it collects a word to a list of characters every time it calls match-constraint. Removing that one line makes the Julia version 5x faster. function match_constraint(word::String, constraint::Constraint)::Bool if constraint.type == has_no constraint.letter ∉ word elseif constraint.type == has_but_not_at (constraint.letter ∈ word) && (word[constraint.index] != constraint.letter) elseif constraint.type == has_at word[constraint.index] == constraint.letter end end This is also what the rust version does.
- Jtsummers 5y ago
  It does the same on line 22. But I'm not at a computer to see if addressing it there as well will have a comparable performance improvement.
  - adgjlsfhk1 5y ago
    That one doesn't matter nearly as much (I couldn't detect a performance difference). match_constraints isn't called nearly as frequently.
kibwen 5y ago
I'm amused that the author reached a satisfactory result of "only" 7 hours, just to later realize that they forgot to compile their Rust code with optimizations thus bringing the runtime down to 30 minutes. I've never used Julia, but unoptimized Rust binaries contain such naive and suboptimal codegen that I assume that something must have been wrong with their Julia code; my ballpark for the performance of unoptimized Rust code is that it's roughly on-par with interpreted (not JITted) Ruby or Python (parallelism notwithstanding, which even without optimizations bears much more fruit in Rust than in Ruby/Python). Still, at the same time, we can judge a language based on how easy it is to fall into the pit of success rather than the pit of failure; if their Julia code had a problem, then maybe the Julia developers could tweak some defaults (or change some documentation) so that people in the future do not fall afoul of the same result. The same sort of thing exists in Rust as well, where the fact that I/O is unbuffered by default makes it perform poorly in microbenchmarks that involve printing a zillion times in a loop: https://nnethercote.github.io/perf-book/io.html#buffering https://nnethercote.github.io/perf-book/io.html#buffering
- adgjlsfhk1 5y ago
  The biggest performance trap they had was copying all their strings in a really hot loop to a vector of characters. I'm not sure what we could do to steer people away from that...
  - deleted 5y ago
    [deleted]
- The_rationalist 5y ago
- udbhavs 5y ago
  Do you have any examples where unoptimized rust is in the ballpark of interpreted Python? That seems extremely slow even for carelessly written code.
  - deleted 5y ago
    [deleted]
  - kibwen 5y ago
    I've been teaching people to use Rust since 2011. It is quite common for someone coming from an interpreted language background to not realize that they have to manually ask for optimizations when building their code. In such circumstances they often come asking for help saying "I must be doing something wrong, I rewrote this Python code in Rust and it appears to be slower somehow?" For a long time on the /r/rust sidebar we even had a note saying "before asking for help, have you tried compiling with --release?" And indeed, once they turn on optimizations their code goes from as slow as Python to as fast as C. The OP's case is completely representative; a 14x improvement merely by compiling in release mode is entirely in line with what I have observed. This may be surprising to people coming from C or C++, where unoptimized code is slower but not that slow. But the point of Rust is that it's selectively provided as many zero-cost abstractions as it can, which when paired with a modern sufficiently-smart backend like LLVM boils away those abstractions into nothing. It's a great feeling the first time that you crack open the assembly output for a highly abstract chain of iterator/closure chains only to find that the whole shebang has been reduced to a handful of fixed-form arithmetic operations without a loop or a function call in sight. But the tradeoff is that you do have to perform the step of boiling those abstractions away.
trimbo 5y ago
> I felt I could rewrite it in Rust within two hours. I'm not sure what to conclude given the title of this post. Rewrites often improve things greatly. But a 2 hour time investment is not what anyone is talking about when they repeat mottos like "never rewrite."
- adgjlsfhk1 5y ago
  Also, this is especially funny since I found the change for the Julia version that makes it 5x faster in approximately the time it took me to read the code.
  - espadrine 5y ago
    That’s fair! It doesn’t go near the ballpark performance I was going after, though. It’s hard to assess to which extent the performance tweaking vs. rewriting tradeoff scales up. For a larger project, the rewrite could take a month; but maybe, diminishing returns helping, the performance tweaking would plateau short of a month.
    - kristofferc 5y ago
      https://discourse.julialang.org/t/rust-julia-comparison-post/75403/16?u=kristoffer.carlsson https://discourse.julialang.org/t/rust-julia-comparison-post... seems to be about 2x faster than the (optimized) Rust version with some minor tweaks to the Julia code so perhaps that is more in your ballpark?
      - espadrine 5y ago
        Absolutely, that is what I was hoping for! So, vcat() instead of append!(). Darn. Faith in Julia restored. I’ll update the article.
  - deleted 5y ago
    [deleted]
edflsafoiewq 5y ago
Changing it to operate on &[u8; 5] instead of &str knocks about 60% off the runtime.
planetis 5y ago
Nim is a better fit for scientific computing. Reason being excellent C interfacing and easy to learn syntax. Fast, lean executable and compile time is a factor too. There is a community page with available projects https://github.com/SciNim https://github.com/SciNim
bitwize 5y ago
I bet this guy really wants to know how to do it in Julia, and is just taking the "Linux sucks because you can't do X the way you can in Windows" route to getting the answer :)
- mcabbott 5y ago
  There is a discussion here: https://discourse.julialang.org/t/rust-julia-comparison-post/75403/19 https://discourse.julialang.org/t/rust-julia-comparison-post... So far, a bug fix improves it 4700 min -> 150 min, changing the type stored -> 20 min, further optimisations -> 15 min.
  - IshKebab 5y ago
    Ha, the best way to optimise your code is to post about how another language can do it faster.
tpoacher 5y ago
I like the ideas behind Julia, but the whole "Julia is performant" mantra without context has to stop. Non-optimally written julia code is as slow as non-optimally written code in any other language. Simply expecting code to be super optimised just because you wrote it in Julia instead of language X, and putting zero effort in taking advantage of Julia's advanced features that actually result in that optimality is just plain silly.
- jakobnissen 5y ago
  Obviously the meaning of "Julia is performant" is that Julia CAN be performant in a way that Python can't. Of course it doesn't mean Julia will write fast code for you, how could it possibly mean that? Edit: This is like saying people has to stop saying Ferraris are fast, because you can still drive slow in them
  - tpoacher 5y ago
    No it is not. It's like saying a Ferrari in third gear will be faster than a Fiat in third gear, because Ferrari. Clearly this is not the same as saying that "therefore a Ferrari is as good as a Fiat", because obviously Fiat only goes up to gear three whereas Ferrari goes up to 7. But chant the "Ferraris are always faster" mantra without this context, and eventually all but your most technical users will be the kind of user who sticks to the third gear that they're used to, and still expect a Ferrari to be fast. You want your Ferrari to go fast? Drive it like a Ferrari. Also, Python absolutely can be as performant as Julia, if not more. The point is that Julia has language-builtin features that were created with this performance in mind, whereas for Python you have to go explore the relevant package ecosystem and go down a numba/cython/pypy/etc route. And, yes, if you bragged how a Fiat could never beat your Ferrari in a race, and you agreed to race me against my modified Fiat with external turbo engines and I beat the crap out of your Ferrari, your "well that wasn't really a Fiat" complain would be valid, but only so much. Especially if Fiats were super-moddable by nature.
    - StefanKarpinski 5y ago
      Eagerly awaiting matrix libraries written in pure Python that outperform BLAS.

56 points by espadrine 5y ago

The comments about V8 don't resonate with me. Sure, V8 is pretty damn fast for a Javascript VM, but that's a really low bar considering how utterly unoptimizable Javascript is. Overall, I have a lot of trouble believing that javascript would be a reasonable contender here compared to Julia. Language semantics matter.

adgjlsfhk1 5y ago

The problem with the Julia version is just that it collects a word to a list of characters every time it calls match-constraint. Removing that one line makes the Julia version 5x faster. function match_constraint(word::String, constraint::Constraint)::Bool if constraint.type == has_no constraint.letter ∉ word elseif constraint.type == has_but_not_at (constraint.letter ∈ word) && (word[constraint.index] != constraint.letter) elseif constraint.type == has_at word[constraint.index] == constraint.letter end end This is also what the rust version does.

Jtsummers 5y ago
It does the same on line 22. But I'm not at a computer to see if addressing it there as well will have a comparable performance improvement.
- adgjlsfhk1 5y ago
  That one doesn't matter nearly as much (I couldn't detect a performance difference). match_constraints isn't called nearly as frequently.

kibwen 5y ago

I'm amused that the author reached a satisfactory result of "only" 7 hours, just to later realize that they forgot to compile their Rust code with optimizations thus bringing the runtime down to 30 minutes. I've never used Julia, but unoptimized Rust binaries contain such naive and suboptimal codegen that I assume that something must have been wrong with their Julia code; my ballpark for the performance of unoptimized Rust code is that it's roughly on-par with interpreted (not JITted) Ruby or Python (parallelism notwithstanding, which even without optimizations bears much more fruit in Rust than in Ruby/Python). Still, at the same time, we can judge a language based on how easy it is to fall into the pit of success rather than the pit of failure; if their Julia code had a problem, then maybe the Julia developers could tweak some defaults (or change some documentation) so that people in the future do not fall afoul of the same result. The same sort of thing exists in Rust as well, where the fact that I/O is unbuffered by default makes it perform poorly in microbenchmarks that involve printing a zillion times in a loop: https://nnethercote.github.io/perf-book/io.html#buffering https://nnethercote.github.io/perf-book/io.html#buffering

adgjlsfhk1 5y ago
The biggest performance trap they had was copying all their strings in a really hot loop to a vector of characters. I'm not sure what we could do to steer people away from that...
- deleted 5y ago
  [deleted]
The_rationalist 5y ago
udbhavs 5y ago
Do you have any examples where unoptimized rust is in the ballpark of interpreted Python? That seems extremely slow even for carelessly written code.
- deleted 5y ago
  [deleted]
- kibwen 5y ago
  I've been teaching people to use Rust since 2011. It is quite common for someone coming from an interpreted language background to not realize that they have to manually ask for optimizations when building their code. In such circumstances they often come asking for help saying "I must be doing something wrong, I rewrote this Python code in Rust and it appears to be slower somehow?" For a long time on the /r/rust sidebar we even had a note saying "before asking for help, have you tried compiling with --release?" And indeed, once they turn on optimizations their code goes from as slow as Python to as fast as C. The OP's case is completely representative; a 14x improvement merely by compiling in release mode is entirely in line with what I have observed. This may be surprising to people coming from C or C++, where unoptimized code is slower but not that slow. But the point of Rust is that it's selectively provided as many zero-cost abstractions as it can, which when paired with a modern sufficiently-smart backend like LLVM boils away those abstractions into nothing. It's a great feeling the first time that you crack open the assembly output for a highly abstract chain of iterator/closure chains only to find that the whole shebang has been reduced to a handful of fixed-form arithmetic operations without a loop or a function call in sight. But the tradeoff is that you do have to perform the step of boiling those abstractions away.

trimbo 5y ago

> I felt I could rewrite it in Rust within two hours. I'm not sure what to conclude given the title of this post. Rewrites often improve things greatly. But a 2 hour time investment is not what anyone is talking about when they repeat mottos like "never rewrite."

adgjlsfhk1 5y ago
Also, this is especially funny since I found the change for the Julia version that makes it 5x faster in approximately the time it took me to read the code.
- espadrine 5y ago
  That’s fair! It doesn’t go near the ballpark performance I was going after, though. It’s hard to assess to which extent the performance tweaking vs. rewriting tradeoff scales up. For a larger project, the rewrite could take a month; but maybe, diminishing returns helping, the performance tweaking would plateau short of a month.
  - kristofferc 5y ago
    https://discourse.julialang.org/t/rust-julia-comparison-post/75403/16?u=kristoffer.carlsson https://discourse.julialang.org/t/rust-julia-comparison-post... seems to be about 2x faster than the (optimized) Rust version with some minor tweaks to the Julia code so perhaps that is more in your ballpark?
    - espadrine 5y ago
      Absolutely, that is what I was hoping for! So, vcat() instead of append!(). Darn. Faith in Julia restored. I’ll update the article.
- deleted 5y ago
  [deleted]

edflsafoiewq 5y ago

Changing it to operate on &[u8; 5] instead of &str knocks about 60% off the runtime.

planetis 5y ago

Nim is a better fit for scientific computing. Reason being excellent C interfacing and easy to learn syntax. Fast, lean executable and compile time is a factor too. There is a community page with available projects https://github.com/SciNim https://github.com/SciNim

bitwize 5y ago

I bet this guy really wants to know how to do it in Julia, and is just taking the "Linux sucks because you can't do X the way you can in Windows" route to getting the answer :)

mcabbott 5y ago
There is a discussion here: https://discourse.julialang.org/t/rust-julia-comparison-post/75403/19 https://discourse.julialang.org/t/rust-julia-comparison-post... So far, a bug fix improves it 4700 min -> 150 min, changing the type stored -> 20 min, further optimisations -> 15 min.
- IshKebab 5y ago
  Ha, the best way to optimise your code is to post about how another language can do it faster.

tpoacher 5y ago

I like the ideas behind Julia, but the whole "Julia is performant" mantra without context has to stop. Non-optimally written julia code is as slow as non-optimally written code in any other language. Simply expecting code to be super optimised just because you wrote it in Julia instead of language X, and putting zero effort in taking advantage of Julia's advanced features that actually result in that optimality is just plain silly.

jakobnissen 5y ago
Obviously the meaning of "Julia is performant" is that Julia CAN be performant in a way that Python can't. Of course it doesn't mean Julia will write fast code for you, how could it possibly mean that? Edit: This is like saying people has to stop saying Ferraris are fast, because you can still drive slow in them
- tpoacher 5y ago
  No it is not. It's like saying a Ferrari in third gear will be faster than a Fiat in third gear, because Ferrari. Clearly this is not the same as saying that "therefore a Ferrari is as good as a Fiat", because obviously Fiat only goes up to gear three whereas Ferrari goes up to 7. But chant the "Ferraris are always faster" mantra without this context, and eventually all but your most technical users will be the kind of user who sticks to the third gear that they're used to, and still expect a Ferrari to be fast. You want your Ferrari to go fast? Drive it like a Ferrari. Also, Python absolutely can be as performant as Julia, if not more. The point is that Julia has language-builtin features that were created with this performance in mind, whereas for Python you have to go explore the relevant package ecosystem and go down a numba/cython/pypy/etc route. And, yes, if you bragged how a Fiat could never beat your Ferrari in a race, and you agreed to race me against my modified Fiat with external turbo engines and I beat the crap out of your Ferrari, your "well that wasn't really a Fiat" complain would be valid, but only so much. Especially if Fiats were super-moddable by nature.
  - StefanKarpinski 5y ago
    Eagerly awaiting matrix libraries written in pure Python that outperform BLAS.