# SortedDict with mutable values - why does this allocate?

**URL:** <https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378>\
**Category:** General Usage\
**Tags:** question, package, performance\
**Created:** [May 16, 2024, 9:57pm UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378 "2024-05-16T21:57:28Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 16, 2024, 9:57pm UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/1 "2024-05-16T21:57:28Z")

</div>

I’m surprised that one of these allocates and the other doesn’t. I’m pretty sure that this isn’t specific to the package and that instead my surprise comes form me not understand Julia well enough. I wonder if someone here could illuminate.

```julia
using DataStructures
using BenchmarkTools

struct MyType1
    x::Float64
end
d = SortedDict{Float64,MyType1}()
@btime setindex!(d, MyType1(1.0), 1) # 23.774 ns (0 allocations: 0 bytes)

mutable struct MyType2
    x::Float64
end
d = SortedDict{Float64,MyType2}()
@btime setindex!(d, MyType2(1.0), 1) # 34.555 ns (2 allocations: 48 bytes)

```

Obviously the difference here is the mutability of the value struct. But why?

---

<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:** [May 17, 2024, 5:54am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/2 "2024-05-17T05:54:57Z")

</div>

If I’m not mistaken, your timing includes the creation of the `MyType2` object.

---

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 18, 2024, 9:47pm UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/3 "2024-05-18T21:47:17Z")

</div>

The two cases are exactly the same in this respect. The only difference is that `MyType1` is immutable and `MyType2` is mutable.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [May 18, 2024, 10:25pm UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/4 "2024-05-18T22:25:05Z")

</div>

Mutable structs are allocated, whereas immutable structs can be kept on the stack or in registers.

---

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 18, 2024, 10:38pm UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/5 "2024-05-18T22:38:55Z")

</div>

What do you mean, kept on the stack? In the example, the SortedDict isn’t on the stack, and the `setindex!` isn’t inside a function.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [May 19, 2024, 7:54am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/6 "2024-05-19T07:54:22Z")

</div>

The dicts are typically not on the stack, but `MyType1` is a “bits type”, whereas `MyType2` is not. Try `isbitstype(MyType1(1.0))`and `isbitstype(MyType2(1.0))`. This has consequences for how they are allocated and treated. So we have e.g.

```julia
julia> MyType1(1.0) === MyType1(1.0)
true
julia> MyType2(1.0) === MyType2(1.0)
false

```

because two “different” `MyType1` with the same `Float64` inside are semantically indistinguishable, but two different `MyType2` can be equal at one time, and different when one of them is changed. We also have:

```julia
julia> reinterpret(UInt8, [MyType1(1.0)])
8-element reinterpret(UInt8, ::Vector{MyType1}):
 0x00
 0x00
 0x00
 0x00
 0x00
 0x00
 0xf0
 0x3f
julia> reinterpret(UInt8, [MyType2(1.0)])
ERROR: ArgumentError: cannot reinterpret `MyType2` as `UInt8`, type `MyType2` is not a bits type

```

The first is the byte pattern of `1.0`, the second would have been a byte pattern of a pointer, though you would need some unsafe trickery to see that.

In terms of memory storage and such things, `MyType1` is treated just like a `Float64`, whereas `MyType2` is treated more like a pointer to a `Float64`. Even though the syntax is similar. This means that an object of type `MyType2` typically(always?) will be allocated on the heap, whereas an object of type `MyType1` is typically not.

You can also try this:

```julia
@btime [MyType1(i) for i in 1:1000];
@btime [MyType2(i) for i in 1:1000];

```

to see the difference. The first one, a `Vector{MyType1}` has exactly the same memory layout as if you did `[Float64(i) for i in 1:1000]`. You can see it by doing a

```julia
reinterpret(Float64, [MyType1(i) for i in 1:1000])

```

---

<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:** [May 19, 2024, 8:49am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/7 "2024-05-19T08:49:59Z")

</div>

> [@freeman](#):
>
> and the `setindex!` isn’t inside a function.

That’s not quite true - `@btime` (and `@benchmark`) wrap the expression you give it in a function, to ensure the expression is compiled. As a result, `MyType1(1.0)` ends up allocated on the stack. Since `MyType2` is mutable and the dictionary you’re writing to is a global object, it can’t be allocated on the stack and must survive while preserving object identity. As a result, it’s forced to be allocated on the heap.

---

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 19, 2024, 9:08am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/8 "2024-05-19T09:08:37Z")

</div>

Ok, good point that `setindex!` is indeex inside a function as it’s called by `@btime`.

However, it’s still the case that the SortedDict lives in the global space. Yes, I get that `MyType1` is immutable and can go on the stack, but I’m still adding it to an object that lives in the global space. When `@btime` exits, where is the `MyType1` object which was on the stack? Must be somewhere, as it’s accessible from the global SortedDict.

---

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 19, 2024, 9:11am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/9 "2024-05-19T09:11:12Z")

</div>

Thanks for that. I think you’re on to something.

I’d like to put to you the same question I just asked Sukera - where is the MyType1 when `@btime` returns? It’s not on the stack because the SortedDict is a global object.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [May 19, 2024, 9:16am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/10 "2024-05-19T09:16:36Z")

</div>

> [@freeman](#):
>
> When `@btime` exits, where is the `MyType1` object which was on the stack? Must be somewhere, as it’s accessible from the global SortedDict.

The `MyType1` object in the `Dict` is technically a copy, but a copy of an immutable is indistinguishable from the original. I.e. the `MyType1` has been “copied” into some `Vector` inside the dict.

---

<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:** [May 19, 2024, 9:19am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/11 "2024-05-19T09:19:57Z")

</div>

> [@freeman](#):
>
> When `@btime` exits, where is the `MyType1` object which was on the stack? Must be somewhere, as it’s accessible from the global SortedDict.

It’s stored inline in the array backing the `SortedDict`. Immutable `isbits` objects are compared by their bitwise identity, so the raw bits can simply be copied into the memory occupied by the array and stored inline there.

Note that this could still end up allocating if the `SortedDict` has to grow, which would require resizing (and thus reallocating) the backing array. This isn’t the case in your benchmark though.

---

<div class="post-metadata">

**Author:** ![freeman](https://avatars.discourse-cdn.com/v4/letter/f/ec9cab/32.png) [@freeman](https://discourse.julialang.org/u/freeman)\
**Post date:** [May 19, 2024, 9:21am UTC](https://discourse.julialang.org/t/sorteddict-with-mutable-values-why-does-this-allocate/114378/12 "2024-05-19T09:21:35Z")

</div>

Ok guys, this solves it. Thanks for the clarification.