# Julia's in.() seems slow compared to R's %in%
**URL:** https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900
**Category:** Performance
**Created:** [May 6, 2019, 7:06am UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900 "2019-05-06T07:06:21Z")
**Posts on this page:** 20
**Page:** 2
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 6, 2019, 8:44pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/21 "2019-05-06T20:44:55Z")
> [@foobar\_lv2](#):
>
> That being said, I completely agree that this is a bad idea (not worth the code complexity)
I thought one of the key ideas of the new broadcasting semantic was to allow specialized methods for broadcasted functions? I’d think caching something (such as a hash table) was a classic example of such a specialization.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [May 6, 2019, 9:35pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/22 "2019-05-06T21:35:36Z")
It certainly can be done, but the question is whether it should be. If you think it should, open an issue on GitHub and we can discuss it. People there who might have opinions.
---
### Author:  [@jeff.bezanson](https://discourse.julialang.org/u/jeff.bezanson)
#### Post date: [May 7, 2019, 10:19pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/23 "2019-05-07T22:19:25Z")
We construct a `Set` internally in `indexin` and `findall(in(y), x)`. We just don’t happen to have a function that returns a boolean vector for this. One of the issues with the “vectorized” approach is that it’s hard to have a function for every combination of input and output formats you might need.
---
### Author:  [@phaverty](https://discourse.julialang.org/u/phaverty)
#### Post date: [May 8, 2019, 3:57am UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/24 "2019-05-08T03:57:56Z")
The table gets thrown away after each call to %in%, which is why Martin Maechler and I put in that special case a few years back. I think Gabe Becker has some plans to keep the table around, while it is valid, as part of the ALTREP framework. FWIW, I think leaving it to the user to explicitly make the table, or not, sounds good to me.
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 8, 2019, 8:23am UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/25 "2019-05-08T08:23:11Z")
> [@jeff.bezanson](#):
>
> One of the issues with the “vectorized” approach is that it’s hard to have a function for every combination of input and output formats you might need.
`in.(x, Ref(y))` does appear pretty canonical, though?
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [May 8, 2019, 9:47am UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/26 "2019-05-08T09:47:40Z")
I still don’t like the idea of overriding slow user choices of algorithm (say: User wants to broadcast `in` of typevars or flint integers, and needs to work around the known quirk that equality does not imply equality of hashes). But making the canonical spelling fast is probably a one-liner
```julia
julia> using BenchmarkTools
julia> N=10_000; lhs = rand(1:N, N); rhs = rand(1:N, N);
julia> res = in.(lhs, Ref(rhs));
julia> @btime in.(lhs, Ref(rhs));
39.737 ms (6 allocations: 5.61 KiB)
julia> Base.Broadcast.broadcasted(::typeof(in), lhs::AbstractArray, rhs::Base.RefValue{<:AbstractArray}) = Base.broadcasted(in, lhs, Ref(Set(rhs[])))
julia> res2 = in.(lhs, Ref(rhs));
julia> res==res2
true
julia> @btime in.(lhs, Ref(rhs));
497.682 μs (15 allocations: 150.30 KiB)
```
If you like the idea, feel free to make a PR with that single line, such that we can discuss the merits and demerits, and @mbauman can bring out all the subtleties I missed. (also, the fact that this single line works is a testament to how well designed the broadcasting system is. Big kudos to mbauman and all the other people involved in designing it!)
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 8, 2019, 11:12am UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/27 "2019-05-08T11:12:42Z")
I do like the idea, will do!
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [May 8, 2019, 12:23pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/28 "2019-05-08T12:23:53Z")
> [@foobar\_lv2](#):
>
> (also, the fact that this single line works is a testament to how well designed the broadcasting system is. Big kudos to mbauman and all the other people involved in designing it!)
I completely agree with this, but I dislike the idea of making this default.
It is not obvious to me that one always wants to build a hash table, and doing it on demand is very easy, as you and others have pointed out.
I think the right way to design APIs in Julia is not to hide the magic from the user, but to make it easily available in a composable and safe manner, so that everyone can just use it transparently. Which is what’s happening with `Ref(Set(...))`.
This also has the added pedagogical benefits of bringing hash tables to users who may not have hard about them. Paradoxically, a typical R user uses has tables _all the time_ without knowing about the concept, and at the same time misses a lot of great opportunities for using them because they are well-hidden. I think that exposing them effortlessly is the proper way for Julia.
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 8, 2019, 12:32pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/29 "2019-05-08T12:32:49Z")
I disagree with this. Whether or not to construct a hash table in the middle of a broadcastet `in` call is an implementation detail. There is no difference in terms of the result or the type being returned to the user. Implementations are always hidden from the user.
Requiring broadcastet `in` on `Vector`s to be slow because `Vector`s don’t have hash tables and the user should know this seems to me an unnecessarily purist approach, and making code slow for purely pedagogical reasons seems needless.
Where I do agree completely is that Vectors should not secretly lug around hash tables, nor should there be hidden tricks that distort the user’s ability to reason about code. But the specific implementation of `in` does not affect this.
---
### Author:  [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)
#### Post date: [May 8, 2019, 12:40pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/30 "2019-05-08T12:40:48Z")
Man, I’m really torn on this—I can see it both ways. I would strongly suggest opening a PR or an issue to discuss.
---
### Author:  [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)
#### Post date: [May 8, 2019, 12:50pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/31 "2019-05-08T12:50:17Z")
One could perhaps imagine a package which, when loaded, overloads functions like the one in this discussion and prints a warning, e.g.
```julia
in.(x,Ref(y)) # takes long time
using PerformancePirates
in.(x,Ref(y))
┌ Warning: in.(x,Ref(y)) can be performed faster by in.(x,Ref(Set(y)))
└ @ Main REPL[1]:1
```
One could also imagine adding this case to Traceur.jl
---
### Author:  [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)
#### Post date: [May 8, 2019, 1:00pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/32 "2019-05-08T13:00:25Z")
> [@mkborregaard](#):
>
> Whether or not to construct a hash table in the middle of a broadcastet `in` call is an implementation detail.
Possibly, but what I would emphasize here is that it is about choosing an _algorithm_. Unfortunately, this is somewhat difficult to automate, which is why many Julia APIs expose these choises (even when offering a sensible default).
> [@mkborregaard](#):
>
> Requiring broadcastet `in` on `Vector` s to be slow because `Vector` s don’t have hash tables and the user should know this seems to me an unnecessarily purist approach, and making code slow for purely pedagogical reasons seems needless.
Calling it “making code slow” possibly misrepresents my position. It is just not applying an optimization which itself has a cost, and the break-even point is unclear and difficult to tune (`Set` also allocates, and not everyone wants that to happen in all contexts).
The pedagogical benefit is just an additional extra. If you think that I would want to punish users so that they learn something new, it is possible that you misunderstood what I said.
---
### Author:  [@Daniel\_Berge](https://discourse.julialang.org/u/Daniel_Berge)
#### Post date: [May 8, 2019, 2:31pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/33 "2019-05-08T14:31:31Z")
I can see both sides of this argument also. It certainly seems like a good example where the broadcasting mechanics can be utilized to improve performance.
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 8, 2019, 4:20pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/34 "2019-05-08T16:20:37Z")
> [@StefanKarpinski](#):
>
> I would strongly suggest opening a PR or an issue to discuss.
I’ll do so tomorrow if nobody beats me to it. The code is already written by @foobar_lv2
---
### Author:  [@affans](https://discourse.julialang.org/u/affans)
#### Post date: [May 8, 2019, 4:23pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/35 "2019-05-08T16:23:32Z")
I use `in` quite frequently but never considered using `Ref` and `Set`. I don’t want to go offtopic, but can someone explain quickly how `Ref` works? and how a `Set` makes it faster (i.e. how does a hash table make the lookup faster)?
---
### Author:  [@mkborregaard](https://discourse.julialang.org/u/mkborregaard)
#### Post date: [May 8, 2019, 4:24pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/36 "2019-05-08T16:24:26Z")
> [@Tamas\_Papp](#):
>
> If you think that I would want to punish users so that they learn something new, it is possible that you misunderstood what I said.
I might have been stretching the point slightly to make the case 🙂
---
### Author:  [@tkluck](https://discourse.julialang.org/u/tkluck)
#### Post date: [May 8, 2019, 4:45pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/37 "2019-05-08T16:45:16Z")
I do see the attractiveness of solving this at the `broadcasted` level, particularly because it shows off its flexibility so well. But I really do think it’s misguided to want to make this choice for the user.
For example, have a look at these timings:
```julia
julia> a = [1,2,3];
julia> b = rand(1:10, 1000);
julia> @btime in.($b, Ref($a));
2.979 μs (3 allocations: 4.42 KiB)
julia> @btime in.($b, Ref(Set($a)));
6.300 μs (8 allocations: 4.91 KiB)
```
Its hard to avoid the conclusion is that, if we construct a hash-table behind the scenes, we’d have to give the user a way to opt-out. In other words, whatever default we choose, there need to be two related patterns that allow for these two options. I honestly can’t think of any way to make this distinction clearer for our users than just what it is: the difference between `a` and `Set(a)`.
(Superfluously, it’s nothing more than a lucky coincidence that `in.(b, Ref(a))` can be transformed in this way at compile time, where `map(in(a), b)` can’t.)
---
### Author:  [@tkluck](https://discourse.julialang.org/u/tkluck)
#### Post date: [May 8, 2019, 4:48pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/38 "2019-05-08T16:48:08Z")
> [@mkborregaard](#):
>
> Whether or not to construct a hash table in the middle of a broadcastet `in` call is an implementation detail. There is no difference in terms of the result or the type being returned to the user. Implementations are always hidden from the user.
One interesting thing to read is [The Law of Leaky Abstractions – Joel on Software](https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/) . A leaky abstraction is _exactly_ what we see here: performance is a very typical observable effect that betrays the implementation. As such, it is never truly hidden from the user.
---
### Author:  [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)
#### Post date: [May 8, 2019, 8:52pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/39 "2019-05-08T20:52:55Z")
> [@tkluck](#):
>
> (Superfluously, it’s nothing more than a lucky coincidence that `in.(b, Ref(a))` can be transformed in this way at compile time, where `map(in(a), b)` can’t.)
```julia
julia> Base.map(f::Base.Fix2{typeof(in), <:AbstractArray}, b::AbstractArray)=map(in(Set(f.x)), b)
```
---
### Author:  [@tkluck](https://discourse.julialang.org/u/tkluck)
#### Post date: [May 8, 2019, 9:26pm UTC](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900/40 "2019-05-08T21:26:17Z")
> [@foobar\_lv2](#):
>
> julia\> Base.map(f::Base.Fix2{typeof(in), \<:AbstractArray}, b::AbstractArray)=map(in(Set(f.x)), b)
TIL! That’s quite cool. The rest of my point still stands 🙂
[Previous page](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900.md?page=1)
[Next page](https://discourse.julialang.org/t/julias-in-seems-slow-compared-to-rs-in/23900.md?page=3)