1
\$\begingroup\$

I'm looking for a structure to store large amounts of strings (5k to 100k) and then test for existence of new strings against the previous inserted data, in the least possible amount of time (memory is mostly irrelevant). The structure would first be fully loaded at the program start, without any queries. After the building process, it would receive many many queries (about 200 million), then the program exists (no mid-execution destruction). Also, there are about 150-200 simultaneous independent structures in-memory.

Initially I though about a HashSet of string keys. This approach is amortized \$O(1)\$ with the data set size and \$O(K)\$ with the the query string size. However, the cost includes some collision handling and bucketing. I learned about Radix Trees, which perform the insert and query operations in the same time complexity as a hash set of strings, but with less overhead.

When I went to search the web for a good implementation, most implementations offer more functionality than needed, bringing some additional overhead. Some build the structure as a map instead of a set, or have operations like removing items and checking for prefixes, that are not needed at all and may incur some performance penalty on the two needed operations. Or worse, they do not deal with non-ASCII strings.

Since there are only two operations and the Radix Tree is not that complex, I thought I could roll it on my own. Even though I'm not proficient in C++, the project runs it (not to mention the performance needs).

Here is my current implementation:

#ifndef radixset_hpp
#define radixset_hpp

#include <string>

class radixset {
public:

   radixset() : isword(false), children(nullptr) { }

   ~radixset() {
      if (children != nullptr) {
         for(auto i = 0; i < 256; i++) {
            delete children[i];
         }
         delete children;
      }
   }


   void insert(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node->children == nullptr) {
            node->children = new radixset*[256];
         }
         node->children[c] = new radixset;
         node = node->children[c];
      }
      node->isword = true;
   }


   bool contains(std::string str) {
      radixset* node = this;
      for (unsigned char c : str) {
         if (node == nullptr || node->children == nullptr) {
            return false;
         }
         node = node->children[c];
      }
      return node->isword;
   }

private:
   bool isword;
   radixset** children;
};

#endif

And a basic set of tests:

#include "radixset.hpp"
#include <cassert>

int main() {
   radixset r = radixset{};

   assert(!r.contains(""));
   assert(!r.contains("abc"));
   assert(!r.contains("def"));

   r.insert("abc");
   r.insert("def");
   r.insert("");

   assert(r.contains("abc"));
   assert(r.contains("def"));
   assert(r.contains(""));
   assert(!r.contains("ab"));
   assert(!r.contains("defg"));

   assert(!r.contains("áý"));
   r.insert("áý");
   assert(r.contains("áý"));
}

The assertions all work as intended. Although every critic is welcome, I'm mostly looking for 1) performance increase, 2) the pointers here are really ugly (radixset** children, really?), a less headache-y/more modern version would be nice.

If it matters, my make runs the line:

