История изменений

Исправление i-rinat, 29.02.20 18:25 (текущая версия) :

Набросал с хешами, получилось в 10 раз быстрее. Не параллелится, правда.

#include <omp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ARRAY_SIZE UINT64_C(100000)
#define HAYSTACK_LENGTH UINT64_C(100)
#define NEEDLE_LENGTH UINT64_C(20)
#define NUM_SEARCHES UINT64_C(1000)
#define BLOOM_ORDER UINT64_C(20)
#define BLOOM_SZ (UINT64_C(1) << BLOOM_ORDER)
#define BLOOM_HASHCOUNT 2
#define BLOOM_MAGIC 0x9747b28c
#define NUM_THREADS 1

typedef uint8_t u8;
typedef uint32_t u32;

static u32 mm2(const void *key, u32 len, const u32 seed) {
  const u32 *data = key;
  return *data ^ seed;
}

static void bloom_add(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    bloom[x / 32] |= 1 << (x % 32);
  }
}

static u32 bloom_has(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);
  u32 hits = 0;

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    hits = !!(bloom[x / 32] & (1 << (x % 32)));
  }

  return hits == BLOOM_HASHCOUNT;
}

int main(void) {

  static const u8 xlat[] = //
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghij"
      "klmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrst"
      "uvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyzABCD"
      "EFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefgh";

  for (size_t try = 0; try < 10; try ++) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    u8 **array = malloc(sizeof(u8 *) * ARRAY_SIZE);
    u32 *bloom = calloc(1, BLOOM_SZ / 8);
    u32 seed = time(NULL);

    for (size_t k = 0; k < ARRAY_SIZE; k++) {
      u8 *hs = malloc(HAYSTACK_LENGTH + 1);
      for (size_t j = 0; j < HAYSTACK_LENGTH; j += sizeof(u32)) {
        const u32 r = rand_r(&seed);
        *(u32 *)(hs + j) = xlat[(r >> 24)] << 24 |
                           xlat[(r >> 16) & 0xffu] << 16 |
                           xlat[(r >> 8) & 0xffu] << 8 | xlat[r & 0xffu];
      }
      for (size_t j = 0; j < HAYSTACK_LENGTH - NEEDLE_LENGTH; j++)
        bloom_add(bloom, hs + j, NEEDLE_LENGTH);
      hs[HAYSTACK_LENGTH] = 0;
      array[k] = hs;
    }

    char needle[NEEDLE_LENGTH + 1];
    for (size_t k = 0; k < NEEDLE_LENGTH; k++)
      needle[k] = xlat[k & 0xffu];
    needle[NEEDLE_LENGTH] = 0;

    size_t count = 0;
    for (size_t iter = 0; iter < NUM_SEARCHES; iter++) {
      if (bloom_has(bloom, needle, NEEDLE_LENGTH))
        for (size_t k = 0; k < ARRAY_SIZE; k++)
          count += !!strstr(array[k], needle);
    }
    for (size_t k = 0; k < ARRAY_SIZE; k++)
      free(array[k]);
    free(array);
    free(bloom);

    struct timespec te;
    clock_gettime(CLOCK_MONOTONIC, &te);
    printf("count = %zu; %.3f secs\n", count,
           (te.tv_sec - ts.tv_sec) + 1e-9 * (te.tv_nsec - ts.tv_nsec));
  }
}

count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.048 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.047 secs

Вариант с простым поиском, выполняющийся в восемь потоков, тратил примерно 450-530 мс на итерацию.

Я думал, что смысл теста был в том, чтобы не убегать от вычислений.

Исходная версия i-rinat, 29.02.20 18:24:

Набросал с хешами, получилось в 10 раз быстрее. Не параллелится, правда.

#include <omp.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ARRAY_SIZE UINT64_C(100000)
#define HAYSTACK_LENGTH UINT64_C(100)
#define NEEDLE_LENGTH UINT64_C(20)
#define NUM_SEARCHES UINT64_C(1000)
#define BLOOM_ORDER UINT64_C(20)
#define BLOOM_SZ (UINT64_C(1) << BLOOM_ORDER)
#define BLOOM_HASHCOUNT 2
#define BLOOM_MAGIC 0x9747b28c
#define NUM_THREADS 1

typedef uint8_t u8;
typedef uint32_t u32;

static u32 mm2(const void *key, u32 len, const u32 seed) {
  const u32 *data = key;
  return *data ^ seed;
}

static void bloom_add(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    bloom[x / 32] |= 1 << (x % 32);
  }
}

static u32 bloom_has(u32 *bloom, u8 *buf, u32 len) {
  u32 a = mm2(buf, len, BLOOM_MAGIC);
  u32 b = mm2(buf, len, a);
  u32 hits = 0;

  for (u32 k = 0; k < BLOOM_HASHCOUNT; k++) {
    u32 x = (a + b * k) % BLOOM_SZ;
    hits = !!(bloom[x / 32] & (1 << (x % 32)));
  }

  return hits == BLOOM_HASHCOUNT;
}

int main(void) {

  static const u8 xlat[] = //
      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghij"
      "klmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrst"
      "uvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyzABCD"
      "EFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefgh";

  for (size_t try = 0; try < 10; try ++) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    u8 **array = malloc(sizeof(u8 *) * ARRAY_SIZE);
    u32 *bloom = calloc(1, BLOOM_SZ / 8);
    u32 seed = time(NULL);

    for (size_t k = 0; k < ARRAY_SIZE; k++) {
      u8 *hs = malloc(HAYSTACK_LENGTH + 1);
      for (size_t j = 0; j < HAYSTACK_LENGTH; j += sizeof(u32)) {
        const u32 r = rand_r(&seed);
        *(u32 *)(hs + j) = xlat[(r >> 24)] << 24 |
                           xlat[(r >> 16) & 0xffu] << 16 |
                           xlat[(r >> 8) & 0xffu] << 8 | xlat[r & 0xffu];
      }
      for (size_t j = 0; j < HAYSTACK_LENGTH - NEEDLE_LENGTH; j++)
        bloom_add(bloom, hs + j, NEEDLE_LENGTH);
      hs[HAYSTACK_LENGTH] = 0;
      array[k] = hs;
    }

    char needle[NEEDLE_LENGTH + 1];
    for (size_t k = 0; k < NEEDLE_LENGTH; k++)
      needle[k] = xlat[k & 0xffu];
    needle[NEEDLE_LENGTH] = 0;

    size_t count = 0;
    for (size_t iter = 0; iter < NUM_SEARCHES; iter++) {
      if (bloom_has(bloom, needle, NEEDLE_LENGTH))
        for (size_t k = 0; k < ARRAY_SIZE; k++)
          count += !!strstr(array[k], needle);
    }
    for (size_t k = 0; k < ARRAY_SIZE; k++)
      free(array[k]);
    free(array);
    free(bloom);

    struct timespec te;
    clock_gettime(CLOCK_MONOTONIC, &te);
    printf("count = %zu; %.3f secs\n", count,
           (te.tv_sec - ts.tv_sec) + 1e-9 * (te.tv_nsec - ts.tv_nsec));
  }
}

count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.048 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.046 secs
count = 0; 0.047 secs
count = 0; 0.047 secs
count = 0; 0.047 secs

Вариант с простым поиском, выполняющийся в восемь потоков тратил примерно 450-530 мс на итерацию.

Я думал, что смысл теста был в том, чтобы не убегать от вычислений.