Dart学习笔记(37):Numeric Computation数值计算

发表于2018-07-04 13:02 阅读(39)

目录
1  整数
2  浮点数
3  Boxed(封箱)和Unboxed(拆箱)
4  数值列表
……..4.1  Object List对象列表
……..4.2  Typed List类型列表
5  揭示内部逻辑
……..5.1  整型
…………….5.1.1  smi和mint
…………….5.1.2  优化按位左移操作
…………….5.1.3  整型列表
…………….5.1.4  bigint
……..5.2  double
……..5.3  Boxing
……..5.4  List
…………….5.4.1  Object List对象列表
…………….5.4.2  Typed List类型列表

本文地址:http://www.cndartlang.com/949.html

对每个人来说,应用的性能至关重要。它直接影响你的底线、转化率和用户满意度。但只要遵循一些简单的规则,就可以给你的应用50-100%的速度提升。

按照这篇文章的准则,在数值应用中,可以从Dart VM获得最大的性能。你需要了解四种不同的数字表示方法,整型和浮点数如何进行数值计算,以及如何选择对于你的数据最好的容器。

本文重点研究Dart VM。如果你主要的编译目的是JavaScript,参见webdev FAQ

注:本文并不涉及SIMD类型(可以并行地操作4个浮点数),但下一篇文章会有所讲解。

在Dart中有两种数值类型:int和double。前者是一个任意长度的有符号整数,后者则是IEEE-754标准的双精度浮点数。例如:

int speed = 3232943523452345329384234242323523;
int hitPoints = 21;
double position = 32.43432;
double hp = hitPoints.toDouble();

1、整型

虽然Dart中说明的是任意大小的整数,但是由于性能的原因,VM有三种不同的内部整型形式:smi、mint和bigint。每种形式用于控制不同的整数范围(参见表格)。当数字增大或减小的时候,VM会在后台自动切换。

内部形式
smi(small integer)
mint(medium integer)
bigint
最小值
-2^30(32位机器)
-2^62(64位机器)
-2^63
受内存限制
最大值
2^30 – 1(32位机器)
2^62 – 1(64位机器)
2^63 – 1
受内存限制

下面是一个例子,表明VM中的一个整数值,如何由smi渐变为bigint:

main() {
  int hitPoints = 21; // 开始是smi
  print(hitPoints);  // 21
  hitPoints += potionOfSuperHealth.points; // 变成mint
  print(hitPoints); // 2133232342342423
  hitPoints += spellOfNearlyInvinciblity.points; // 变成bigint
  print(hitPoints);  // 99999999999999999999999999999999999999999
}

2、浮点数

对于浮点数,VM只有IEEE-754标准的双精度浮点数一种形式,具体可查看Double-precision_floating-point_format

3、Boxed(封箱)和Unboxed(拆箱)

在Dart中,一切都是对象,甚至是数值。如果你之前熟悉的是C/C++,对此可能会让你很吃惊。任何算法或按位操作的结果都在一个新的数值对象中。因此,直接分配一个新的对象来存储一个数值操作的结果是无效的,因为这个原因,VM使用了一种被称为Unboxing的优化技术。Unboxed的数值位于CPU寄存器中。因此,所有数值和按位操作的结果也在CPU寄存器中,以避免将数值作为对象而产生大部分系统开销。

目前,VM支持拆箱double和mint。VM使用了一个被称为Tagging(标记)的小技巧,以便可以封箱和拆箱smi值,而无需分配内存或从对象加载值。更多内容稍后会谈到。

4、数值列表

Dart有两种方式来存储数值数据的列表:object listtyped list

4.1 Object List对象列表

List存储对象,例如:

var a = [ 1.0, 2.0, 3.0 ];
var b = new List(3); // 创建一个固定长度为3的List
b[0] = 5;
b[1] = 99;
b[2] = 34;

列表b是一个对象列表,它可以存储任意对象,例如String或null。这也意味着,List中的每个条目都和CPU的指针类型宽度一样。

4.2 Typed List类型列表

Dart提供了类型列表,仅用于存储数值,这些列表在dart:typed_data库中。Typed List仅能存储数值,并且不能保存常规对象和空的条目。针对普通整数大小、32位和64位浮点数,dart:typed_data库有不同的List。当使用比指针宽度更小的数值的时候,这些List可以节约相当大的内存。例如:

var a = new Float64List(3);
a[0] = 1.0;
a[1] = 2.0;
a[2] = 3.0;
var b = new Int8List(3);
b[0] = 5;
b[1] = 99;
b[2] = 34;

在Object List和Typed List示例中,名为a的列表保存了相同的数值,列表b同样如此。它们之间的区别在于如何存储和访问值。更多内容稍后会谈到。

5、揭示内部逻辑

重点来了。本节更详细的涵盖了上述概念,并提供了可操作的技巧。

