Julia 中的高效聚合

我们最近引入了一项激动人心的功能，该功能已计划了很长时间：不可变聚合类型。事实上，我们已经计划了这么久，以至于此功能是我们 GitHub 上的第 13 个问题，迄今为止超过 2400 个问题。

本质上，此功能极大地减少了表示小型数字类值或包装少量其他对象的自定义类型的开销。考虑一个 RGB 像素类型

immutable Pixel
    r::Uint8
    g::Uint8
    b::Uint8
end

现在，这种类型的实例可以有效地打包到数组中，每个对象使用正好 3 个字节。在所有其他方面，这些对象继续像正常的一流对象一样工作。为了了解我们如何使用它，这里有一个函数，它将标准 24 位帧缓冲区格式的 RGB 图像转换为灰度

function rgb2gray!(img::Array{Pixel})
    for i=1:length(img)
        p = img[i]
        v = uint8(0.30*p.r + 0.59*p.g + 0.11*p.b)
        img[i] = Pixel(v,v,v)
    end
end

此代码将以极快的速度运行，不执行任何内存分配。我们还没有进行彻底的基准测试，但实际上这可能是从现在开始在 Julia 中编写此函数的最快方法。

这种行为的关键是新的 immutable 关键字，它意味着该类型的实例不能被修改。乍一看，这听起来只是一个限制——为什么我不允许修改一个？——但这实际上意味着对象与其内容相关联，而不是其内存地址。一个可变对象具有“行为”；它会随着时间的推移而发生变化，并且可能存在对该对象的许多引用，所有这些引用都可以观察到这些变化。另一方面，不可变对象只有值，没有随时间变化的行为。它的位置并不重要。它只是“一些位”。

Julia 一直以来都有一些不可变值，以位的形式，用于表示固定位宽的数字。数字是不可变的，这是非常直观的。如果 x 等于 2，你可能稍后会改变 x 的值，但人们理解，2 本身的值不会改变。immutable 关键字将这种想法推广到具有命名字段的结构化数据类型。Julia 变量和容器（包括数组）仍然是可变的。虽然 Pixel 对象本身不能改变，但在数组中可以将新的 Pixel 写入旧的 Pixel 上，因为数组是可变的。

让我们看看此功能的好处。

编译器和 GC 在移动和复制这些对象方面有很大的自由度。

这种灵活性可用于更有效地存储数据，例如将复数的实部和虚部保存在不同的寄存器中，或者只将其中一部分保存在寄存器中。

不可变对象易于推理。

一些语言，如 C++ 和 C#，提供“值类型”，它具有不可变对象的许多好处。但是，它们的行为可能会令人困惑。考虑以下代码

item = lookup(collection, index)
modify!(item)

这里的问题是我们是否修改了集合中的同一个 item，或者我们是否修改了本地副本。在 Julia 中，只有两种可能性：要么 item 是可变的，在这种情况下，我们修改了它的唯一副本，要么它是不可变的，在这种情况下，不允许修改它。

无开销的数据抽象成为可能。

定义一个新的类型通常很有用，它只包装一个值，并以某种方式修改其行为。我们最喜欢的模整数示例类型符合此描述

immutable ModInt{n} <: Integer
  k::Int
  ModInt(k) = new(mod(k,n))
end

由于给定的 ModInt 不需要在特定地址存在，因此可以像单个 Int 一样有效地将其传递给函数、存储在数组中等等，而没有包装开销。但是，在 Julia 中，开销并不总是为零。ModInt 类型信息将在编译时尽可能地“跟随数据”，但将在运行时根据需要添加堆分配的包装器。通常这些包装器是短暂的；例如，如果 ModInt 的最终目的地是在 ModInt 数组中，则可以在分配值时丢弃包装器。但是，如果该值仅在函数内部局部使用，则很可能根本没有包装器。

抽象得到充分执行。如果为不可变类型编写了自定义构造函数，则所有实例都将通过它创建。

由于构造的对象永远不会被修改，因此构造函数提供的约束条件不会被违反。目前，未初始化的数组是此规则的例外。新的“纯数据”不可变类型的数组具有未指定的內容，因此可以从其中获取无效值。在实践中，这通常是无害的，因为数组必须无论如何进行初始化，并且通常通过像 zeros 这样的函数创建，这些函数会执行此操作。

我们可以自动类型专门化字段。

由于构造时的字段值是最终的，因此它们的类型也是最终的，因此我们在构造不可变对象时了解了关于其类型的所有信息。

这里有许多潜在的优化，我们还没有实现所有优化。但是，拥有此功能为我们提供了另一个杠杆，帮助我们随着时间的推移提高性能。

不过，目前，我们至少有一个更简单的复数实现，并且将能够利用高效的有理矩阵和其他类似的优点。

附录：幕后

为了调用 C 和编写反射代码，了解不可变类型的实现方式有助于我们了解。在此更改之前，我们有类型 AbstractKind、BitsKind 和 CompositeKind，用于区分哪些类型是抽象的、哪些由不可变位字符串表示以及哪些是可变聚合。类型系统反映这些差异有时很方便，但也有些没有道理，因为所有这些类型都参与相同的层次结构并遵循相同的子类型规则。

现在，类型环境既简单又复杂。三个 Kind 已合并为一个名为 DataType 的 Kind。现在，Julia 中每个值的类型要么是 DataType，要么是元组类型（联合类型仍然存在，但当然始终是抽象的）。要了解 DataType 物理表示的详细信息，必须查询其属性。DataType 具有三个布尔属性 abstract、mutable 和 pointerfree，以及一个整型属性 size。CompositeKind 属性 names 和 types 仍然存在，用于描述字段。

abstract 属性表示该类型是用 abstract 关键字声明的，并且没有直接实例。mutable 表示，对于具体类型，实例是否可变。pointerfree 表示实例包含“仅数据”，没有对其他 Julia 值的引用。size 给出实例的大小（以字节为单位）。

以前是 BitsKind 的现在是 DataType，它们是不可变的、具体的、没有字段，并且大小不为零。以前的 CompositeKind 是可变的和具体的，并且要么有字段，要么如果没有字段则大小为零。显然，现在可以实现新的组合。我们已经提到了具有字段的不可变类型。我们可以拥有可变 BitsKind 的等价物，但这种组合在语言中没有公开，因为它很容易使用可变字段来模拟。另一种新的组合是具有字段的抽象类型，这将允许你声明某种抽象类型的所有子类型应该具有一些特定字段。这绝对有用，我们计划提供语法来实现它。

通常，你唯一需要担心这些事情的时候是调用本机代码时，当你想要知道某个数组或结构体是否具有与 C 兼容的数据布局时。这是通过类型谓词 isbits(T) 处理的。

2013 年 3 月 5 日 | Jeff Bezanson

附录：幕后