内存效率更高的布尔值会有实际应用吗?
Would there be a practical application for a more memory efficient boolean?
我注意到布尔值占据了整个字节,尽管只需要 1 位。我在想我们是否可以有类似
的东西
struct smartbool{char data;}
,一次存储 8 个布尔值。
我知道检索数据会花费更多时间,但这种权衡在某些情况下是否具有实际应用价值?
我是否遗漏了布尔值的内存使用情况?
通常变量在字边界上对齐,内存使用与访问效率保持平衡。对于一次性布尔变量,以更密集的形式存储它们可能没有意义。
如果你确实需要一堆布尔值,你可以使用像这样的 BitSet 数据结构:https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/BitSet.html.
有一种数据库索引可以有效地存储布尔值:
https://en.wikipedia.org/wiki/Bitmap_index。 space 一个索引占用越少,就越容易保存在内存中。
已经有广泛使用的支持多个布尔值的数据类型,它们被称为整数。您可以使用按位运算以整数类型存储和检索多个布尔值,使用称为位掩码的位模式筛选出您不关心的位。
作为节省内存的优化,这种“打包”当然是可能的,有时也很有用。许多语言和库提供了一种使其方便的方法,例如std::vector<bool>
在 C++ 中就是这样实现的。
但是,只有当程序员知道它会发生并且特别想要它时才应该这样做。在速度上有一个权衡:如果使用位,那么设置/清除/测试特定的 bool
需要首先计算一个具有适当移位的掩码,现在设置或清除它需要读-修改-写而不是随便写一个。
而且在多线程程序中还有一个更严重的问题。像 C++ 这样的语言承诺不同的线程可以自由修改不同的对象,包括同一数组的不同元素,而不需要同步或导致 data race。例如,如果我们有
bool a, b; // not atomic
void thread1() { /* reads and writes a */ }
void thread2() { /* reads and writes b */ }
那么这应该可以正常工作。但是,如果编译器在同一个字节中设置 a
和 b
两个不同的位,则对它们的并发访问将是该字节上的数据竞争,并可能导致不正确的行为(例如,如果读取-修改-两个线程完成的写入是交错的)。使其安全的唯一方法是要求两个线程对其所有访问都使用原子操作,这通常要慢很多倍。如果编译器可以以这种方式自由打包 bool
,那么在整个程序中,对潜在共享 bool
的每个操作都必须是原子的。那将是非常昂贵的。
所以如果程序员想打包 bool
s 来节省内存,愿意承担速度问题,并且可以保证它们不会被并发访问,这很好。但他们应该意识到它正在发生,并控制它是否发生。
(事实上,有些人认为让 C++ 提供 vector<bool>
是一个错误,因为程序员必须知道它是 vector<T>
行为的一般规则的特殊例外一个 T
的数组,并且可以安全地同时访问向量的不同元素。也许他们应该让 vector<bool>
以天真的方式工作,并为打包版本赋予不同的名称,类似于std::bitset
.)
我注意到布尔值占据了整个字节,尽管只需要 1 位。我在想我们是否可以有类似
的东西struct smartbool{char data;}
,一次存储 8 个布尔值。
我知道检索数据会花费更多时间,但这种权衡在某些情况下是否具有实际应用价值? 我是否遗漏了布尔值的内存使用情况?
通常变量在字边界上对齐,内存使用与访问效率保持平衡。对于一次性布尔变量,以更密集的形式存储它们可能没有意义。
如果你确实需要一堆布尔值,你可以使用像这样的 BitSet 数据结构:https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/BitSet.html.
有一种数据库索引可以有效地存储布尔值: https://en.wikipedia.org/wiki/Bitmap_index。 space 一个索引占用越少,就越容易保存在内存中。
已经有广泛使用的支持多个布尔值的数据类型,它们被称为整数。您可以使用按位运算以整数类型存储和检索多个布尔值,使用称为位掩码的位模式筛选出您不关心的位。
作为节省内存的优化,这种“打包”当然是可能的,有时也很有用。许多语言和库提供了一种使其方便的方法,例如std::vector<bool>
在 C++ 中就是这样实现的。
但是,只有当程序员知道它会发生并且特别想要它时才应该这样做。在速度上有一个权衡:如果使用位,那么设置/清除/测试特定的 bool
需要首先计算一个具有适当移位的掩码,现在设置或清除它需要读-修改-写而不是随便写一个。
而且在多线程程序中还有一个更严重的问题。像 C++ 这样的语言承诺不同的线程可以自由修改不同的对象,包括同一数组的不同元素,而不需要同步或导致 data race。例如,如果我们有
bool a, b; // not atomic
void thread1() { /* reads and writes a */ }
void thread2() { /* reads and writes b */ }
那么这应该可以正常工作。但是,如果编译器在同一个字节中设置 a
和 b
两个不同的位,则对它们的并发访问将是该字节上的数据竞争,并可能导致不正确的行为(例如,如果读取-修改-两个线程完成的写入是交错的)。使其安全的唯一方法是要求两个线程对其所有访问都使用原子操作,这通常要慢很多倍。如果编译器可以以这种方式自由打包 bool
,那么在整个程序中,对潜在共享 bool
的每个操作都必须是原子的。那将是非常昂贵的。
所以如果程序员想打包 bool
s 来节省内存,愿意承担速度问题,并且可以保证它们不会被并发访问,这很好。但他们应该意识到它正在发生,并控制它是否发生。
(事实上,有些人认为让 C++ 提供 vector<bool>
是一个错误,因为程序员必须知道它是 vector<T>
行为的一般规则的特殊例外一个 T
的数组,并且可以安全地同时访问向量的不同元素。也许他们应该让 vector<bool>
以天真的方式工作,并为打包版本赋予不同的名称,类似于std::bitset
.)