Все потоки
Поиск
Редактировать
Обновить
4
Карма
@gchebanov

Пользователь

Отправить сообщение
ПрофильСтатьиПостыНовостиКомментарии129
Операции сравнения в C++20

Удобней же структуры сравнивать по другому, по очереди для всех полей проверяешь что они не равны, и если это так возвращаешь первый меньше второго, ну и с последним так же. Получается n сравнений в худшем случае, вместо 2*n-1, более того они могут быть легковеснее, так как сравнение на неравенство может быть реализовано эффективнее сравнения на меньше.

Комментарий пока не оценивали0
Посмотреть
Ускоряем неускоряемое или знакомимся с SIMD

Ну если есть 3 параллельных алу, но наверное они зачем-то нужны?
"zero idioms" — Как я понял это про полную элиминацию, у нас же все результаты важны и нужны. Возможно я неправильно представляю себе процессор, и то что я принимал за результат параллельной конвейерной обработки (muops unfused domain) есть всего лишь результат macrofusion. Как будет время поэкспериментирую с uarch-bench + libpfc, должно быть наглядно видно работу muops.
P.S. таблица с портами
Про skylake написано что sub может идти на p0, p1, p5; cmp — p0, p1.


исправленные результаты
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        183 ns        182 ns    3837383
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         17 ns         17 ns   40434848

haswell
Model name:            Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz

CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.20, 0.27, 0.20
--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_Count                               148 ns          148 ns      4735708
BM_ShiftCount                          107 ns          107 ns      6542438
BM_SbbCount                            514 ns          514 ns      1363918
BM_Sbb2Count                           513 ns          513 ns      1366066
BM_SSE_COUNT_NG_HSUMM_ARRAY           17.9 ns         17.9 ns     39193335
BM_SSE_COUNT_NG_HSUMM                 33.6 ns         33.6 ns     20792054
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY       18.3 ns         18.3 ns     38331316
BM_SSE_COUNT_NG_NAIVESUMM             35.8 ns         35.8 ns     19558590
BM_SSE_COUNT_SET_EPI                   352 ns          352 ns      1989417
BM_SSE_COUNT_LOADU                    92.6 ns         92.6 ns      7564254
BM_SSE_COUNT_DIRECT                   91.7 ns         91.7 ns      7625196
BM_SSE_HADD                           62.2 ns         62.2 ns     11142194
BM_AVX2_COUNT                         49.0 ns         49.0 ns     14261594
BM_AVX2_HADD                          33.5 ns         33.5 ns     20831687
BM_AVX2_HADD2                         25.5 ns         25.5 ns     27379074

--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_Count                               583 ns          583 ns      1200624
BM_ShiftCount                          410 ns          410 ns      1589399
BM_SbbCount                           2048 ns         2048 ns       341928
BM_Sbb2Count                          2046 ns         2046 ns       342064
BM_SSE_COUNT_NG_HSUMM_ARRAY            102 ns          102 ns      6859708
BM_SSE_COUNT_NG_HSUMM                  134 ns          134 ns      5268616
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        104 ns          104 ns      6409371
BM_SSE_COUNT_NG_NAIVESUMM              133 ns          133 ns      5282830
BM_SSE_COUNT_SET_EPI                  1413 ns         1413 ns       497718
BM_SSE_COUNT_LOADU                     357 ns          357 ns      1964100
BM_SSE_COUNT_DIRECT                    355 ns          355 ns      1976462
BM_SSE_HADD                            239 ns          239 ns      2934372
BM_AVX2_COUNT                          183 ns          183 ns      3829745
BM_AVX2_HADD                           107 ns          107 ns      6562871
BM_AVX2_HADD2                         93.6 ns         93.6 ns      7396527
Комментарий пока не оценивали0
Посмотреть
Ускоряем неускоряемое или знакомимся с SIMD
Это тут непричём.

Неточно выразился, конечно же независимость.


Абсолютно неверно.

