【AICon】 如何构建高效的 RAG 系统?RAG 技术在实际应用中遇到的挑战及应对策略?>>> 了解详情
写点什么

.NET 集合类型的发展

  • 2008-07-04
  • 本文字数:2492 字

    阅读完需:约 8 分钟

.NET Framework 中的集合类型在这几年经历了显著的发展。得益于微软新的开放策略,让我们可以展现一个常用数据结构的两个版本:在.NET 和 Mono 中的哈希表。

理论上,哈希表是一个非常简单的构造,就是数组或链表的集合被划分到有限数量的存储体中。然而,即使你擅长于多线程逻辑,在获取该数据结构的元素项时,仍然有些复杂。 // Copyright © Microsoft Corporation. All rights reserved.

public virtual Object this[Object key] {
get {
if (key == null) {
throw new ArgumentNullException(“key”, Environment.GetResourceString(“ArgumentNull_Key”));
}
uint seed;
uint incr;

// Take a snapshot of buckets, in case another thread does a resize
bucket[] lbuckets = buckets;
uint hashcode = InitHash(key, lbuckets.Length, out seed, out incr);
int ntry = 0;
bucket b;
int bucketNumber = (int) (seed % (uint)lbuckets.Length);
do
{
int currentversion;
// A read operation on hashtable has three steps:
// (1) calculate the hash and find the slot number.
// (2) compare the hashcode, if equal, go to step 3. Otherwise end.
// (3) compare the key, if equal, go to step 4. Otherwise end.
// (4) return the value contained in the bucket.
// After step 3 and before step 4. A writer can kick in a remove the old item and add a new one
// in the same bukcet. So in the reader we need to check if the hash table is modified during above steps.
//
// Writers (Insert, Remove, Clear) will set ‘isWriterInProgress’ flag before it starts modifying
// the hashtable and will ckear the flag when it is done. When the flag is cleared, the ‘version’
// will be increased. We will repeat the reading if a writer is in progress or done with the modification
// during the read.
//
// Our memory model guarantee if we pick up the change in bucket from another processor,
// we will see the ‘isWriterProgress’ flag to be true or ‘version’ is changed in the reader.
//
int spinCount = 0;
do {
// this is violate read, following memory accesses can not be moved ahead of it.
currentversion = version;
b = lbuckets[bucketNumber];

// The contention between reader and writer shouldn’t happen frequently.
// But just in case this will burn CPU, yield the control of CPU if we spinned a few times.
// 8 is just a random number I pick.
if( (++spinCount) % 8 == 0 ) {
Thread.Sleep(1); // 1 means we are yeilding control to all threads, including low-priority ones.
}
} while ( isWriterInProgress || (currentversion != version) );
if (b.key == null) {
return null;
}
if (((b.hash_coll & 0x7FFFFFFF) == hashcode) &&
KeyEquals (b.key, key))
return b.val;
bucketNumber = (int) (((long)bucketNumber + incr)% (uint)lbuckets.Length);
} while (b.hash_coll < 0 && ++ntry < lbuckets.Length);
return null;
}

是的,各位读者请注意,这里存在一个伪自循环锁(pseudo-spin lock),并调用了 Threading.Sleep。

而在.NET 2.0 和泛型集合中,微软决定放弃集合的内部锁定机制。相反,要求任何锁定都必须在外部调用。我们在 Generic.Dictionary 类中可以发现更为简洁的代码。

// Copyright © Microsoft Corporation. All rights reserved.

private int FindEntry(TKey key) {
if( key == null) {
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
}
if (buckets != null) {
int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
}
}
return -1;
}

Mono 版本的 Hashtable 和 Dictionary 在实现上仍然是大相径庭,而且也不同于微软的实现。

// Copyright © 2004-2005 Novell, Inc ( http://www.novell.com )

