3
\$\begingroup\$

I've written a pretty basic algorithm to convert a string to a binary hash tree of its characters, where each character represents a leaf node. The hash tree itself is being stored in a vector.

If the number of leaf nodes is not a power of 2, I'm padding the number leaf nodes with empty substrings until the number of leaves is a power of 2.

I know there's likely a much better way to achieve this, but I'm having trouble picturing what that would look like. What are some alternate, potentially more performant approaches I may have overlooked?

Please disregard the chosen hash function (DJB2()).

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <math.h>
#include "../code/hash.h"

using namespace std;

struct Node {
    unsigned int hash;
};

bool IsPowerOfTwo(int c) {
    int a = ceil(log2(c));
    int b = floor(log2(c));

    return a == b;
}

int NextPowerOfTwo(int c) {
    int a = ceil(log2(c));

    return pow(2, a);
}

int main(int argc, char* argv[])
{

    string str = "abc34";

    vector<shared_ptr<Node>> nodes;

    int leaves = IsPowerOfTwo(str.length()) ? str.length() : NextPowerOfTwo(str.length());

    int total_nodes = 2 * leaves - 1;

    int non_leaves = total_nodes - leaves;

    // Add root + internal nodes to vector
    for(int i = 0; i < non_leaves; i++) {
        shared_ptr<Node> new_node(new Node);
        nodes.push_back(new_node);
    }

    // Generate the hash for leaf nodes + add to vector
    for (int i = 0; i < leaves; i++) {
        shared_ptr<Node> new_node(new Node);

        string substr = (i >= str.length()) ? "" : string (1, str[i]);

        new_node->hash = DJB2(substr);

        nodes.push_back(new_node);
    }

    // Generate the hash for internal and root nodes
    for (int i = non_leaves - 1; i >= 0; i--) {

        int left_child_index = 2 * i + 1;

        int right_child_index = 2 * i + 2;

        string left_child_hash = to_string(nodes[left_child_index]->hash);

        string right_child_hash = to_string(nodes[right_child_index]->hash);

        string child_hashes = left_child_hash + right_child_hash;

        nodes[i]->hash = DJB2(child_hashes);
    }

    // Output index of node in vector/tree and its corresponding hash value
    for (int i = 0; i < nodes.size(); i++) {
        cout << i << " : " << nodes[i]->hash << endl;
    }

    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ Defnitely more suited here ;) +1 \$\endgroup\$
    – YSC
    Dec 12, 2022 at 9:11

1 Answer 1

5
\$\begingroup\$

Use the C++ version of standard C header files

You are including <math.h>, but you should include <cmath>. Especially for the math functions, using the versions from std:: will make sure they automatically deduce whether they should return float or double.

Avoid unnecessary use of floating point arithmetic

Converting an integer to floating point, doing some operation, and then converting back is going to be slow. Floating point math is also not always exact, and this can cause problems if you assume it is. If possible, do everything using integer arithmetic where possible.

To see what you can do with just integers, look at Sean Eron Anderson's bit twiddling hacks, it includes how to check if an integer is a power of two and how to round up to the next power of two.

Even better, if you can use C++20, use std::has_single_bit() to check if something is a power of two, and std::bit_ceil() to round up to the nearest power of two.

Unnecessary use of std::shared_ptr

I don't see any reason to use std::shared_ptr for storing Nodes. You should be able to just write:

…
int non_leaves = total_nodes - leaves;
std::vector<Node> nodes(non_leaves);

This creates a vector of non_leaves Nodes. Then to add the leaf nodes:

for (int i = 0; i < leaves; ++i) {
    std::string substr = (i >= str.length()) ? "" : std::string(1, str[i]);
    nodes.emplace_back(DJB2(substr));
}

In the rest of the code, you can replace ->hash with .hash, since the elements of nodes` are no longer pointers.

Use .reserve()

Since STL containers do not know up front how many elements you are going to place in them, they start out small and allocate more memory later, and for std::vector is also has to move elements from the old to the new memory region each time it grows. But if you know up front how many elements you are going to store, you can call .reserve() so it can do one big allocation up front:

std::vector<Node> nodes(…);
nodes.reserve(total_nodes);

Use '\n' instead of std::endl

Prefer to use '\n' instead of std::endl; the are mostly equivalent, but the latter also forces the output to be flushed, which is often unnecessary and can be bad for performance.

Suboptimal calculation of internal node hash values

Regardless of the performance of DJB2() itself, one issue is that for the internal nodes, you are converting indices to strings, concatenating those strings, and then hashing the result of that. That is not efficient, and it also has some issues. For example, consider these scenarios:

  • `left_child_hash = "123"; right_child_hash = "45";
  • `left_child_hash = "12"; right_child_hash = "345";

The child hashes in the second case are clearly different from the first case, but the concatenation is the same. While hash functions don't guarantee uniqueness, so it's probably not a big problem, you are actually providing less information to the hash function than you could, so it's going to perform slightly worse.

One solution would be to do a bitwise copy of the integers into a std::string and hash that. Making use of the fact that the two child hash values are already consecutive inside nodes:

std::string child_hashes(2 * sizeof(Node));

for (int i = non_leaves - 1; i >= 0; --i) {
    std::copy_n(reinterpret_cast<char*>(&nodes[2 * i + 1]), 2 * sizeof(Node), child_hashes.data());
    nodes[i].hash = DJB2(child_hashes);
}

Make use of std::string_view if possible

It would be nice if DJB2() would take a std::string_view as an argument. This would avoid some copies that your code is currently making, like substr, and even the std::copy_n() into child_hashes in the example above.

Pre-compute commonly used hash values

While the compiler might be able to optimize this for you if it can inline DJB2(), you can help it yourself by pre-computing the hash of the empty string:

Node empty_node{DJB2("")};

for (int i = 0; i < leaves; ++i) {
    if (i >= str.length()) {
        nodes.push_back(empty_node);
    } else {
        nodes.emplace_back(DJB2(str.substr(i, 1)));
    }
}

Or even better, remove the if entirely and just loop up to str.length() and pad the vector afterwards:

for (int i = 0; i < str.length(); ++i) {
    nodes.emplace_back(DJB2(str.substr(i, 1)));
}

nodes.insert(nodes.back(), leaves - str.length(), DJB2(""));

Also note that if str is very large, you will likely calculate the hash of the same character multiple times. You could then speed up this part by pre-computing all possible hashes of a char, or by creating a simple cache.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.