5.1 整型

Dart VM中,对于整数值有多种内部形式。下面的章节将讲解每种形式,以及如何高效地执行按位左移操作。

5.1.1 smi和mint

请记住,VM有三种不同的整数形式,并且会根据整数的大小自动切换。本节重点关注smi和mint。

第一种形式,smi,它的大小为你平台中的指针大小减1。在32位的机器中,smi保存了一个31位的有符号整数。在64位的机器中,smi保存的是一个63位的有符号整数。smi并不要求分配内存来被创建,而是直接存储在字段中。VM可以通过存储数值的两倍来做到这一点,以确保低位为0。对于其它所有对象(包括Boxed double、mint和bigint),低位为1。VM使用低位来区分smi和其它所有对象。

因为存储的smi是数值的两倍,因此在运算前,值必须按位右移1位,这被称为untagging。相反,数值在运算后,必须加上它自身(等于乘2),这被称为tagging。尽管有这些额外操作,smi仍然非常地高效,因为它并不需要分配内存,所有访问可以直接执行,避免对加载的依赖。注意,许多常见的操作,如加法,并不需要smi为untagged。

思考一个名为entity的对象,定义如下:

class Entity {
  Entity() {
    scale = 2;
    x = 3;
    y = 0x40000000;
  }
  int scale;
  int x;
  int y;
}

Entity entity = new Entity();

上面的代码执行后,在32位机器的内存中,entity看上去像这样:

现在思考一下下面的Dart代码:

entity.x = entity.x * entity.scale;

它被转化成下面图中所示的VM指令。每个VM指令可以返回一个值,显示为v1、v2,等等。

在代码执行后,entity在内存中看上去像这样:

现在考虑一下第二种形式,mint,它保存了一个64位的有符号整数。在存储时,mint需要分配内存。mint字段存储的是mint实例的地址。当加载mint值的时候,CPU在加载mint实际的值前,必须先加载mint保存的地址。

下面的Dart代码将被转化为下面所示的VM指令:

entity.y = entity.y + entity.x;


在代码执行后,entity在内存中看上去像这样:

性能提示:如果可以的话,尽量使数值在smi范围内。smi会放入寄存器,并且可以直接加载和存储在字段中,而不是从内存中获取。它也不需要内存分配。

提示:smi的范围依赖于CPU的架构。

5.1.2 优化按位左移操作

按位左移被用于算术和逻辑运算。当执行按位左移操作时,需要注意,值要保持在smi范围内。当VM认为按位左移操作使用了一个常量的smi值作为掩码时,会执行优化:

result = (int1 << int2) & CONSTANT;  // CONSTANT 在smi范围内

例如:

a = (b << c) & 0x3FFFFFFF;

VM知道结果可以被存储为smi,并生成不需要检查是否需要mint存储结果的代码。在32位的架构中,常量0x3FFFFFFF是smi的最大正整数,而在64位架构中,则是常量0x3FFFFFFFFFFFFFFF。常量不一定是0x3FFFFFFF,它可以是任意的smi值。

性能提示:因为smi的范围是可变的,所以假设范围是31位,除非你需要更多的位数。

提示:在Dart中,十六进制的常量是有符号数。因此,如果你希望是负数,必须在十六进制的常量前使用负号“-”作为前缀。在32位机器中,最大的负数仍然是smi形式的值-0x40000000,最大的正数则是smi形式的0x3FFFFFFF。

5.1.3 整型列表

当smi被加载或被存储到一个对象列表(List)时,smi值保持不变,并被复制到列表中。这是smi范围内加载和存储整数最高效的方式。相比之下,加载和存储smi到类型列表(dart:typed_data)需要smi分别进行取消标记(untagged)和标记(tagged)操作。

思考下面的代码,假设所有的整型变量保持在smi范围内:

for (int i = 0; i < list.length; i++) {
  list[i] = list[i] + b;
}

如果list是一个对象列表,则不会对smi进行标记(tagging)和取消标记(untagging)。注意,一些整型操作,如乘法,必须首先要取消标记。如果list是一个类型列表,加载的值必须被标记。然后,在结果被存储之前,它必须被取消标记。index (i)添加到列表中时,先取消标记,再进行标记。

性能提示:在smi范围内运行时,考虑使用对象列表代替类型列表,以提高速度。

然而,你也可能想使用类型列表,而不是对象列表,因为类型列表对GC(垃圾回收机制)影响更小,并且拥有更好的CPU缓存性能。

因为类型列表不能存储对象引用,所以垃圾回收机制的负载非常低。相比之下,对象列表必须被扫描,每个条目都会对对象指针进行检查。

类型列表可以更加的密集。例如,如果你知道你仅需要8位精度,那么可以使用Int8List,将少消耗很多的内存,并且更好地使用CPU缓存。

因为上面所说的原因,建议对你的计算程序使用对象列表和类型列表进行基准测试,取好择优。

