编译器高性能计算【免费下载链接】numbaNumPy aware dynamic Python compiler using LLVM项目地址https://gitcode.com/gh_mirrors/nu/numba点击查看免费下载导读本文围绕 Numba 官方设计提案 NBEP 6: Typing Recursion 展开系统讲解 Numba 如何在不显式标注函数签名的前提下让 LLVM 编译器对**自递归self-recursion与互递归mutual recursion**函数完成类型推断。你将理解 Numba 当前递归支持的历史局限、编译期调用栈compile-time callstack与部分类型推断partial type inference两大核心机制的工作细节、递归类型推断的可终止性前提与边界限制以及如何通过控制编译顺序规避这些限制。文中所有机制均结合当前仓库 numba/core/typeinfer.py、numba/core/typing/context.py 与 numba/tests/recursion_usecases.py 中的真实实现与测试进行验证。背景Numba 类型推断为何对递归束手无策Numba 的核心价值在于将 Python 函数通过 LLVM 编译为高效机器码而这一切的前提是类型推断type inference编译器必须先确定函数参数与返回值的具体类型才能生成类型化 IR 并进一步降级为机器码。类型推断过程在 numba/core/typeinfer.py 的TypeInferer中完成其核心是一个约束网络ConstraintNetwork编译器遍历函数 IR为每个变量建立类型变量typevar再通过约束传播propagate不断收敛每个类型变量的可能类型集合直至状态不再变化。递归函数对这套机制提出了一个根本性难题要推断foo()的返回类型必须先知道其体内所有return表达式的类型若某个return表达式中调用了bar()则必须先完成bar()的类型推断而bar()内部又调用了foo()于是bar()的类型推断又依赖于foo()的返回类型。以提案原文的例子说明def foo(x): if x 0: return bar(x) # foo 依赖 bar else: return 1 def bar(x): return foo(x - 1) # bar 依赖 foofoo的类型推断依赖于barbar又依赖于foo形成一个循环依赖cyclic dependency。在传统的单遍类型推断中被调用者的推断过程会“悬挂”等待其调用者的函数类型而调用者又在等待它整个算法无法终止。提案之前只有显式签名的自递归可用NBEP 6 明确指出在引入该提案之前Numba 对递归的支持仅限带有显式类型注解的自递归。用户必须手写类似jit(i8(i8))的签名编译器才能绕过“无法确定递归调用返回类型”的问题。例如 numba/tests/recursion_usecases.py 中的fib1jit(i8(i8), nopythonTrue) def fib1(n): if n 2: return n # 注意第二个调用使用了具名参数 return fib1(n - 1) fib1(nn - 2)显式签名把返回类型i8直接“播种”seed给了编译器递归调用点无需再推断返回类型。但这种方式要求用户精确掌握 Numba 类型系统语法如i8、i8(i8)等对于更复杂的互递归场景几乎不可用——这正是 NBEP 6 要解决的问题。方案总览两大核心组件NBEP 6 提出的解决方案由两部分组成编译期调用栈compile-time callstack跟踪当前正在编译的函数集合用于在编译期识别递归调用部分类型推断partial type inference允许在递归调用点上暂时搁置递归路径仅利用非递归控制流路径上可确定的返回类型来打破循环依赖。两个组件在当前仓库中都有对应实现提案概念源码实现位置编译期调用栈numba/core/typing/context.py 中的CallStack类调用帧numba/core/typing/context.py 中的CallFrame类部分类型推断numba/core/typeinfer.py 中的TypeInferer.return_types_from_partial()递归调用识别与解析numba/core/typeinfer.py 的resolve_call以及 numba/core/types/functions.py 的RecursiveCall类型组件一编译期调用栈Compile-time CallStack设计意图CallStack是一个编译期而非运行时的数据结构模拟普通程序运行时调用栈的行为每当编译器开始编译一个函数就向栈中压入一条记录编译完成后再弹出。但与运行时调用栈不同这里的“调用”发生在编译阶段——一次调用即触发一次对被调用者的编译。源码实现在 numba/core/typing/context.py 中class CallStack(Sequence): A compile-time call stack 其核心方法包括register(target, typeinfer, func_id, args)第 64-93 行以上下文管理器的形式注册一次编译。压栈前会先检查是否“以相同签名重复编译同一函数”第 68-70 行若命中则抛出NumbaRuntimeError(compiler re-entrant to the same function signature)随后获取线程锁RLock将CallFrame追加到self._stack退出时自动出栈。finditer(py_func)/findfirst(py_func)第 95-111 行从栈顶向下bottom-up搜索匹配某 Python 函数对象的调用帧。findfirst返回第一个匹配帧无匹配时返回None。match(py_func, args)第 113-120 行查找与函数对象和参数类型同时匹配的调用帧——即判断“某个签名是否正在被编译”。提案中“调用栈从下往上搜索以匹配被调用者”的描述对应实现中finditer的迭代方向CallStack.__getitem__中索引0代表栈顶finditer从for frame in self即从栈顶开始依次遍历因此最先找到的是最近的、最外层尚未编译完成的同名函数帧。与类型推断状态的关系提案强调调用栈记录中保存着类型推断状态的引用。在实现中CallFramenumba/core/typing/context.py正是这样一个载体class CallFrame(object): def __init__(self, target, typeinfer, func_id, args): self.typeinfer typeinfer # 类型推断器引用 self.func_id func_id # 函数标识 self.args args # 参数类型 self.target target self._inferred_retty set() # 已推断出的返回类型集合其中typeinfer字段正是提案所说的“类型推断状态”——当递归被识别后编译器可以借助它**恢复resume**被挂起的类型推断过程。CallStack还额外实现了_fail_cache第 51-52 行、122-146 行一个仅在当前编译会话内有效的失败解析缓存避免同一失败解析被反复重试当栈清空时缓存自动清空且可通过配置DISABLE_TYPEINFER_FAIL_CACHE关闭。这属于实现层面的工程细节不是 NBEP 6 提案的核心内容但体现了真实实现相较提案的演进。组件二部分类型推断Partial Type Inference核心思想利用非递归路径给出“初始猜测”仅靠调用栈识别出递归还不够因为循环依赖的根源是递归调用的返回类型未知。NBEP 6 的洞察是一个有用的程序必然存在终止条件即至少存在一条不经过递归调用的路径。因此类型推断可以在递归调用点上暂时忽略包含递归调用的控制流路径仅考虑非递归路径推导出函数返回类型的一个初始猜测利用该初始返回类型在递归路径上继续传播类型信息得到最终返回类型在类型推断的后续迭代中用最终返回类型进一步细化所有路径的类型信息。提案中的完整流程仍以foo/bar为例下图展示了编译器从bar到达对foo的递归调用时编译期调用栈的状态此刻foo()的类型推断处于挂起suspended状态bar()的推断活动active。编译器通过自栈顶向下搜索调用栈发现被调用者foo正在编译中从而判定这是一次递归调用。随后编译器“恢复”foo的类型推断但忽略包含递归调用的路径——本例中只考虑else分支于是轻易得出foo()在此场景返回int。编译器据此将foo与bar的初始返回类型都设为int后续类型传播借助这一信息完成两个函数的推断并统一所有返回路径的返回类型。源码实现return_types_from_partial提案中的“部分类型推断”在 numba/core/typeinfer.py 中实现为TypeInferer.return_types_from_partial()def return_types_from_partial(self): Resume type inference partially to deduce the return type. Note: No side-effect to self. Returns the inferred return type or None if it cannot deduce the return type. # Clone the typeinferer and disable typing recursive calls cloned self.copy(skip_recursionTrue) # rebuild constraint network cloned.build_constraint() # propagate without raising cloned.propagate(raise_errorsFalse) # get return types rettypes set() for retvar in cloned._get_return_vars(): ... if not rettypes: return # unify return types return cloned._unify_return_types(rettypes)其实现要点与提案一一对应克隆推断器并禁用递归类型化第 1047 行self.copy(skip_recursionTrue)创建一个副本并通过TypeInferer._skip_recursion标志第 989 行在克隆体上跳过对递归调用的类型化。这正是提案“忽略包含递归调用的路径”的实现——递归调用被跳过剩下的就是非递归路径。无副作用所有操作都在克隆体上进行不会污染正在进行的原始推断过程方法注释明确写着No side-effect toself。收集所有返回路径的类型_get_return_vars()第 1006-1012 行遍历所有基本块收集每个ir.Return终止指令的返回值变量若克隆体的类型变量中已有定义则取其唯一类型typevar.getone()并通过types.unliteral去掉字面量类型。统一返回类型最后调用_unify_return_types将多条路径的返回类型归并为一个统一的类型作为递归调用的签名返回类型。递归调用的解析链从调用栈识别递归到完成部分推断完整链路位于 numba/core/typeinfer.py 的resolve_call当被调用者的函数类型是types.RecursiveCall定义于 numba/core/types/functions.py且未跳过递归时进入递归分支disp.fold_argument_types(pos_args, kw_args)折叠实参得到规范化的argsframe self.context.callstack.match(disp.py_func, args)在编译期调用栈中查找与“函数对象 参数类型”匹配的调用帧若frame is None该签名尚未在编译则走普通函数解析路径并把该签名记录到RecursiveCall的重载集合中fnty.add_overloads若frame命中该签名正在编译即递归调用则通过frame.typeinfer.return_types_from_partial()恢复父帧的部分类型推断得到返回类型若返回类型为None抛出TypingError(cannot type infer runaway recursion)——这正是提案所说“检测到潜在失控递归时抛出异常”的实现构造typing.signature(return_type, *args)作为递归调用点使用的签名调用frame.add_return_type(return_type)记录已推断出的返回类型。CallFrame.add_return_typenumba/core/typing/context.py还有一个重要的收敛保护RETTY_LIMIT 16当同一帧累积的返回类型达到 16 种时抛出TypingError(Return type of recursive function does not converge)防止类型不断增长例如递归中返回越来越大的元组导致推断永不收敛。自递归的识别对于自递归函数直接调用自身还存在一个特殊场景递归函数以全局变量形式引用自身时若 dispatcher 尚处于编译中numba/core/typeinfer.py 会通过typeof_global检查typ.dispatcher.is_compiling随后在调用栈中查找callstack.findfirst(typ.dispatcher.py_func)若找到则包装为types.RecursiveCall(typ)若找不到则抛出NotImplementedError(call to %s: unsupported recursion)。这保证了只有真正在编译栈中的递归调用才会走部分推断路径。限制与应对运行失控递归与编译顺序可终止性前提NBEP 6 明确指出为使该类型推断算法能够终止必须假设函数至少存在一条不经过递归调用即可到达 return 语句的控制流路径。若所有路径都最终导向递归调用算法将抛出异常提示可能存在失控递归runaway recursion。提案原文给出了一个三函数互递归的例子jit def first(x): # 递归调用必须有一条非递归路径 if x 0: return second(x) else: return 1 jit def second(x): return third(x) jit def third(x): return first(x - 1)这里first必须最先被编译类型推断才能成功完成。若先编译其他任何函数例如先编译second递归调用点会被转移到first上当编译器尝试恢复second的类型推断时将找不到任何非递归路径从而判定为失控递归并失败。提案总结道这是一个很小的限制可通过重构代码或按特定顺序预编译轻松克服。源码与测试印证该限制在真实实现与测试中均有对应失控递归的报错路径numba/core/typeinfer.py 中return_types_from_partial()返回None时抛出TypingError(cannot type infer runaway recursion)。失控自递归测试用例numba/tests/recursion_usecases.pyjit(nopythonTrue) def runaway_self(x): return runaway_self(x)失控互递归测试用例numba/tests/recursion_usecases.pyjit(nopythonTrue) def runaway_mutual(x): return runaway_mutual_inner(x) jit(nopythonTrue) def runaway_mutual_inner(x): return runaway_mutual(x)对应的测试 numba/tests/test_recursion.py 断言调用runaway_mutual(123)会抛出异常。与提案示例完全一致的四层间接互递归numba/tests/recursion_usecases.py 的make_four_level正是提案中first → second → third → first结构的直接翻版且first带有else: return 1的非递归退出路径被设计为“必须先编译”的入口函数。测试 numba/tests/test_recursion.py 的test_four_level验证其可正确编译执行。实战递归在 Numba 中的正确写法结合提案与测试用例可以总结出在 Numba 中编写递归函数的实践准则。1. 隐式签名的自递归提案核心收益NBEP 6 带来的直接收益无需显式签名即可编译自递归函数。numba/tests/recursion_usecases.py 中的fib3# 隐式签名 jit(nopythonTrue) def fib3(n): if n 2: return n return fib3(n - 1) fib3(n - 2)对比fib1显式签名i8(i8)fib3完全依靠类型推断确定n与返回值的类型这正是 NBEP 6 想消除的限制。2. 互递归提案的核心增量能力测试 numba/tests/recursion_usecases.py 展示了标准互递归写法阶乘与带不同参数名的互递归# 互递归 jit(nopythonTrue) def outer_fac(n): if n 1: return 1 return n * inner_fac(n - 1) jit(nopythonTrue) def inner_fac(n): if n 1: return 1 return n * outer_fac(n - 1)注意make_mutual2中bar(y, z)通过关键字参数bar(z1, yx)被调用——resolve_call中的fold_argument_types专门负责处理这类参数折叠。3. 必须遵守的准则每个递归函数都必须有一条非递归返回路径否则编译期抛出TypingError: cannot type infer runaway recursion递归链的“根”函数应最先被编译即第一个被实际调用触发编译的函数应包含非递归出口否则可能被误判为失控递归返回类型应最终收敛若递归导致返回类型无界增长如嵌套元组不断变大会触发CallFrame的RETTY_LIMIT 16保护numba/core/typing/context.py抛出Return type of recursive function does not converge。测试 numba/tests/test_recursion.py 的test_growing_return_tuple即针对此类场景源自 issue #4387见 numba/tests/recursion_usecases.py递归中的类型可以变化但须可统一make_type_change_mutualnumba/tests/recursion_usecases.py演示了递归过程中参数类型发生变化的场景编译器通过部分推断在递归调用点确定返回类型后再统一。总结NBEP 6 为 Numba 的类型推断引入了两项关键机制编译期调用栈让编译器能够在编译阶段识别“正在编译中”的递归调用部分类型推断则利用非递归路径先确定返回类型的初始猜测从而打破递归调用带来的循环依赖。从源码看该提案已完整落地于 numba/core/typeinfer.pyreturn_types_from_partial、resolve_call与 numba/core/typing/context.pyCallStack、CallFrame并被 numba/tests/test_recursion.py 与 numba/tests/recursion_usecases.py 中的自递归、互递归、失控递归、类型变化、返回类型增长等用例系统验证。理解这套机制不仅有助于正确编写 Numba 递归代码尤其是把握“非递归出口”与“编译顺序”两条铁律也为深入阅读类型推断管线的其他部分约束传播、类型统一等提供了良好的切入点。更多背景可参考 numba/core/typing/context.py、numba/core/types/functions.py 以及开发文档中的 类型推断说明。赞分享编译器高性能计算【免费下载链接】numbaNumPy aware dynamic Python compiler using LLVM项目地址https://gitcode.com/gh_mirrors/nu/numba点击查看免费下载相关推荐Bugly进阶功能探索自定义异常上报与数据统计分析Bugly进阶功能探索自定义异常上报与数据统计分析 Bugly Android SDK是一款强大的异常监控与分析工具能够帮助开发者及时发现并解决应用中的崩溃C模板递归gh_mirrors/st/STL中的编译期递归与递归终止C模板递归gh_mirrors/st/STL中的编译期递归与递归终止 你是否曾在编译C代码时遇到过模板递归深度超限的错误或者好奇标准库 Stan标准库33-js-concepts递归算法递归思想与尾递归优化技术33 js concepts递归算法递归思想与尾递归优化技术 引言递归的魔力与挑战 你是否曾经遇到过这样的困境面对一个复杂的嵌套数据结构传统的循环方法显教程前端文档创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
