为什么 Elixir 的 Enum.any？减缓？

Question

我运行下面的命令

MIX_ENV=prod  mix profile.fprof --no-start -e "Math.prime_seq 501"

对于以下代码

  def prime_seq(n) do
    prime_seq(n, 1, 3, [2,3,5,7,11,13,17,19,23])
  end

  def prime_seq(n, c, p, cache) when c < n do
    is_it = cache |> Enum.any?(fn n -> rem(p, n) == 0 end)
    if not is_it do
      prime_seq(n, c+1, p+2, cache ++ [p])
    else
      if(is_prime(p)) do
        prime_seq(n, c+1, p+2, cache ++ [p])
      else
        prime_seq(n, c, p+2, cache)
      end
    end
  end

  def prime_seq(n, c, p, _) when c == n do
    p-2
  end

结果：

为什么 Enum.do_any? 花费了太多时间？

是的，这是一个愚蠢的算法寻找第 n 个素数，还有更好的算法。但重点是，Enum.any? 比使用专门函数遍历列表慢。

我相信 anom 函数是 rem(p,n)，CMIIW

更新： 我用我的 Enum.any? 删除了 divisible?

 def divisible?(n, [h|t]) do
    if rem(n, h) == 0 do
      true
    else
      divisible?(n, t)
    end
  end

  def divisible?(n, []) do
    false
  end
  ..... 
  def prime_seq(n, c, p, cache) when c < n do
    #is_it = cache |> Enum.any?(fn n -> rem(p, n) == 0 end)
    is_it = divisible?(p, cache)
    if not is_it do
      prime_seq(n, c+1, p+2, cache ++ [p])
    else
      if(is_prime(p)) do
        prime_seq(n, c+1, p+2, cache ++ [p])
      else
        prime_seq(n, c, p+2, cache)
      end
    end
  end
  .....

结果：

所以..通过简单的修改我可以让它快 3 倍并且迭代次数是一样的。

注：这是我学习灵药时的玩具项目。请多多包涵。

is_prime函数：

def is_prime(n, i) when i < n do
    if rem(n, i) == 0 do
      false
    else
      is_prime(n, i+1)
    end
  end
  def is_prime(n, i) when i >= n do
    true
  end
  def is_prime(n) do
    cond do
    n <= 1 -> false
    n <= 3 -> true
    rem(n, 2) == 0 or rem(n, 3) == 0 -> false
    true -> is_prime(n, 3)
    end
  end

Answer 1

查看 source code of Enum.do_any?，我们可以看到它所做的只是遍历列表并调用提供的 lambda。

分析结果似乎表明大部分时间都花在了 lambda 之外，即迭代上，这在一定程度上让我感到困惑。

无论如何，这些结果的解释是，大部分时间花在了这一行：

is_it = cache |> Enum.any?(fn n -> rem(p, n) == 0 end)

另一个有用的信息是代码对 501 的输入大小进行了 135k 次迭代。这很好地表明算法复杂度至少是多项式的。

基于此，我建议考虑一些算法更改，例如 Eratosthenes 筛法。不幸的是，我无法弄清楚这段代码是什么 return，所以我无法提供替代解决方案。

Answer 2

如果您需要极致性能，Elixir/Erlang 可能不是合适的工具。 Erlang VM 的性能对于 CPU 绑定的任务来说不是很好。相反，您可能想要调用高度优化的外部库，例如 primesieve. You can learn how to write a so-called port in order to call native code in this recent Elixir Sips episode（免费）。

Answer 3

为了回答为什么 Enum.do_any? 比 divisible? 慢的问题，我为非分析版本创建了一个简单的测试用例：

cache |> Enum.any?(fn n -> rem(p, n) == 0 end)
divisible?(p, cache)
divisible_anon?(cache, fn n -> rem(p, n) == 0 end)

