标签: contiguous

我正在阅读essisentals第8版的操作系统概念.当作者查看连续的内存分配和最差拟合时,作者说"分配最大的洞.再次,我们必须搜索整个列表,除非它按大小排序.这个策略产生最大的剩余空洞,这可能比从最合适的方法中获得较小的剩余孔."

所以我的问题是,什么时候离开最大的剩余洞更好的方法？

如何在没有C++中其他内存管理器(如Malloc/New)的帮助下,如何创建自定义MemoryManager来管理给定的连续内存块？

这里有一些更多的背景:

   MemManager::MemManager(void* memory, unsigned char totalsize)
   {
       Memory = memory;
       MemSize = totalsize;
   }

我需要能够使用MemManager分配和释放这个连续内存的块.构造函数以字节为单位给出块的总大小.

Allocate函数应该以字节为单位占用所需的内存量,并返回指向该内存块开头的指针.如果没有剩余内存,则返回NULL指针.

Deallocate函数应该接收指向必须释放的内存块的指针,并将其返回给MemManager以备将来使用.

请注意以下约束:

- 除了给它的内存块,MemManager不能使用任何动态内存

- 最初指定,MemManager不能使用其他内存管理器来执行其功能,包括new/malloc和delete/free

我已经在几次面试中收到了这个问题,但即使是几个小时的在线研究也没有帮助我,我每次都失败了.我已经找到了类似的实现,但它们都使用了malloc/new,或者是来自操作系统的通用和请求的内存,我不允许这样做.

请注意,我很乐意使用malloc/new和free/delete,并且使用它们时遇到的问题很少.

我尝试过以LinkedList方式利用节点对象的实现,这些实现指向分配的内存块并说明使用了多少字节.然而,在这些实现中,我总是被迫在堆栈中创建新节点并将它们插入到列表中,但是一旦它们超出范围,整个程序就会因地址和内存大小丢失而中断.

如果有人对如何实现这样的事情有某种想法,我将非常感激.提前致谢!

编辑:我忘了在我的原始帖子中直接指定这个,但是用这个MemManager分配的对象可以是不同的大小.

编辑2:我最终使用了同源内存块,由于下面的答案提供的信息,实际上很容易实现.没有指定有关实现本身的确切规则,因此我将每个块分成8个字节.如果用户请求超过8个字节,我将无法提供,但如果用户请求少于8个字节(但> 0),那么我会给予额外的内存.如果传入的内存量不能被8整除,那么最后会浪费内存,我认为这比使用更多内存要好得多.

是的，我最终会将它用于 DMA，但暂时将一致性放在一边。我有 64 位 BAR 寄存器，因此，AFAIK，所有 RAM（例如高于 4G）都可用于 DMA。

我正在寻找大约 64MB 的连续 RAM。是的，很多。

Ubuntu 16 和 18 具有CONFIG_CMA=y但未CONFIG_DMA_CMA在内核编译时设置。

我注意到，如果两者都设置（在内核构建时），我可以简单地调用dma_alloc_coherent，但是，出于逻辑原因，重新编译内核是不可取的。

这些机器将始终具有至少 32GB 的 RAM，不运行任何占用大量内存的东西，并且内核模块将在启动后不久加载，然后 RAM 变得明显碎片化，而且，AFAIK，没有其他东西使用 CMA。

我已经设置了内核参数 CMA=1G。（并尝试过 256M 和 512M）

# dmesg | grep cma
[    0.000000] Command line: BOOT_IMAGE=/boot/vmlinuz-4.4.170 root=UUID=2b25933c-e10c-4833-b5b2-92e9d3a33fec ro cma=1G
[    0.000000] Kernel command line: BOOT_IMAGE=/boot/vmlinuz-4.4.170 root=UUID=2b25933c-e10c-4833-b5b2-92e9d3a33fec ro cma=1G
[    0.000000] Memory: 65612056K/67073924K available (8604K kernel code, 1332K rwdata, 3972K rodata, 1484K init, 1316K bss, 1461868K reserved, 0K cma-reserved)

我试过了 …

我知道标准不强制std::vector分配连续的内存块,但所有实现都遵循这一点.

假设我希望创建一个多维静态数组的向量.为简单起见考虑2个维度,并考虑长度为N的向量.也就是说,我希望创建一个具有N个元素的向量int[5].

我可以确定所有N*5整数现在在内存中是连续的吗？所以我原则上可以通过知道第一个元素的地址来访问所有整数？这个实现依赖吗？

作为参考,我当前在连续内存块中创建2D数组的方法是首先创建一个长度为N的浮动*(动态)数组,在一个数组中分配所有N*5个浮点数,然后将每个第5个元素的地址复制到第一个数组float*.

我目前有以下函数来读取数据或原始数据的向量(_readStream是a std::ifstream):

