Dan*_*dor 46 .net string memory-management
由于我正在计划一个将大量数据保存在内存中的应用程序,我希望有一种"紧凑"的字符串类,至少有一个字符串格式不超过字符串的零终止ASCII版本.
你知道任何这样的字符串类实现 - 它应该有一些实用函数,如原始字符串类.
编辑:
我需要对字符串进行排序并能够扫描它们,只是提到我将使用的一些操作.
理想情况下,它将与System.String源兼容,因此基本的搜索和替换操作将优化应用程序内存占用.
号码:
我可以拥有每条记录的100k记录,最多10个字符串,包含30-60个字符.所以:
100000x10x60 = 60000000 = 57mega字符.为什么不使用60兆公羊而不是120兆公羊？操作会更快,一切都会更紧.
树将用于搜索,但对我计划拥有的正则表达式扫描没有帮助.
Jon*_*eet 51
按你的数字去:
我可以拥有每条记录的100k记录,最多10个字符串,包含30-60个字符.
让我们从添加对象开销开始 - 由于不可避免的对象开销和长度,字符串占用大约20个字节(IIRC - 可能更多地在64位CLR上)加上实际数据.让我们再做一次数学运算:
使用字符串:20 + 120字节的100万个对象= 140MB
使用新类:20 + 60字节的100万个对象= 80MB
当然还有60MB的差异,但比例低于你的预期.你只节省了42%的空间而不是50%.
现在,你谈论更快的事情:鉴于CLR本身意识到string,我怀疑第三方课程无法匹配其某些操作的速度,你必须投入大量的努力让其他许多人保持同样的速度.不可否认,你将拥有更好的缓存一致性,如果你可以忽略文化问题,那么通过进行所有比较顺序也可以节省一些时间.
为了60MB,我不会打扰.现在这是一个微小的差异 - 考虑一下,为了弥补使用两种不同字符串类型的巨大额外成本,您需要通过减少多少客户来获得这些节省.
说完所有这些之后,我很想自己实施它作为像Edulinq这样的博客项目.不要指望几周或几个月有任何结果:)
编辑:我刚刚想到了另一个问题.我们上面得到的数字实际上并不正确......因为字符串类是特殊的.它将数据直接嵌入到对象中 - 与数组之外的任何其他数据类型不同,string实例的大小不固定; 它根据其中的数据而有所不同.
编写自己的AsciiString类,你将无法做到这一点 - 你必须在类中嵌入一个数组引用:
public class AsciiString
{
private readonly byte[] data;
}
这意味着您需要额外的4或8个字节用于引用(32或64位CLR)以及每个字符串的数组对象(16个字节,IIRC)的额外开销.
如果你像Java一样设计它,那么获取子字符串可以重用现有的字节数组(两个字符串可以共享),但是你需要一个额外的长度和偏移量AsciiString.您还会失去一些缓存一致性优势.
您可以只使用原始字节数组作为数据结构,并编写一堆扩展方法来对它们进行操作......但这样会很糟糕,因为那时你无法区分正常字节数组和意味着字节数组之间的区别表示ASCII字符串.
另一种可能性是创建一个这样的结构:
struct AsciiString
{
private readonly byte[] data;
...
}
这样可以让你再次强力打字,但你需要考虑以下事情:
AsciiString x = new AsciiString();
最终会得到一个空data引用.您可以有效地将其视为x空值,但它非常非惯用.
Nig*_*ler 13
我实际上遇到了类似的问题,但问题参数有些不同.我的应用程序涉及两种类型的字符串 - 相对较短的字符串,测量60-100个字符,较长的字符串,100-1000字节(平均值约为300).
我的用例还必须支持unicode文本,但是相对较小比例的字符串实际上具有非英语字符.
在我的用例中,我将每个String属性公开为本机String,但底层数据结构是一个包含unicode字节的byte [].
我的用例还需要搜索和排序这些字符串,获取子字符串和其他常见的字符串操作.我的数据集测量数以百万计.
基本实现看起来像这样:
byte[] _myProperty;
public String MyProperty
{
get
{
if (_myProperty== null)
return null;
return Encoding.UTF8.GetString(value);
}
set
{
_myProperty = Encoding.UTF8.GetBytes(value);
}
}
即使您进行搜索和排序,这些转换的性能也相对较小(约为10-15%).
这很好,但我想进一步减少开销.下一步是为给定对象中的所有字符串创建一个合并数组(一个对象将包含1个短字符串和1个长字符串,或4个短字符串和1个长字符串).所以每个对象都会有一个byte [],每个字符串只需要1个字节(保存它们的长度总是<256).即使你的字符串可以超过256,并且int仍然比字节[]的12-16字节开销便宜.
这减少了大部分字节[]开销,并且增加了一点复杂性但对性能没有额外影响(与所涉及的阵列复制相比,编码传递相对昂贵).
这个实现看起来像这样:
byte _property1;
byte _property2;
byte _proeprty3;
private byte[] _data;
byte[] data;
//i actually used an Enum to indicate which property, but i am sure you get the idea
private int GetStartIndex(int propertyIndex)
{
int result = 0;
switch(propertyIndex)
{
//the fallthrough is on purpose
case 2:
result+=property2;
case 1:
result+=property1;
}
return result;
}
private int GetLength(int propertyIndex)
{
switch (propertyIndex)
{
case 0:
return _property1;
case 1:
return _property2;
case 2:
return _property3;
}
return -1;
}
private String GetString(int propertyIndex)
{
int startIndex = GetStartIndex(propertyIndex);
int length = GetLength(propertyIndex);
byte[] result = new byte[length];
Array.Copy(data,startIndex,result,0,length);
return Encoding.UTF8.GetString(result);
}
所以getter看起来像这样:
public String Property1
{
get{ return GetString(0);}
}
setter具有相同的精神 - 将原始数据复制到两个数组中(0开始到startIndex,以及startIndex和length到length之间),并创建一个包含3个数组的新数组(dataAtStart + NewData + EndData)并设置数组的长度为适当的局部变量.
我仍然不满意节省的内存和每个属性的手动实现的非常繁重的工作,所以我构建了一个内存压缩分页系统,它使用惊人的快速QuickLZ来压缩整页.这让我对时间 - 内存权衡(基本上就是页面的大小)有很多控制权.
我的用例的压缩率(与更高效的byte []存储相比)接近50%(!).我使用每页大约10个字符串的页面大小并将相似的属性组合在一起(往往具有相似的数据).这增加了10-20%的额外开销(在编码/解码过程之上仍然需要).分页机制将最近访问的页面缓存到可配置的大小.即使没有压缩,此实现也允许您为每个页面的开销设置固定因子.我当前实现页面缓存的主要缺点是使用压缩它不是线程安全的(没有它就没有这样的问题).
如果你对压缩的分页机制感兴趣,请告诉我(我一直在寻找开源的借口).
我建议,鉴于你想要搜索存储的"字符串"值,你应该考虑是否是一个Trie结构,如Patricia Trie,或者为了更好的记忆摊销,是一个有向无环字图(指的是一个属性作为一个DAWG)会更好.
它们的构建需要更长的时间(尽管通常它们用于底层存储本身代表这种形式相当好的情况,允许预先快速构建)并且即使它们上的某些操作在算法上更优越,您可能会发现在您的现实世界中使用的东西实际上,只要有合理的重复次数,它们会显着降低数据的内存占用量.
这些可以被视为字符串实习的.net(以及java和许多其他托管语言)中提供的(内置)de duplification的概括.
如果您特别希望以字典方式保留字符串的顺序(因此您一次只需考虑一个字符或代码点),那么Patricia Trie可能是更好的选择,在DAWG之上实现排序会有问题.
如果您有特定的字符串域,则可以使用替代的,更深奥的解决方案,包括:
以随机访问字符串为代价,如果输入结果不符合预期,则实际使用更多内存的风险.霍夫曼编码往往在英文文本上运行良好,并且很容易实现,它的优点是只要字母的频率分布具有可比性,它的字典就可以在集合中的所有字体中进行分片.排序将再次成为问题.
如果你知道字符串很小,并且你可以用固定大小的值存储几乎相同(或完全相同)的大小(如果字符数在16或更小的范围内,则可以存在结构(如果需要)这里的使用限制将取决于您的确切用法,并且可能在很大程度上取决于您如何调整代码以便与此设计一起玩得很好)
您可以创建一个新的数据结构来保存这些,但我认为这是过度的.
但是,如果您有每个单词或常用短语的数组,则将索引存储为每个单词的数组.
然后你为每个单词支付4个字节,但是如果每个单词平均为3.6个字符,那么平均每个单词就节省了3.2个字节,因为你需要支付2个字节/字母一次/单词.
但是,为了进行搜索或排序,您必须至少在短时间内重建字符串才能获得巨大的性能提升.
您可能想重新考虑如何设计程序,因为有许多程序使用大量数据并且可以在相对受限的内存中运行.