写点什么

高性能的.NET 不可变数组

  • 2013-07-05
  • 本文字数:1401 字

    阅读完需:约 5 分钟

最新发布的.NET不可变集合中包含了 ImmutableArray,一种在只读、索引化的场景中比 ImmutableList更快速的选择。ImmutableList在设计时选择了一种平衡的方案。由于其复杂的内部结构,添加新项只能是 O(log n) 的操作。同样,通过索引读取某项也要耗费 O(log n) 的时间。

ImmutableArray则没有这么复杂。它只是一个包装了数组的结构。用 ildasm 可以看到,它不包含任何其他字段。这意味着从不可变数组中读取只需要 O(1) 的时间。相反,向不可变数组添加一项则需要对实际数组进行完全拷贝,为 O(n) 操作。

Immo Landwerth 提出了以下建议:

使用不可变数组的理由:

  • 极少更新数据,并且元素数量很小(小于 16)
  • 对迭代数据的性能要求很高
  • 有很多不可变集合的实例,并且无法负担将它们全放在树中的开销。

仍然使用不可变列表的理由:

  • 更新数据比较常见,或者元素数量预计不会太小
  • 对更新集合的性能要求比迭代要高

作为一个值类型,ImmutableArray在创建时不需要显式初始化。此时,结构将检测到内部空指针,其行为就像是长度为 0 的数组。

重大改变

不可变集合正处于开发过程中,重大变更时有发生。这一次,我们看到 Create(IEnumerable items) 函数更名为“From”。

Immo 写到,

我们发现接受 IEnumerable参数的重载可能会产生意想不到的结果。你可能认为要通过其他集合创建集合可以使用接受 IEnumerable参数的重载:

但你最终创建的是 ImmutableList<List> 而不是 Immutable,这是因为在进行重载决策时,参数重载的优先级要高于从 List到 IEnumerable的隐式转换。

因此我们决定将所有操作 IEnumerable的工厂方法改名为 From,以消除这种歧义。

最初的 IImmutableList包含一个 ValueComparer 属性,并匹配 WithComparer 方法。为了让 ImmutableArray保持为一个简单的包装器,就有必要在 IImmutableList接口中移除它们。

扩展方法 GetValueOrDefault 曾经接受一个 IDictionary<TKey, TValue> 或 IReadOnlyDictionary<TKey, TValue>。如果实际的类同时实现了这两个接口就会引起编译器错误,因此用只接受 IImmutableDictaionary<TKey, TValue> 的版本进行了替换。

其他改变

IImmutableSet新增了 TryGetValue 方法。如果使用了比较器如 StringComparer.OrdinalIgnoreCase,并且想得到集中的实际值而不仅仅是判断是否存在等价的元素时,就需要使用该方法了。

不可变集合仍然是预览版,并且不允许在生产中使用。它们目前可用于.NET 4.5、Windows Store、Windows Phone 8 和 Portable Class Library。

数组的性能

Jon Skeet 最近测试了数组的性能并发现了一些有趣的结果。用包装器包装数组竟然可以使它们能够更快地写入。对一个包含 100 项的数组进行 1 亿次写入,字符串数组用了 40.865 秒,而包装的字符数组只用了 29.338 秒。读取速度两者差不多,字符数组用了 12 秒,包装的数组用了 11.843 秒。

其原因要追溯到 Java 了。Java 的数组是协变的,也就是说可以将一个 String[] 传递给任何期望 Object[] 的参数或变量。.NET 的运行时 CLR 要设计为支持 Java,所以也支持协变数组。因此在每次写入数组时 CLR 都需要执行一次类型检查。

Jon Skeet 的数组包装器与我们上面提到的 ImmutableArray 中使用的并不相同。它在内部对数组中的每一项使用了基于结构的包装器。由于它只是一个包含了指针的结构,因此并不比数组中存储的普通引用耗费更多的空间。但其设计可以使 CLR 的 JIT 编译器忽略类型检查。

查看英文原文 High Performance Immutable Arrays in .NET

2013-07-05 06:122623
用户头像

发布了 59 篇内容, 共 25.8 次阅读, 收获喜欢 3 次。

关注

评论

发布
暂无评论
发现更多内容

膜拜!清华大佬手撸多线程并发源码笔记Github上线3天星标35k+

Java~~~

Java 架构 面试 JVM 多线程

不愧是华为内部的“操作系统学习笔记”,一篇说细节,一篇讲哲学

Java~~~

Java 架构 面试 操作系统 网络

美团面试:说说MySQL存储引擎原理,幸好我准备过!

Java MySQL 程序员 面试 计算机

不愧是阿里内部“SpringCloudAlibaba学习笔记”从头到尾,都是精华

Java 架构 面试 微服务

ipfs挖矿市场即将爆发 ipfs挖矿原理是什么?ipfs挖矿值得投资吗?

IPFS挖矿值得投资吗 ipfs挖矿原理是什么

Vue进阶(九十一):自定义指令

No Silver Bullet

Vue 9月日更

CPU 功能

Changing Lin

9月日更

银行对公业务数字化迎来新机遇

CECBC

Python代码阅读(第24篇):根据筛选函数将列表元素分成两组

Felix

Python 编程 Code Programing 阅读代码

头一次见,阿里大牛把计算机网络协议讲得这么有趣,已火爆Github

Java~~~

Java 架构 面试 网络协议 计算机

Socket接口固定QPS性能测试实践

FunTester

socket 性能测试 接口测试 测试框架 FunTester

ipfs分布式存储技术的优势在哪里?ipfs即将取代http是真的吗?

区块链 分布式存储 IPFS ipfs到底能否取代http?

微信朋友圈的高性能复杂度分析

晓波

架构实战营

大牛分享,献出这份年薪68W的蚂蚁金服Java高级开发封神宝典!

公众号_愿天堂没有BUG

Java 编程 程序员 架构 面试

微信朋友圈架构设计

小智

架构实战营

fil大涨:fil币价格行情怎样?投资fil靠谱吗?Fil多长时间能回本?

区块链 FIL币价格今日行情 fil挖矿靠谱吗 fil挖矿多久能回本? 投资filecoin

量化策略交易平台开发,马丁策略交易系统源码搭建

13530558032

LeetCode刷题35-简单-搜索插入位置

ベ布小禅

9月日更

微信业务架构分析

黑鹰

微信业务架构

GitHub标星翻倍!阿里大牛呕心沥血终成39w字Java面试笔记

Java~~~

Java 架构 面试 微服务 多线程

【LeetCode】二叉搜索树的最近公共祖先Java题解

Albert

算法 LeetCode 9月日更

Linux内核时钟机制及调度算法

hanaper

网络攻防学习笔记 Day126

穿过生命散发芬芳

主机安全 9月日更

逆袭!裸辞26天,历经4面,60w“跳”进鹅厂(附面试流程和真题)

Java~~~

Java 架构 面试 微服务 JVM

链路性能测试中参数多样性方法分享

FunTester

性能测试 测试框架 全链路测试 FunTester 链路测试

ipfs矿机工作原理是什么?ipfs矿机怎么买?

ipfs矿机怎么买 ipfs矿机工作原理是什么

模块七作业

king

仅靠七个步骤,4面通过拿offer,终“跳进”字节跳动

Java 程序员 架构 面试 计算机

单链路性能测试实践

FunTester

性能测试 接口测试 测试框架 压力测试 全链路测试

北鲲云超算平台能够为药物研发提供哪些层面的解决方案?

北鲲云

微信朋友圈高性能复杂度分析

缘分呐

微信朋友圈 高性能架构

高性能的.NET不可变数组_.NET_Jonathan Allen_InfoQ精选文章