string-search-benchmark.cc

Go to the documentation of this file.

// Copyright 2012 Cloudera Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include "util/benchmark.h"
#include "util/cpu-info.h"
#include "runtime/string-search.h"
#include "experiments/string-search-sse.h"

#include "common/names.h"

using namespace impala;

// Benchmark tests for string search.  This is probably a science of its own
// but we'll run some simple tests.  (We can't use libc strstr because our
// strings are not null-terminated and also, it's not that fast).
// Results:
// String Search:        Function                Rate          Comparison
// ----------------------------------------------------------------------
//                         Python               81.93                  1X
//                           LibC               262.2              3.201X
//            Null Terminated SSE               212.4              2.592X
//        Non-null Terminated SSE               139.6              1.704X

struct TestData {
  vector<StringValue> needles;
  vector<StringValue> haystacks;
  int matches;
  vector<string> strings;       // Memory store for allocated strings
};

void TestLibc(int batch_size, void* d) {
  TestData* data = reinterpret_cast<TestData*>(d);
  for (int i = 0; i < batch_size; ++i) {
    data->matches = 0;
    for (int n = 0; n < data->needles.size(); ++n) {
      char* needle = data->needles[n].ptr;
      for (int iters = 0; iters < 10; ++iters) {
        for (int h = 0; h < data->haystacks.size(); ++h) {
          if (strstr(data->haystacks[h].ptr, needle) != NULL) {
            ++data->matches;
          }
        }
      }
    }
  }
}

void TestPython(int batch_size, void* d) {
  TestData* data = reinterpret_cast<TestData*>(d);
  for (int i = 0; i < batch_size; ++i) {
    data->matches = 0;
    for (int n = 0; n < data->needles.size(); ++n) {
      StringSearch needle(&(data->needles[n]));
      for (int iters = 0; iters < 10; ++iters) {
        for (int h = 0; h < data->haystacks.size(); ++h) {
          if (needle.Search(&(data->haystacks[h])) != -1) {
            ++data->matches;
          }
        }
      }
    }
  }
}

void TestImpalaNullTerminated(int batch_size, void* d) {
  TestData* data = reinterpret_cast<TestData*>(d);
  for (int i = 0; i < batch_size; ++i) {
    data->matches = 0;
    for (int n = 0; n < data->needles.size(); ++n) {
      // Exercise the null-terminated path.
      StringSearchSSE needle(data->needles[n].ptr);
      for (int iters = 0; iters < 10; ++iters) {
        for (int h = 0; h < data->haystacks.size(); ++h) {
          if (needle.Search(data->haystacks[h]) != -1) {
            ++data->matches;
          }
        }
      }
    }
  }
}

void TestImpalaNonNullTerminated(int batch_size, void* d) {
  TestData* data = reinterpret_cast<TestData*>(d);
  for (int i = 0; i < batch_size; ++i) {
    data->matches = 0;
    for (int n = 0; n < data->needles.size(); ++n) {
      // Exercise the non null-terminated path.
      StringSearchSSE needle(&(data->needles[n]));
      for (int iters = 0; iters < 10; ++iters) {
        for (int h = 0; h < data->haystacks.size(); ++h) {
          if (needle.Search(data->haystacks[h]) != -1) {
            ++data->matches;
          }
        }
      }
    }
  }
}

