Mathematica 中函数和模式匹配之间的性能差异
因此 Mathematica 与 Lisp 的其他方言不同,因为它模糊了函数和宏之间的界限。在 Mathematica 中,如果用户想要编写数学函数,他们可能会使用模式匹配,例如 f[x_]:= x*x
而不是 f=Function[{x},x*x ]
尽管用 f[x]
调用时两者都会返回相同的结果。我的理解是,第一种方法相当于 lisp 宏,根据我的经验,由于语法更简洁,因此受到青睐。
所以我有两个问题,执行函数与模式匹配/宏方法之间是否存在性能差异?如果函数实际上被转换为某种版本的宏以允许实现诸如 Listable
之类的功能,我内心的一部分不会感到惊讶。
我关心这个问题的原因是因为最近的一系列问题 (1) (2) 关于尝试捕获大型程序中的 Mathematica 错误。如果大多数计算都是根据函数定义的,那么在我看来,跟踪计算顺序和错误起源比在通过连续应用宏重写输入后尝试捕获错误更容易/模式。
So Mathematica is different from other dialects of lisp because it blurs the lines between functions and macros. In Mathematica if a user wanted to write a mathematical function they would likely use pattern matching like f[x_]:= x*x
instead of f=Function[{x},x*x]
though both would return the same result when called with f[x]
. My understanding is that the first approach is something equivalent to a lisp macro and in my experience is favored because of the more concise syntax.
So I have two questions, is there a performance difference between executing functions versus the pattern matching/macro approach? Though part of me wouldn't be surprised if functions were actually transformed into some version of macros to allow features like Listable
to be implemented.
The reason I care about this question is because of the recent set of questions (1) (2) about trying to catch Mathematica errors in large programs. If most of the computations were defined in terms of Functions, it seems to me that keeping track of the order of evaluation and where the error originated would be easier than trying to catch the error after the input has been rewritten by the successive application of macros/patterns.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
我对 Mathematica 的理解是,它是一个巨大的搜索替换引擎。所有函数、变量和其他赋值本质上都存储为规则,在评估过程中,Mathematica 会遍历这个全局规则库并应用它们,直到结果表达式停止变化。
因此,您必须浏览规则列表的次数越少,评估速度就越快。看看使用
Trace
发生的情况(使用 gdelfino 的函数 g 和 h)就清楚了为什么匿名函数最快,以及为什么使用
Function
会比简单的SetDelayed
带来额外的开销。我建议您查看 Leonid Shifrin 的优秀著作的简介,其中包含这些概念解释了一些细节。我有时构建了一个
Dispatch
表我需要的所有功能并手动将其应用到我的起始表达式中。与正常计算相比,这提供了显着的速度提升,因为 Mathematica 的任何内置函数都不需要与我的表达式进行匹配。The way I understand Mathematica is that it is one giant search replace engine. All functions, variables, and other assignments are essentially stored as rules and during evaluation Mathematica goes through this global rule base and applies them until the resulting expression stops changing.
It follows that the fewer times you have to go through the list of rules the faster the evaluation. Looking at what happens using
Trace
(using gdelfino's function g and h)it becomes clear why anonymous functions are fastest and why using
Function
introduces additional overhead over a simpleSetDelayed
. I recommend looking at the introduction of Leonid Shifrin's excellent book, where these concepts are explained in some detail.I have on occasion constructed a
Dispatch
table of all the functions I need and manually applied it to my starting expression. This provides a significant speed increase over normal evaluation as none of Mathematica's inbuilt functions need to be matched against my expression.并不真地。 Mathematica 是一个术语重写器,Lisp 宏也是如此。
是的。请注意,您从来没有真正在 Mathematica 中“执行函数”。您只是应用重写规则将一个表达式更改为另一种表达式。
考虑将
Sqrt
函数映射到浮点数的压缩数组上。 Mathematica 中最快的解决方案是将Sqrt
函数直接应用于打包数组,因为它恰好实现了我们想要的,并且针对这种特殊情况进行了优化:我们可以定义一个包含术语的全局重写规则将
sqrt[x]
形式重写为Sqrt[x]
,以便计算平方根:请注意,这比之前的解决方案慢约 100 倍。
或者,我们可以定义一个全局重写规则,用调用
Sqrt
的 lambda 函数替换符号sqrt
:请注意,这比之前的解决方案快约 10 倍。
为什么?因为慢的第二个解决方案是查找重写规则
sqrt[x_] :> Sqrt[x]
在内循环中(对于数组的每个元素),而快速的第三种解决方案查找符号sqrt< 的值
Function[...]
/code> 一次,然后重复应用该 lambda 函数。相比之下,最快的第一个解决方案是循环调用用 C 编写的sqrt
。因此搜索全局重写规则的成本非常高,并且术语重写的成本也很高。如果是这样,为什么
Sqrt
如此快?您可能预计速度会减慢 2 倍,而不是 10 倍,因为我们已将Sqrt
的一次查找替换为sqrt
和Sqrt
但事实并非如此,因为Sqrt
具有作为内置函数的特殊地位,它将在 Mathematica 术语重写器本身的核心中进行匹配,而不是通过通用全局重写表进行匹配。其他人描述了相似函数之间的性能差异要小得多。我相信这些情况下的性能差异只是 Mathematica 内部的具体实现的微小差异。 Mathematica 最大的问题是全局重写表。特别是,这就是 Mathematica 与传统术语级解释器的不同之处。
您可以通过编写迷你 Mathematica 实现来了解有关 Mathematica 性能的更多信息。在这种情况下,上述解决方案可能会编译为(例如)F#。数组可以这样创建:
内置的
sqrt
函数可以转换为闭包并提供给map
函数,如下所示:这需要 6ms 就像
Sqrt[xs]
。但这是可以预料到的,因为该代码已由 .NET JIT 编译为机器代码,以便快速评估。在 Mathematica 的全局重写表中查找重写规则类似于在字典中查找闭包的函数名称。这样的字典可以在 F# 中这样构造:
这类似于 Mathematica 中的
DownValues
数据结构,只不过我们不会搜索多个结果规则来查找第一个与函数参数匹配的规则。然后程序变成:
请注意,由于内部循环中的哈希表查找,我们得到了类似 10 倍的性能下降。
另一种方法是将与符号关联的
DownValues
存储在符号本身中,以避免哈希表查找。我们甚至可以用几行代码编写一个完整的术语重写器。术语可以表示为以下类型的值:
请注意,
Packed
实现了 Mathematica 的打包列表,即未装箱数组。以下
init
函数使用函数f
构造一个包含n
个元素的List
,返回一个Packed< /code> 如果每个返回值都是
Float
或更通用的Apply(Symbol "List", ...)
否则:以下
规则
函数使用模式匹配来识别它可以理解的表达式,并将其替换为其他表达式:请注意,此函数的类型
expr -> expr
是术语重写的特征:重写将表达式替换为其他表达式,而不是将它们简化为值。我们的程序现在可以由我们的自定义术语重写器定义和执行:
我们已经恢复了 Mathematica 中
Map[Sqrt, xs]
的性能!我们甚至可以通过添加适当的规则来恢复
Sqrt[xs]
的性能:我写了一篇关于F# 中的术语重写。
Not really. Mathematica is a term rewriter, as are Lisp macros.
Yes. Note that you are never really "executing functions" in Mathematica. You are just applying rewrite rules to change one expression into another.
Consider mapping the
Sqrt
function over a packed array of floating point numbers. The fastest solution in Mathematica is to apply theSqrt
function directly to the packed array because it happens to implement exactly what we want and is optimized for this special case:We might define a global rewrite rule that has terms of the form
sqrt[x]
rewritten toSqrt[x]
such that the square root will be calculated:Note that this is ~100× slower than the previous solution.
Alternatively, we might define a global rewrite rule that replaces the symbol
sqrt
with a lambda function that invokesSqrt
:Note that this is ~10× faster than the previous solution.
Why? Because the slow second solution is looking up the rewrite rule
sqrt[x_] :> Sqrt[x]
in the inner loop (for each element of the array) whereas the fast third solution looks up the valueFunction[...]
of the symbolsqrt
once and then applies that lambda function repeatedly. In contrast, the fastest first solution is a loop callingsqrt
written in C. So searching the global rewrite rules is extremely expensive and term rewriting is expensive.If so, why is
Sqrt
ever fast? You might expect a 2× slowdown instead of 10× because we've replaced one lookup forSqrt
with two lookups forsqrt
andSqrt
in the inner loop but this is not so becauseSqrt
has the special status of being a built-in function that will be matched in the core of the Mathematica term rewriter itself rather than via the general-purpose global rewrite table.Other people have described much smaller performance differences between similar functions. I believe the performance differences in those cases are just minor differences in the exact implementation of Mathematica's internals. The biggest issue with Mathematica is the global rewrite table. In particular, this is where Mathematica diverges from traditional term-level interpreters.
You can learn a lot about Mathematica's performance by writing mini Mathematica implementations. In this case, the above solutions might be compiled to (for example) F#. The array may be created like this:
The built-in
sqrt
function can be converted into a closure and given to themap
function like this:This takes 6ms just like
Sqrt[xs]
in Mathematica. But that is to be expected because this code has been JIT compiled down to machine code by .NET for fast evaluation.Looking up rewrite rules in Mathematica's global rewrite table is similar to looking up the closure in a dictionary keyed on its function name. Such a dictionary can be constructed like this in F#:
This is similar to the
DownValues
data structure in Mathematica, except that we aren't searching multiple resulting rules for the first to match on the function arguments.The program then becomes:
Note that we get a similar 10× performance degradation due to the hash table lookup in the inner loop.
An alternative would be to store the
DownValues
associated with a symbol in the symbol itself in order to avoid the hash table lookup.We can even write a complete term rewriter in just a few lines of code. Terms may be expressed as values of the following type:
Note that
Packed
implements Mathematica's packed lists, i.e. unboxed arrays.The following
init
function constructs aList
withn
elements using the functionf
, returning aPacked
if every return value was aFloat
or a more generalApply(Symbol "List", ...)
otherwise:The following
rule
function uses pattern matching to identify expressions that it can understand and replaces them with other expressions:Note that the type of this function
expr -> expr
is characteristic of term rewriting: rewriting replaces expressions with other expressions rather than reducing them to values.Our program can now be defined and executed by our custom term rewriter:
We've recovered the performance of
Map[Sqrt, xs]
in Mathematica!We can even recover the performance of
Sqrt[xs]
by adding an appropriate rule:I wrote an article on term rewriting in F#.
一些测量
基于 @gdelfino 的回答和 @rcollyer 的评论,我制作了这个小程序:
至少对我来说,结果非常令人惊讶:
有什么解释吗?请随意编辑这个答案(评论对于长文本来说是一团糟)
编辑
使用恒等函数 f[x] = x 进行测试,以将解析与实际评估分开。结果(相同颜色):
注意:结果与此常量函数图非常相似 (f[x]: =1);
Some measurements
Based on @gdelfino answer and comments by @rcollyer I made this small program:
The results are, at least for me, very surprising:
Any explanations? Please feel free to edit this answer (comments are a mess for long text)
Edit
Tested with the identity function f[x] = x to isolate the parsing from the actual evaluation. Results (same colors):
Note: results are very similar to this Plot for constant functions (f[x]:=1);
模式匹配似乎更快:
模式匹配也更灵活,因为它允许您重载定义:
对于简单的函数,您可以编译以获得最佳性能:
Pattern matching seems faster:
Pattern matching is also more flexible as it allows you to overload a definition:
For simple functions you can compile to get the best performance:
您可以使用之前答案中的函数recordSteps了解 Mathematica 对函数的实际用途。它对待它就像对待任何其他头一样。 IE,假设您有以下内容
首先将 f[2] 转换
为 下一步,将
x+2
转换为2+2
。本质上,“函数”评估的行为就像模式匹配规则的应用程序,因此它的速度并不快也就不足为奇了。您可以将 Mathematica 中的所有内容视为一个表达式,其中求值是在 预定义序列,这适用于函数,就像任何其他头一样
You can use function recordSteps in previous answer to see what Mathematica actually does with Functions. It treats it just like any other Head. IE, suppose you have the following
It first transforms f[2] into
At the next step,
x+2
is transformed into2+2
. Essentially, "Function" evaluation behaves like an application of pattern matching rules, so it shouldn't be surprising that it's not faster.You can think of everything in Mathematica as an expression, where evaluation is the process of rewriting parts of the expression in a predefined sequence, this applies to Function like to any other head