# Pool allocation at run time - how hard is it?

**URL:** <https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514>\
**Category:** Internals & Design\
**Tags:** question\
**Created:** [November 23, 2016, 1:47am UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514 "2016-11-23T01:47:53Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Stephen\_Vavasis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stephen_vavasis/32/3389_2.png) [@Stephen\_Vavasis](https://discourse.julialang.org/u/Stephen_Vavasis)\
**Post date:** [November 23, 2016, 1:47am UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514/1 "2016-11-23T01:47:53Z")

</div>

The main loop of nonlinear conjugate gradient looks like this:

```
  g = grad_f(x)
  <compute beta>
  p = -g + beta * p
  <compute alpha>
  x += alpha * p

```

Here, g, p, x are all n-vectors. If implemented in Julia exactly as written, then the above loop will cause many allocations and deallocations as x, p, g are recomputed. There are a number of techniques available in Julia to avoid this overhead, but all of them obfuscate the plain meaning of the code.

In principle, these allocations and deallocations could be completely avoided if the run-time system notices that it is repeatedly allocating and deallocating vectors of length n, and in response creates a finite-length pool of such vectors and quickly selects the first free vector in the pool for each new assignment statement.

This pattern of frequently reusing vectors and matrices of a particular size occurs commonly in scientific computation. How difficult would it be for the run-time system to detect it and to switch to a finite pool when it would be useful?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [November 23, 2016, 1:54am UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514/2 "2016-11-23T01:54:56Z")

</div>

Not impossible but very hard. And you can achieve that with broadcast fusion, once the dot operators are parsed this way.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [November 23, 2016, 2:47am UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514/3 "2016-11-23T02:47:09Z")

</div>

> [@Stephen\_Vavasis](#):
>
> g = grad\_f(x)  
> \<compute beta\>  
> p = -g + beta \* p  
> \<compute alpha\>  
> x += alpha \* p

```julia
  grad_f!(x,g)
  <compute beta>
  p .= -g .+ beta .* p
  <compute alpha>
  x .+= alpha .* p

```

in v0.6 once broadcast fuses shouldn’t allocate as @yuyichao said. I don’t that that’s bad at all.

---

<div class="post-metadata">

**Author:** ![pint](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pint/32/125_2.png) [@pint](https://discourse.julialang.org/u/pint)\
**Post date:** [November 28, 2016, 12:45pm UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514/4 "2016-11-28T12:45:24Z")

</div>

another idea: the runtime could spot that p has only one reference (and will be marked for GC), and the new value has the same size (this, even the compiler could determine in some cases), thus the array can simply be recycled.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 28, 2016, 5:56pm UTC](https://discourse.julialang.org/t/pool-allocation-at-run-time-how-hard-is-it/514/5 "2016-11-28T17:56:18Z")

</div>

That had not occurred to us, Dude.

Seriously, though, this is a well-known optimization technique that we will eventually implement, but it’s not exactly a “why don’t you just” kind of thing:

> **[Escape analysis](https://en.wikipedia.org/wiki/Escape_analysis)**
>
> In compiler optimization, escape analysis is a method for determining the dynamic scope of pointers – where in the program a pointer can be accessed. It is related to pointer analysis and shape analysis.
> When a variable (or an object) is allocated in a subroutine, a pointer to the variable can escape to other threads of execution, or to calling subroutines. If an implementation uses tail call optimization (usually required for functional languages), objects may also be seen as escaping to calle...