// This should be tailored to represent the data we expect.
// Some algos are better suited for longer vs shorter needles, finding the string vs.
// not finding the string, etc.
// For now, pick data that mimicks the grep data set.
void InitTestData(TestData* data) {
  vector<string> needles;
  vector<string> haystacks;

  needles.push_back("xyz");

  // From a random password generator:
  // https://www.grc.com/passwords.htm
  haystacks.push_back("d1h2POju5AG3zCxiBNKBxdzLdW7VfPkgvHDRLK2o78pGu4eywZ5mmmsV1LscqIH");
  haystacks.push_back("Xv7rmDx3ksECRPg94mPLI1gQjRIviZNINZwbDsvcyNAf7q4pzGQ6JHUqYHxFk0x");
  haystacks.push_back("cI8f2V9cYjmE70ruUeST9Arty7B8iKLiF4DaXhY4nF7OmXZOKRBVPd5cmjxiDRw");
  haystacks.push_back("3cb7QCWJ7QzNSwaXQQIByo7is1b3YPTx9u0ZmRV0IJEKJE2z2oMaKgzeA1ny7hx");
  haystacks.push_back("teRFhdOc5HrGvXUo1yGZSUc46hCVLjVzGaK37vfGAsuCpiji2R4YQ7Y4FN2O3lu");
  haystacks.push_back("xecRm4HYLTfhQgPQHTIhWQKNGJcAUYCziDJQlbAitVHC9ClbbcEkVrXsFSpVrx9");
  haystacks.push_back("M1k4su3sxpcBl8SQgnF6LOD1fNjTrQQW84vLofF39IbY4gTVpsHIlon8mbJ74D7");
  haystacks.push_back("dMROjEop61WoHNSegkiw7o1uIM5xgccf9SRhIEOnq9CoM7e0KatpjAmGLlANggK");
  haystacks.push_back("OIPM3iTT40sSkCTfDOjK4BSHZvV0xazTXarwYhyQEu5aGn7XeCABezJhbO1X8rr");
  haystacks.push_back("0YyLBoITUS7Mxfo3o44j4eEdWqwx6Um5EkUzIo7c0ETYfnkcaHsYcpT5Xn3coyE");
  haystacks.push_back("LzOFXp8ekVkeBy6Br9rRefzDDA30SLkvV3gGochoKGUkS0oj9fANBfOSBeyNypm");
  haystacks.push_back("uYDMZ4SNIh6XwBQcGCS3AQ5h5c2iyaPS70r4emPheC3hQhM84zwsMovByLNecTW");
  haystacks.push_back("EFY8GtkUkXRJQr3ZjANKhUFXTmnA2S4V6hTKeeskQhlUA65lTCO0PpyZxL8kyVE");
  haystacks.push_back("fgU8K01JtTn3UldvO9jAywDEN4HW5PwCFEJ4pwSwHfec6HsBN5rzzhQ2Tn4QDxE");
  haystacks.push_back("TMLE6UzW3CUUogfRFjZooP1eCZn05bI6NsWL67fOmwYhZND1nuAASG0ZhGFBdZH");

  // Contains the key in the beginning/middle/end
  haystacks.push_back("of9VxyzzWca0GBs8CrFsDIvi8yWCkRTRRL7X4TlMhPfRAWPOZfRVwybJoYQhslJ");
  haystacks.push_back("iEO7zz7wWm4LmvumisOwPRUzv9xyzhI7omKDlLYM7Vao9pggACVgDJBhAzDkcJp");
  haystacks.push_back("tQJzS0SiXRElwq1QEBhy0gGGii9xAcQbTIrt4QcGMViyOx4lfZ73zZ5XHxyzk1V");
  haystacks.push_back("tQJzS0SiXRElwq1QEBhy0gGGii9xAcQbTIrt4QcGMViyOx4lfZ73zZ5XHyzaxyz");

  for (int i = 0; i < needles.size(); ++i) {
    StringValue v(const_cast<char*>(needles[i].c_str()), needles[i].size());
    data->needles.push_back(v);
    data->strings.push_back(needles[i]);
  }
  for (int i = 0; i < haystacks.size(); ++i) {
    StringValue v(const_cast<char*>(haystacks[i].c_str()), haystacks[i].size());
    data->haystacks.push_back(v);
    data->strings.push_back(haystacks[i]);
  }
}

int main(int argc, char **argv) {
  CpuInfo::Init();
  cout << Benchmark::GetMachineInfo() << endl;

  TestData data;
  InitTestData(&data);

  Benchmark suite("String Search");
  suite.AddBenchmark("Python", TestPython, &data);
  suite.AddBenchmark("LibC", TestLibc, &data);
  suite.AddBenchmark("Null Terminated SSE", TestImpalaNullTerminated, &data);
  suite.AddBenchmark("Non-null Terminated SSE", TestImpalaNonNullTerminated, &data);
  cout << suite.Measure();

  return 0;
}