测试代码为：

 def divisible_anon?([h|t], fun) do
    if fun.(h) do
      true
    else
      divisible_anon?(t, fun)
    end
  end

  def divisible_anon?([], _) do
    false
  end

  def divisible?(n, [h|t]) do
    if rem(n, h) == 0 do
      true
    else
      divisible?(n, t)
    end
  end

  def divisible?(n, []) do
    false
  end

测量：

  def measure(function) do
    function
    |> :timer.tc
    |> elem(0)
    |> Kernel./(1_000_000)
  end

Math.prime_seq 501 的结果：

0.009852 秒
0.008797 秒
0.012836 秒

Math.prime_seq 10001 的结果：

2.686799 秒
1.395422 秒
2.687937 秒

结论，在@sasajuric 的帮助下："Anonymous function call is expensive"

Answer 4

既然有人问我，我就把它作为答案而不是评论。

问题不在于匿名函数是 "expensive"，而是代码除了遍历列表外几乎什么都不做。

BEAM 调度程序使用缩减来执行其功能切片。它稍微复杂一点，但每个函数调用都算作一次缩减。当您使用匿名函数时，您正在增加减少的时间成本（即，对实际函数的查找被添加到减少。）通常这种额外成本可以忽略不计，但是当你这样做时数百万次，它加起来。

BEAM 调度程序为每个进程提供 2000 次缩减，然后将时间片放入一个新的过程。

您创建了一个病态的边缘案例，将值零与另一个值进行比较。如果您将零与它看起来 "expensive" 的任何东西进行比较，那么绝对值的大小无关紧要。

正确的结论是，扩展速度快于 O(n) 的递归算法对每次递归中完成的工作量极为敏感。您应该惊讶于这完全有效，而不是它很慢。

如果我今天有时间，我将尝试使用 :erlang.statistics(:exact_reductions) 获取各种情况下的减少计数。

我使用这段代码获得了一些基本指标。

defmodule Counter do

 def count(function,arg) do
  {_ , count } = :erlang.process_info(self,:reductions)
  function.(arg)
  {_ , new_count } = :erlang.process_info(self,:reductions)
  new_count - count
 end

end

此代码计算减少量的方式并不完美，它确实应该运行自己的过程。

这些是我得到的结果，首先是 Enum.any?版本。

iex(4)> Counter.count(&Math.prime_seq/1, 10)
283
iex(5)> Counter.count(&Math.prime_seq/1, 100)
14086
iex(6)> Counter.count(&Math.prime_seq/1, 1000)
1105114
iex(7)> Counter.count(&Math.prime_seq/1, 10000)
103654258
iex(8)> Counter.count(&Math.prime_seq/1, 100000)
10068833898

请注意，所有这些减少都发生在单个调度线程中，我的 8 核笔记本电脑在该测试期间几乎不忙。很明显这是一个 O(n**2) 的归约算法。现在有了整除功能

iex(1)> Counter.count(&Math.prime_seq_div/1, 10)
283
iex(2)> Counter.count(&Math.prime_seq_div/1, 100)
14062
iex(3)> Counter.count(&Math.prime_seq_div/1, 1000)
1105485
iex(4)> Counter.count(&Math.prime_seq_div/1, 10000)
103655170
iex(5)> Counter.count(&Math.prime_seq_div/1, 100000)
10068870615

老实说，我预计这些数字会更小。事实上，它们并没有让我得出关于正在发生的事情的另一个结论，不是更多的减少，而是每次减少更多的时间。

Answer 5

Enum.any?是依赖Enumerable（使用reducees）实现的：http://blog.plataformatec.com.br/2015/05/introducing-reducees/

泛化与专业化相反。因此，虽然我们可以使用任何数据类型，但它不会像您自己实现列表变体那样快。然而，这并不意味着我们一定会变慢，我们可以轻松地将这些操作内联到 Enum 中，从而完全降低成本。

为什么 Elixir 的 Enum.any？减缓？

Why Elixir's Enum.any? slow?

profiling

elixir