# Best way to optimize code

**URL:** <https://discourse.julialang.org/t/best-way-to-optimize-code/37980>\
**Category:** Performance\
**Tags:** question\
**Created:** [April 21, 2020, 6:10pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980 "2020-04-21T18:10:00Z")\
**Posts on this page:** 10\
**Page:** 2

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 22, 2020, 6:22pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/21 "2020-04-22T18:22:57Z")

</div>

I haven’t checked this really well, but I think it should be close to correct:

```julia
function word_sim_alternative(τ, ω, μ)
    wordcount = 1
    for i in (τ+2):ω
        wordcount += (i * rand()) < (1-μ) * wordcount
    end
    return wordcount
end

```

---

<div class="post-metadata">

**Author:** ![jmaths](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jmaths/32/21240_2.png) [@jmaths](https://discourse.julialang.org/u/jmaths)\
**Post date:** [April 22, 2020, 7:43pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/22 "2020-04-22T19:43:43Z")

</div>

This is fantastic! I didn’t realise random number generation can effect speed so much.

---

<div class="post-metadata">

**Author:** ![jmaths](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jmaths/32/21240_2.png) [@jmaths](https://discourse.julialang.org/u/jmaths)\
**Post date:** [April 22, 2020, 7:44pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/23 "2020-04-22T19:44:40Z")

</div>

This is a really neat function. At some points I will need the entire array of words but in general this should be good for most of them. Thanks so much.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [April 22, 2020, 10:30pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/24 "2020-04-22T22:30:35Z")

</div>

> [@jmaths](#):
>
> This is fantastic! I didn’t realise random number generation can effect speed so much.

Still, my latest change to the program, with the help of that RNG package, more that doubles [EDIT: almost triples, if I recall old number] the speed (what is it on your faster machine?) on top of the best so far, and I think could be made better by avoiding converting (from int to float, in that package, and back) to int:

```julia
julia> using BenchmarkTools, ProfileView, VectorizedRNG # note,
# version v0.1.6, master version is broken, so use the released one
[Info: Precompiling VectorizedRNG [33b4df10-0173-11e9-2a0c-851a7edac40e]

rng = local_rng() 

julia> @btime begin
[..]
               pops[jj] = word_sim5(tau, omega, mu);
[..]
  63.522 ms (300002 allocations: 218.21 MiB)

@profview begin ... now shows the bottleneck moved

For:

julia> function word_sim5(tau::Int, omega::Int, mu::Float64)
                  # inserts a word in position (tau+1), at each point creates a new word with prob mu
                  # otherwise randomly chooses a previously used. Runs the program until time omega
                  words = Array{Int32}(undef, omega) # to store the words
                  tests = rand(local_rng(), omega) # will compare mu to these
                  words[1] = 1; # initialize the words
                  next_word = 2 # will be the next word used
                  words[tau+1] = omega + 1; # max possible word so insert that at time tau
                  rand0 = Vector{Float64}(undef, omega) # one extra element, by design
                  rand!(local_rng(), rand0) # precalc. float random numbers
                  @inbounds for i = 2:tau # simulate the process
                      if mu > tests[i] # innovate 
                          words[i] = next_word
                          next_word = next_word + 1
                      else # copy
                          words[i] = words[1 + floor(Int, rand0[i])]
                      end
                  end
                  # force the word we're interested in
                  @inbounds for i = (tau+2):omega
                      if mu > tests[i] # innovate 
                          words[i] = next_word
                          next_word = next_word + 1
                      else # copy
                          words[i] = words[1 + floor(Int, rand0[i])]
                      end
                  end
                  result = count(==(omega + 1), words) # count how many times our word occurred
                  return result
              end

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 22, 2020, 10:39pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/25 "2020-04-22T22:39:09Z")

</div>

> [@jmaths](#):
>
> At some points I will need the entire array of words

If that happens, it might be enough to just store the location indices of that word, and you still wouldn’t need those locations for the assignment of the next word.

> [@jmaths](#):
>
> but in general this should be good for most of them.

Great!

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [April 22, 2020, 11:30pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/26 "2020-04-22T23:30:16Z")

</div>

Am I not reading the profile right?

By now the single slowest line is “word\_sim5: line 4”, about 20%+ (but three rand lines combined, 5, 9 and 16, about 75% of the time).

Do the numbers for that line make sense (it seems already fast, and with “undef” should be O(1), as not initializing):

```julia
julia> @time words = Array{Int32}(undef, omega);
  0.000003 seconds (1 allocation: 496 bytes)

julia> omega = 100000
100000

julia> @time words = Array{Int32}(undef, omega);
  0.000008 seconds (2 allocations: 390.703 KiB)

julia> omega = 1000000000
1000000000

julia> @time words = Array{Int32}(undef, omega);
  0.012678 seconds (2 allocations: 3.725 GiB, 99.61% gc time)

julia> @time words = Array{Int32}(undef, omega);
  0.004373 seconds (2 allocations: 3.725 GiB, 99.06% gc time)

julia> @time words = Array{Int32}(undef, omega);
  0.047590 seconds (2 allocations: 3.725 GiB, 99.92% gc time)

```

For those extra test I did (unrelated to the program, really), I’m exercising the GC [with `@btime` I do see the same allocations, but “gc time” is gone, as it takes care of avoiding GC], but why? It seems I’m testing Clibs malloc, and it’s not O(1), even then why GC?

[Funny story, I have 128 GB in mem. so the computer is not swapping, I thought I had 12 GB, and was told, “that can’t be right, we didn’t give you only 12 GB”, I had never seen the + before in top so disregarded a digit cut off:

KiB Mem : 13182060+total, 10671788+free, 14977804 used, 10124916 buff/cache  
KiB Swap: 2097148 total, 2097148 free, 0 used. 11454323+avail Mem ]

---

<div class="post-metadata">

**Author:** ![jmaths](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jmaths/32/21240_2.png) [@jmaths](https://discourse.julialang.org/u/jmaths)\
**Post date:** [April 23, 2020, 10:21pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/27 "2020-04-23T22:21:24Z")

</div>

Wow, I’m hitting .9 seconds with this version (down from .26) really impressive. I’ll need to look into the VectorizedRNG package (does it have any of the previously mentioned bias issues for example)?

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [April 24, 2020, 2:36am UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/28 "2020-04-24T02:36:43Z")

</div>

> [@Palli](#):
>
> ooked a bit into what’s currently possible without the algorithm, at least if you can handle bias, and got more than twice the speed for the same range:

There’s an open issue for integer support. I’ll try and get around to adding it soon.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [April 24, 2020, 12:28pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/29 "2020-04-24T12:28:44Z")

</div>

> [@jmaths](#):
>
> I’ll need to look into the VectorizedRNG package (does it have any of the previously mentioned bias issues for example)?

I don’t think so, but note I wasn’t using it directly, I was however using a claimed non-biased workaround for speed of ranges. That package is based on the work here (what I recommended for new RNG in Julia, as `MersenneTwister()` is known to be slower): [http://prng.di.unimi.it/](http://prng.di.unimi.it/)

> [@Elrod](#):
>
> There’s an open issue for integer support. I’ll try and get around to adding it soon.

Yes, I added that issue, after looking into optimizing the program in this thread. I could make a PR based on the work I did here, to make simplifying the program here possible. But doing the int-\>float (your packages does) and back to int, wouldn’t be the best way, while could be optimized later. Then however you would get a different stream of random numbers. I guess you have no guarantee, so that’s ok.

Other package that DOES work for integers, and is faster ~~but last I checked surprisingly wasn’t faster~~ than Julia Base:

> **[GitHub - JuliaRandom/RandomNumbers.jl: Random Number Generators for the Julia...](https://github.com/JuliaRandom/RandomNumbers.jl)**
>
> Random Number Generators for the Julia Language. Contribute to JuliaRandom/RandomNumbers.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [May 21, 2020, 11:04pm UTC](https://discourse.julialang.org/t/best-way-to-optimize-code/37980/30 "2020-05-21T23:04:35Z")

</div>

Sorry, sonuru’s package is actually very fast, faster than Base. I made a timing mistake. I’m close the my best version here with that package, and only older version uses vectorization. I’m doing:

```julia
julia> using RandomNumbers.Xorshifts

julia> r = Xoroshiro128Plus();

```

And I’m not yet using, now merged in Julia 1.6-DEV:

> <https://github.com/JuliaLang/julia/pull/29240>
>
> Cf. https://arxiv.org/abs/1805.10941.
> Closes #20582, #29004.
> 
> This is still a…bout 30 percent slower than the "biased" solution (e.g. #28987), but as fast as the "best case" of the current version (when the range length is a power of 2). So this is strictly better, and should become the default version in a future (major) release. How do we make this available in the meantime? \`rand(Random.fast(a:b))\` is what the PR currently implements.

[Previous page](https://discourse.julialang.org/t/best-way-to-optimize-code/37980.md?page=1)