# Topological sort (performance)

**URL:** <https://discourse.julialang.org/t/topological-sort-performance/17153>\
**Category:** Performance\
**Tags:** sort\
**Created:** [November 5, 2018, 4:27am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153 "2018-11-05T04:27:55Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 7, 2018, 7:55am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/21 "2018-11-07T07:55:51Z")

</div>

> [@Liso](#):
>
> 10000 loops, best of 3: 20.2 µs per loop

You’re right. I have _no_ idea what this statistic is supposed to mean (get it?). Is it a mean, a minimum, a median? No clue.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 7, 2018, 8:23am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/22 "2018-11-07T08:23:06Z")

</div>

> [@StefanKarpinski](#):
>
> > [@Liso](#):
> >
> > 10000 loops, best of 3: 20.2 µs per loop
> 
> You’re right. I have _no_ idea what this statistic is supposed to mean (get it?). Is it a mean, a minimum, a median? No clue.

This is quite off topic but if you like to dig into it, newer version are more clear in (i)python now:

```python
Jupyter QtConsole 4.4.1
Python 3.6.6 |Anaconda custom (64-bit)| (default, Oct 9 2018, 12:34:16) 
Type 'copyright', 'credits' or 'license' for more information
IPython 7.1.1 -- An enhanced Interactive Python. Type '?' for help.

%timeit 1+1
10.4 ns ± 0.213 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)

```

End of off topic part:

```julia
  median time: 16.964 μs (0.00% GC)

```

In the light of

> [@Sukera](#):
>
> Generators are fine when reusing them or their contents, but not so when continously recreating them.

what does (0.00% GC) mean? Wasn’t just important part of code (GC) not measured here? (I have to admit that I don’t know what (i)python measure either - it could be that it is quicker just because GC was just postponed outside of measurement?)

Doing real, useful benchmarks is hard…

---

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [November 7, 2018, 8:42am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/23 "2018-11-07T08:42:46Z")

</div>

EDIT: Very sorry, I carried out this benchmark incorrectly in Python-- I’ll try to figure this out again later.

~~Here is one possibly extraneous datapoint for this discussion. I modified the  
OP’s Julia set-up-code to first convert all the strings to `Vector{Float64}` (using the ASCII codes). I also made the same modification to the Python code. I didn’t change either work routine at all-- the only change was to the input. It turns out that you can’t use Python lists as dictionary keys, so for Python I converted the strings to tuples rather than arrays of floats. The running time is now: mean 23.8 usec for Julia, 43.3 usec for Python. So this experiment seems to support the contention made by several posters that the Python internals are optimized for strings and are less performant for other data types.~~

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 7, 2018, 10:34am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/24 "2018-11-07T10:34:56Z")

</div>

> [@Stephen\_Vavasis](#):
>
> I modified the OP’s Julia set-up-code to first convert all the strings to `Vector{Float64}` (using the ASCII codes).

> [@Stephen\_Vavasis](#):
>
> So this experiment seems to support the contention made by several posters that the Python internals are optimized for strings

It is also my observation/hypothesis that for this kind of work current String implementation in Julia is not so good (if we want speed) in comparison to python’s.

This looks promising: _" The general philosophy of the architecture is as follows: have a single easy to use type that can replace `String` that conforms to the recommendations of the Unicode Organization (which internally uses 4 types and is implemented currently as a Julia Union, and has O(1) indexing to characters, not just code units)"_ (source: [GitHub - JuliaString/Strs.jl: String support package for Julia](https://github.com/JuliaString/Strs.jl)) but I am nor sure it is production ready nor it could really help here.

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [November 7, 2018, 10:50am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/25 "2018-11-07T10:50:09Z")

</div>

It would be pretty easy to replace the strings with integer id’s in this case, since it’s really just using them as keys rather than processing

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 7, 2018, 1:23pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/26 "2018-11-07T13:23:21Z")

</div>

> [@Liso](#):
>
> It is also my observation/hypothesis that for this kind of work current String implementation in Julia is not so good (if we want speed) in comparison to python’s.

Is this just a guess or do you actually have anything to support the hypothesis? Did you do any profiling? What is slower about Julia strings than Python?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 7, 2018, 1:25pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/27 "2018-11-07T13:25:46Z")

</div>

> [@Liso](#):
>
> not discourage people from using generator because “we have it”

Using `Channel`s (I don’t know why we are talking about generators in this thread) as a way to implement the iteration protocol could indeed be warned against, perhaps in the language difference section.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 7, 2018, 2:28pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/28 "2018-11-07T14:28:59Z")

</div>

> [@kristoffer.carlsson](#):
>
> I don’t know why we are talking about generators in this thread

@Liso linked another thread where a performance drop when continuously creating generators was observed. This is akin to the continuous creation of new Sets in the OP - why he referenced that exactly, I do not know.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 7, 2018, 2:38pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/29 "2018-11-07T14:38:34Z")

</div>

Alright, the example in that post is better on master (4x faster):

```julia
julia> @btime inversions1($p)
  179.826 ns (21 allocations: 640 bytes)
45

```

compared to 1.0.1:

```julia
julia> @btime inversions1($p)
  717.085 ns (111 allocations: 3.44 KiB)
45

```

So while there is still a slow-down compared to the hand written loop, things are improving!  
It might not be possible to get every high level abstraction to exactly match the performance of a hand written loop but the goal is to make them close enough that it shouldn’t be a big problem in practice.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 7, 2018, 3:21pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/30 "2018-11-07T15:21:15Z")

</div>

Without channels, using just generators is still 20% slower than in python. I think it is problem too. Don’t you agree?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 7, 2018, 3:38pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/31 "2018-11-07T15:38:00Z")

</div>

Again, this just seems like it is a mistaken belief that any Python code directly translated to Julia will be (magically) faster even if most of the time in the Python code is running optimized C code. That this is not the case is not a problem in itself. It is not the goal of Julia to be faster than Python when writing code in a Pythonic way.

What would be useful here is for some profiling and trying to identify if there is anything specific that is unreasonably slow and could be improved.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 7, 2018, 8:29pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/32 "2018-11-07T20:29:18Z")

</div>

> [@Liso](#):
>
> what does (0.00% GC) mean? Wasn’t just important part of code (GC) not measured here?

It was measured and no GC was performed so it took 0% of the time. GC is triggered by allocation so code that doesn’t allocate will never trigger GC. It can’t take time if it doesn’t happen.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 8, 2018, 4:27am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/33 "2018-11-08T04:27:15Z")

</div>

But there is:

```julia
  memory estimate: 31.05 KiB
  allocs estimate: 447

```

so allocation happened and if we want measure performance impact to system we need to measure GC work too.

Is this

```julia
  mean time: 24.255 μs (26.77% GC)

```

GC work caused only by `toposort3` function? Or there could be for example something caused by `BenchmarkTools.collect` ?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [November 8, 2018, 5:01am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/35 "2018-11-08T05:01:11Z")

</div>

FYI Python’s timeit module disable GC during the timing by default: [timeit — Measure execution time of small code snippets — Python 3.10.6 documentation](https://docs.python.org/3/library/timeit.html#timeit.Timer.timeit)

Not sure what is the setting in IPython though. It may be fair to enable the GC in Python.

---

<div class="post-metadata">

**Author:** ![Liso](https://avatars.discourse-cdn.com/v4/letter/l/898d66/32.png) [@Liso](https://discourse.julialang.org/u/Liso)\
**Post date:** [November 8, 2018, 6:23am UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/36 "2018-11-08T06:23:33Z")

</div>

If I am not wrong ipython suppress possibility to enable gc in timing! So comparing median from julia `16.964 μs (0.00% GC)` to python’s `20.2 µs per loop` seems to be most fair here. So it seems julia is ~15% better in this test…

EDIT:  
or better subtract GC work from mean (`mean time: 24.255 μs (26.77% GC)`)?

```julia
julia> 24.255*(100-26.77)/100
17.7619365

```

=\> 17.76 μs for Julia? (still ~14% better)

---

<div class="post-metadata">

**Author:** ![y4lu](https://avatars.discourse-cdn.com/v4/letter/y/47e85d/32.png) [@y4lu](https://discourse.julialang.org/u/y4lu)\
**Post date:** [November 8, 2018, 2:08pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/37 "2018-11-08T14:08:15Z")

</div>

What was the topological sort use-case after all?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 8, 2018, 3:20pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/38 "2018-11-08T15:20:02Z")

</div>

To summarize the main outcomes of this thread (since it’s gotten a bit off-topic):

- Python is quite good at executing the Pythonic style implementation of toposort quickly.
- Julia 1.0 is about as fast at the Pythonic algorithm, depending on the size of the problem.
- Julia seems to have gotten about [4x faster on master](https://discourse.julialang.org/t/topological-sort-performance/17153/29), so probably it is now about 4x faster than Python on the Pythonic version of the algorithm.
- There are other algorithms in Julia which are [orders of magnitude faster](https://discourse.julialang.org/t/topological-sort-performance/17153/10), which are available in well-established pure Julia packages ([LightGraphs](https://github.com/JuliaGraphs/LightGraphs.jl)).

Am I missing anything?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 8, 2018, 3:29pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/39 "2018-11-08T15:29:17Z")

</div>

> [@StefanKarpinski](#):
>
> Julia seems to have gotten about [4x faster on master](https://discourse.julialang.org/t/topological-sort-performance/17153/29), so probably it is now about 4x faster than Python on the Pythonic version of the algorithm.

That was from the timing in [Performance problem of count? - #13 by Sukera](https://discourse.julialang.org/t/performance-problem-of-count/16873/13) which was linked from [Topological sort (performance) - #18 by Liso](https://discourse.julialang.org/t/topological-sort-performance/17153/18).

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 8, 2018, 3:33pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/40 "2018-11-08T15:33:15Z")

</div>

So my claim is incorrect then?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 8, 2018, 3:34pm UTC](https://discourse.julialang.org/t/topological-sort-performance/17153/41 "2018-11-08T15:34:51Z")

</div>

Yes, because it is for a different benchmark. I don’t think anyone has measured the benchmark in this thread vs master.

[Previous page](https://discourse.julialang.org/t/topological-sort-performance/17153.md?page=1)

[Next page](https://discourse.julialang.org/t/topological-sort-performance/17153.md?page=3)