# Tutorial: Efficient and safe approaches to mutation in data parallelism

**URL:** <https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105>\
**Category:** General Usage\
**Tags:** parallel, multithreading, tutorials\
**Created:** [May 31, 2021, 1:02am UTC](https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105 "2021-05-31T01:02:29Z")\
**Posts on this page:** 4\
**Page:** 1

<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:** [May 31, 2021, 1:02am UTC](https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105/1 "2021-05-31T01:02:29Z")

</div>

Hi, I just wrote another tutorial on data-parallel programming in Julia: [Efficient and safe approaches to mutation in data parallelism](https://juliafolds.github.io/data-parallelism/tutorials/mutations/). This is a sequel of [A quick introduction to data parallelism in Julia](https://juliafolds.github.io/data-parallelism/tutorials/quick-introduction/).

> As discussed in [a quick introduction to data parallelism](https://juliafolds.github.io/data-parallelism/tutorials/quick-introduction/), data parallel style lets us write fast, portable, and generic parallel programs. One of the main focuses was to unlearn the “sequential idiom” that accumulates the result into mutable state. However, mutable state is sometimes preferred for efficiency. After all, a fast parallel program is typically a composition of fast sequential programs. Furthermore, managing mutable states is sometimes unavoidable for interoperability with libraries preferring or requiring mutation-based API. However, sharing mutable state is almost always a bad idea. Naively doing so likely results in [data races](https://en.wikipedia.org/wiki/Data_race) and hence programs with [undefined behaviors](https://en.wikipedia.org/wiki/Undefined_behavior). Although low-level concurrency APIs such as locks and atomics can be used for writing (typically) _inefficient_ but technically correct programs, a better approach is to use single-owner local mutable state. In particular, we will see that unlearning sequential idiom was worth the effort since it points us to what we call [ownership-passing style](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#ownership-passing_style) that can be used to construct mutation-based parallel reduction from mutation-free (“purely functional”) reduction _as an optimization_.
> 
> This tutorial provides an overview of the mutable object handling in data-parallel Julia programs. It also discusses the effect and analysis of _false sharing_ which is a major performance pitfall when using in-place operations in a parallel program.

Table of contents:

> 1. [Example: multiplying and adding matrices](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#example_multiplying_and_adding_matrices)
> 1. [Advanced: fusing multiplication and addition in base cases](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#advanced_fusing_multiplication_and_addition_in_base_cases)
> 
> 2. [Categorizing mutation use-cases](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#categorizing_mutation_use-cases)
> 3. [Filling outputs](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#filling_outputs)
> 1. [Pitfalls with filling pre-allocated outputs](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#pitfalls_with_filling_pre-allocated_outputs)
> 
> 4. [In-place reductions](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#in-place_reductions)
> 1. [Flexible reduction with `FLoops.@reduce`](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#flexible_reduction_with_floopsreduce)
> 1. [`@reduce(acc = op(init, input))` example](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#reduceacc_opinit_input_example)
> 2. [Ownership-passing style](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#ownership-passing_style)
> 3. [`@reduce() do` example](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#reduce_do_example)
> 4. [General form of `@reduce() do` syntax](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#general_form_of_reduce_do_syntax)
> 5. [Ownership-passing style: second argument](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#ownership-passing_style_second_argument)
> 
> 2. [Initializing mutable accumulator using `Transducers.OnInit`](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#initializing_mutable_accumulator_using_transducersoninit)
> 3. [Combining containers](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#combining_containers)
> 4. [`OnlineStats`](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#onlinestats)
> 5. [Pitfalls with mutable reduction states](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#pitfalls_with_mutable_reduction_states)
> 
> 5. [Mutable temporary objects (private variables)](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#mutable_temporary_objects_private_variables)
> 6. [Accidental mutations](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#accidental_mutations)
> 7. [Advanced/Performance: False sharing](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#advancedperformance_false_sharing)
> 1. [Analyzing false sharing using `perf c2c`](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#analyzing_false_sharing_using_perf_c2c)
> 
> 8. [Advanced: adjoining trick](https://juliafolds.github.io/data-parallelism/tutorials/mutations/#advanced_adjoining_trick)

---

<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:** [May 31, 2021, 1:17am UTC](https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105/2 "2021-05-31T01:17:35Z")

</div>

By the way, I’m by no means an expert on CPU hardware and have very little understanding of how the coherence protocol actually works. In particular, I don’t know how on earth [certain false sharing does _not_ happen in Intel and IBM CPUs](https://discourse.julialang.org/t/is-amd-cpu-more-sensitive-to-false-sharing-than-intel-and-power/61679). So, I appreciate if the experts comment on/fact check the false sharing part.

(Of course, comments on other points are also welcome too 🙂 )

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [May 31, 2021, 9:13am UTC](https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105/3 "2021-05-31T09:13:14Z")

</div>

Why in all `append` examples `tuple` is used? For example, this

```julia
using FLoops

@floop for x in 1:10
    if isodd(x)
        @reduce(odds = append!(Int[], (x,)))
    else
        @reduce(evens = append!(Int[], (x,)))
    end
end

```

produces the same result as

```julia
@floop for x in 1:10
    if isodd(x)
        @reduce(odds = append!(Int[], x))
    else
        @reduce(evens = append!(Int[], x))
    end
end

```

Also

```julia
ys = Folds.mapreduce(tuple, withinit(() -> Int[], append!), 1:10; init = Init())

```

produces the same result as

```julia
ys = Folds.reduce(withinit(() -> Int[], append!), 1:10; init = Init())

```

so, why do we need this extra `tuple` conversion?

---

<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:** [May 31, 2021, 9:55pm UTC](https://discourse.julialang.org/t/tutorial-efficient-and-safe-approaches-to-mutation-in-data-parallelism/62105/4 "2021-05-31T21:55:48Z")

</div>

That’s a good point that touches the corner of Julia I wish I can ignore 🙂 Basically, the code without tuple-wrapping is working “by accident” (in some sense). It’s actually nothing to do with parallelism. Consider the implementations of `collect` with and without the tuple-wrapping;

```julia
julia> function collect1(xs)
           ys = Any[]
           for x in xs
               append!(ys, x) # no tuple
           end
           return ys
       end;

julia> function collect2(xs)
           ys = Any[]
           for x in xs
               append!(ys, (x,)) # tuple
           end
           return ys
       end;

```

As you’ve observed, there is no difference if the input is a collection of numbers (which is a singleton collection of itself):

```julia
julia> collect1(1:3)
3-element Vector{Any}:
 1
 2
 3

julia> collect2(1:3)
3-element Vector{Any}:
 1
 2
 3

```

However, your version won’t work when each element is also a collection (note: `Base.collect(1 => 2) == [1, 2]`):

```julia
julia> collect1(x => x^2 for x in 1:3)
6-element Vector{Any}:
 1
 1
 2
 4
 3
 9

julia> collect2(x => x^2 for x in 1:3)
3-element Vector{Any}:
 1 => 1
 2 => 4
 3 => 9

```

In other words, you are observing that

```julia
for e in x
    ...
end

```

and

```julia
for e in (x,)
    ...
end

```

are equivalent if `x isa Number`.

So, in the examples using `Int`, you are correct that there is no need to use a tuple. However, since this is a tutorial, it is important to demonstrate the fundamental pattern in parallel computing:

1. Create a singleton solution (e.g., the singleton tuple)
2. Combine the solutions (e.g., `append!`)

I was hoping that explicitly constructing the singleton solution like `(x,)` helps the readers to familiarize themselves with this pattern.