0

How to implement a single byte based string?

Application uses a large list of words.
Words come from SQL and is varchar (single byte).
Each word also has in Int32 ID.
Download the words to: 

Dictionionary<Int32,string>

for performance.

Problem is the Dictionary gets so large that will get an out of memory exception.
We end up splitting up the data.
The app hits the list so much that hitting SQL for each request is not an option.
The database is already very active.
Dynamically paging into and out of the Dictionary is not an option - it is bound to ListView and with virtualiztion works great.
Words are only loaded at night - the user just needs a static list.
They use the words to search and process other data but they don't process the words.

Since it is char thought could just implement a single byte based word:

public class StringByte1252 : Object, IComparable, IComparable<StringByte1252>
{
    static Encoding win1252 = Encoding.GetEncoding("Windows-1252");

    public Int32 ID { get; private set; }
    public byte[] Bytes { get; private set; }

    public string Value { get { return win1252.GetString(Bytes); } }
    public Int32 Length { get { return Bytes.Length; } }

    public int CompareTo(object obj)
    {
        if (obj == null)
        {
            return 1;
        }
        StringByte1252 other = obj as StringByte1252;
        if (other == null)
        {
            throw new ArgumentException("A StringByte1252 object is required for comparison.", "obj");
        }
        return this.CompareTo(other);
    }
    public int CompareTo(StringByte1252 other)
    {
        if (object.ReferenceEquals(other, null))
        {
            return 1;
        }
        return string.Compare(this.Value, other.Value, StringComparison.OrdinalIgnoreCase);
    }
    public override bool Equals(Object obj)
    {
        //Check for null and compare run-time types.
        if (obj == null || !(obj is StringByte1252)) return false;
        StringByte1252 item = (StringByte1252)obj;
        return (this.Bytes == item.Bytes);
    }
    public override int GetHashCode() { return ID; }

    public StringByte1252(Int32 id, byte[] bytes) { ID = id; Bytes = bytes; } 
}

This above works but it is NOT more memory efficient than 

Dictionionary<Int32,string>

Dictionary with Int16 based characters actually uses slightly less memory.

Where did I go wrong?
Does a byte array take more space than the sum of the bytes?
Is there a way to achieve single byte string?

4

4 回答 4

3

一个数组在 64 位运行时大约有 50 个字节的开销。在 32 位运行时，它会少一点：可能是 40 字节。有标准的 .NET 分配开销（64 位运行时为 24 个字节），然后是数组的所有元数据：维数、长度等。您不能通过使用单个字节数组存储短来节省内存字符串。

一种方法是分配一个非常大的字节数组并将字符串存储在该数组中，UTF-8 编码。你的字典变成了一个Dictionary<int,int>，它Value是数组的索引。

我在我的文章Reducing Memory Required for Strings中展示了如何做到这一点。通过这种方式，我能够比正常的字符串分配节省大约 50%。有关更多详细信息，请参阅文章。

另一个问题是Dictionary开销大约是每个条目 24 个字节。如果你有一大堆小物件，那是相当昂贵的。您可以考虑改为制作结构列表，按 ID 对其进行排序，并使用二进制搜索。给你的不是 O(1) 访问Dictionary，但对于用户界面来说，它可能足够快。然后，您的开销将是每个条目 8 个字节。

该结构将类似于：

struct WordEntry
{
    public readonly int Id;
    public readonly int IndexIntoStringTable;
}
于 2013-04-18T19:43:17.740 回答
1

尽管 char 是字节大小的两倍，但如果字符串很长，您只会在内存占用方面获得显着差异。

内存以块的形式分配，例如 16 字节（可能因平台和实现而异）。这意味着一个字符长的字符串可能占用与六个字符长的字符串一样多的内存，因为两者都需要两个内存块来保存字符数据和字符串对象的开销。

考虑到字典中引用的开销、字符串对象的开销以及部分未使用的内存块的开销，平均而言，您需要在字符串中放入大约 16 个字符，然后才会有不到 50% 的开销。

由于开销如此之大，仅通过减小数据大小来减少内存占用是很困难的。

您可能会寻找一种解决方案，其中每个项目的开销较小，例如一个用于字符数据的巨型字符串（或字节数组），并为该大字符串中的每个字符串指定起始索引。

于 2013-04-18T19:43:41.570 回答
0

由于数组的构建方式，字节数组肯定会占用更多/与其内容之和一样多的空间。数组由特定大小的块组成。确实能够区分数组的不同元素，元素必须有固定的大小，所以数字不会混淆。这就像说您要存储最多 9999 的十进制数，因此为了能够“一起”存储它们，您必须使用前导零来填补空白，例如：1,5,32,1293,12 = 00010005003212930012。一个词是由字符组成的。为了能够表示一个字符，您需要找到可能使用的最少字符数，并从中定义数组的基本构造单元。由于字母表有26个字符，大写和小写加起来是52个，使用其他符号，您可能会得到少于 128 个可能性，从而导致您选择 7 位。内存由 8 位块（字节）组成，因此您应该解决这些问题并使用 ASCII 进行编码，或者找到一种方法来处理数据，以便每个字符仅使用 7 位，并且每第 8 个字符保存一个字节。我想有一些开放的解决方案，虽然我不知道。

字符串只是一个字符数组。在 c 中，字符串是 byte[]。尝试使用 byte[] 数组。