g++ -Wall -std=c++11 radixset.hpp test.cpp -o output/test`

I'm on a Linux/Debian 8 system. I haven't yet spent time choosing compiler flags, don't bother with that. Also, I know the documentation is missing.

Side question: is the contains operation thread-safe? Since it only reads (not writing) members I'm inclined to guess so, but I find the C++ world so confusing...

\$\endgroup\$
  • \$\begingroup\$ It seems like your code has undefined behavior, because you have new[] and no delete[] \$\endgroup\$ – Incomputable Jun 1 '16 at 1:22
  • \$\begingroup\$ Will the input file fit in L3 cache? I believe it's around 3 MB. \$\endgroup\$ – Incomputable Jun 2 '16 at 7:16
  • \$\begingroup\$ @OlzhasZhumabek no, the largest input file is currently 15MB, and the input files are ever growing (not during a program execution, but in between executions). \$\endgroup\$ – Mephy Jun 2 '16 at 11:26
  • \$\begingroup\$ Is there a reason you can't store these large amounts of strings in a file, read the file into a buffer on program initialization, then use a standard library string search method to search for a duplicate word? It seems like this would reduce a lot of complexity with your code, and most likely improve speed as well. \$\endgroup\$ – syb0rg Jun 2 '16 at 14:48
  • \$\begingroup\$ @syb0rg what is the "standard library string search method"? The best solution for this problem I can find in the standard library in the hash set approach, as the question says. \$\endgroup\$ – Mephy Jun 2 '16 at 15:26
2
\$\begingroup\$

I think I'd start by structuring the code a bit differently. In particular, I'd define a RadixSet that holds the root of a tree, and provides the insert and contains members. Then there'd be a separate node type to represent the individual nodes in the tree:

class RadixTree
    class Node {
        // ...
    };
    // ...
};

Then I think I'd use a std::vector<Node *> instead of handling all the dynamic allocation manually:

std::vector<Node *> root;

I'd also use std::numeric_limits<unsigned char>::max(); instead of hard-coding 256 as the sizes for the arrays:

const int size = std::numeric_limits<unsigned char>::max();

With those, root.empty() is roughly equivalent to your current node==nullptr, insert (for example) ends up looking something generally similar to this:

void insert(std::string const &str, Node *node = root) {
    if (str.empty())
        return;

    for (unsigned char c : str) {
        auto &children = node->children;
        children.resize(size);
        if (children[c] == nullptr)
            children[c] = new Node;
        node = children[c];
    }
}

Node's destructor would look something like this:

~Node() { 
    for (auto n : children)
        delete n;
}

Since the objects being deleted (if any) are also Node objects, this will recursively delete the entire tree (i.e., as the Node's at the top level are destroyed, that will invoke the destructor for each of its child nodes, and so on. delete nullptr; is a nop, so we don't need to check for the pointers being non-null before we delete them.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions! The code performance is the same, but definitely prettier. A few corrections: only resize the vector if the size is zero, the empty string is valid (before early-returning, just set the isword flag), no need to have the extra optional parameter since there should be no way to access the children elements, and the vector elements should be deleted. Thanks for the input! \$\endgroup\$ – Mephy Jun 2 '16 at 13:50
  • \$\begingroup\$ @Mephy: Resizing the vector is a nop if it's already the same size, so leaving out a condition for that was intentional. You're right about the optional parameter--it's a leftover from a point where I was thinking of making the function recursive. Deleting the elements should be done in the dtor, which is obviously needed, but I didn't include here (its contents seemed pretty obvious). \$\endgroup\$ – Jerry Coffin Jun 2 '16 at 15:59
  • \$\begingroup\$ Constructors and destructors are definitely not obvious for non-C++ programmers. \$\endgroup\$ – Mephy Jun 2 '16 at 16:03
3
\$\begingroup\$

As Olzhas Zhumabek mentioned in the comments, the allocation and de-allocation is poorly done and cause undefined behavior, which will most likely cause a segmentation fault.

First, the allocation in the insert function: every time you insert, you're overwriting the previous node with the line node->children[c] = new radixset;, and it's a bug that your tests do not cover (happens in the case of inserting two words with the same prefix), so you haven't noticed it. Also, it would be better to allocate all the children upfront to avoid pointing to garbage; so, the insert function becomes:

void insert(std::string str) {
   radixset* node = this;
   for (unsigned char c : str) {
      if (node->children == nullptr) {
         node->children = new radixset*[256];
         for (auto i = 0; i < 256; i++) {
            node->children[i] = new radixset;
         }
      }
      node = node->children[c];
   }
   node->isword = true;
}

Then, the de-allocation. Whenever you allocate using new[] you must de-allocate using delete[], and not just delete. The allocations to the recursive radixset structure do not use the subscript allocation, so their delete also do not use the subscript.

~radixset() {
   if (children != nullptr) {
      for (auto i = 0; i < 256; i++) {
         delete children[i];
      }
      delete[] children;
   }
}

And don't forget to add the non-tested case to the test cases! (Note: I have changed the tests from cassert to GoogleTest).

TEST (RadixSetInsert, MatchingPrefixLongerFirst) {
   radixset r = radixset{};
   r.insert("abc");
   r.insert("ab");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}

TEST (RadixSetInsert, MatchingPrefixShorterFirst) {
   radixset r = radixset{};
   r.insert("ab");
   r.insert("abc");
   ASSERT_TRUE(r.contains("ab"));
   ASSERT_TRUE(r.contains("abc"));
}

Actually, the memory usage for sparse data sets is way too much in this implementation. To avoid allocating too much and still not pointing to garbage, point to nullptr and allocate as needed:

if (node->children == nullptr) {
    node->children = new radixset*[256];
    for (auto i = 0; i < 256; i++) {
        node->children[i] = nullptr;
    }
}
if (node->children[c] == nullptr) {
    node->children[c] = new radixset;
}

And check for nullptr properly when deleting the children members.

\$\endgroup\$
  • \$\begingroup\$ Okay, self reviewing is kind of awkward, but I discovered some nasty bugs. New answers are definitely welcome! \$\endgroup\$ – Mephy Jun 1 '16 at 17:56
  • \$\begingroup\$ The last addition gives segfault. Have you compiled and run it? \$\endgroup\$ – Incomputable Jun 2 '16 at 11:38
  • \$\begingroup\$ @OlzhasZhumabek it does not cause segfault for my test cases nor a real 750k words input, I've run it multiple times. In the destructor I'm checking for nullptr before deallocating, as said but not shown. \$\endgroup\$ – Mephy Jun 2 '16 at 11:40
  • \$\begingroup\$ I've put check node->children[c] == nulptr in contains function and it worked. Great job on fixing memory issue, cause it was eating 6+ gigs on my rig on 10'000 words. \$\endgroup\$ – Incomputable Jun 2 '16 at 11:42
0
\$\begingroup\$

EDIT: constructor now accepts a stream. It assumes that input contains only words. estimated_count will give only a clue, and will reserve the space so reallocations and copying won't happen frequently (actually there are only 23 reallocations if your implementations uses growth factor equal 2). Even if the word count is more than estimated_count, it will work.


In my opinion, the code mostly adds complexity. On the top of that, your implementation stores them as characters, not strings. This causes the tree to be gigantic. Given that the depth of tree is at least 4 with all nodes allocated, it will be 32 GBs. The real input can produce bigger tree.

I propose a very simple solution:

#include <vector>
#include <algorithm>
#include <string>


class Words
{
    std::vector<std::string> words;
    public:
    Words(std::ifstream& stream, std::size_t estimated_count = 750'000)
    {
        words.reserve(estimated_count);
        std::string buffer;
        while (stream >> buffer)
        {
            words.push_back(buffer);
        }
    }

    bool contains(const std::string& word) const
    {
        return std::binary_search(words.cbegin(), words.cend(), word);
    }

}; 

This gives you thread safety for free.

As answer for your side question: yes. But you could make it more explicit by making it a const function of the class.

bool contains(std::string str) const;
\$\endgroup\$
  • \$\begingroup\$ Why O(K * log n) when I can achieve O(K)? If I was looking for a standard implementation, std::unordered_set would overperform. There are about 40 billion queries (200 million entries * 200 datasets) per program execution, each query instruction does count. \$\endgroup\$ – Mephy Jun 2 '16 at 15:34
  • \$\begingroup\$ @Mephy, you are thinking in terms of algorithmic complexity. Couldn't benchmark real input due to memory constraints, but really, you want to give 32 GBs for arguable performance? Data retrieval is going to be really slow. Take a look at the video of C++ 2014 conference talk by Chandler Carruth. Look closely at stat difference of RAM and L1 cache. On top of that, adjacent memory retrieval is a way faster, giving you an infinite L4 cache. Herb Sutter. \$\endgroup\$ – Incomputable Jun 2 '16 at 15:52
  • \$\begingroup\$ I'm not able to compile your code (how should I be constructing and inserting elements?), but my current code for a 750000 words real sample uses only 31 MB, and inserts then queries each of them in 2.2 seconds. It is still worse than the std::unordered_set with 0.95 seconds. \$\endgroup\$ – Mephy Jun 2 '16 at 16:03
  • \$\begingroup\$ @Mephy, I can change constructor signature if you want me to, but I will need a way in which you retrieve the text. You need to pile words in a vector and the Words will move from it (it will perform shallow copy, copying size, capacity, pointer and may be some other small stuff), you can do it in constructor as well. Beware that vector moved from is in valid, but in undefined state. About size, on my input, generated by std::random_device the program crashes with out of memory (even paging doesn't help). \$\endgroup\$ – Incomputable Jun 2 '16 at 16:11
  • \$\begingroup\$ The input words are in a text file, line by line, which I'm reading with while (in >> word) { ... }. I've changed your code to call vector::push_back() on every word, and it runs on 1.1 seconds. I'll stick with unordered_set anyway (I knew I would probably). Thanks for the effort! \$\endgroup\$ – Mephy Jun 2 '16 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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