Возможно я не прав, но я вижу 64 * 2 + eps инструкций которые выполняются в цикле, причем это суммарно занимает 18 * 3.1 ~= 56 тактов на цикл, причем соотношение сохраняется при росте размера задачи (пока она влезает в L1). Реорганизация вычислений действительно может случатся, я не смотрел как написан libbenchmark (rdtscp?). Но даже rdtscp разрешает реордеринг, который может всё испортить, если компилятор развернет цикл бенчмарка.


Никакие трупуты не складываются, особенно так колхозно

А как они по-вашему должны складываться, как среднее гармоническое?
На работе посмотрю выхлоп IACA, только после этого будет понятно что там на самом деле, а пока мы знаем что ядро умеет делать 2 vpcmpeqw за такт, и 3 vpsubw за такт. Также нет ничего что бы помешало выполнять эти инструкции параллельно (при наличии нужного числа регистров и использовании нужного числа аккумуляторов). Этого уже должно хватать на 5/6 такта на 16 элементов, а если еще и они друг другу не мешают — то и 1/2 такта (во что я лично не верю, т.к. skylake на картинке только 3 INT Vect ALU).
Моя реализация скорее всего упирается в l1i, хотя на 6 итераций я использую 72 байта инструкций, а кеш должен уметь читать 96.


BENCHMARK 4096 (clang)
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               944 ns        942 ns     708115
BM_ShiftCount                          394 ns        392 ns    1748745
BM_SbbCount                            454 ns        447 ns    1580556
BM_Sbb2Count                           465 ns        460 ns    1572391
BM_SSE_COUNT_NG_HSUMM_ARRAY            183 ns        182 ns    3813966
BM_SSE_COUNT_NG_HSUMM                  109 ns        109 ns    6448166
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        143 ns        140 ns    5204190
BM_SSE_COUNT_NG_NAIVESUMM              149 ns        148 ns    4719780
BM_SSE_COUNT_SET_EPI                   320 ns        319 ns    2228249
BM_SSE_COUNT_LOADU                     233 ns        233 ns    2998886
BM_SSE_COUNT_DIRECT                    236 ns        235 ns    2997461
BM_SSE_HADD                            150 ns        149 ns    4609448
BM_AVX2_COUNT                          114 ns        114 ns    6065280
BM_AVX2_HADD                            77 ns         77 ns    9087605
BM_AVX2_HADD2                           76 ns         76 ns    8660472

BENCHMARK 4096 (g++-8)
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               967 ns        958 ns     692185
BM_ShiftCount                          390 ns        389 ns    1794035
BM_SbbCount                            443 ns        442 ns    1573041
BM_Sbb2Count                           448 ns        446 ns    1583743
BM_SSE_COUNT_NG_HSUMM_ARRAY            181 ns        180 ns    3766114
BM_SSE_COUNT_NG_HSUMM                  108 ns        108 ns    6484183
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        138 ns        137 ns    4938655
BM_SSE_COUNT_NG_NAIVESUMM              146 ns        146 ns    4791501
BM_SSE_COUNT_SET_EPI                   308 ns        307 ns    2280309
BM_SSE_COUNT_LOADU                     236 ns        234 ns    2973763
BM_SSE_COUNT_DIRECT                    232 ns        231 ns    3009575
BM_SSE_HADD                            151 ns        150 ns    4695529
BM_AVX2_COUNT                          116 ns        116 ns    6000600
BM_AVX2_HADD                            76 ns         76 ns    9235438
BM_AVX2_HADD2                           76 ns         75 ns    8653085

