如何提高C++中merkle root的计算速度? [英] How to improve the speed of merkle root calculation in C++?

查看：75
本文介绍了如何提高C++中merkle root的计算速度?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在尝试尽可能地优化默克尔根计算.到目前为止，我在 Python 中实现了它导致了这个问题 以及用 C++ 重写它的建议.

I am trying to optimise the merkle root calculation as much as possible. So far, I implemented it in Python which resulted in this question and the suggestion to rewrite it in C++.

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <streambuf>
#include <sstream>

#include <openssl/evp.h>
#include <openssl/sha.h>
#include <openssl/crypto.h>



std::vector<unsigned char> double_sha256(std::vector<unsigned char> a, std::vector<unsigned char> b)
{
    unsigned char inp[64];
    int j=0;
    for (int i=0; i<32; i++)
    {
        inp[j] = a[i];
        j++;
    }
    for (int i=0; i<32; i++)
    {
        inp[j] = b[i];
        j++;
    }

    const EVP_MD *md_algo = EVP_sha256();
    unsigned int md_len = EVP_MD_size(md_algo);
    std::vector<unsigned char> out( md_len );
    EVP_Digest(inp, 64, out.data(), &md_len, md_algo, nullptr);
    EVP_Digest(out.data(), md_len, out.data(), &md_len, md_algo, nullptr);
    return out;
}

std::vector<std::vector<unsigned char> > calculate_merkle_root(std::vector<std::vector<unsigned char> > inp_list)
{
   std::vector<std::vector<unsigned char> > out;
   int len = inp_list.size();
   if (len == 1)
   {
        out.push_back(inp_list[0]);
        return out;
   }
   for (int i=0; i<len-1; i+=2)
   {
        out.push_back(
            double_sha256(inp_list[i], inp_list[i+1])
        );
   }
   if (len % 2 == 1)
   {
        out.push_back(
            double_sha256(inp_list[len-1], inp_list[len-1])
        );
   }
   return calculate_merkle_root(out);
}



int main()
{
    std::ifstream infile("txids.txt");

    std::vector<std::vector<unsigned char> > txids;
    std::string line;
    int count = 0;
    while (std::getline(infile, line))
    {
        unsigned char* buf = OPENSSL_hexstr2buf(line.c_str(), nullptr);
        std::vector<unsigned char> buf2;
        for (int i=31; i>=0; i--)
        {
            buf2.push_back(
                buf[i]
            );
        }
        txids.push_back(
            buf2
        );
        count++;
    }
    infile.close();
    std::cout << count << std::endl;

    std::vector<std::vector<unsigned char> > merkle_root_hash;
    for (int k=0; k<1000; k++)
    {
        merkle_root_hash = calculate_merkle_root(txids);
    }
    std::vector<unsigned char> out0 = merkle_root_hash[0];
    std::vector<unsigned char> out;
    for (int i=31; i>=0; i--)
    {
        out.push_back(
            out0[i]
        );
    }

    static const char alpha[] = "0123456789abcdef";
    for (int i=0; i<32; i++)
    {
        unsigned char c = out[i];
        std::cout << alpha[ (c >> 4) & 0xF];
        std::cout << alpha[ c & 0xF];
    }
    std::cout.put('\n');

    return 0;
}

然而，与 Python 实现相比，性能更差(~4s):

However, the performance is worse compared to the Python implementation (~4s):

$ g++ test.cpp -L/usr/local/opt/openssl/lib -I/usr/local/opt/openssl/include -lcrypto
$ time ./a.out 
1452
289792577c66cd75f5b1f961e50bd8ce6f36adfc4c087dc1584f573df49bd32e

real      0m9.245s
user      0m9.235s
sys       0m0.008s

完整的实现和输入文件可以在这里找到:test.cpp 和 txids.txt.

The complete implementation and the input file are available here: test.cpp and txids.txt.

如何提高性能?默认情况下是否启用编译器优化?是否有比 openssl 更快的 sha256 库?

How can I improve the performance? Are the compiler optimizations enabled by default? Are there faster sha256 libraries than openssl available?

推荐答案

您可以做很多事情来优化代码.

There are plenty of things you can do to optimize the code.

