# Conditional array comprehension vs. simple for loop - 750k allocations vs. 1 allocation - why?

**URL:** <https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249>\
**Category:** Performance\
**Tags:** loops\
**Created:** [June 20, 2021, 5:19pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249 "2021-06-20T17:19:39Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 20, 2021, 5:19pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/1 "2021-06-20T17:19:39Z")

</div>

Hello!

Thanks for taking a moment to have a look at my question 🙂

Full disclosure: I’m only a few weeks into learning Julia, brand new to Discourse and an interdisciplinary engineer (not a computer scientist) by training.

I wrote a simple function to calculate the Hamming distance between two strings for an exercise in an online learning course for Julia.

> **[Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)**
>
> In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is nam...

First I used a simple `for` loop which compared each character in the strings sequentially and tallied up those that didn’t match. This function’s code → `distance_loop()` which worked nicely.

Just out of curiosity and trying to learn about Julia, I tried re-writing the `for` loop to be identical, but on a single line using Julia’s nice _array comprehension_ syntax, which also worked nicely. This function’s code → `distance_array_comp()`.

Being new to examining function performance and to keep things simple I tested their performance using the `@time` macro, and two randomly generated strings of 1 million characters each.

Trying my best to be consistent, I restarted Julia, generated the two long strings and ran the `@time` test for each function once each to compile them, and then once more to time the compiled versions. The two functions produced identical answers, as expected.

This is the difference reported by the `@time` macro:

```julia
julia> @time distance_loop(long_rand_str_1, long_rand_str_2)
  0.011152 seconds (1 allocation: 16 bytes)
749296

julia> @time distance_array_comp(long_rand_str_1, long_rand_str_2)
  0.124214 seconds (748.81 k allocations: 20.426 MiB)
749296

```

**My (first-ever) question(s) for the community are:**

1. Am I mis-using the array comprehension syntax?
2. Why does changing this syntax make such a big difference?
3. Should this change in syntax make such a big difference?

I would be very grateful for help in what’s going on and look forward to your feedback!

**P.S.** I used `@code_lowered` on each function to see whether I could spot any differences between the functions → to me they were identical - happy to provide these on request!

**P.P.S.** I then used `@code_typed` on each function and there were many differences, though I was struggling to comprehend what they were at this stage, perhaps here is a good place to look? Also happy to provide these on request!

* * *

**Version info**

```julia
Julia Version 1.6.1
Commit 6aaedecc44 (2021-04-23 05:59 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.7.0)
  CPU: Intel(R) Core(TM) i5-5250U CPU @ 1.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, broadwell)
Environment:
  JULIA_NUM_THREADS = 2

```

* * *

**Minimum working example code**

```julia
function distance_array_comp(a::AbstractString, b::AbstractString)
    differences = 0
    [differences += 1 for i in eachindex(a) if a[i] != b[i]]
    return differences
end

function distance_loop(a::AbstractString, b::AbstractString)
    differences = 0

    for i in eachindex(a)
        if a[i] != b[i]
            differences += 1
        end
    end

    return differences
end

long_rand_str_1 = join(rand(['A', 'C', 'G', 'T'], 10^6))
long_rand_str_2 = join(rand(['A', 'C', 'G', 'T'], 10^6))

@time distance_loop(long_rand_str_1, long_rand_str_2)
@time distance_array_comp(long_rand_str_1, long_rand_str_2)

```

---

<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:** [June 20, 2021, 5:32pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/2 "2021-06-20T17:32:47Z")

</div>

This will perform better because you aren’t changing the binding to `differences` in the closure:

```julia
function distance_array_comp(a::AbstractString, b::AbstractString)
    differences = Ref(0)
    [differences[] += 1 for i in eachindex(a) if a[i] != b[i]]
    return differences[]
end

```

However, the comprehension is still allocating a return vector.

Compare the `@code_warntype` of this function with the original. You’ll notice the `Core.Box` and `Any`s that were highlighted in red have now disappeared.

If all you’re interested in is DNA base pairs, you might be better off with `Vector{Char}`s.

```julia
long_rand_1 = rand(['A', 'C', 'G', 'T'], 10^6);
long_rand_2 = rand(['A', 'C', 'G', 'T'], 10^6);
function distance_loop2(a, b)
    differences = 0

    @inbounds for i in eachindex(a)
        differences += a[i] != b[i]
    end

    return differences
end

```

will be much faster for this operation than `join`ing.

---

<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:** [June 20, 2021, 5:40pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/3 "2021-06-20T17:40:11Z")

</div>

> [@jlawrie](#):
>
> Am I mis-using the array comprehension syntax?

yes, in the sense that if you don’t want to allocate a return vector as big as number of iteration, you shouldn’t be using comprehension.

you could, however, do it in one-liner:

```julia

julia> @btime distance_loop($long_rand_str_1, $long_rand_str_2)
  6.042 ms (0 allocations: 0 bytes)
749914

julia> function distance_each(a,b)
           count(a[i] != b[i] for i in eachindex(a))
       end
distance_each (generic function with 1 method)

julia> @btime distance_each($long_rand_str_1, $long_rand_str_2)
  7.800 ms (0 allocations: 0 bytes)
749914

```

---

<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:** [June 20, 2021, 11:30pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/4 "2021-06-20T23:30:01Z")

</div>

If you like one-liners, you can use a generator instead of a comprehension as it doesn’t allocate and it has the same performance as a loop.

```julia
@btime sum($a[i] != $b[i] for i in eachindex($a))
  256.300 μs (0 allocations: 0 bytes)
749829

```

If you want the shortest, you can use this (but it won’t be as fast as a generator because it allocates):

```julia
@btime sum($a .!= $b)
  362.800 μs (4 allocations: 126.42 KiB)
749829

```

---

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 23, 2021, 7:13pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/5 "2021-06-23T19:13:33Z")

</div>

Thank your for confirming that the array comprehension was generating a vector. Rookie mistake - I the clue was in the name all along! That makes sense as to why it was doing so much allocation.

In this case, the task happened to require two input arguments of the type `string`, but otherwise I agree this would be a nicer and faster way to work with the base pairs 🧬 🧬 🧬 🧬.

> [@Elrod](#):
>
> `differences += a[i] != b[i]`

I did not know it was possible to increment based on `count += true`, that’s really neat, thanks for the tip!

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [June 23, 2021, 7:23pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/6 "2021-06-23T19:23:16Z")

</div>

> [@jlawrie](#):
>
> In this case, the task happened to require two input arguments of the type `string`

Then it might be quicker to iterate them, not to index:

```julia
distance_zip(as,bs) = count(a!=b for (a,b) in zip(as, bs))

```

---

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 23, 2021, 7:27pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/7 "2021-06-23T19:27:30Z")

</div>

Thank you for answering my question about whether I was mis-using the array comprehension syntax - I suspected so but glad to confirm this.

> [@jling](#):
>
> `count(a[i] != b[i] for i in eachindex(a))`

Writing an inline command `for i in itr` was the aim, but upon reflection I think I reached for a solution using an array comprehension because that was the form which I am most familiar with (at this stage).

Using the inline syntax but as part of a function call is definitely a much better idea!

I must remember to try using functions with names matching the things that I want to do more often, this usually seems to lead to a good answer in Julia for me (so far as a beginner anyway).

---

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 23, 2021, 7:35pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/8 "2021-06-23T19:35:24Z")

</div>

Thank you for your ideas and for showing how small differences to the syntax can sometimes cause a difference. I definitely would have not spotted that the second version would allocate and the first wouldn’t by myself 😅

I looked at the solutions written by some of the other members of the community who had also completed this task.

FWIW I liked this version which strays away from the `for i in itr` syntax a little and seems to be just as speedy (or be just as well optimised by the compiler).

`mapreduce(≠, +, a, b, init = 0)`

---

<div class="post-metadata">

**Author:** ![zdenek\_hurak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zdenek_hurak/32/53118_2.png) [@zdenek\_hurak](https://discourse.julialang.org/u/zdenek_hurak)\
**Post date:** [June 23, 2021, 7:56pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/9 "2021-06-23T19:56:52Z")

</div>

The whole trick is discussed here [Single- and multi-dimensional Arrays · The Julia Language](https://docs.julialang.org/en/v1/manual/arrays/#Generator-Expressions:)

> Comprehensions can also be written without the enclosing square brackets, producing an object known as a generator. This object can be iterated to produce values on demand, instead of allocating an array and storing them in advance…

---

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 23, 2021, 8:05pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/10 "2021-06-23T20:05:46Z")

</div>

You’re absolutely right, thank you! For me it was about 5 times faster than the original version with the simple short for loop 🥳

From the REPL:

```julia
julia> @time distance(a, b)
  0.014991 seconds (1 allocation: 16 bytes)
749981

julia> @time distance_zip(a, b)
  0.003066 seconds (1 allocation: 16 bytes)
749981

julia> 0.014991/0.003066
4.889432485322897

```

EDIT:

I just tried out the version using `mapreduce()` and it looks like it’s even a little faster than the `zip()` version (on my laptop using the simplest of benchmarks, at least).

```julia
julia> @time distance_mapreduce(a, b)
  0.002518 seconds (1 allocation: 16 bytes)
749981

julia> @time distance_zip(a, b)
  0.003585 seconds (1 allocation: 16 bytes)
749981

julia> 0.003585/0.002518
1.4237490071485308

```

---

<div class="post-metadata">

**Author:** ![jlawrie](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlawrie/32/26283_2.png) [@jlawrie](https://discourse.julialang.org/u/jlawrie)\
**Post date:** [June 23, 2021, 8:12pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/11 "2021-06-23T20:12:25Z")

</div>

That’s written concretely and clearly about how it will not allocate memory. Thank you for pointing me towards the relevant part of the documentation! 🙂

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 24, 2021, 8:41am UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/12 "2021-06-24T08:41:18Z")

</div>

> [@jlawrie](#):
>
> I did not know it was possible to increment based on `count += true` , that’s really neat, thanks for the tip

`Bool` is a subtype of `Integer` in julia, they thus behave like 1/0

```julia
julia> true == 1
true

julia> true isa Integer
true

julia> typetree(Bool)
Bool <: Integer <: Real <: Number <: Any

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [June 24, 2021, 7:39pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/13 "2021-06-24T19:39:18Z")

</div>

> [@baggepinnen](#):
>
> `typetree(Bool)`

Which version of Julia enables this?

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [June 24, 2021, 7:46pm UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/14 "2021-06-24T19:46:04Z")

</div>

Sorry, I forgot it was my own function, it’s here

```julia
typetree(x) = typetree(typeof(x))
typetree(::Type{Any}) = println("Any")
typetree(T::Union{DataType, UnionAll}) = (print(T, " <: "); typetree(supertype(T)))

```

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [June 25, 2021, 8:26am UTC](https://discourse.julialang.org/t/conditional-array-comprehension-vs-simple-for-loop-750k-allocations-vs-1-allocation-why/63249/15 "2021-06-25T08:26:54Z")

</div>

@jlawrie, fyi your `mapreduce()` and @mcabbott’s zip iterating solutions have the same performance here and both run faster for the long random strings above than the `Hamming()` function in [StringDistances.jl](https://github.com/matthieugomez/StringDistances.jl), which is already very fast and has other options.

_NB:_  
_The Levenshtein distance, which takes much longer to run, has some Julia0.6 code posted in [RosettaCode.org](https://rosettacode.org/wiki/Levenshtein_distance#Julia), whose iterative version seems buggy._