c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法

coder 2023-06-04 原文

我有一个 std::vector<std::vector<double>>我试图尽快转换为单个连续 vector 。我的 vector 的形状大约为 4000 x 50 .

问题是，有时我需要以列为主连续顺序的输出 vector (只是连接我的 2d 输入 vector 的内部 vector )，有时我需要以行为主连续顺序的输出 vector ，实际上需要转置。

我发现一个简单的 for 循环转换为列主 vector 的速度非常快:

auto to_dense_column_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[i * n_row + j] = vec[i][j];
    return out_vec;
}

但显然，由于所有缓存未命中，类似的方法对于逐行转换来说非常慢。因此，对于逐行转换，我认为促进缓存局部性的阻塞策略可能是我最好的选择:

auto to_dense_row_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[i * n_col + j] = column[i];
            }
        }
    }
    return out_vec;
}

这比行优先转换的朴素循环快得多，但仍然比输入大小的朴素列优先循环慢几乎一个数量级。

我的问题是 ，是否有更快的方法将 double vector 的(列主) vector 转换为单个连续的行主 vector ？我正在努力推理这段代码的速度限制应该是多少，因此我怀疑我是否遗漏了一些明显的东西。我的假设是阻塞会给我一个比它实际提供的更大的加速。

该图表是使用 QuickBench 生成的(并在我的机器上本地使用 GBench 进行了一些验证)，代码如下:(Clang 7、C++20、-O3)

auto to_dense_column_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[i * n_row + j] = vec[i][j];
    return out_vec;
}

auto to_dense_row_major_naive(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    for (size_t i = 0; i < n_col; ++i)
        for (size_t j = 0; j < n_row; ++j)
            out_vec[j * n_col + i] = vec[i][j];
    return out_vec;
}

auto to_dense_row_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[i * n_col + j] = column[i];
            }
        }
    }
    return out_vec;
}

auto to_dense_column_major_blocking(std::vector<std::vector<double>> const & vec)
    -> std::vector<double>
{
    auto n_col = vec.size();
    auto n_row = vec[0].size();
    std::vector<double> out_vec(n_col * n_row);
    size_t block_side = 8;

    for (size_t l = 0; l < n_col; l += block_side) {
        for (size_t k = 0; k < n_row; k += block_side) {
            for (size_t j = l; j < l + block_side && j < n_col; ++j) {
                auto const &column = vec[j];
                for (size_t i = k; i < k + block_side && i < n_row; ++i)
                    out_vec[j * n_row + i] = column[i];
            }
        }
    }
    return out_vec;
}

auto make_vecvec() -> std::vector<std::vector<double>>
{
  std::vector<std::vector<double>> vecvec(50, std::vector<double>(4000));
  std::mt19937 mersenne {2019};
  std::uniform_real_distribution<double> dist(-1000, 1000);
  for (auto &vec: vecvec)
   for (auto &val: vec)
       val = dist(mersenne);
  return vecvec;
}

static void NaiveColumnMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_column_major_naive(vecvec));
  }
}
BENCHMARK(NaiveColumnMajor);

static void NaiveRowMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_row_major_naive(vecvec));
  }
}
BENCHMARK(NaiveRowMajor);

static void BlockingRowMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_row_major_blocking(vecvec));
  }
}
BENCHMARK(BlockingRowMajor);

static void BlockingColumnMajor(benchmark::State& state) {
  // Code before the loop is not measured

  auto vecvec = make_vecvec();
  for (auto _ : state) {
    benchmark::DoNotOptimize(to_dense_column_major_blocking(vecvec));
  }
}
BENCHMARK(BlockingColumnMajor);

最佳答案

首先，每当某些东西被限定为“显然”时，我都会畏缩。这个词经常用来掩盖一个人在推理中的缺点。

But obviously a similar approach is very slow for row-wise conversion, because of all of the cache misses.

我不确定哪个应该是显而易见的:逐行转换会很慢，或者由于缓存未命中而变慢。无论哪种情况，我都觉得这并不明显。毕竟，这里有两个缓存注意事项，不是吗？一读一写？我们从阅读的角度来看代码:
row_major_naive

for (size_t i = 0; i < n_col; ++i)
    for (size_t j = 0; j < n_row; ++j)
        out_vec[j * n_col + i] = vec[i][j];

连续读取来自 vec是连续内存的读取:vec[i][0]其次是 vec[i][1]等，非常适合缓存。所以...缓存未命中？减缓？ :) 也许不那么明显。
尽管如此，还是可以从中得到一些启示。只有声称“显然”是错误的。存在非局部性问题，但它们发生在写入端。 (连续写入被 50 个 double 值的空间所抵消。)经验测试证实了缓慢。所以也许一个解决方案是翻转被认为是“明显”的东西？
行专业翻转