性能提示:如果可能,应避免使用类型列表存储smi范围外的整数。类型列表可以保存smi范围外或mint范围内的值。当类型列表加载整数时,必定会进行检查,并且可能会分配一个对象。在32位架构中,Int32List和Uint32List可以保存比smi更大的数值。Int64List和Uint64List则支持所有平台,可以保存比mint更大的数,并将结果保存到bigint中。

5.1.4 bigint

第三种整数形式,bigint,保存任意大的有符号整数。bigint字段存储的是bigint实例的地址。当加载bigint值的时候,整个数值并不会放入CPU寄存器,而且CPU并没有针对bigint值操作的指令。因此,这意味着bigint比smi或mint的开销更大。

性能提示:无论什么时候,尽量避免使用bigint。VM并不会对bigint实例的操作进行优化。

5.2 double

涉及到double值的计算是都是经过拆箱(Unboxed)的,这使得它们的计算非常高效。

double列表

当double值存储到对象列表中时,它必须被封箱(Boxed),这需要进行内存分配和内存存储。

有两个类型列表支持双精度值:Float32List和Float64List。这需要在存储密度和转换成本之间进行利弊权衡。Float32List的密度是Float64List的两倍,但是从Float32List中加载值的时候,必须转换成双精度值。相反,存储在Float32List中的时候,double必须转化成单精度浮点数。

性能提示:无论何时,如果要存储double值到列表中时,使用Float32List或Float64List。不像存储smi的情况,使用对象列表保存double始终会更慢。

性能提示:在你的应用中使用Float32List和Float64List进行基准测试,以决定哪个执行得更好。

5.3 Boxing

封箱(Boxing)操作是指移动寄存器中的一个标量值(scalar value),将它放入Dart对象中。拆箱(Unboxing)操作则相反,它会取出存储在Dart对象中的标量值,放入寄存器中进行操作。

封箱的开销大,你应该在数值计算中避免此操作。下面的情况会使数值触发封箱:

  • 将一个数字传递给另一个函数。函数只会接收封箱后的对象,因此如果你传递一个未封箱的数值给函数时,数值首先会被封箱。
  • 从函数返回一个数值。函数只会返回封箱后的对象,因此如果你在函数中返回一个未封箱的数值时,数值首先会被封箱。
  • 存储一个非smi数值到字段。字段只会保存smi值或对象指针。

封箱需要进行内存分配和存储。拆箱需要进行加载。

5.4 List

记住,两种类型的List可以存储数值数据:对象列表和类型列表。本节将讲解列表如何在内存中安排数据,以及如何加载和存储。

5.4.1 Object List对象列表

也可以称为实例列表(instances of List)。在运行时,对象列表(List)是一个指针数组。数组中的每个条目,都持有一个指向存储的数值的指针。唯一的例外是smi,它通过存储指针来装入内存。当类型检查未强制执行时,对象列表可以保存任意类型的对象,包括null。

从对象列表加载数值时,运行如下:

  1. 计算列表在后端存储的基地址。(对于可增长列表,这包括加载依赖)
  2. 从列表的后端存储中,加载数值或标记的(tagged)smi的地址。


对象列表存储数值时,运行如下:

  1. 如果数值并不是smi,分配一个新的数值实例。
  2. 计算列表在后端存储的基地址。(对于可增长列表,这包括加载依赖)
  3. 数值或标记的smi值的地址被存入列表的后端存储中。


5.4.2 Typed List类型列表

在运行时,类型列表是一个数值数组。数组中的每个条目会直接保存值。类型列表能更密集,能提高内存和CPU缓存的使用率。在垃圾回收的时候,类型列表处理更快,因为它并不需要扫描对象指针。

从类型列表加载双精度数值时,运行如下:

  1. 计算列表在后端存储的基地址。(对于可转换的列表,这包括加载依赖)
  2. 从列表的后端存储中,加载值。

类型列表存储双精度数值时,运行如下:

  1. 计算列表在后端存储的基地址。(对于可转换的列表,这包括加载依赖)
  2. double数值被存入列表的后端存储中。

在下面两种情况下,从类型列表中加载整型数值比double开销更大:

  1. 在列表中检索的数值在smi范围外,但在mint范围内。在这种情况下,mint必须被分配来存储数值。这种情况可能出现在使用Int32List、Uint32List、Int64List,和Uint64List的时候。优化的代码可能直接加载到unboxed的mint中,而避开分配的mint。
  2. 检索的数值在mint范围外。在这种情况下,bigint必定会被分配以存储数值。这种情况可能出现在使用Int64List和Uint64List的时候。

注意,加载或存储smi到类型列表时,要求值分别为tagged或untagged。

性能提示:将多维列表存入一维列表,然后在运行时计算多维索引。这样可以避开处理多个列表的开销。