BENCHMARK 1024 (clang)
-----------------------------------------------------------------------
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               223 ns        222 ns    3164557
BM_ShiftCount                          103 ns        101 ns    6838475
BM_SbbCount                            112 ns        112 ns    5843657
BM_Sbb2Count                           114 ns        113 ns    6204464
BM_SSE_COUNT_NG_HSUMM_ARRAY             15 ns         15 ns   48139412
BM_SSE_COUNT_NG_HSUMM                   29 ns         29 ns   24739178
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         22 ns         22 ns   31956904
BM_SSE_COUNT_NG_NAIVESUMM               35 ns         35 ns   19836715
BM_SSE_COUNT_SET_EPI                    82 ns         82 ns    8580219
BM_SSE_COUNT_LOADU                      57 ns         57 ns   12195122
BM_SSE_COUNT_DIRECT                     58 ns         57 ns   12200861
BM_SSE_HADD                             38 ns         38 ns   18213135
BM_AVX2_COUNT                           29 ns         29 ns   24371053
BM_AVX2_HADD                            18 ns         18 ns   38745102
BM_AVX2_HADD2                           15 ns         15 ns   46509774

BENCHMARK 1024 (g++-8)
-----------------------------------------------------------------------
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               221 ns        221 ns    3104351
BM_ShiftCount                          103 ns        102 ns    6613569
BM_SbbCount                            114 ns        113 ns    6270379
BM_Sbb2Count                           112 ns        111 ns    6243366
BM_SSE_COUNT_NG_HSUMM_ARRAY             15 ns         15 ns   48197085
BM_SSE_COUNT_NG_HSUMM                   28 ns         28 ns   24614519
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         22 ns         22 ns   31906505
BM_SSE_COUNT_NG_NAIVESUMM               35 ns         35 ns   19846164
BM_SSE_COUNT_SET_EPI                    82 ns         82 ns    8507949
BM_SSE_COUNT_LOADU                      57 ns         57 ns   11635638
BM_SSE_COUNT_DIRECT                     59 ns         58 ns   11748120
BM_SSE_HADD                             38 ns         38 ns   18002911
BM_AVX2_COUNT                           29 ns         29 ns   24417043
BM_AVX2_HADD                            18 ns         18 ns   39480660
BM_AVX2_HADD2                           15 ns         15 ns   47806044

code
#include <benchmark/benchmark.h>
#include <x86intrin.h>
#include <emmintrin.h>
#include <immintrin.h>
#include <cstring>
#include <stdlib.h>

#define ARR_SIZE 4096
#define VAL 50

static int16_t *getRandArr() {
    auto res = new int16_t[ARR_SIZE];
    for (int i = 0; i < ARR_SIZE; ++i) {
        res[i] = static_cast<int16_t>(rand() % (VAL * 2));
    }
    return res;
}

static auto arr = getRandArr();

static int16_t *getAllignedArr() {
    void *res;
    posix_memalign(&res, 64, sizeof(int16_t) * ARR_SIZE);
    //auto res =  aligned_alloc(16, sizeof(int16_t) * ARR_SIZE);
    memcpy(res, arr, sizeof(int16_t) * ARR_SIZE);
    return static_cast<int16_t *>(res);
}

static auto allignedArr = getAllignedArr();

static void BM_Count(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        for (int i = 0; i < ARR_SIZE; ++i)
            if (arr[i] == VAL)
                ++cnt;
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_Count);

static void BM_ShiftCount(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          diff |= (diff >> 1) & 0xEFFFEFFFEFFFEFFFUL;
          diff |= (diff >> 2) & 0xCFFFCFFFCFFFCFFFUL;
          diff |= (diff >> 4) & 0x0FFF0FFF0FFF0FFFUL;
          diff |= (diff >> 8) & 0x00FF00FF00FF00FFUL;
          diff &= 0x0001000100010001UL;
          sum += diff;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_ShiftCount);

static void BM_SbbCount(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          if ((diff >> 0) & 0xFFFF) ++sum;
          if ((diff >>16) & 0xFFFF) ++sum;
          if ((diff >>32) & 0xFFFF) ++sum;
          if ((diff >>48) & 0xFFFF) ++sum;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_SbbCount);

static void BM_Sbb2Count(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          if (diff & 0x000000000000FFFFUL) ++sum;
          if (diff & 0x00000000FFFF0000UL) ++sum;
          if (diff & 0x0000FFFF00000000UL) ++sum;
          if (diff & 0xFFFF000000000000UL) ++sum;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_Sbb2Count);