以下是重点列表:

  • 编译器优化需要启用(在 GCC 中使用 -O3)；
  • std::array 可以用来代替较慢的动态大小的 std::vector(因为散列的大小是32)，为了清楚起见，甚至可以定义一个新的Hash类型；
  • 参数应该通过引用传递(C++默认通过复制传递参数)
  • 可以保留 C++ vectors 以预先分配内存空间并避免不需要的副本；
    • 必须调用
  • OPENSSL_free来释放OPENSSL_hexstr2buf的分配内存；
  • push_back 当大小是编译时已知的常量时，应避免使用；
  • 使用 std::copy 通常比手动复制更快(更干净)；
  • std::reverse 通常比手动循环更快(更干净)；
  • 散列的大小应该是 32，但可以使用断言来检查它是否正确；
  • count 不需要，因为它是 txids 向量的大小；
  • compiler optimizations need to be enabled (using -O3 in GCC);
  • std::array can be used instead of the slower dynamically-sized std::vector (since the size of a hash is 32), one can even define a new Hash type for clarity;
  • parameters should be passed by reference (C++ pass parameter by copy by default)
  • the C++ vectors can be reserved to pre-allocate the memory space and avoid unneeded copies;
  • OPENSSL_free must be called to release the allocated memory of OPENSSL_hexstr2buf;
  • push_back should be avoided when the size is a constant known at compile time;
  • using std::copy is often faster (and cleaner) than a manual copy;
  • std::reverse is often faster (and cleaner) than a manual loop;
  • the size of a hash is supposed to be 32, but one can check that using assertions to be sure it is fine;
  • count is not needed as it is the size of the txids vector;

这是结果代码:

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <streambuf>
#include <sstream>
#include <cstring>
#include <array>
#include <algorithm>
#include <cassert>

#include <openssl/evp.h>
#include <openssl/sha.h>
#include <openssl/crypto.h>

using Hash = std::array<unsigned char, 32>;

Hash double_sha256(const Hash& a, const Hash& b)
{
    assert(a.size() == 32 && b.size() == 32);

    unsigned char inp[64];
    std::copy(a.begin(), a.end(), inp);
    std::copy(b.begin(), b.end(), inp+32);

    const EVP_MD *md_algo = EVP_sha256();
    assert(EVP_MD_size(md_algo) == 32);

    unsigned int md_len = 32;
    Hash out;
    EVP_Digest(inp, 64, out.data(), &md_len, md_algo, nullptr);
    EVP_Digest(out.data(), md_len, out.data(), &md_len, md_algo, nullptr);
    return out;
}

std::vector<Hash> calculate_merkle_root(const std::vector<Hash>& inp_list)
{
   std::vector<Hash> out;
   int len = inp_list.size();
   out.reserve(len/2+2);
   if (len == 1)
   {
        out.push_back(inp_list[0]);
        return out;
   }
   for (int i=0; i<len-1; i+=2)
   {
        out.push_back(double_sha256(inp_list[i], inp_list[i+1]));
   }
   if (len % 2 == 1)
   {
        out.push_back(double_sha256(inp_list[len-1], inp_list[len-1]));
   }
   return calculate_merkle_root(out);
}

int main()
{
    std::ifstream infile("txids.txt");

    std::vector<Hash> txids;
    std::string line;
    while (std::getline(infile, line))
    {
        unsigned char* buf = OPENSSL_hexstr2buf(line.c_str(), nullptr);
        Hash buf2;
        std::copy(buf, buf+32, buf2.begin());
        std::reverse(buf2.begin(), buf2.end());
        txids.push_back(buf2);
        OPENSSL_free(buf);
    }
    infile.close();
    std::cout << txids.size() << std::endl;

    std::vector<Hash> merkle_root_hash;
    for (int k=0; k<1000; k++)
    {
        merkle_root_hash = calculate_merkle_root(txids);
    }
    Hash out0 = merkle_root_hash[0];
    Hash out = out0;
    std::reverse(out.begin(), out.end());

    static const char alpha[] = "0123456789abcdef";
    for (int i=0; i<32; i++)
    {
        unsigned char c = out[i];
        std::cout << alpha[ (c >> 4) & 0xF];
        std::cout << alpha[ c & 0xF];
    }
    std::cout.put('\n');

    return 0;
}

在我的机器上，此代码比初始版本快 3 倍，比 Python 实现快 2 倍.

On my machine, this code is 3 times faster than the initial version and 2 times faster than the Python implementation.

此实现在 EVP_Digest 中花费了 >98% 的时间.因此，如果您想要更快的代码，您可以尝试找到一个更快的散列库，尽管 OpenSSL 应该已经相当快了.当前代码已经成功地在主流 CPU 上每秒连续计算 170 万个哈希.这很好.或者，您也可以使用 OpenMP 并行化程序(这在我的 6 核机器上大约快 5 倍).

This implementation spends >98% of its time in EVP_Digest. As a result, if you want a faster code, you could try to find a faster hashing library although OpenSSL should be already pretty fast. The current code already succeed to compute 1.7 millions hashes per second in sequential on a mainstream CPU. This is quite good. Alternatively, you can also parallelize the program using OpenMP (this is roughly 5 times faster on my 6 core machine).

这篇关于如何提高C++中merkle root的计算速度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