5
\$\begingroup\$

As part of a C++ library, I'm implementing a filter class for approximate set membership and abundance queries. The filter has two primary operations: add to store an element, and get to query the element's presence or abundance.

Under the hood, my filter class contains a fixed array of counters/buckets with d rows and approximately w columns. When an element is inserted, it is hashed and stored d times, once for each row. I'm using a very simple hashing scheme: the element value modulus the row length. If each row has a slightly different length, and if all the lengths are prime numbers, this ensures the hash functions are pairwise independent and preserves the filter's accuracy properties.

template<typename ElementType, typename CounterType, size_t maxcount>
class filter
{
    protected:
        std::vector<size_t> _cells_occupied;
        std::vector<std::vector<CounterType>> _arrays;
    public:
        explicit filter(std::vector<size_t> array_sizes);
        void add(ElementType element);
        CounterType get(ElementType element);
};

As shown above: using templates, I've implemented a single class that can be instantiated as a Bloom filter (1 bit per counter, set membership queries) or a Count-min sketch (8 bits per counter, element abundance queries).

The add and get operations are implemented as follows.

template<typename ElementType, typename CounterType, size_t maxcount>
void filter<ElementType, CounterType, maxcount>::add(ElementType element)
{
    for (size_t i = 0; i < _arrays.size(); i++){
        size_t index = element % _arrays[i].size();
        if (_arrays[i][index] == 0) {
            _cells_occupied[i] += 1;
        }
        if (_arrays[i][index] < maxcount) {
            _arrays[i][index] = _arrays[i][index] + 1;
        }
    }
}

template<typename ElementType, typename CounterType, size_t maxcount>
CounterType filter<ElementType, CounterType, maxcount>::get(ElementType element)
{
    CounterType mincount = _arrays[0][element % _arrays[0].size()];
    for (auto array : _arrays) {
        size_t index = element % array.size();
        CounterType count = array[index];
        if (count == 0) {
            // No need to check other arrays if any of them contain a 0
            return 0;
        }
        if (count < mincount) {
            mincount = count;
        }
    }
    return mincount;
}

See this gist for the full implementation.

I've written the following program to evaluate the filter's performance. It generates 100,000 random values, inserts them into the filter, and then does a second pass and queries the abundance of each element.

#include <cstdlib>
#include <chrono>
#include <iostream>
#include <vector>
#include "filter.hpp"

typedef std::chrono::time_point<std::chrono::system_clock> timepoint;

int main()
{
    srand(112358);
    std::vector<uint64_t> elements(0);
    for (int i = 0; i < 100000; i++) {
        int element = rand();
        elements.push_back(element);
    }

    filter<int, uint8_t, 255> counts({499979, 499973, 499969, 499957});
    std::cerr << "Being populating filter...";
    timepoint start = std::chrono::system_clock::now();
    for (auto element : elements) {
        counts.add(element);
    }
    timepoint end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cerr << "done! (" << elapsed.count() << " seconds elapsed)\n";

    std::cerr << "Begin querying filter...";
    start = std::chrono::system_clock::now();
    for (auto element : elements) {
        uint8_t count = counts.get(element);
        if (count > 1) {
            std::cout << "Element " << element << " appears " << (int)count << " times\n";
        }
    }
    end = std::chrono::system_clock::now();
    elapsed = end - start;
    std::cerr << "done! (" << elapsed.count() << "seconds elapsed)\n";

    return 0;
}

In this example, it takes takes approximately 0.01 seconds to store all 100k elements, but takes nearly 10 seconds to query the abundance of those same 100k elements.

I've intentionally avoided trying to do anything clever under the hood: I'm sure there's a lot that could be done with bitwise operations and raw pointers to make this a lot more efficient. But the 3-orders-of-magnitude difference in performance between add and get is startling. What could be causing this?

Of course, I'd be happy to entertain any other feedback on how to improve the implementation.

\$\endgroup\$
  • \$\begingroup\$ because you are doing cout which takes time \$\endgroup\$ – juvian May 10 '18 at 2:19
  • \$\begingroup\$ What does the profiler show? \$\endgroup\$ – JDługosz May 10 '18 at 2:30
5
\$\begingroup\$

Your issue with speed is here:

for (auto array : _arrays) {

Each iteration you are making a copy of the internal array from _arrays[x] into the array object. To prevent this use a reference.

for (auto const& array : _arrays) {

Review:

Avoid underscore as the first character of an identifier.

   std::vector<size_t> _cells_occupied;
    std::vector<std::vector<CounterType>> _arrays;

Even if you know the rules very few people do. So best avoided.

Since you use the modern timing routines you are aware of the modern library. So look up the modern random number generator.

// This is old and outdated.
srand(112358);

If you know how much data you are going to push into an array. Use the reserve() method to prevent reallocation several times.

std::size_t constexpr elementsSize = 100000;
std::vector<uint64_t> elements;
elements.reserve(elementsSize);  // Add this line.
for (int i = 0; i < elementsSize; i++) {
    int element = rand();
    elements.push_back(element);
}

Printing during a timing operation:

       std::cout << "Element " << element << " appears " << (int)count << " times\n";

This will throw off your results. Don't do it.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your comments, especially the reminder about the reference. I love the syntactic simplicity of auto but this isn't the first time this has bitten me in the back. \$\endgroup\$ – Daniel Standage May 10 '18 at 20:07
1
\$\begingroup\$

As juvian pointed out,

if (count > 1) {
        std::cout << "Element " << element << " appears " << (int)count << " times\n";
    }

appears inside the timed region.

When benchmarking, use a microbenchmark utility to just surround the actual code of interest. In this case, you can discard the answers you found without affecting those results, so just don’t print.

I’ve had cases where I wanted to keep results or logs as well as check time, and I got around it by storing the results in a pre-allocated array instead of writing to a file. Then afterwards, they can be saved all at once.

\$\endgroup\$

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.