# Serialize() is prohibitively slow for recursive structs. What am I missing?

**URL:** <https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276>\
**Category:** New to Julia\
**Tags:** serialization, recursion\
**Created:** [February 12, 2022, 1:32am UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276 "2022-02-12T01:32:21Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 12, 2022, 1:32am UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/1 "2022-02-12T01:32:21Z")

</div>

I am representing some data with a large number of tree structs:

```julia
mutable struct MinimalNode
    childvalues::Union{NTuple{4, Int8}, NTuple{3, Int8}, NTuple{2, Int8}, NTuple{1, Int8}, Tuple{}};
    childnodes::Union{NTuple{4, MinimalNode}, NTuple{3, MinimalNode}, NTuple{2, MinimalNode}, NTuple{1, MinimalNode}, Tuple{}};
end

```

I need to be very parsimonious in order to keep it in memory (I will eventually have ~2M trees of size ~400), hence the `Int8`s and explicit types in there. Each tree is about 10kB according to Base.summarysize().

Serializing 21580 of these trees in a vector takes 30s. The resulting .jls file is about 90MB. I know from experience that Julia can (de)serialize 90MB files in an instant.

I have two guesses for what the problem is:

- The Int8s
- Each tree has a slightly different shape, so allocating memory cannot be done in advance

but I’m not sure how to solve either one. Maybe there’s an aspect of the serializer or the type system or something that I haven’t sussed out yet, that can help me make this fast?

---

<div class="post-metadata">

**Author:** ![ufechner7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ufechner7/32/51363_2.png) [@ufechner7](https://discourse.julialang.org/u/ufechner7)\
**Post date:** [February 12, 2022, 3:32am UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/2 "2022-02-12T03:32:30Z")

</div>

It would be helpful if you could provide a minimal working example that contains:

1. the type definition (as above)
2. the code to create a tree of the desired size, filled with random data
3. a function that serializes 21580 of these trees
4. a call of this function using `@btime` from BenchmarkTools.jl

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 3:20pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/3 "2022-02-13T15:20:54Z")

</div>

I know MWEs are useful. In this case, creating random data that has the same structure as my actual data is not so easy. I will work on it anyway, but in the meantime here is the _actual_ data: [test.jls](https://drive.google.com/file/d/1xcFXaNnpwAxYIWLEGF-a7LN_4myUO4fK/view?usp=sharing)

It was serialized with Julia 1.7.1 and takes me 28s to deserialize on my machine, with `using Serialization; deserialize("test.jls")`

I note that you ask me to use `@btime` rather than just `@time` – which suggests you think the slowness is due to compilation time, right? So you think it is my second guess? Unfortunately, this is an action that will be run once after Julia is first started, so I cannot take advantage of compile times on subsequent uses. At any rate, the current time for first deserialization will be measured in days which is unacceptable.

Edit to add: @btime returns `24.913 s (45550300 allocations: 1.99 GiB)` so it’s not compilation time after all.

---

<div class="post-metadata">

**Author:** ![jpsamaroo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jpsamaroo/32/46804_2.png) [@jpsamaroo](https://discourse.julialang.org/u/jpsamaroo)\
**Post date:** [February 13, 2022, 3:32pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/4 "2022-02-13T15:32:44Z")

</div>

Can you profile this with `Profile.@profile` and post the results of `Profile.print()` (via a pastebin)? Make sure to only post the results after a second run, after clearing the profile buffer with `Profile.clear()` and re-running `Profile.@profile` to eliminate overhead from compilation.

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 3:39pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/5 "2022-02-13T15:39:44Z")

</div>

Sure, here you go: [https://pastebin.com/M4g06vtc](https://pastebin.com/M4g06vtc)

---

<div class="post-metadata">

**Author:** ![ufechner7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ufechner7/32/51363_2.png) [@ufechner7](https://discourse.julialang.org/u/ufechner7)\
**Post date:** [February 13, 2022, 3:42pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/6 "2022-02-13T15:42:53Z")

</div>

I am asked for a password when clicking on this link …

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 3:43pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/7 "2022-02-13T15:43:37Z")

</div>

sorry, my first time using pastebin. Try again please.

---

<div class="post-metadata">

**Author:** ![ufechner7](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ufechner7/32/51363_2.png) [@ufechner7](https://discourse.julialang.org/u/ufechner7)\
**Post date:** [February 13, 2022, 3:44pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/8 "2022-02-13T15:44:25Z")

</div>

Now the link works… 🙂

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 4:54pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/9 "2022-02-13T16:54:02Z")

</div>

OK, here is a MWE. (a previous version had some randomness in the structure; that randomness is not essential).

The nodes generated by `addbranches!` are about 25kB in size, and a vector of 10,000 of them takes about 30s to serialize on my machine.

```julia
mutable struct MinimalNode
    childvalues::Union{NTuple{4, Int8}, NTuple{3, Int8}, NTuple{2, Int8}, NTuple{1, Int8}, Tuple{}};
    childnodes::Union{NTuple{4, MinimalNode}, NTuple{3, MinimalNode}, NTuple{2, MinimalNode}, NTuple{1, MinimalNode}, Tuple{}};
end

function addbranches!(mn::MinimalNode, aleft::Int64, bleft::Int64, parity::Int64, depth = 0)

    (depth == 12) && (return nothing);

    if parity == 1
        (aleft <= 1) && (return nothing);
        mn.childvalues = Tuple(1:aleft);
        mn.childnodes = Tuple([MinimalNode((), ()) for ii in 1:aleft]);
        aleft -= 1;
    else
        (bleft <= 1) && (return nothing);
        mn.childvalues = Tuple(1:bleft);
        mn.childnodes = Tuple([MinimalNode((), ()) for ii in 1:bleft]);
        bleft -= 1;
    end

    addbranches!.(mn.childnodes, aleft, bleft, 3-parity, depth + 1);
    
end

function buildfaketree()
    root = MinimalNode((), ());
    addbranches!(root, 4, 4, 1, 0);
    return root;
end

MN = [buildfaketree() for ii in 1:10000];
using Serialization;
@time serialize("test.jls", MN);

```

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 5:01pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/10 "2022-02-13T17:01:21Z")

</div>

An just in case it’s useful, the flame graph from `ProfileView.@profview serialize("test.jls", MN)`:

 ![flamegraph](https://global.discourse-cdn.com/julialang/original/3X/3/e/3ea50ab00d4c9cadd5c7cee53eb8caa8ac0e8198.png)

All of the red bars are `serialize_any` calls. I chose one at random; here is the `warntype_last()`:

```julia
MethodInstance for Serialization.serialize_any(::Serializer{IOStream}, ::Any)
  from serialize_any(s::AbstractSerializer, x) in Serialization at C:\Users\rNr\AppData\Local\Programs\Julia-1.7.1\share\julia\stdlib\v1.7\Serialization\src\Serialization.jl:655
Arguments
  #self#::Core.Const(Serialization.serialize_any)
  s::Serializer{IOStream}
  x::Any
Locals
  @_4::Union{Nothing, Tuple{Int64, Int64}}
  nf::Int64
  t::DataType
  tag::Int32
  i::Int64
Body::Nothing
1 ── nothing
│ Core.NewvarNode(:(@_4))
│ Core.NewvarNode(:(nf))
│ Core.NewvarNode(:(t))
│ (tag = Serialization.sertag(x))
│ %6 = (tag > 0)::Bool
└─── goto #3 if not %6
2 ── %8 = Base.getproperty(s, :io)::IOStream
│ %9 = Serialization.write_as_tag(%8, tag)::Core.Const(nothing)
│ %38 = Core.getfield(%36, 2)::Int64
│ %39 = Serialization.isdefined(x, i)::Bool
└─── goto #14 if not %39
13 ─ %41 = Serialization.getfield(x, i)::Any
│ Serialization.serialize(s, %41)
└─── goto #15
14 ─ %44 = Base.getproperty(s, :io)::IOStream
└─── Serialization.writetag(%44, Serialization.UNDEFREF_TAG)
15 ┄ (@_4 = Base.iterate(%31, %38))
│ %47 = (@_4 === nothing)::Bool
│ %48 = Base.not_int(%47)::Bool
└─── goto #17 if not %48
16 ─ goto #12
17 ┄ return Serialization.nothing

```

The only red in the actual output are the Argument `x::Any`, the Local `t::DataType`, and the line: `%41 = Serialization.getfield(x, i)::Any`.

---

<div class="post-metadata">

**Author:** ![jpsamaroo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jpsamaroo/32/46804_2.png) [@jpsamaroo](https://discourse.julialang.org/u/jpsamaroo)\
**Post date:** [February 13, 2022, 5:32pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/11 "2022-02-13T17:32:36Z")

</div>

Yeah, that’s what I figured might be happening: you’re hitting the slow dynamic dispatch path. What you probably want to do for deserialization is define a custom `deserialize` method that will decode your nested structs until you hit some other kind of object (or it terminates). It’s not particularly easy to write these, but you could see [https://github.com/JuliaData/MemPool.jl/blob/d6e92519259df3e5cda57ee515b5b5bd6f69ddcf/src/datastore.jl#L31-L41](https://github.com/JuliaData/MemPool.jl/blob/d6e92519259df3e5cda57ee515b5b5bd6f69ddcf/src/datastore.jl#L31-L41) for an example. You can do something similar for serialization, like in [https://github.com/JuliaData/MemPool.jl/blob/d6e92519259df3e5cda57ee515b5b5bd6f69ddcf/src/datastore.jl#L19-L22](https://github.com/JuliaData/MemPool.jl/blob/d6e92519259df3e5cda57ee515b5b5bd6f69ddcf/src/datastore.jl#L19-L22).

Aside: why is this slow by default? Because `serialize_any` and friends use `@nospecialize` annotations to prevent excessive compilation when doing ser/des. This makes messages with fewer large objects very efficient, but also means that many smaller objects are much more taxing, due to the dynamic dispatch overhead. It’s a tradeoff that was likely intentionally chosen to ensure decent performance in the common case (since most usages of serialization are likely serializing very large but simple objects).

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 13, 2022, 6:00pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/12 "2022-02-13T18:00:36Z")

</div>

Thanks very much for the info! I already did a quick search on custom serialization and came up empty, so your pointer to an existing example is much appreciated.

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [February 14, 2022, 5:19am UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/13 "2022-02-14T05:19:32Z")

</div>

I have a different analysis. The vast majority of time appears to be spent in the `serialize_cycle` routine, and while almost all time is spent in functions with dynamic dispatch, the _overead_ of those functions (i.e. the cost of dynamic dispatch) appears to be low. We can see this because the bars above the red lines occupy almost the entire width of the red lines.

Further, a large portion of the overhead appears to be in evaluating `iddict`’s `get`, a command used for cycle serialization.

I suspect that the issue is that you are serializing a data structure that could theoretically (although in your case doesn’t) contain pointer cycles, and `serialize` is spending 99% of its time checking for cycles.

The following addendum speeds things up 5x, but is still substantially slower than serializing a vector

```julia
struct ImmutableMinimalNode2
    childvalues::Union{NTuple{4, Int8}, NTuple{3, Int8}, NTuple{2, Int8}, NTuple{1, Int8}, Tuple{}};
    childnodes::Union{NTuple{4, ImmutableMinimalNode2}, NTuple{3, ImmutableMinimalNode2}, NTuple{2, ImmutableMinimalNode2}, NTuple{1, ImmutableMinimalNode2}, Tuple{}};
end
function make_immutable(node::MinimalNode)
    ImmutableMinimalNode2(node.childvalues, make_immutable.(node.childnodes))
end

immutable_MN = make_immutable.(MN)

@elapsed serialize("immutable_test.jls", immutable_MN)

```

I’ve explained and eliminated 80% of the runtime, but there is still a ways to go.

---

<div class="post-metadata">

**Author:** ![SortofDamocles](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sortofdamocles/32/15709_2.png) [@SortofDamocles](https://discourse.julialang.org/u/SortofDamocles)\
**Post date:** [February 14, 2022, 7:56pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/14 "2022-02-14T19:56:56Z")

</div>

Oh, brilliant idea just to have a single `make_immutable` pass after building the tree! This is a write-once, read-many situation so that is a _very_ easy improvement I can make.

I spent a couple of hours last night working through `Serialization.jl` with an eye toward a custom dispatch for `serialize`. In the meantime, it was easy enough to flatten the tree into a vector of `Int`s representing all the `childvalues` instances and serialize that instead. Even with the overhead of flattening and expanding, I’ve already gotten a huge increase in throughput.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [February 14, 2022, 7:57pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/15 "2022-02-14T19:57:32Z")

</div>

I’ve made [https://github.com/JuliaLang/julia/issues/44175](https://github.com/JuliaLang/julia/issues/44175) to track this issue.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [February 14, 2022, 8:11pm UTC](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/16 "2022-02-14T20:11:16Z")

</div>

> [@SortofDamocles](#):
>
> n the meantime, it was easy enough to flatten the tree into a vector of `Int` s representing all the `childvalues` instances and serialize that instead.

This has (not so?) surprising similarity to the transformation necessary to preallocate vectors as backing store for node based containers like lists and trees.