# A simple tool for common subexpression elimination

**URL:** <https://discourse.julialang.org/t/a-simple-tool-for-common-subexpression-elimination/1676>\
**Category:** Community\
**Tags:** package, announcement\
**Created:** [January 25, 2017, 2:38am UTC](https://discourse.julialang.org/t/a-simple-tool-for-common-subexpression-elimination/1676 "2017-01-25T02:38:54Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [January 25, 2017, 2:38am UTC](https://discourse.julialang.org/t/a-simple-tool-for-common-subexpression-elimination/1676/1 "2017-01-25T02:38:54Z")

</div>

As part of some of my various Julia side projects, I’ve put together a very simple tool to perform common subexpression elimination (CSE). The idea of CSE is that if you have an expression like:

```julia
y = f(x)
z = g(f(x))
a = 2 * g(f(x))

```

which calls `f(x)` 3 times and `g(f(x))` twice, then you can get the same result by identifying and combining identical function evaluations, like so:

```julia
f_x = f(x)
g_f_x = g(f_x)
g_f_x_2 = 2 * g_f_x
a = g_f_x_2

```

which calls each function exactly once.

This optimization only makes sense if the functions are **pure** , that is if they have no side effects and don’t mutate their arguments. That makes it hard to apply CSE automatically inside Julia.

However, there are often situations where you know that all of your functions are pure, so it’s nice to be able to opt into this optimization. I’ve written [CommonSubexpressions.jl](https://github.com/rdeits/commonsubexpressions.jl) to do just that. Just wrap your code in the `@cse` macro and it might magically become faster. Or it might explode horribly, because this is a brand new package and probably still has bugs. Use with caution.

If this ends up being useful or interesting, then I’ll go ahead and register it. Meanwhile, I’d appreciate any feedback.

Cheers,  
Robin

---

<div class="post-metadata">

**Author:** ![bramtayl](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bramtayl/32/3614_2.png) [@bramtayl](https://discourse.julialang.org/u/bramtayl)\
**Post date:** [January 25, 2017, 3:46am UTC](https://discourse.julialang.org/t/a-simple-tool-for-common-subexpression-elimination/1676/2 "2017-01-25T03:46:28Z")

</div>

It might be useful to provide also output to highlight where the sub-expressions were. Then, instead of optimization, you could just spruce up your code.

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [January 25, 2017, 4:16am UTC](https://discourse.julialang.org/t/a-simple-tool-for-common-subexpression-elimination/1676/3 "2017-01-25T04:16:57Z")

</div>

That’s a good idea. I’ve opened an issue to remind myself: [https://github.com/rdeits/CommonSubexpressions.jl/issues/1](https://github.com/rdeits/CommonSubexpressions.jl/issues/1)