test_compare.cpp

//
//  main.cpp
//  FaceFeaturesCompare
//
//  Created by king on 2023/5/13.
//

#include <chrono>
#include <ctime>
#include <iostream>
#include <memory>
#include <omp.h>
#include <random>
#include <thread>

/// 10w 条特征
constexpr static uint32_t COUNT = 100000;

/// 特征向量长度
constexpr static size_t FEATURE_LENGHT = 1024;

#pragma pack(1)
struct Feature {
    /// 用户ID
    uint32_t userId;
    /// 特征
    float features[FEATURE_LENGHT];
};
#pragma pack()

struct ElapsedTimer {
    ElapsedTimer(const std::string &name)
        : m_name(name)
        , m_start(std::chrono::steady_clock::now()) {
    }
    ~ElapsedTimer() {
        auto end = std::chrono::steady_clock::now();
        std::cout << m_name
                  << " Elapsed time in milliseconds: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - m_start).count()
                  << " ms"
                  << std::endl;
    }

    std::chrono::steady_clock::time_point m_start;
    std::string m_name;
};

#define SCOPE_CONCAT_(a, b) a##b
#define SCOPE_CONCAT(a, b) SCOPE_CONCAT_(a, b)
#define SCOPE_ELAPSED_TIMER(NAME) ElapsedTimer SCOPE_CONCAT(_et_, __COUNTER__){NAME};

static std::unique_ptr<Feature[]> database(new Feature[COUNT]);
static std::unique_ptr<float[]> feature(new float[FEATURE_LENGHT]);

float compare(const float *lhs, const float *rhs, int size) {
    float sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += *lhs * *rhs;
        ++lhs;
        ++rhs;
    }
    return sum;
}

float similarity(float x) {
    float m_a = 0, m_b = 1.0;
    return 1 / (1 + std::exp(m_a - m_b * std::max<float>(x, 0)));
}

void calculate(const float *feature, uint32_t start, uint32_t end, std::pair<uint32_t, float> &result) {

    //    std::cout << "bacth range " << start << " ~ " << end << std::endl;
    printf("bacth range %u ~ %u\n", start, end);
    float sim = 0.0;
    result.first = start;
    result.second = sim;
    for (uint32_t idx = start; idx < end; idx++) {
        Feature &item = database[idx];
        float v = compare(feature, item.features, FEATURE_LENGHT);
        if (v > sim) {
            sim = v;

            result.first = idx;
            result.second = sim;
        }
    }
}

void single_thread_calculate() {
    SCOPE_ELAPSED_TIMER("单线程特征比较")
    float sim = 0.0;
    Feature matched;
    for (uint32_t idx = 0; idx < COUNT; idx++) {
        Feature &item = database[idx];
        float v = compare(feature.get(), item.features, FEATURE_LENGHT);
        if (v > sim) {
            sim = v;

            matched = item;
        }
    }
    std::cout << "match userID: "
              << matched.userId
              << " sim: "
              << similarity(sim)
              << std::endl;
}

void multi_thread_calculate() {
    SCOPE_ELAPSED_TIMER("多线程特征比较");
    const unsigned int num_thread = std::thread::hardware_concurrency() - 1;
    const uint32_t block_size = static_cast<uint32_t>(COUNT / num_thread + 1);
    std::vector<std::pair<uint32_t, float>> results(num_thread);
    std::vector<std::thread> threads(num_thread);

    uint32_t start = 0;
    for (int i = 0; i < num_thread; i++) {
        uint32_t end = std::min(start + block_size, COUNT - 1);
        threads[i] = std::thread(calculate, feature.get(), start, end, std::ref(results[i]));
        start = end;
    }

    std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));

    std::pair<uint32_t, float> matched = results[0];
    for (int i = 1; i < results.size(); i++) {
        auto &item = results[i];
        if (item.second > matched.second) {
            matched.first = item.first;
            matched.second = item.second;
        }
    }

    auto &user = database[matched.first];
    std::cout << "match userID: "
              << user.userId
              << " sim: "
              << similarity(matched.second)
              << std::endl;
}

void omp_calculate_unit(const float *feature, std::vector<std::pair<uint32_t, float>> &result) {

    int thread_num = omp_get_thread_num();
    int thread_count = omp_get_num_threads();
    const uint32_t block_size = static_cast<uint32_t>(COUNT / thread_count + 1);
    uint32_t start = thread_num * block_size;
    uint32_t end = std::min(start + block_size, COUNT - 1);

    printf("bacth range %u ~ %u\n", start, end);
    float sim = 0.0;
    result[thread_num].first = start;
    result[thread_num].second = sim;
    for (uint32_t idx = start; idx < end; idx++) {
        Feature &item = database[idx];
        float v = compare(feature, item.features, FEATURE_LENGHT);
        if (v > sim) {
            sim = v;

            result[thread_num].first = idx;
            result[thread_num].second = sim;
        }
    }
}

/*
 brew install libomp llvm
 
 CC=/opt/homebrew/Cellar/llvm/16.0.3/bin/clang
 CXX=/opt/homebrew/Cellar/llvm/16.0.3/bin/clang
 LIBRARY_SEARCH_PATHS=/opt/homebrew/opt/libomp/lib
 HEADER_SEARCH_PATHS=/opt/homebrew/opt/libomp/include
 OTHER_LDFLAGS=-lomp
 OTHER_CFLAGS=-fopenmp
 COMPILER_INDEX_STORE_ENABLE=NO
 */

void omp_calculate() {
    SCOPE_ELAPSED_TIMER("omp特征比较");
    std::cout << "omp begin" << std::endl;
    const unsigned int num_thread = std::thread::hardware_concurrency() - 1;
    std::vector<std::pair<uint32_t, float>> results(num_thread);

#pragma omp parallel num_threads(num_thread)
    omp_calculate_unit(feature.get(), results);

    std::pair<uint32_t, float> matched = results[0];
    for (int i = 1; i < results.size(); i++) {
        auto &item = results[i];
        if (item.second > matched.second) {
            matched.first = item.first;
            matched.second = item.second;
        }
    }

    auto &user = database[matched.first];
    std::cout << "match userID: "
              << user.userId
              << " sim: "
              << similarity(matched.second)
              << std::endl;
    std::cout << "omp end" << std::endl;
}

int main(int argc, const char *argv[]) {

    srand(time(NULL));

    std::cout << "database size: " << sizeof(Feature) * COUNT << std::endl;

    {
        SCOPE_ELAPSED_TIMER("初始化数据")
        for (uint32_t idx = 0; idx < COUNT; idx++) {
            Feature &item = database[idx];
            item.userId = idx + 1;
            for (size_t j = 0; j < FEATURE_LENGHT; j++) {
                float v = rand() / static_cast<float>(RAND_MAX) * 0.01;
                item.features[j] = v;
            }
        }
    }

    {
        SCOPE_ELAPSED_TIMER("初始化特征")
        for (size_t j = 0; j < FEATURE_LENGHT; j++) {
            float v = rand() / static_cast<float>(RAND_MAX) * 0.01;
            feature[j] = v;
        }
    }

    single_thread_calculate();

    multi_thread_calculate();

    omp_calculate();

    return 0;
}