由于我目前正在运行 linux，因此我发现很难测试，但您也可以尝试使用：

byte[] bytes = Encoding.ASCII.GetBytes("Hello World!");
于 2013-04-18T19:33:07.600 回答
0

得出的结论是，一个简单的结构是将 char 存储为单字节的最佳内存执行者。

这是我的假设。
内存一次分配 4 个字节。
单个变量末尾的字节或不在 4 字节边界上的数组都被浪费了。

字节池消除了单个单词上浪费的字节，但代价是对池起点和字长的索引。

假设即使是字典 Int32，字符串也有浪费。
任何奇数长度的字符串都会浪费 16 个字节。

考虑 Int32 单词索引。
Int32 浪费了 1 个字节。
在池的情况下，池索引只有 Int32，所以很明显它不能保存 Int32 字。
对于 .NET 中的对象大小，有 4 GB 的限制。
字加索引的最佳情况是 8 个字节。
32(4GB) - 8 = 24
最大字数加索引数为 2 ** 24 = 16,777,216。

该结构使用索引中的一个字节作为一个字符。
一个字节就是一个字节。该结构不必存储长度，因为它可以从内容中导出长度。 

public struct Word1252bytes 
{
    static Encoding win1252 = Encoding.GetEncoding("Windows-1252");
    private UInt64 packed;
    private byte[] bytes;
    public Int32 Key { get { return (Int32)(packed & ((1 << 24) - 1)); } }
    private byte[] Bytes
    {
        get
        {
            // yes a lot of work to salage just one byte out of the key 
            // but a byte is a byte and the design objective is size
            byte[] bytesT = new byte[Length];
            bytesT[0] = (byte)((packed >> 24) & ((1 << 8) - 1));
            for (int i = 0; i < bytes.Length; i++) bytesT[i + 1] = bytes[i];
            return bytesT;
        }
    }
    public Int32 Length { get { return bytes.Length + 1; } }
    public String Value
    {
        get
        {
            return win1252.GetString(Bytes);
        }
    }
    public Word1252bytes(UInt64 Packed, byte[] Bytes) 
    { 
        packed = Packed;
        bytes = Bytes;
    }
}

如何打包

pack32 = (UInt32)(bits24wordI) | ((UInt32)charB[0] << 24);
byte[] bytesT = new byte[bits8wLen - 1];
for (int i = 1; i < bits8wLen; i++) bytesT[i - 1] = charB[i];
iWordsList.Add(new Word1252bytes(pack32, bytesT));

它快速补水。我的测试用例是 600 万字，Word1252bytes 的构建速度和字典一样快（大约 20 秒）

大小对比。
用字节池可以使用一个字节的字索引作为字长。
这将字长限制为 256，但在字符串池中节省了空间。

上述结构在每个单词大小上都与所述假设相关。索引是索引的大小。对于 Dict 和上述结构，它是 32。
对于字节池，它是 64 - 单词索引和池索引。
浪费是不在 4 字节边界上的字节。

        Index   Content Waste   Total
exactly 1               
dict16  dict16  32  16      16  64
word8   pool    64  8           72
word8   imbed   32  0       0   32

exactly 2               
dict16  dict16  32  32      0   64
word8   pool    64  16          80
word8   imbed   32  8       24  64

exactly 3               
dict16  dict16  32  48      16  96
word8   pool    64  24          88
word8   imbed   32  16      16  64

exactly 4               
dict16  dict16  32  64      0   96
word8   pool    64  32          96
word8   imbed   32  24      8   64

exactly 5               
dict16  dict16  32  80      16  128
word8   pool    64  40          104
word8   imbed   32  32  0   64

exactly 6               
dict 16 dict16  32  96      0   128
word 8  pool    64  48          112
word 8  imbed   32  40      24  96

exactly 7               
dict 16 dict16  32  112     16  160
word 8  pool    64  56          120
word 8  imbed   32  48      16  96

exactly 8               
dict 16 dict16  32  128     0   160
word 8  pool    64  64          128
word 8  imbed   32  56      8   96

exactly 9               
dict 16 dict16  32  144     16  192
word 8  pool    64  72          136
word 8  imbed   32  64      0   96

exactly 10              
dict 16 dict16  32  160      0  192
word 8  pool    64  80          144
word 8  imbed   32  72       24 128

exactly 254             
dict 16 dict16  32  4064    0   4096
word 8  pool    64  2032        2096
word 8  imbed   32  2024    24  2080

exactly 255             
dict 16 dict16  32  4080    16  4128
word 8  pool    64  2040        2104
word 8  imbed   32  2032    16  2080

exactly 256             
dict 16 dict16  32  4096    0   4128
word 8  pool    64  2048        2112
word 8  imbed   32  2040    8   2080

exactly 257             
dict 16 dict16  32  4112    16  4160
word 8  pool    64  2056        2120
word 8  imbed   32  2048    0   2080

字节池可以压缩的地方是搜索池中已经存在的字符串。在小字符串上，池处于 30% 的劣势，因此它需要有很高的匹配率。在较大的字符串上，找到匹配项的机会很低。问题是搜索时间。在超过 1,000,000 的列表中，即使 10 毫秒的搜索时间也是 10,000 秒 = 2.78 小时。

于 2013-04-23T21:13:19.430 回答