public virtual Object this[Object key]
{
get
{
if (key == null)
throw new ArgumentNullException(“key”, “null key”);

Slot[] table = this.table;
int[] hashes = this.hashes;
uint size = (uint)table.Length;
int h = this.GetHash(key) & Int32.MaxValue;
uint indx = (uint)h;
uint step = (uint)((h >> 5) + 1) % (size - 1) + 1;

for (uint i = size; i > 0; i–)
{
indx %= size;
Slot entry = table[indx];
int hashMix = hashes[indx];
Object k = entry.key;
if (k == null)
break;

if (k == key || ((hashMix & Int32.MaxValue) == h
&& this.KeyEquals(key, k)))
{
return entry.value;
}

if ((hashMix & CHAIN_MARKER) == 0)
break;

indx += step;
}

return null;
}

而 Mono 的 dictionary 实现则为:

// Copyright © 2004 Novell, Inc ( http://www.novell.com)
// Copyright © 2005 David Waite
// Copyright © 2007 HotFeet GmbH ( http://www.hotfeet.ch )

public TValue this [TKey key] {
get {
if (key == null)
throw new ArgumentNullException (“key”);

// get first item of linked list corresponding to given key
int hashCode = hcp.GetHashCode (key);
int cur = table [(hashCode & int.MaxValue) % table.Length] - 1;
// walk linked list until right slot is found or end is reached
while (cur != NO_SLOT) {
// The ordering is important for compatibility with MS and strange
// Object.Equals () implementations
if (linkSlots [cur].HashCode == hashCode && hcp.Equals (keySlots [cur], key))
return valueSlots [cur];
cur = linkSlots [cur].Next;
}
throw new KeyNotFoundException ();
}

好了,现在你可以看到,四种方法本质上实现了同样的功能。毋庸置疑,使用 Sleep 命令的那种是最差的,至于哪一个最好,我想还得由你来决定。

查看英文原文: On the Evolution of the .NET Collections

2008-07-04 22:29816
用户头像

发布了 254 篇内容, 共 52.6 次阅读, 收获喜欢 2 次。

关注

评论

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

软件测试/测试开发全日制|Pytest结合Excel实现数据驱动

霍格沃兹测试开发学社

网易首款鸿蒙原生游戏《倩女幽魂》手游完成开发,商业化版本已就绪

新消费日报

🛠 开源即时通讯(IM)项目OpenIM源码部署指南

Geek_1ef48b

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

加密眼界

PreparedStatement实践和批处理实践

FunTester

Programming Abstractions in C阅读笔记:p242-p245

codists

数字化转型究竟是什么意思?

高端章鱼哥

数字化

可编程线性霍尔传感器 IC

攻城狮Wayne

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

石头财经

C 语言文件读取全指南:打开、读取、逐行输出

小万哥

程序人生 编程语言 软件工程 C/C++ 后端开发

文心大模型融入荣耀MagicOS!打造大模型“端云协同”创新样板

爱编程的喵喵

Kubernetes Pod配置:从基础到高级实战技巧

互联网工科生

Kubernetes

软件测试/测试开发全日制|Pytest结合yaml实现数据驱动

霍格沃兹测试开发学社

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

股市老人

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

大瞿科技

坎昆升级在即,ZKFair 已开启 ZKF 质押

股市老人

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

BlockChain先知

在线文档软件哪个好?5个好用的协同文档app推荐!

彭宏豪95

团队协作 在线文档 在线白板 在线协同文档 效率软件

软件测试/测试开发全日制培训|Pytest的异常处理

霍格沃兹测试开发学社

2023 IoTDB Summit:天谋科技高级开发工程师张金瑞《筑其形:如何轻松搞定 IoTDB 数据建模》

Apache IoTDB

如何利用 NFTScan Portfolio 功能分析钱包 NFT 持仓

NFT Research

NFT NFT\ NFTScan

🛠 开源即时通讯(IM)项目OpenIM源码部署指南

Geek_1ef48b

使用JMeter安装RabbitMQ测试插件的步骤

百度搜索:蓝易云

云计算 Linux 运维 RabbitMQ Jmeter

关于AI PC,英特尔CEO帕特·基辛格说了三个法则

E科讯

传统 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

西柚子

端侧AI的“春风化雨手”,翻开中国科技下一页

脑极体

AI

吃人血馒头 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

EOSdreamer111

软件测试/测试开发/全日制/测试管理丨Allure测试报告特点与优势

测试人

软件测试

从像素到洞见:图像分类技术的全方位解读

不在线第一只蜗牛

机器学习 深度学习 图像 项目开发

吃惯人血馒头的 VC 机构,是否还能在 Fair launch 的散户牛市中胜出?

长安区块链

2024-01-10:用go语言,给你一个下标从 0 开始的二维整数数组 pairs 其中 pairs[i] = [starti, endi] 如果 pairs 的一个重新排列 满足对每一个下标 i

福大大架构师每日一题

福大大架构师每日一题

.NET集合类型的发展_.NET_Jonathan Allen_InfoQ精选文章