using int16_vec_t = int16_t __attribute__((__vector_size__(16)));

auto vhadd(int16_vec_t a, int16_vec_t b) {
  return __builtin_ia32_phaddw128(a, b);
}

auto vhsumm(int16_vec_t v) {
  v = vhadd(v, v);
  v = vhadd(v, v);
  v = vhadd(v, v);
  return v;
}

auto summ(int16_vec_t v) {
  return v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + v[6] + v[7];
}

static void BM_SSE_COUNT_NG_HSUMM_ARRAY(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{} - 1;
    for (size_t i = 0; i < ARR_SIZE; i += 64) {
      cnt += ((int16_vec_t*)allignedArr)[i] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 16] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 32] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 48] == VAL;
    }
    cnt = -1 - cnt;
    auto res = vhsumm(cnt)[0];
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_HSUMM_ARRAY);

static void BM_SSE_COUNT_NG_HSUMM(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{} - 1;
    // for (size_t i = 0; i < ARR_SIZE; i += 16) {
    //   cnt += ((int16_vec_t*)allignedArr)[i] == VAL;
    // }
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
    }
    cnt = -1 - cnt;
    auto res = vhsumm(cnt)[0];
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_HSUMM);

static void BM_SSE_COUNT_NG_NAIVESUMM_ARRAY(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{};
    for (size_t i = 0; i < ARR_SIZE; i += 64) {
      cnt += (((int16_vec_t*)allignedArr)[i] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 16] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 32] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 64] == VAL) & 1;
    }
    auto res = summ(cnt);
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_NAIVESUMM_ARRAY);

static void BM_SSE_COUNT_NG_NAIVESUMM(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{};
    // for (size_t i = 0; i < ARR_SIZE; i += 16) {
    //   cnt += (((int16_vec_t*)allignedArr)[i] == VAL) & 1;
    // }
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
    }
    auto res = summ(cnt);
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_NAIVESUMM);

static void BM_SSE_COUNT_SET_EPI(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2],
                                        arr[i + 1], arr[i]);
            cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_SET_EPI);

static void BM_SSE_COUNT_LOADU(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = _mm_loadu_si128((__m128i *) &arr[i]);
            cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_LOADU);

static void BM_SSE_COUNT_DIRECT(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = *(__m128i *) &allignedArr[i];
            auto mask = _mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr));
            cnt += _popcnt32(mask);
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_DIRECT);

static void BM_SSE_HADD(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        auto sseOne = _mm_set1_epi16(1);
        auto sseSum = _mm_set1_epi16(0);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = *(__m128i *) &allignedArr[i];
            auto mask_ff = _mm_cmpeq_epi16(sseVal, sseArr);
            auto mask_01 = _mm_and_si128(mask_ff, sseOne);
            sseSum = _mm_add_epi16(sseSum, mask_01);
        }
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        cnt = _mm_extract_epi16(sseSum, 0);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_SSE_HADD);

static void BM_AVX2_COUNT(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 16) {
            auto sseArr = *(__m256i *) &allignedArr[i];
            auto mask_ff = _mm256_cmpeq_epi16(sseVal, sseArr);
            cnt += _popcnt32(_mm256_movemask_epi8(mask_ff));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_AVX2_COUNT);

static void BM_AVX2_HADD(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        auto sseOne = _mm256_set1_epi16(1);
        auto sseSum = _mm256_setzero_si256();
        for (int i = 0; i < ARR_SIZE; i += 16) {
            auto sseArr = *(__m256i *) &allignedArr[i];
            auto mask_ff = _mm256_cmpeq_epi16(sseVal, sseArr);
            sseSum = _mm256_sub_epi16(sseSum, mask_ff); 
        }
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        cnt = _mm256_extract_epi16(sseSum, 0) +
              _mm256_extract_epi16(sseSum, 8);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_AVX2_HADD);