template<typename IteratorType> 
inline bool MyClass::readRawData(
    const IteratorType& first, 
    const IteratorType& last, 
    typename std::iterator_traits<IteratorType>::iterator_category* = nullptr
    )
{
    _readStream.read(reinterpret_cast<char*>(&*first), (last-first)*sizeof(*first));
    return _readStream.good();
}

第一个问题:这个功能对你来说好吗？

当我们直接读取内存块,如果从内存块只会工作first到last是在内存中连续的.怎么检查？

由于我创建的算法,我有一个二维数组具有以下值,

String [2,12] array = {
    {"ab","ab","ab","FREE","me","me","me","FREE","mo","mo","FREE","FREE"},
    {"so","so","FREE","no","no","FREE","to","to","to","FREE","do","do"}
};

我希望随机地对数组中的数据进行随机播放,以便具有相同值的数据保持在一起但位置发生变化.请有人帮忙解决这个问题.

例如,如果要对数组进行洗牌,它应该是这样的,

 String [2,12] array = {
     {"me","me","me","FREE","so","so","FREE","mo","mo","FREE","do","do"},
     {"ab","ab","ab""FREE","to","to","to","FREE","no","no","FREE","FREE"}
 };

我想知道下面代码中的数组a和b是否在内存中是连续的:

int main() {
    int a[3];
    int b[3];

    return 0;
}

a[0],a[1]并且a[2]应该是连续的和相同的b,但是否有任何关于b将在哪里分配的保证a？

如果没有,有没有办法强迫a和b相互毗连？即,使它们在堆栈中彼此相邻分配.

C++20 对std::contiguous_iterator_tag. 一些 STL 算法（例如std::copy）可以在连续迭代器上表现得更好。但是，我不清楚程序员应该如何访问这个新功能。

为了论证起见，让我们假设我们有一个完全符合 C++20 的库实现。我想编写最简单的连续迭代器。

这是我的第一次尝试。

#include <iterator>

class MyIterator {
    int *p_;
public:
    using value_type = int;
    using reference = int&;
    using pointer = int*;
    using difference_type = int;
    using iterator_category = std::contiguous_iterator_tag;
    int *operator->() const;
    int& operator*() const;
    int& operator[](int) const;
    MyIterator& operator++();
    MyIterator operator++(int);
    MyIterator& operator--();
    MyIterator operator--(int);
    MyIterator& operator+=(int);
    MyIterator& operator-=(int);
    friend auto operator<=>(MyIterator, MyIterator) = default;
    friend int operator-(MyIterator, MyIterator);
    friend MyIterator operator+(MyIterator, int);
    friend MyIterator …

问题 ：

我偶然发现了一个对行业产生深远（且非常有影响力）影响的问题，并且似乎没有在任何地方记录：

似乎在 python 中，矩阵乘法（使用@或np.matmul）在 C 连续数组和 F 连续数组之间给出了不同的答案：

import platform
print(platform.platform()) # Linux-5.10.0-23-cloud-amd64-x86_64-with-glibc2.31
import numpy as np
print(np.__version__) # 1.23.5

np.random.seed(0) # Will work with most of seed, I believe
M, N = 10, 5

X_c = np.random.normal(size=M*N).reshape(M,N)
X_f = np.asfortranarray(X_c)
assert (X_c == X_f).all()

p = np.random.normal(size=N)
assert (X_c @ p == X_f @ p).all() # FAIL

据您所知，此问题是否记录在任何地方？

后果示例：

在某些情况下，这些错误可能会变得很大：

示例：在sklearn.linear_model.LinearRegression类中，fit在 F 连续的近奇异矩阵 X（通常来自 pandas DataFrame）的情况下，该方法将导致非常错误的参数。这可能会导致预测到处都是并且 R2 …

我有一个 X × Y 网格，其中的单元格包含 1（如果满足某个条件）或 0（如果不满足）。现在我想识别网格中至少有 N 个包含 1 的连续单元格的特征。连续单元格可以并排相邻，也可以对角相邻。我制作了一张图片来说明问题（请参阅链接），其中 N = 5。为了清楚起见，我省略了标记 0，它们位于未标记的单元格中。红色 1 属于我想要识别的特征，黑色 1 则不属于。期望的结果如图所示，但所有黑色的 1 都变成了 0。我使用 R，因此使用该语言的解决方案将非常受欢迎，但我很乐意接受其他语言。我在 R 库（例如 rgeos）中找不到任何具体内容，但也许我遗漏了一些东西。任何帮助表示感谢，谢谢！

这是创建的一个可重复的小示例

input.mat <- structure(c(1L, 1L, 0L, 0L, 0L, 1L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 
                         0L, 1L, 1L, 1L, 0L, 0L, 0L, 0L, 1L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 
                         1L, 0L, 0L, 1L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 1L, 0L, 1L, 0L, 1L, 
                         0L, 0L, 0L, 1L, …