# Massive memory allocation on iterating algorithm \`8.789115 seconds (26.65 M allocations: 7.826 GiB, 25.07% gc time)\`

**URL:** <https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275>\
**Category:** New to Julia\
**Tags:** question, performance, memory-allocation\
**Created:** [October 13, 2020, 3:00am UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275 "2020-10-13T03:00:18Z")\
**Posts on this page:** 5\
**Page:** 2

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [October 13, 2020, 12:03pm UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275/21 "2020-10-13T12:03:39Z")

</div>

Type assertion might narrow the types. Because compare is only meaningful between Int, so we can narrow type to Int before comparing. This might be better than invoke `<(::Union{Nothing,Int},Union{Nothing,Int})`.  
Edit: compiler is good at optimizing, I guess compiler can do union splitting on this case, so adding type assertion might not be quite useful here.

---

<div class="post-metadata">

**Author:** ![valenmgama](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/valenmgama/32/18623_2.png) [@valenmgama](https://discourse.julialang.org/u/valenmgama)\
**Post date:** [October 13, 2020, 5:05pm UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275/22 "2020-10-13T17:05:21Z")

</div>

> [@Sukera](#):
>
> `partialsort!(child1_genes, cross_point+1:lastindex(child1_genes), by=x -> findfirst(==(x), parent2_genes))`

Follwing your suggested approach for the `cross_parents` function did indeed **reduced memory allocation to about half but doubled run time**. That is why I decided to stick to existing approach.

After follwing most tips performance is amazing **`0.926318 seconds (3.88 M allocations: 485.378 MiB, 10.53% gc time)`**

Here is the most up to date code:

```julia
        - using Random, CSV, DataFrames
        - const file = "21_Points.csv"
        - 
        - const pop_size = 20000
        - const elites = 200
        - const survivors = 9900
        - const mutts = 5000
        - const gens = 50
        - 
        - function generate_distance_matrix(file = "21_Points.csv")
        - #Importar datos de Excel
        0 nodes_import = CSV.read(file, header = true)
        - 
        - #Definir que hay en cada columna del excel y cuantos nodos hay en total
        0 num_nodes = size(nodes_import,1)
        - idcol = 1
        - Xcol = 2
        - Ycol = 3
        - 
        - #Generar la Matriz de distancias a partir del numero de nodos
        0 distance_matrix = Array{Float64}(undef, (num_nodes, num_nodes))
        - #Llenar la matriz de distancias entre todos los puntos usando Pitagoras
        0 for n in 1:num_nodes
        0 for s in 1:num_nodes
        0 distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
        - (nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
        - end
        - end
        - #println(pretty_table(nodes_import))
        - #println(pretty_table(distance_matrix))
        0 return distance_matrix
        - end
        - 
        - const distance_matrix = generate_distance_matrix("21_Points.csv")
        - const num_nodes = size(distance_matrix, 1)
        - 
        - function fitness_function(path)
        - return distance_matrix[path[end],path[1]] +
        - sum(distance_matrix[path[i-1],path[i]] for i = 2:num_nodes)
        - end
        - 
        - struct Individual
        - generation::Int
        - genes::Vector{Int}
        - fitness_score::Float64
        - end
        - Individual(gen, genes) = Individual(gen, genes, fitness_function(genes))
        - 
        - function init_poulation(pop_size)
   160080 population = Vector{Individual}(undef,pop_size)
        0 for i in 1:pop_size
  6080000 population[i] = Individual(1,randperm(num_nodes))
        - end
        0 return population
        - end
        - 
        - function new_generation!(population, mating_pool, gen)
        - 
        0 for p in 1:survivors
        0 parent1 = mating_pool[p]
        0 parent2 = mating_pool[rand(1:survivors)]
        - 
        0 for (c,I) in enumerate(cross_parents(parent1.genes, parent2.genes, gen))
        0 if c == 1
        0 population[elites+p] = I
        0 elseif c == 2
        0 population[elites+survivors+p] = I
        - else
        0 print("Error")
        - end
        - end
        - end
        - 
        0 for m in 1:(mutts÷2)
        0 mutt_1 = population[rand(10:pop_size)]
        0 mutt_2 = population[rand(10:pop_size)]
        0 mutate_type1!(mutt_1)
        0 mutate_type2!(mutt_2)
        - end
        - end
        - 
        - function cross_parents(parent1_genes, parent2_genes, gen)
        - 
        0 cross_point = rand(1:num_nodes-1)
        - 
131947200 ch1_genes = similar(parent1_genes)
131947200 ch2_genes = similar(parent2_genes)
 23284800 ch1_genes[1:cross_point] = @view parent1_genes[1:cross_point]
 23284800 ch2_genes[1:cross_point] = @view parent2_genes[1:cross_point]
        0 parent1_left = @view parent1_genes[cross_point+1:end]
        0 parent2_left = @view parent2_genes[cross_point+1:end]
        - 
130339920 ch1_pending = similar(parent1_left, Tuple{Int, Int})
130339920 ch2_pending = similar(parent2_left, Tuple{Int, Int})
        - 
        - 
        0 for (index, value) in enumerate(parent1_left)
        0 ch1_pending[index] = (value, findfirst(isequal(value), parent2_genes)::Int64)
        - end
 43035072 sort!(ch1_pending, by = last)
        0 for (index, (value, _)) in enumerate(ch1_pending)
        0 ch1_genes[cross_point+index] = value
        - end
        - 
        0 for (i, v) in enumerate(parent2_left)
        0 ch2_pending[i] = (v, findfirst(isequal(v), parent1_genes)::Int64)
        - end
 43035072 sort!(ch2_pending, by = last)
        0 for (i,(v, _)) in enumerate(ch2_pending)
        0 ch2_genes[cross_point+i] = v
        - end
        - 
 46569600 return (Individual(gen,ch1_genes), Individual(gen,ch2_genes))
        - end
        - 
        - function mutate_type1!(mutt_1::Individual)
        0 mutt_gene = rand(1:num_nodes-1)
        0 i = findfirst(isequal(mutt_gene), mutt_1.genes)
        0 j = findfirst(isequal(mutt_gene+1), mutt_1.genes)
        0 mutt_1.genes[i] = mutt_gene+1
        0 mutt_1.genes[j] = mutt_gene
        - end
        - 
        - function mutate_type2!(mutt_2::Individual)
        0 mutt_gene = rand(1:num_nodes-2)
        0 i = findfirst(isequal(mutt_gene), mutt_2.genes)
        0 j = findfirst(isequal(mutt_gene+2), mutt_2.genes)
        0 mutt_2.genes[i] = mutt_gene+2
        0 mutt_2.genes[j] = mutt_gene
        - end
        - 
        - function GA()
     2560 population = init_poulation(pop_size)
    79312 mating_pool = Array{Individual}(undef, survivors)
        - 
        0 for g = 2:gens
        - 
        0 partialsort!(population, survivors, by = p -> p.fitness_score)
     2352 mating_pool = @view population[1:survivors]
        - 
        0 new_generation!(population, mating_pool, g)
        - 
        0 if (population[1].fitness_score == population[elites].fitness_score) || ((g - population[1].generation) > 6)
        0 print("Convergencia en la GEN")
        0 println(g)
        0 print("TODOS ELITES IGUALES")
        - break
        - end
        0 if ((g - population[1].generation) > gens/5)
        0 print("Convergencia en la GEN")
        0 println(g)
        0 print("SIN CAMBIOS en x GENS x = ")
        0 println(gens/5)
        - break
        - end
     9968 println(g)
        - end
        - 
    80144 sort!(population, by = p -> p.fitness_score)
        0 return population[1]
        - end
        - 
        0 @time winner = GA()
        - print(winner)
        - 

```

---

<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:** [October 13, 2020, 5:10pm UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275/23 "2020-10-13T17:10:22Z")

</div>

> [@valenmgama](#):
>
> Follwing your suggested approach for the `cross_parents` function did indeed **reduced memory allocation to about half but doubled run time**. That is why I decided to stick to existing approach.

Huh, that’s very surprising to me 🤔 Is the CSV file you’re using publicly available? I’d like to play around with it a little, if that’s possible.

---

<div class="post-metadata">

**Author:** ![valenmgama](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/valenmgama/32/18623_2.png) [@valenmgama](https://discourse.julialang.org/u/valenmgama)\
**Post date:** [October 13, 2020, 5:18pm UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275/24 "2020-10-13T17:18:53Z")

</div>

This are the points I was using (they are actually 23 😬 haha) They are random coordinates between 1 and 100.

```julia
ID,X coordinate,Y coordiante
1,64,74
2,53,63
3,53,20
4,98,53
5,90,97
6,43,44
7,48,46
8,87,55
9,58,45
10,40,82
11,43,13
12,23,74
13,12,80
14,65,7
15,64,99
16,11,74
17,55,98
18,65,99
19,92,17
20,96,11
21,67,68
22,24,79
23,17,32

```

---

<div class="post-metadata">

**Author:** ![halleysfifthinc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/halleysfifthinc/32/206280_2.png) [@halleysfifthinc](https://discourse.julialang.org/u/halleysfifthinc)\
**Post date:** [October 13, 2020, 5:20pm UTC](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275/25 "2020-10-13T17:20:25Z")

</div>

> [@valenmgama](#):
>
> ```julia
> for n in 1:num_nodes
> for s in 1:num_nodes
> distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
> (nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
> end
> end
> 
> ```

Additionally, Julia arrays are column-major, so iterating the first dimension should take place in the innermost loop:

```julia
for s in 1:num_nodes
    for n in 1:num_nodes
        distance_matrix[n,s] = sqrt((nodes_import[n,Ycol] - nodes_import[s,Ycol])^2 +
        (nodes_import[n,Xcol] - nodes_import[s,Xcol])^2)
    end
end

```

[Previous page](https://discourse.julialang.org/t/massive-memory-allocation-on-iterating-algorithm-8-789115-seconds-26-65-m-allocations-7-826-gib-25-07-gc-time/48275.md?page=1)