# Serializing a tree requires a huge amount of storage

**URL:** <https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934>\
**Category:** General Usage\
**Tags:** question\
**Created:** [March 15, 2022, 10:25pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934 "2022-03-15T22:25:33Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 15, 2022, 10:25pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/1 "2022-03-15T22:25:33Z")

</div>

This is the code I used for testing

```julia
julia> struct Tree
           left::Tree
           right::Tree
           Tree() = new()
           Tree(l, r) = new(l, r)
       end

julia> a = Tree()
Tree(#undef, #undef)

julia> for i=1:20
           a = Tree(a, a)
       end

julia> using Serialization

julia> serialize("s.dat", a)

```

The resulting file has size 10MB. It does not resolve the objectid to save space I guess.  
Is there some trick to circumvent 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:** [March 15, 2022, 10:32pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/2 "2022-03-15T22:32:41Z")

</div>

We had a similar discussion [recently](https://discourse.julialang.org/t/serialize-is-prohibitively-slow-for-recursive-structs-what-am-i-missing/76276/14). But interestingly there we talked about time, not space…

---

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 15, 2022, 10:44pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/3 "2022-03-15T22:44:17Z")

</div>

Good point, they are probably the same thing. My temporary solution is keeping a dictionary of objects, and then dump this dictionary. Wondering if it can be made more elegant.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 15, 2022, 11:01pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/4 "2022-03-15T23:01:01Z")

</div>

> [@1115](#):
>
> The resulting file has size 10MB.

This seems pretty reasonable for a tree with 2^20 nodes?

---

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 15, 2022, 11:03pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/5 "2022-03-15T23:03:35Z")

</div>

The actual storage is 20 x (the object size of `Tree` type). Because we only create this many objects. They are conceptually big, but in the computer memory, they are just 20 linked addresses with a lot memory sharing.

---

<div class="post-metadata">

**Author:** ![feanor12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/feanor12/32/8212_2.png) [@feanor12](https://discourse.julialang.org/u/feanor12)\
**Post date:** [March 15, 2022, 11:40pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/6 "2022-03-15T23:40:08Z")

</div>

How does it scale if you double the tree nodes? Maybe other things take up the space.

Another thing might be a hidden copy of data. Did you try to use `Ref` instead?

---

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 15, 2022, 11:58pm UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/7 "2022-03-15T23:58:16Z")

</div>

```julia
julia> a = Tree()
Tree(#undef, #undef)

julia> for i=1:21
           a = Tree(a, a)
       end

julia> serialize("s.dat", a)

shell> ls s.dat -l
-rw-rw-r-- 1 leo leo 20971537 Mar 15 19:55 s.dat

julia> a = Tree()
Tree(#undef, #undef)

julia> for i=1:20
           a = Tree(a, a)
       end

julia> serialize("s.dat", a)

shell> ls s.dat -l
-rw-rw-r-- 1 leo leo 10485777 Mar 15 19:55 s.dat

julia> objectid(a.left)
0xb6935cdf82ed648e

julia> objectid(a.right)
0xb6935cdf82ed648e

```

So, we have

1. The size is exponential increasing as the depth,
2. The object id of left and right branch is the same.

---

<div class="post-metadata">

**Author:** ![feanor12](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/feanor12/32/8212_2.png) [@feanor12](https://discourse.julialang.org/u/feanor12)\
**Post date:** [March 16, 2022, 7:40am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/8 "2022-03-16T07:40:24Z")

</div>

Did you check the object IDs after deserialization ?

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [March 16, 2022, 8:19am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/9 "2022-03-16T08:19:23Z")

</div>

Your struct is immutable, so has copy semantics, so indeed you have about 2^21 objects to serialise.

If you define it to be mutable, which has reference semantics, it should serialise to a small file.

---

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 16, 2022, 8:22am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/10 "2022-03-16T08:22:33Z")

</div>

Yes, the objectid of left and right branches after deserialization are the same.

---

<div class="post-metadata">

**Author:** ![1115](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/1115/32/4465_2.png) [@1115](https://discourse.julialang.org/u/1115)\
**Post date:** [March 16, 2022, 8:32am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/11 "2022-03-16T08:32:20Z")

</div>

I think immutable types do not always copy, otherwise the following code would blow up my memory:

```julia
julia> struct Tree
           left::Tree
           right::Tree
           Tree() = new()
           Tree(l, r) = new(l, r)
       end

julia> a = Tree()
Tree(#undef, #undef)

julia> for i=1:200
           a = Tree(a, a)
       end

```

But I do tried your suggestion of making it mutable, and the serialized file is reasonablly small.

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [March 16, 2022, 8:56am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/12 "2022-03-16T08:56:49Z")

</div>

_Semantically_ they copy, though in this case the compiler can optimise things by using references instead (probably because you have possibly undefined fields), which is why your example doesn’t blow up.

---

<div class="post-metadata">

**Author:** ![pfitzseb](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pfitzseb/32/45566_2.png) [@pfitzseb](https://discourse.julialang.org/u/pfitzseb)\
**Post date:** [March 16, 2022, 9:59am UTC](https://discourse.julialang.org/t/serializing-a-tree-requires-a-huge-amount-of-storage/77934/13 "2022-03-16T09:59:06Z")

</div>

Yup:

```julia
julia> mutable struct Tree
                  left::Tree
                  right::Tree
                  Tree() = new()
                  Tree(l, r) = new(l, r)
              end

julia> a = Tree()
Tree(#undef, #undef)

julia> for i=1:20
           a = Tree(a, a)
       end

julia> using Serialization

julia> serialize("s.dat", a)

julia> stat("s.dat")
StatStruct for "s.dat"
   size: 167 bytes

```