for (size_t j = 0; j < n_row; ++j)
    for (size_t i = 0; i < n_col; ++i)
        out_vec[j * n_col + i] = vec[i][j];

我在这里所做的只是反转循环。从字面上交换这两行代码的顺序，然后调整缩进。现在连续读取可能无处不在，因为它们从不同的 vector 中读取。但是，连续写入现在是对连续的内存块。从某种意义上说，我们的处境和以前一样。但就像以前一样，在假设“快”或“慢”之前应该先衡量性能。
NaiveColumnMajor:3.4 秒
NaiveRowMajor:7.7 秒
翻转行主要:4.2 秒
BlockingRowMajor:4.4 秒
BlockingColumnMajor:3.9 秒
仍然比朴素的列主要转换慢。但是，这种方法不仅比 naive row major 快，而且也比 快。阻塞 行专业。至少在我的电脑上(使用 gcc -O3 显然 :P 迭代数千次)。里程可能会有所不同。我不知道花哨的分析工具会说什么。关键是有时越简单越好。
对于 funsies，我做了一个测试，其中维度交换了(从 4000 个元素的 50 个 vector 更改为 50 个元素的 4000 个 vector )。所有方法都以这种方式受到伤害，但“NaiveRowMajor”受到的打击最大。值得注意的是，“翻转行专业”落后于阻塞版本。因此，正如人们所期望的那样，适合这项工作的最佳工具取决于具体的工作内容。
NaiveColumnMajor:3.7 秒
NaiveRowMajor: 16 秒
翻转行主要:5.6 秒
BlockingRowMajor:4.9 秒
BlockingColumnMajor:4.5 秒
(顺便说一句，我还尝试了阻塞版本的翻转技巧。变化很小 - 大约 0.2 - 与翻转天真的版本相反。也就是说，对于问题的“翻转阻塞”比“阻塞”慢50-of-4000 vector ，但对于我的 4000-of-50 变体更快。微调可能会改善结果。)

更新:我对阻塞版本的翻转技巧进行了更多测试。这个版本有四个循环，所以“翻转”不像只有两个循环那样直接。看起来交换外部两个循环的顺序对性能不利，而交换内部两个循环的顺序是好的。 (最初，我已经完成了这两项工作，但结果喜忧参半。)当我只交换内部循环时，我测量了 。 3.8 秒 (在 4000-of-50 场景中为 4.1 秒)，使其成为我测试中最好的行优先选项。
排大杂种

for (size_t l = 0; l < n_col; l += block_side)
    for (size_t i = 0; i < n_row; ++i)
        for (size_t j = l; j < l + block_side && j < n_col; ++j)
            out_vec[i * n_col + j] = vec[j][i];

(交换内循环后，我合并了中间循环。)
至于这背后的理论，我猜这相当于一次尝试写入一个缓存块。一旦一个块被写入，在它们从缓存中弹出之前尝试重用 vector (vec[j])。用完这些源 vector 后，转到一组新的源 vector ，再次一次写入完整块。

关于c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55232880/

有关c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法的更多相关文章

ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2
我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div
ruby - 如何从 ruby 中的字符串运行任意对象方法？ - 2
总的来说，我对ruby还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用
ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
ruby-on-rails - 在 Rails 中将文件大小字符串转换为等效千字节 - 2
我的目标是转换表单输入，例如“100兆字节”或“1GB”，并将其转换为我可以存储在数据库中的文件大小(以千字节为单位)。目前，我有这个:defquota_convert@regex=/([0-9]+)(.*)s/@sizes=%w{kilobytemegabytegigabyte}m=self.quota.match(@regex)if@sizes.include?m[2]eval("self.quota=#{m[1]}.#{m[2]}")endend这有效，但前提是输入是倍数(“gigabytes”，而不是“gigabyte”)并且由于使用了eval看起来疯狂不安全。所以，功能正常，
ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2
我正在尝试设置一个puppet节点，但rubygems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由rubygems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby
ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2
我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..
ruby - 使用 ruby 将 HTML 转换为纯文本并维护结构/格式 - 2
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。最佳答案首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
Ruby 方法() 方法 - 2
我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco
ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
ruby - 将数组的内容转换为 int - 2
我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法

有关c++ - 将 vector vector 转换为具有相反存储顺序的单个连续 vector 的更快方法的更多相关文章

随机推荐