# Memory footprint is much larger than expected

**URL:** <https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157>\
**Category:** General Usage\
**Created:** [May 26, 2018, 2:54am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157 "2018-05-26T02:54:17Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 2:54am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/1 "2018-05-26T02:54:17Z")

</div>

```julia
docs = Vector{Tuple{Tuple{Int64, Int64}, Vector{Int32}}}(60000000)

for i = 1:60000000
    docs[i] = ((i, i), Vector{Int32}(2))
end
while true
end

```

I reduced my problem to be above code. I expect `docs` to consume about 1.5GiB of memory. However, top shows it consumes about 7.8GiB.

1.5GiB because 60M \* 24Bytes = 1440 MBytes \< 1.5GiB.

I think there are probably a lot of things that I don’t yet understand about Julia Object’s memory footprint. Could someone please help me understand why this consumes so much more memory than I expected and maybe some suggestions to reduce the memory footprint?

Thanks!

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [May 26, 2018, 3:12am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/2 "2018-05-26T03:12:06Z")

</div>

Vectors take a very large amount of space.  
You might have thought that a `Vector{Int32}(2)` would only take a small about of space, but in addition to the 8 bytes to store the 32-bit integers, it will take at least another 40 more (on a 64-bit platform).  
Do those vectors need to be growable?  
If they are always of length 2, you could just use a Tuple{Int32,Int32} to store two integer values.

---

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 3:16am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/3 "2018-05-26T03:16:40Z")

</div>

I see. Thanks!

The vectors don’t have to grow but its content will need to be updated frequently. Also, it’s not necessarily a 2-element vector at each position. The length at each position actually depends on the input data. I use a constant here to make the presentation simple.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [May 26, 2018, 3:20am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/4 "2018-05-26T03:20:46Z")

</div>

Even though a tuple (or struct) is immutable, if they are small, frequently it’s better just to update the whole thing, if they are contained in something that _is_ mutable, such as a vector.  
Is there a small range of sizes for what you have as a vector there? If so, it might still be more efficient to use a tuple large enough for the largest)  
If the lengths of the vectors tend to be large, the overhead for using a Vector won’t be so noticeable.

---

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 3:27am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/5 "2018-05-26T03:27:14Z")

</div>

Thanks! I think tuple is probably going to help, but it would be nice if there was a mutable tuple type.

The problem is that the range of vector length depends on the input data and this program needs to be general. In practice, I think most vectors are small (a few elements) but there could be a few very large ones that contain tens of elements.

---

<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:** [May 26, 2018, 5:07am UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/6 "2018-05-26T05:07:29Z")

</div>

`MVector`s from the StaticArrays package are a mutable struct wrapping a tuple (with `setindex!` defined).

---

<div class="post-metadata">

**Author:** ![Ultima](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ultima/32/4244_2.png) [@Ultima](https://discourse.julialang.org/u/Ultima)\
**Post date:** [May 26, 2018, 1:35pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/7 "2018-05-26T13:35:32Z")

</div>

I ran the code on my machine, the created Arrayit looks like this (with N = 6):

> julia\> docs  
> 6-element Array{Tuple{Tuple{Int64,Int64},Array{Int32,1}},1}:  
> ((1, 1), Int32[132080144, 0])  
> ((2, 2), Int32[76064064, 0])  
> ((3, 3), Int32[76064000, 0])  
> ((4, 4), Int32[135077488, 0])  
> ((5, 5), Int32[143207064, 0])  
> ((6, 6), Int32[143207064, 0])  
> It appears to me that the tuple (**(1, 1)**, Int32[132080144, 0]) is the index of the array anyway (with 2 identical values in the tuple, so get rid of it.  
> What remains is this:

> (Int32[143207064, 0])

so, this could be setup by a simple Array:  
julia: a=Array{Int32}(N,2)  
then you iterate through it.  
simple Example:

> function iterat(N)  
> ar= Array{Int32}(N,2)  
> for k = 1:2  
> for i in 1:N  
> ar[i,k]= k×i # example calculation  
> end  
> return ar  
> end

julia\> @time iterat(60\_000\_000)  
0.492816 seconds (2.17 k allocations: 457.874 MiB, 12.88% gc time)  
Nonetheless, this could be optimized.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [May 26, 2018, 2:10pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/8 "2018-05-26T14:10:22Z")

</div>

He did say that the vectors were of varying lengths, so a matrix would not work for him.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [May 26, 2018, 3:48pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/9 "2018-05-26T15:48:38Z")

</div>

A Vector has more than 40 byte overhead: You have the header struct, which is one cache-line, plus the type-tag, plus whatever gc / malloc / free uses.

Then, you wrap your Vectors in Tuples. This is bad: Extra allocations, type-tags, pointers, etc.

As far as I gathered, each `doc[i]` needs to store two `Int64` and a variable number of `Int32`. The easiest update would be to store `doc_meta=Matrix{Int64}(2,num_docs)` (the same as `Vector{Tuple{Int64,Int64}}`, pointers are literally exchangable, choose whatever is nicer for syntax or has better dispatch; possibly keep both variants around, via `reinterpret`) and `doc_var = Vector{Vector{Int32}}(num_docs)`.

This still has the bad memory access patterns and memory overhead in `doc_var`. Do you construct doc\_var once and then never change `length(doc_var[i])`?

In this case I would store `doc_var_elems::Vector{Int32}` as well as `doc_var_idx::Vector{Tuple{Int64,Int64}}` where the first tells us where in `doc_var_elems` the first `doc_var[i]` is stored, and the second tells us the `length(doc_var[i])`. If you only need `1<<32` `doc_var_elems`, feel free to use `Int32` or `UInt32`. If the none of the `doc_var_elems` are very large, feel free to use `UInt8` or `UInt16` for the lengths (but then you need to store them in a separate vector, because of alignment/padding). Feel free to store pointers to the data instead of offsets into the array if you need 64bit because you have so many `Int32`s to store. Feel free to reuse some of these 64 bit for tags.

edit: If you can construct in order, you don’t need to store lengths at all, but instead each doc\_var\_idx[i] stores the offset of doc\_var[i], and` length(doc_var[i])=doc_var_idx[i+1]-doc_var_idx[i]`.

---

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 6:19pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/10 "2018-05-26T18:19:17Z")

</div>

Thanks! But yeah, it’s not a 2-element vector at every position. Besides, the Tuple{Int64, Int64} is not really the array index. Again I did that for simple presentation. So I can just get rid of it.

---

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 6:25pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/11 "2018-05-26T18:25:29Z")

