# Funny Benchmark with Julia (no longer) at the bottom

**URL:** <https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611>\
**Category:** Performance\
**Tags:** benchmark\
**Created:** [October 5, 2023, 1:12pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611 "2023-10-05T13:12:30Z")\
**Posts on this page:** 20\
**Page:** 2

<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:** [October 8, 2023, 12:17pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/21 "2023-10-08T12:17:21Z")

</div>

[[julia] add comments, reduce getindex(), use MVector to speed up by Moelf · Pull Request #162 · jinyus/related\_post\_gen · GitHub](https://github.com/jinyus/related_post_gen/pull/162) I think `MVector` and not checking `if > ...` every single time with `getindex()` helped reduce runtime by 33%, I checked the output diff seems okay:

```julia
> diff related_posts_julia.json related_posts_julia_new.json

```

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [October 8, 2023, 12:21pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/22 "2023-10-08T12:21:15Z")

</div>

If I understand correctly, that finds the topn largest values in a list ? (edit: index of the ntop largest values)  
If so, you might look into this

> [@Find n smallest values in an n dims array](https://discourse.julialang.org/t/find-n-smallest-values-in-an-n-dims-array/81092/11):
>
> Thanks guys. This should be included somewhere in Julia

---

<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:** [October 8, 2023, 12:22pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/23 "2023-10-08T12:22:25Z")

</div>

we need the index of topn largest values in a list, which is precise `partialsortperm( ;rev=true)`, but it’s much slower

---

<div class="post-metadata">

**Author:** ![JM\_Beckers](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jm_beckers/32/22482_2.png) [@JM\_Beckers](https://discourse.julialang.org/u/JM_Beckers)\
**Post date:** [October 8, 2023, 12:30pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/24 "2023-10-08T12:30:28Z")

</div>

That is then exactly (?) what was discussed

> [@Find n smallest values in an n dims array](https://discourse.julialang.org/t/find-n-smallest-values-in-an-n-dims-array/81092/11):
>
> Thanks guys. This should be included somewhere in Julia

but for the minimum.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 8, 2023, 12:51pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/25 "2023-10-08T12:51:44Z")

</div>

> [@jling](#):
>
> `partialsortperm`

sortperm and friends are really slow in Julia [sortperm has poor performance · Issue #939 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/939)

Also, partialsort dispatches between partial-scratch-quicksort (good for long inputs) and insertionsort of the whole input (good for short inputs) but does not use partial-insertionsort (good for when the number of elements being searched for is small, asymptotically, when that number is less than log(length)).

---

<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:** [October 8, 2023, 2:34pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/26 "2023-10-08T14:34:52Z")

</div>

> <https://github.com/jinyus/related_post_gen/pull/163>
>
> This should significantly reduce the "total" time, which before was unfairly sho…wing the compilation time.
> 
> The native code caching was introduced in 1.9: https://julialang.org/blog/2023/04/julia-1.9-highlights/#caching\_of\_native\_code
> 
> \## this PR
> 
> \`\`\`
> Processing time (w/o IO): 24 milliseconds
> Time (mean ± σ): 407.2 ms ± 12.5 ms \[User: 430.0 ms, System: 338.5 ms\]
> Range (min … max): 394.0 ms … 431.2 ms 10 runs
> 
> Checking output
> Success: related\_posts\_julia.json is valid!
> \`\`\`

should make the second column (“total”) more reasonable, basically just put it into its own project and utilize some of those native code caching.

Locally it reduced ~3 seconds to about 400 ms

```julia
> hyperfine 'julia --startup-file=no --project=Related/ related.jl'
Benchmark 1: julia --startup-file=no --project=Related/ related.jl
  Time (mean ± σ): 407.2 ms ± 12.5 ms [User: 430.0 ms, System: 338.5 ms]
  Range (min … max): 394.0 ms … 431.2 ms 10 runs

```

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [October 8, 2023, 3:27pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/27 "2023-10-08T15:27:57Z")

</div>

Current results:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/1/f/1f1d07edd4d4097f950e39d6cceaa4a5509e8c6c.png)

The underlying data (used for the leaderboard) is changing from run to run, and it seems to affect the results regardless of underlying implementations.

For example, Zig was not updated in 4 days and jumped on top for the current run (the same implementation a day back did worse than Java - GraalVM).

Maybe a better way to optimize this is to use the random `post` generator and check the improvements by averaging the results of multiple randomly generated datasets.

Leaving the leaderboard aside - I find this kind of real-world benchmark more valuable than micro-benchmarking (although we can admit that we are not always comparing apples to apples here: because anybody is free to do whatever algorithmic tricks and end up with different implementations from language to language).

> [@jling](#):
>
> should make the second column (“total”) more reasonable, basically just put it into its own project and utilize some of those native code caching.
> 
> Locally it reduced ~3 seconds to about 400 ms

This was not merged yet - so it still has a large total time value.

---

<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:** [October 9, 2023, 10:57am UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/28 "2023-10-09T10:57:46Z")

</div>

this function has the funny property that if I add `@inbounds` it actually becomes slower (given we’re using `MVector` now)

---

<div class="post-metadata">

**Author:** ![aplavin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aplavin/32/222056_2.png) [@aplavin](https://discourse.julialang.org/u/aplavin)\
**Post date:** [October 9, 2023, 11:29am UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/29 "2023-10-09T11:29:45Z")

</div>

As an alternative to the highly-optimized solution built of manual loops, I’d like to propose a solution using higher-level data manipulation tools.  
It’s about 2x slower for me than the code in repo, but shorter and easier to understand what’s actually going on – once got used to each primitive.  
Uses NamedTuples instead of custom structs.

```julia
using DataManipulation, StructArrays

function related_2(posts_raw)
	# arguably the processing is more convenient with namedtuples instead of custom structures
	# converting here, but potentially this could be created when reading in the first place:
	posts = @p posts_raw |> map(Accessors.getproperties) |> StructArray |> @insert __.ix = eachindex(__)

	tagmap = @p let
		posts
		flatmap(_.tags, (p, tag) -> (; p.ix, tag))
		group(_.tag)
		map(map(x->x.ix, _))
	end

	nsharedtags = zeros(Int, length(posts))
	@p let
		posts
		map() do post
			nsharedtags .= 0
			for t in post.tags
				@views nsharedtags[tagmap[t]] .+= 1
			end
			nsharedtags[post.ix] = 0

			related = partialsort(posts, 1:5; by=p -> nsharedtags[p.ix], rev=true)
			(; post..., related)
		end
		collect
	end
end

# code above works without these definitions,
# but Base.partialsort is muuuch slower
using DataStructures: nlargest
partialsort(v, k; kwargs...) = partialsort(v, Base.OneTo(k); kwargs...)
partialsort(v, k::Base.OneTo; by, rev=false) = @p v |> nlargest(length(k), eachindex(__); by=i -> by(__[i])) |> map(v[_])

```

---

<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:** [October 9, 2023, 11:54am UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/30 "2023-10-09T11:54:34Z")

</div>

Julia went from last to the top (while no longer fastest). It’s not new that Julia can be optimized (and it’s neither as scalable in its now optimized version, as e.g. Go’s).

What I would be curious about, then know problem with unoptimized code, could that be optimized (i.e. by Julia improvements, no code changes to the code/benchmark)? I’m ok with it, since I know of it, but dynamic code is maybe slower than it needs to be? And at least possibly surprising to some (new users)?

It’s sort of good that unoptimized is not too fast… then people would “know”, or not. Unoptimized code can’t of course be made as fast, but what would be a reasonable margin?

---

<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:** [October 9, 2023, 12:09pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/31 "2023-10-09T12:09:12Z")

</div>

Do you mean like LitteDict? It’s often much faster, if your Dict is small. But note it’s O(n), why not the default (I think that might though be ok for Julia itself, i.e. what does Julia need when e.g. compiling?).

I did think up a hybrid, LittleDict + regular, I or someone should implement, then it’s back to O(1), first scanning a limited n for LittleDict before the fallback. I could be ok for Base, or not…

> [@Ordered Dict in Base: Is LittleDict not thread safe, and possibly the reason I can't add it to Base?](https://discourse.julialang.org/t/ordered-dict-in-base-is-littledict-not-thread-safe-and-possibly-the-reason-i-cant-add-it-to-base/47372/4):
>
> Also note that LittleDict has O(n) lookup cost compared to O(1) for the current Dict implementation. This means hat if the collection isn’t super small, LittleDict will perform much, much worse than the current implementation. For dicts that are small, Base already has ImmutableDict, which has similar performance characteristics for lookup as LittleDict, so places where you would really see a benefit of using LittleDict should already be using ImmutableDict instead of Dict.

> [@algunion](#):
>
> The [`Dictionaries.jl`](https://github.com/andyferris/Dictionaries.jl) supports a size hint, but in the current scenario, seems slower than the native implementation.

That’s not the same, it seems then, though I guess helpful for something.

---

<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:** [October 9, 2023, 12:20pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/32 "2023-10-09T12:20:30Z")

</div>

> [@Lilith](#):
>
> sortperm and friends are really slow in Julia

Are they, and would this PermFast here, help in this case:

> <https://github.com/JuliaLang/julia/pull/47587>
>
> This is a draft on how to speed up \`permsort\`. The idea is that it is not necess…ary to maintain the stability by \`Perm\` if a stable sorting algorithm is used. Thus \`PermUnstable\` is introduces with a simplify and faster \`lt(p::PermUnstable, a::Integer, b::Integer)\` implementation.
> 
> Notice the PR builds upon #47383 that has not been merged yet. 
> 
> @LilithHafner Do you like this idea (as the original author of the changes)?
> 
> \`\`\`julia
> julia\> using BenchmarkTools
> 
> \#47383
> julia\> @btime sortperm(x) setup=(x=rand(1000));
> 29.741 μs (5 allocations: 15.92 KiB)
> 
> \# This PR
> julia\> @btime sortperm(x) setup=(x=rand(1000));
> 23.349 μs (5 allocations: 15.92 KiB)
> \`\`\`

The issue you linked was closed in 2022, since “greatly improved”, then reopened again (otherwise incredible that a 2012 issue was still open).

---

<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:** [October 9, 2023, 12:24pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/33 "2023-10-09T12:24:20Z")

</div>

> [@algunion](#):
>
> ```julia
> function fastmaxindex!(xs::Vector{Int}, topn, maxn, maxv)
> maxn .= 1
> maxv .= 0
> for (i, x) in enumerate(xs)
> if x > maxv[1]
> maxv[1] = x
> maxn[1] = i
> for j in 2:topn
> if maxv[j-1] > maxv[j]
> maxv[j-1], maxv[j] = maxv[j], maxv[j-1]
> maxn[j-1], maxn[j] = maxn[j], maxn[j-1]
> end
> end
> end
> end
> 
> reverse!(maxn)
> 
> return maxn
> end
> 
> ```

I tried some other approach, especially the one Go-lang took, which is too insert at the correct location instead of doing the `maxv[j-1], maxv[j]` dance every time there’s a new top 5 candidate:

```julia
function fastmaxindex!(xs::Vector{Int64}, topn, maxn, maxv)
    maxn .= 1
    maxv .= _min = 0
    for (i, x) in enumerate(xs)
        x <= _min && continue

        pos = findfirst(<(x), maxv)

        for j in pos+1:4
            maxv[j+1] = maxv[j]
            maxn[j+1] = maxn[j]
        end
        maxv[pos] = x
        maxn[pos] = i
        _min = last(maxv)
    end

    return maxn
end

```

unfortunately this is slower than yours

---

<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:** [October 9, 2023, 12:25pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/34 "2023-10-09T12:25:15Z")

</div>

> [@Palli](#):
>
> LitteDict

what is this? I can’t find anything in Julia that has this name

---

<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:** [October 9, 2023, 12:27pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/35 "2023-10-09T12:27:05Z")

</div>

> [@algunion](#):
>
> ```julia
> for j in 2:topn
> if maxv[j-1] > maxv[j]
> maxv[j-1], maxv[j] = maxv[j], maxv[j-1]
> maxn[j-1], maxn[j] = maxn[j], maxn[j-1]
> end
> 
> ```

Given we’re operating on small (size = 5) `MVector`, I also tried to unroll this via `Base.@nexpr`, but that make things slower again

---

<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:** [October 9, 2023, 12:28pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/36 "2023-10-09T12:28:54Z")

</div>

It’s actually in OrderedCollections.jl (and thus also in DataStructures.jl, since it includes and adds to it), so that may be all you need, a faster dependency, ~~at least at one point~~.

It’s still faster to import/use:

```julia
julia> @time import OrderedCollections
  0.020884 seconds (21.83 k allocations: 1.599 MiB)

julia> @time using DataStructures
  0.109690 seconds (55.32 k allocations: 4.020 MiB)

```

Both are then slower still if you use `using` rather than `import`, not something I’ve considered before. So I’ll use import from now on, unless people think you make of for it later somehow if you use using…

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [October 9, 2023, 12:32pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/37 "2023-10-09T12:32:47Z")

</div>

@Palli, I would say that the original (the 600ms one) was just a straightforward implementation without any kind of type-instability. Maybe there was some unnecessary allocation (I don’t remember). And I remember that the original implementation actually used `partialsortperm!` (which was the sensible thing to do).

However - the point is that one might expect to get a reasonable performance out of the box without the need to start implementing manual stuff like I did with `fastmaxindex!`.

For example, the Go version seems pretty straightforward without needing acrobatics for a decent speed.

So we brought Julia to the top - but now what? One can honestly ask, what was the development time cost for getting a performant solution for a straightforward and real-world task?

This is in no way a critique (and even less finger-pointing) - just trying to be realistic here.

---

<div class="post-metadata">

**Author:** ![algunion](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/algunion/32/51630_2.png) [@algunion](https://discourse.julialang.org/u/algunion)\
**Post date:** [October 9, 2023, 12:38pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/38 "2023-10-09T12:38:38Z")

</div>

> [@jling](#):
>
> Given we’re operating on small (size = 5) `MVector`, I also tried to unroll this via `Base.@nexpr`, but that make things slower again

Maybe we can try a different approach altogether and not get anchored (as in _bias_) in how I implemented the `fastmaxindex!`.

---

<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:** [October 9, 2023, 12:42pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/39 "2023-10-09T12:42:18Z")

</div>

> [@algunion](#):
>
> Maybe we can try a different approach altogether and not get anchored (as in _bias_) in how I implemented the `fastmaxindex!`.

that’s what I did by copying Go-lang’s implementation, which insert and shifts everything. But that is slower than yours in Julia

---

<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:** [October 9, 2023, 1:41pm UTC](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611/40 "2023-10-09T13:41:35Z")

</div>

> <https://github.com/jinyus/related_post_gen/blob/4b2a3910a5ef49c7f74327a3d576f908db07dbda/java/src/main/java/related_post_gen/App.java#L91-L110>

Java is using the same algorithm as Go-lang, hmm, maybe we should try this but with better implementation, maybe I did something wrong

* * *

it’s also possible that you have a better sorting algorithm than them, which means we’re extra slow in some other parts

[Previous page](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611.md?page=1)

[Next page](https://discourse.julialang.org/t/funny-benchmark-with-julia-no-longer-at-the-bottom/104611.md?page=3)