# Rust / Julia Comparison Post

**URL:** <https://discourse.julialang.org/t/rust-julia-comparison-post/75403>\
**Category:** Performance\
**Tags:** rust\
**Created:** [January 29, 2022, 1:45am UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403 "2022-01-29T01:45:37Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 29, 2022, 4:41pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/21 "2022-01-29T16:41:10Z")

</div>

> [@stevengj](#):
>
> This is crazy, why are you using vectors of `Char` to work with strings?

Important observation: because the hot loops

```julia
constraint.letter ∉ word
constraint.letter ∈ word

```

seem to be way faster for `Vector{Char}` than for `String`. Quick example

```julia
julia> x = "salet"
"salet"

julia> @btime in('t', $x)
  14.930 ns (0 allocations: 0 bytes)
true

julia> x = Vector{Char}("salet")
5-element Vector{Char}:
 's': ASCII/Unicode U+0073 (category Ll: Letter, lowercase)
 'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
 'l': ASCII/Unicode U+006C (category Ll: Letter, lowercase)
 'e': ASCII/Unicode U+0065 (category Ll: Letter, lowercase)
 't': ASCII/Unicode U+0074 (category Ll: Letter, lowercase)

julia> @btime in('t', $x)
  3.200 ns (0 allocations: 0 bytes)
true

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 29, 2022, 4:47pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/22 "2022-01-29T16:47:34Z")

</div>

> [@Seif\_Shebl](#):
>
> `GRanking guesses... 100/12972 words (20 min left) # Rust`

I wonder about this because the blog post of the original author mentions

```julia
$ time cargo run
Ranking guesses... 11/12972 words (441 min left)

```

---

<div class="post-metadata">

**Author:** ![Jake](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jake/32/46007_2.png) [@Jake](https://discourse.julialang.org/u/Jake)\
**Post date:** [January 29, 2022, 4:53pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/23 "2022-01-29T16:53:01Z")

</div>

> [@GunnarFarneback](#):
>
> I think the real morale of the story is to extend the title of the blog post,

And the other morale is “Discourse is a great place for optimization hints!”

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 29, 2022, 5:00pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/24 "2022-01-29T17:00:05Z")

</div>

The blog post includes this edit:

> Edit: using `time cargo run --release` even brings it all the way down to 30 minutes!

which was explained with a bit more detail in [this HN comment](https://news.ycombinator.com/item?id=30123234):

> 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).

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [January 29, 2022, 5:12pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/25 "2022-01-29T17:12:26Z")

</div>

> [@Benny](#):
>
> cargo run --release

I use `cargo run --release` as pointed out by @Benny for fair comparison with Julia’s command line `julia -O3 --check-bounds=no`. BTW, the code by @Vasily_Pisarev is even better:

```julia
GRanking guesses... 100/12972 words (13 min left) # Julia 
GRanking guesses... 100/12972 words (20 min left) # Rust

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 29, 2022, 5:17pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/26 "2022-01-29T17:17:10Z")

</div>

Applying the `vcat` bug fix (which I missed completely) both serial and parallel implementation show for me

```julia
1. ['r', 'o', 'a', 't', 'e'] (keeps 60.42462203023758 words on average)
2. ['r', 'a', 'i', 's', 'e'] (keeps 61.00086393088553 words on average)
3. ['r', 'a', 'i', 'l', 'e'] (keeps 61.33088552915767 words on average)
4. ['s', 'o', 'a', 'r', 'e'] (keeps 62.30107991360691 words on average)
5. ['a', 'r', 'i', 's', 'e'] (keeps 63.72570194384449 words on average)
6. ['i', 'r', 'a', 't', 'e'] (keeps 63.7792656587473 words on average) 
7. ['o', 'r', 'a', 't', 'e'] (keeps 63.89071274298056 words on average)
8. ['a', 'r', 'i', 'e', 'l'] (keeps 65.28768898488121 words on average)
9. ['a', 'r', 'o', 's', 'e'] (keeps 66.02116630669546 words on average)
10. ['r', 'a', 'i', 'n', 'e'] (keeps 67.0561555075594 words on average)

```

This seems slightly off compared to [The best strategies for Wordle - Things (various)](http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle).

@Vasily_Pisarev: your implementation also yields

```julia
1. roate (keeps 60.42462203023758 words on average)
2. raise (keeps 61.00086393088553 words on average)
3. raile (keeps 61.33088552915767 words on average)
4. soare (keeps 62.30107991360691 words on average)
5. arise (keeps 63.72570194384449 words on average)
6. irate (keeps 63.7792656587473 words on average)
7. orate (keeps 63.89071274298056 words on average)
8. ariel (keeps 65.28768898488121 words on average)
9. arose (keeps 66.02116630669546 words on average)
10. raine (keeps 67.0561555075594 words on average)

```

for me. Are my word lists broken?

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [January 29, 2022, 5:40pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/27 "2022-01-29T17:40:03Z")

</div>

No, the lists are fine. The algorithm on the page you reference should find the globally-optimal solution. The algorithm linked in OP uses the greedy approach, i.e. just finds at each step the word that narrows the search the most.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [January 29, 2022, 5:58pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/28 "2022-01-29T17:58:20Z")

</div>

I would suggest making a PR to author’s code and maybe we will see them make an edit/update in the blog post too

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 29, 2022, 6:02pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/29 "2022-01-29T18:02:35Z")

</div>

> [@Seif\_Shebl](#):
>
> That said, I still second the suggestion by @GunnarFarneback to use an `SVector` and redesign the whole code if one desires speed.

No big redesign necessary, simply replacing does most of the trick.

> [@Seif\_Shebl](#):
>
> `GRanking guesses... 100/12972 words (13 min left) # Julia `

Here is my current best using `ThreadX` and `StaticArrays`…

```julia
using StaticArrays
using ThreadsX

function _readline(path)::SVector{5, Char}
  word = readline(path)
  SVector{5, Char}(word...)
end
function _readlines(path)::Vector{SVector{5, Char}}
  words = Vector{SVector{5, Char}}()
  for word in readlines(path)
      push!(words, SVector{5, Char}(word...))
  end
  println(length(words))
  words
end

const words = _readlines("solutions.txt")
const non_solution_words = _readlines("non-solution-guesses.txt")
const allowed_guesses = vcat(words, non_solution_words)

@enum ConstraintType has_no has_but_not_at has_at
struct Constraint
  type::ConstraintType
  letter::Char
  index::Int
end

function isequal(c0::ConstraintType, c1::ConstraintType)::Bool
  c0.type == c1.type && c0.letter == c1.letter && (c0.type == has_no || c0.index == c1.index)
end

function hash(c::ConstraintType, h::UInt = 0)::UInt
  hash(c.type, h) ⊻ hash(c.letter, h ⊻ 1) ⊻ hash(c.index, h ⊻ 2)
end

function constraints(guess::SVector{5, Char}, actual::SVector{5, Char})::Vector{Constraint}
  c = Vector{Constraint}()
  for (i, g, a) in zip(1:5, guess, actual)
    if g == a
      push!(c, Constraint(has_at, g, i))
    elseif g ∈ actual
      push!(c, Constraint(has_but_not_at, g, i))
    else
      push!(c, Constraint(has_no, g, i))
    end
  end
  c
end

# Code: . = has_no, x = has_but_not_at, o = has_at
function parse_constraints(template::SVector{5, Char}, guess::SVector{5, Char})::Vector{Constraint}
  constraints = Vector{Constraint}()
  for (i, c) in zip(1:5, template)
    if c == 'x'
      push!(constraints, Constraint(has_but_not_at, guess[i], i))
    elseif c == 'o'
      push!(constraints, Constraint(has_at, guess[i], i))
    else
      push!(constraints, Constraint(has_no, guess[i], i))
    end
  end
  constraints
end

function match_constraint(word::SVector{5, Char}, constraint::Constraint)::Bool
  if constraint.type == has_at
    word[constraint.index] == constraint.letter
  elseif constraint.type == has_no
    constraint.letter ∉ word
  elseif constraint.type == has_but_not_at
    (word[constraint.index] != constraint.letter) && (constraint.letter ∈ word)
  else
    @assert false
  end
end

# Average number of possible words left after performing a given guess,
# and receiving the corresponding constraint information.
function avg_remaining(guess::SVector{5, Char}, words::Vector{SVector{5, Char}})::Float64
  rem = ThreadsX.sum(words) do wo
    cs = constraints(guess, wo)
    sum(words) do wi
      all(cs) do c
        match_constraint(wi, c)
      end ? 1 : 0
    end
  end
  rem / length(words)
end

struct Choice
  word::SVector{5, Char}
  avg_remaining::Float64
end

function rank_guesses(guesses::Vector{SVector{5, Char}}, words::Vector{SVector{5, Char}})::Vector{Choice}
  wt = length(guesses)
  avg_time = 0
  choices = Vector{Choice}(undef, wt)
  for (wi, g) in zip(0:wt-1, guesses)
    print("\x1b[1K\x1b[GRanking guesses... ", wi, "/", wt, " words (", Int(ceil(avg_time*(wt-wi)/60)), " min left)")
    avg_time = (wi*avg_time + @elapsed choices[wi+1] = Choice(g, avg_remaining(g, words))) / (wi+1)
  end
  print("\x1b[1K\x1b[G")
  sort!(choices, by = c -> c.avg_remaining)
end

function main()
  global words; global allowed_guesses
  remaining_words = copy(words) # List of words that currently fit all known constraints.
  while length(remaining_words) > 1
    best_guesses = rank_guesses(allowed_guesses, remaining_words)[1:10]
    for (i, g) in zip(1:10, best_guesses)
      println(i, ". ", g.word, " (keeps ", g.avg_remaining, " words on average)")
    end
    println("Insert your guess: ")
    guess = _readline(stdin)
    println("Insert the results (o = letter at right spot, x = wrong spot, . = not in the word): ")
    constraint_template = _readline(stdin)
    remaining_words = filter(w -> match_constraints(w, parse_constraints(constraint_template, guess)), remaining_words)
  end
  println("Solution: ", remaining_words[1], ".")
end

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 29, 2022, 6:04pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/30 "2022-01-29T18:04:26Z")

</div>

> [@Benny](#):
>
> I’m not exactly sure what the Julia equivalents would be

Did a bit of reading on Rust `String`s and turns out they are also mutable, or at least growable (couldn’t find an example of explicitly in-place-mutating an index). If the Rust version doesn’t mutate `String`s, Julia’s immutable `String`s might be a fair analogue just for being heap-allocated UTF-8 structures.

(Also all those `mut` keywords don’t specify the object as mutable, but rather [the variable](https://www.snoyman.com/blog/2020/05/no-mutable-parameters-in-rust/). In a way, Julia’s variables are `mut` if reassigned. Low-level is very cool, if quite a bit more complicated to wrap my head around.)

---

<div class="post-metadata">

**Author:** ![tk3369](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tk3369/32/2824_2.png) [@tk3369](https://discourse.julialang.org/u/tk3369)\
**Post date:** [January 29, 2022, 6:26pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/31 "2022-01-29T18:26:55Z")

</div>

Might as well invite the author here 😛

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [January 29, 2022, 6:44pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/32 "2022-01-29T18:44:48Z")

</div>

That would make a huge speedup (4 cores and 8 threads cpu):

```julia
GRanking guesses... 100/12972 words (3 min left) # Julia multithreaded

```

But since only a single-threaded Rust version was available, people here were concerned more with fixing the single-threaded code.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 29, 2022, 8:41pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/33 "2022-01-29T20:41:45Z")

</div>

> [@goerch](#):
>
> seem to be way faster for `Vector{Char}` than for `String` .

Seems like a missing optimization; there’s no inherent reason why this should be so, especially for an ASCII character where it is just a byte search (`memchr`). [char in string is slow for short strings · Issue #43980 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/43980)

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [January 30, 2022, 9:02am UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/34 "2022-01-30T09:02:06Z")

</div>

Maybe I’m missing something, but to me it seems clear why the vector is faster: The string needs logic to determine the position of the next char, which both takes time, and inhibits instruction level parallelism.

You’re right that isn’t needed for ASCII strings, but how would the compiler know the string is ASCII? One solution would be to cache whether strings are ASCII somewhere in the struct, e.g. in the top bit of its length. I’d wager the majority of strings are ASCII, so that could be a big deal for speed

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [January 30, 2022, 1:24pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/35 "2022-01-30T13:24:39Z")

</div>

> [@jakobnissen](#):
>
> The string needs logic to determine the position of the next char

No — because of the way UTF-8 works, you don’t actually need to decode characters in order to search for a character, especially an ASCII character. You just need to search for a matching byte.

> [@jakobnissen](#):
>
> You’re right that isn’t needed for ASCII strings, but how would the compiler know the string is ASCII?

It doesn’t need to know. Because of the way UTF-8 works, to check if an ASCII character is in the string you just need to search for that byte in the string. So, you only need to check if the _character_ is `ASCII`.

More generally, to determine if _any_ character is in the string, you just need to search for that byte sequence in the string. And the way `Char` is encoded in Julia is that it actually stores the UTF-8 byte sequence in the `Char`.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [January 30, 2022, 2:14pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/36 "2022-01-30T14:14:44Z")

</div>

> [@Seif\_Shebl](#):
>
> But since only a single-threaded Rust version was available, people here were concerned more with fixing the single-threaded code.

OK, more ‘fixing’ of the serial code is possible: using memoization (like the original poster already tried?)

```julia
function rank_guesses(guesses::Vector{SVector{5, Char}}, words::Vector{SVector{5, Char}})::Vector{Choice}
  wt = length(guesses)
  avg_time = 0
  memo = Dict()
  choices = Vector{Choice}(undef, wt)
  for (wi, guess) in enumerate(guesses)
    rem = 0
    time = @elapsed for actual in words
      cs = constraints(guess, actual)
      if !haskey(memo, cs)
        rem_cs = 0
        for w in words
          rem_cs += match_constraints(w, cs) ? 1.0 : 0.0
        end
        memo[cs] = rem_cs
      end
      rem += memo[cs]
    end
    choices[wi] = Choice(guess, rem / length(words))
    print("\x1b[1K\x1b[GRanking guesses... ", wi, "/", wt, " words (", Int(ceil(avg_time*(wt-wi)/60)), " min left)")
    avg_time = (wi*avg_time + time) / (wi+1)
  end
  print("\x1b[1K\x1b[G")
  sort!(choices, by = c -> c.avg_remaining)
end

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 30, 2022, 4:44pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/37 "2022-01-30T16:44:50Z")

</div>

@Vasily_Pisarev’s [pull request](https://github.com/espadrine/optimal-wordle/pull/1) (with a very good explanation of the changes) was merged, and [the original blog post](https://espadrine.github.io/blog/posts/sometimes-rewriting-in-another-language-works.html#Pessimism_is_healthy_too) was updated to explain the effects. @GunnarFarneback’s `vcat` fix alone reportedly brought it down from the ~17 days (~416 hours) down to 4 hours. 104x is a much bigger effect than people in this thread have reported, so I’m guessing that wasn’t the only quick change (maybe de-`global`-ing?). The full revision ran for the poster in 20 minutes (12x from 4 hours, 1248x from 17 days).

My remaining questions on this topic:

1. how can the Rust version (30 minutes with compiler optimizations via `cargo run --release`) be so performant without the type optimizations described in section III of the pull request? The Rust version uses heap-allocated strings and views on them. There are certainly places where the original Julia version did extraneous allocations to iterate over `String`s, but maybe there’s an actual performance discrepancy between the language’s strings?

2. I’m not exactly sure where the `remaining_for_constraint` memoization method is used in any of the versions. It was mentioned in the pull request, so I assumed it was important at first. The only line calling it in the original Julia version is in the `remaining` method, but it’s commented out entirely. The original Rust version doesn’t have it at all. The revised Julia version makes the memoization dictionary `const` but there is no longer any line calling `remaining_for_constraint`.

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [January 30, 2022, 4:48pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/38 "2022-01-30T16:48:00Z")

</div>

> [@Benny](#):
>
> heap-allocated strings

Maybe because Rust has no GC to stop the world?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [January 30, 2022, 5:02pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/39 "2022-01-30T17:02:52Z")

</div>

The big thing that would be needed to get the Julia `String` version faster is [https://github.com/JuliaLang/julia/issues/43980](https://github.com/JuliaLang/julia/issues/43980) (gc improvements would also probably help)

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [January 30, 2022, 5:04pm UTC](https://discourse.julialang.org/t/rust-julia-comparison-post/75403/40 "2022-01-30T17:04:09Z")

</div>

I don’t doubt it has a nonzero effect, but the Rust version ran in 30 minutes. Given the reported 4 hours of the `vcat` fix, I hesitate to believe that the entire 3.5 hour discrepancy (87.5% of runtime) was spent on garbage collection, though I admit I don’t know the code well enough and have not profiled it to gauge how much allocation/deallocation is happening in each version.

[Previous page](https://discourse.julialang.org/t/rust-julia-comparison-post/75403.md?page=1)

[Next page](https://discourse.julialang.org/t/rust-julia-comparison-post/75403.md?page=3)