</div>

Thanks! @foobar_lv2 This is very helpful.

For future readers’ benefit, I did an experiment to measure the memory overhead of using `Vector{Int32}`, `Tuple` (abstract type) or `Tuple{Int32, Int32}` to store the two `Int32` in each `doc`.

Using `Vector{Int32}` consumed 8005MiB, `Tuple` consumed 3613MiB and `Tuple{Int32, Int32}` consumed 1504MiB. This makes sense to me.

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [May 26, 2018, 6:26pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/12 "2018-05-26T18:26:38Z")

</div>

Another question, is the number of Int32’s fixed once a “doc” element is allocated?

One very memory efficient structure would be to simple have one big growable `Vector{Int32}` to store the data,  
and then use the indices into that to find the actual data.

For example:

```julia
struct MyStruct
    fixdata::Tuple{Int,Int}
    offsets::Vector{UInt32} # The size of this depends on how many Int32 vector elements you'll have total, if more than 4 billion, use UInt64.
    data::Vector{Int32}
end

```

---

<div class="post-metadata">

**Author:** ![jinliangwei](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jinliangwei/32/1929_2.png) [@jinliangwei](https://discourse.julialang.org/u/jinliangwei)\
**Post date:** [May 26, 2018, 6:28pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/13 "2018-05-26T18:28:42Z")

</div>

@ScottPJones Yeah, exactly. I think @foobar_lv2 was also going that direction. And it’s what I am doing for my program now.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [May 28, 2018, 5:34pm UTC](https://discourse.julialang.org/t/memory-footprint-is-much-larger-than-expected/11157/14 "2018-05-28T17:34:32Z")

</div>

FWIW, what I’m using in my crappy code is the following:

```julia
struct uvec{T}<:AbstractVector{T}
    ptr::Ptr{T}
    len::Int64
end
Base.length(x::uvec{T}) where {T} =x.len
Base.size(x::uvec{T}) where {T} =(x.len,) 
Base.IndexStyle(::uvec) = Base.IndexLinear()

Base.getindex(x::uvec,i) = unsafe_load(x.ptr,i)
Base.setindex!(x::uvec,v,i) = unsafe_store!(x.ptr,v,i)

struct ragVec{T} <:AbstractVector{uvec{T}}
    offsets::Vector{Int64}
    elems::Vector{T}
end

function ragVec(x::Vector{Vector{T}}) where T
    n = length(x)
    nelems = sum(length.(x))
    offsets=Vector{Int}(n+1)
    elems = Vector{T}(nelems)
    off=1
    for i=1:n
        offsets[i]=off
        for j=1:length(x[i])
            elems[off] = x[i][j]
            off+=1
        end
    end
    offsets[n+1]=off
    return ragVec(offsets,elems)
end
Base.length(x::ragVec{T}) where T =length(x.offsets)-1
Base.size(x::ragVec{T}) where {T} =(length(x),) 
Base.IndexStyle(::ragVec) = Base.IndexLinear()
Base.@propagate_inbounds function Base.getindex(x::ragVec{T},i) where T
   ptr = pointer(x.elems, x.offsets[i])
   len = x.offsets[i+1]-x.offsets[i]
   return uvec(ptr,len)
end

```

In my use, it is about avoiding the extra indirection and cache friendlyness (I construct once, and then spend a lot of time indexing into `ragVec`), not about amount of data.