static void BM_AVX2_HADD2(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        auto sseOne = _mm256_set1_epi16(1);
        auto sseSum0 = _mm256_setzero_si256();
        auto sseSum1 = _mm256_setzero_si256();
        for (int i = 0; i < ARR_SIZE; i += 32) {
            auto sseArr0 = *(__m256i *) &allignedArr[i];
            auto sseArr1 = *(__m256i *) &allignedArr[i + 16];
            auto mask_ff0 = _mm256_cmpeq_epi16(sseVal, sseArr0);
            auto mask_ff1 = _mm256_cmpeq_epi16(sseVal, sseArr1);
            sseSum0 = _mm256_sub_epi16(sseSum0, mask_ff0); 
            sseSum1 = _mm256_sub_epi16(sseSum1, mask_ff1); 
        }
        sseSum0 = _mm256_add_epi16(sseSum0, sseSum1);
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        cnt = _mm256_extract_epi16(sseSum0, 0) +
              _mm256_extract_epi16(sseSum0, 8);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_AVX2_HADD2);

BENCHMARK_MAIN();
Всего голосов 1: ↑1 и ↓0+1
Посмотреть
Ускоряем неускоряемое или знакомимся с SIMD

Что за условное суммирование? У меня векторное решение, но тут log(16bit) >= общему числу элементов в пачке. Странно что даже такая лапша обгоняет тупой иф.


Benchmark
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                    211 ns        210 ns    3313500
BM_ShiftCount               100 ns         99 ns    7066068
BM_SSE_COUNT_SET_EPI         83 ns         83 ns    8598664
BM_SSE_COUNT_LOADU           57 ns         57 ns   12265424

code
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          diff |= (diff >> 1) & 0xEFFFEFFFEFFFEFFFUL;
          diff |= (diff >> 2) & 0xCFFFCFFFCFFFCFFFUL;
          diff |= (diff >> 4) & 0x0FFF0FFF0FFF0FFFUL;
          diff |= (diff >> 8) & 0x00FF00FF00FF00FFUL;
          diff &= 0x0001000100010001UL;
          sum += diff;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_ShiftCount);
Комментарий пока не оценивали0
Посмотреть
Ускоряем неускоряемое или знакомимся с SIMD

Добавил вариант(1 c sse, 2 c avx2) где вместо movemask делается and(set1_epi16(1)); sum_epi16 в цикле, в конце цикла 3 раза hadd + extract_epi16(0) + (avx2 ? extract_epi16(8) : 0). Ускорение уже не в 4(7) раза, а в 6(12.5).


Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
Run on (4 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 262K (x2)
  L3 Unified 4194K (x1)
------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                    228 ns        227 ns    3088640
BM_SSE_COUNT_SET_EPI         82 ns         81 ns    8573808
BM_SSE_COUNT_LOADU           57 ns         57 ns   11927684
BM_SSE_COUNT_DIRECT          66 ns         65 ns   10831051
BM_SSE_HADD                  39 ns         38 ns   18249460
BM_AVX2_COUNT                29 ns         29 ns   24458164
BM_AVX2_HADD                 18 ns         18 ns   39366536

UPD
оптимизатор это превратил в (vpcmpeqw+vpsubw) на каждые 16 uint16_t. согласно спеке throughput = 0.5 + 0.33 (предполагаем зависимость). Общее время — (0.5 + 0.33) * 1024 / 16 / 3.2 = 16.6ns, что очень похоже на правду.

Всего голосов 1: ↑1 и ↓0+1
Посмотреть
О чем я думаю, когда читаю роман «Червь» Wildbow

Мне вот тоже "Червь" очень понравился, но в основном из-за проработанности персонажей. Из фиков неплохи "Тейлор — Медея", "Сказание о бесстрашной маске", "Режь, чтобы жить", Данилов с "Игротекой", "Вспомнить молодость" (предупреждаю: обилие постельных сцен так свойственных автору), "Ловчий" (Отсутствует во всех известных мне списках).

Комментарий пока не оценивали0
Посмотреть
Пишем DNS proxy на Go
type T struct {
	msg string
}

var g *T

func setup() {
	t := new(T)
	t.msg = "hello, world"
	g = t
}

func main() {
	go setup()
	for g == nil {
	}
	print(g.msg)
}

Тут в переменной g тоже всегда корректный указатель, но это не мешает «there is no guarantee that it will observe the initialized value for g.msg».
Другими словами оптимизатор может вначале выполнить config.go:66, заполнив указатель новым свежим конфигом, и только потом заполнить этот конфиг значениями, т.к он не знает что кто-то может этот самый конфиг читать. Т.е по факту может случиться так что часть полей конфига уже новые, а часть — какие угодно. Вроде бы паники тут быть нигде быть не должно.
Всего голосов 2: ↑2 и ↓0+2
Посмотреть
Сумма сумм арифметических прогрессий

Ну незнаю. Так то формулировка вполне известная: "Задача о шарах и перегородках", А S_l(n) \eq C_n^l, число сочетаний. Другая формулировка: число решений уравнения \sum_{i = 1}^{l+1}{x_i} \eq N-l, x_i \in \mathbb{N}_0, в ней ваше доп условие про r задается так x_i < r (если вычесть из общего числа вариантов). Теперь методом динамического программирования должно получиться простое решение за O(nl*bigint_add) (чтобы получилось без r нужно сумму на отрезке выразить через предыдущее значение) которое выглядит естественнее того что написано в статье. Возможно с мемоизацией ваше решение не так уж и плохо, но точно выглядит ужасно.

Комментарий пока не оценивали0
Посмотреть
Точное вычисление средних и ковариаций методом Уэлфорда
Не впечатлил что-то ваш Уэлфорд.
code
void perr(const std::string& type, double v, double u) {
  double abs_e = std::abs(v - u);
  std::cout << type << " abs: " << abs_e << " rel: " << abs_e / u << std::endl;
};

void test_m(const size_t n = 100000000, double from = 128, double step = 1) {
  double m = from + step * (n - 1) / (2 * n);
  MeanDummy m0;
  MeanKahan m1;
  MeanWelford m2;
  for (size_t i = 0; i < n; ++i) {
    double v = from + i * step / n;
    m0.add(v);
    m1.add(v);
    m2.add(v);
  }
  std::cout << "test mean\n";
  perr("Dummy", m0.mean(), m);
  perr("Kahan", m1.mean(), m);
  perr("Welford", m2.mean(), m);
}

void test_c(const size_t n = 100000000, double from0 = 128, double step0 = 3, double from1 = 32, double step1 = 2) {
  double c = step0 * step1 / 12 * (1 - 1.0/(n * n));
  CovariationDummy c0;
  CovariationKahan c1;
  CovariationWelford c2;
  CovariationWelford2 c3;
  CovariationWelfordKahan c4;
  for (size_t i = 0; i < n; ++i) {
    double v = from0 + i * step0 / n;
    double u = from1 + i * step1 / n;
    c0.add(v, u);
    c1.add(v, u);
    c2.add(v, u);
    c3.add(v, u);
    c4.add(v, u);
  }
  std::cout << "test covariation\n";
  perr("Dummy", c0.covariation(), c);
  perr("Kahan", c1.covariation(), c);
  perr("Welford", c2.covariation(), c);
  perr("Welford2", c3.covariation(), c);
  perr("WelfordKahan", c4.covariation(), c);
}


test mean
Dummy abs: 2.84217e-14 rel: 2.21181e-16
Kahan abs: 0 rel: 0
Welford abs: 3.96642e-07 rel: 3.0867e-09
test covariation
Dummy abs: 1.55029e-10 rel: 3.10059e-10
Kahan abs: 6.10456e-13 rel: 1.22091e-12
Welford abs: 1.18424e-07 rel: 2.36848e-07
Welford2 abs: 1.18424e-07 rel: 2.36848e-07
WelfordKahan abs: 0 rel: 0
Комментарий пока не оценивали0
Посмотреть
12 ...
56
7
ТудаНазад

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2026, Habr