Пишем свой file_path (2 стр)

innuendo
Постоялец

#15
10:27, 20 янв 2026

Subject
И тебе хорошего дня :)
Краткость есть сестра таланта ... Тем более пишу с телефона

Zab
Постоялец

#16
13:14, 20 янв 2026

Все же, хотелось бы услышать, почему применение буста не рассматривается. Просто не знают о его существовании? Очень хочется сделать такое же, но свое? Какая-то часть функциональности проблемы доставляет? Какие?

v1c
Постоялец

#17
14:09, 21 янв 2026

Zab
> Все же, хотелось бы услышать, почему применение буста не рассматривается. Просто не знают о его существовании? Очень хочется сделать такое же, но свое? Какая-то часть функциональности проблемы доставляет? Какие?
Там наверняка куча зависимостей, не хочу тащить весь boost в проект. std::filesystem есть в C++17, но я хочу своё решение для virtual file system.

v1c
Постоялец

#18
19:27, 23 янв 2026

Написал по-быстрому свой класс string_id. Никаких глобальных хеш-мап и подобного непотребства.

class alignas(32) string_id
{
public:
    template<size_t N>
    constexpr string_id(const char (&str)[N]) noexcept;
    constexpr const char* c_str() const noexcept { return str; }
    constexpr size_t length() const noexcept { return len; }
    bool operator==(const string_id& id) const noexcept;
    bool operator!=(const string_id& id) const noexcept;

private:
    union
    {
        char data[32];
        __m256 ymm;
        __m256i ymmi;
    };
    const char *str;
    const size_t len;
};

template<size_t N>
constexpr string_id::string_id(const char (&str)[N]) noexcept:
    data{}, str(str), len(N - 1)
{
    static_assert(N <= 33, "string too long");
    for (int i = 0; i < N - 1; ++i) // excluding '\0'
        data[i] = str[i];
}

inline bool string_id::operator==(const string_id& id) const noexcept
{
#ifdef AVX2
    __m256i x = _mm256_xor_si256(ymmi, id.ymmi);
    return _mm256_testz_si256(x, x);
#else // AVX1
    __m256 cmp = _mm256_cmp_ps(ymm, id.ymm, _CMP_EQ_OQ);
    int mask = _mm256_movemask_ps(cmp);
    return (0xFF == mask);
#endif
}

Главная идея - сравниваем строки напрямую, минуя вычисление хеша. Основное ограничение - длина строки не более 32 байт. Можно расширить до 64 байт если есть AVX-512 или сравнивать четыре ymm регистра.

Unit-test:

int main()
{
    constexpr string_id id1("It was a bright cold day in town");
    constexpr string_id id2("So it goes and goes and goes on!");
    bool equal = (id1 == id2);
    std::cout << "Strings are equal: " << std::boolalpha << equal << std::endl;

AVX2 генерит чуть меньше инструкций, но зато AVX1 есть почти везде.

v1c
Постоялец

#19
20:19, 25 янв 2026

Решил что неплохо бы реализовать все операторы сравнения для string_id:

bool operator==(const string_id&) const noexcept;
bool operator!=(const string_id&) const noexcept;
bool operator<(const string_id&) const noexcept;
bool operator<=(const string_id&) const noexcept;
bool operator>(const string_id&) const noexcept;
bool operator>=(const string_id&) const noexcept;

Но написать operator< оказалось намного сложнее, чем оператор равенства, т. к. сравнение должно быть лексикографическим. Сначала пришлось добавить алиазинг для лэйнов внутри __m256:

 union
    {
        alignas(32) char data[32];
        alignas(32) uint32_t lanes[8];
        __m256 ymm;
        __m256i ymmi;
    };

Оператор less than:

inline bool string_id::operator<(const string_id& id) const noexcept
{
#ifdef AVX2
    __m256i cmp = _mm256_cmpeq_epi8(ymmi, id.ymmi);
    int mask = _mm256_movemask_epi8(cmp);
    if (-1 == mask) return false;
    uint32_t pos = ctz(~mask);
    return data[pos] < id.data[pos]; // ASCII only
#else // AVX1
    __m256 x = _mm256_xor_ps(ymm, id.ymm);
    __m256 cmp = _mm256_cmp_ps(x, _mm256_setzero_ps(), _CMP_EQ_OQ);
    int mask = _mm256_movemask_ps(cmp);
    if (0xFF == mask) return false;
    uint32_t lane = ctz(~mask);
    uint32_t x0r = lanes[lane] ^ id.lanes[lane];
    uint32_t pos = (lane << 2) + (ctz(x0r) >> 3);
    return data[pos] < id.data[pos];
#endif
}

где ctz() - это count trailing zeros, на x86 инструкция bsf (bit scan forward).
На AVX2 код сравнения строк получается более эффективным, у AVX у нас нет побайтовой маски (epi8) и приходится подключать ALU чтобы добраться до отдельных символов строки.

Что интересно, для char data[32] компилятор генерирует movdaq инструкции по загрузке в регистры, если переписать на unsigned char data[32] то компилятор генерирует множество mov инструкций. Т. е. char data[] рассматривается как native данные для SSE/AVX, а unsigned уже нет.

Все остальные операторы сравнения выводятся из == и <.

v1c
Постоялец

#20
15:57, 27 янв 2026

Решил написать branchless вариант оператора less than т. к. джампы CPU не любит.
Добавил fallback для не-AVX архитектур.

inline bool string_id::operator<(const string_id& id) const noexcept
{
#if defined(AVX2)
    __m256i cmp = _mm256_cmpeq_epi8(ymmi, id.ymmi);
    uint32_t mask = (uint32_t)_mm256_movemask_epi8(cmp);
    uint32_t pos = _tzcnt_u32(~mask);
    pos &= (uint32_t)-(mask != 0xFFFFFFFFu);
    return data[pos] < id.data[pos]; // ASCII only
#elif defined(AVX1)
    __m256 x = _mm256_xor_ps(ymm, id.ymm);
    __m256 z = _mm256_setzero_ps();
    __m256 cmp = _mm256_cmp_ps(x, z, _CMP_EQ_OQ);
    uint32_t mask = (uint32_t)_mm256_movemask_ps(cmp);
    uint32_t lane = _tzcnt_u32((~mask & 0xFFu) | (mask == 0xFFu));
    uint32_t x0r = lanes[lane] ^ id.lanes[lane];
    uint32_t pos = (lane << 2) + (_tzcnt_u32(x0r | !x0r) >> 3);
    return data[pos] < id.data[pos]; // ASCII only
#else
    return strncmp(data, id.data, sizeof(data)) < 0;
#endif
}

v1c
Постоялец

#21
(Правка: 16:07) 16:02, 27 янв 2026

Также решил добавить простые методы поиска символа в строке.
У AVX1 нет инструкций для работы с байтами, поэтому я использовал пару инструкций SSE над двумя регистрами __m128:

inline size_t string_id::find(char ch) const noexcept
{
#if defined(AVX2)
    __m256i cmp = _mm256_cmpeq_epi8(ymmi, _mm256_set1_epi8(ch));
    uint32_t mask = (uint32_t)_mm256_movemask_epi8(cmp);
    if (mask) return _tzcnt_u32(mask);
#elif defined(AVX1) || defined(SSE2)
    __m128i v = _mm_set1_epi8(ch);
    __m128i cmp0 = _mm_cmpeq_epi8(xmmi[0], v);
    __m128i cmp1 = _mm_cmpeq_epi8(xmmi[1], v);
    uint32_t mask0 = (uint32_t)_mm_movemask_epi8(cmp0);
    uint32_t mask1 = (uint32_t)_mm_movemask_epi8(cmp1);
    if (mask0) return _tzcnt_u32(mask0);
    if (mask1) return _tzcnt_u32(mask1) + 16;
#else
    for (size_t i = 0; i < len; ++i)
        if (data[i] == ch) return i;
#endif
    return npos;
}

inline size_t string_id::find_last(char ch) const noexcept
{
#if defined(AVX2)
    __m256i cmp = _mm256_cmpeq_epi8(ymmi, _mm256_set1_epi8(ch));
    uint32_t mask = (uint32_t)_mm256_movemask_epi8(cmp);
    if (mask) return 31 - _lzcnt_u32(mask);
#elif defined(AVX1) || defined(SSE2)
    __m128i v = _mm_set1_epi8(ch);
    __m128i cmp1 = _mm_cmpeq_epi8(xmmi[1], v);
    __m128i cmp0 = _mm_cmpeq_epi8(xmmi[0], v);
    uint32_t mask1 = (uint32_t)_mm_movemask_epi8(cmp1);
    uint32_t mask0 = (uint32_t)_mm_movemask_epi8(cmp0);
    if (mask1) return (31 - _lzcnt_u32(mask1)) + 16;
    if (mask0) return 31 - _lzcnt_u32(mask0);
#else
    for (size_t i = len; i-- > 0;)
        if (data[i] == ch) return i;
#endif
    return npos;
}

Тут уже есть бранчинг, но методы поиска не так критичны. К тому же от него трудно избавиться.

union для алиазинга усложнился:

    union
    {
        alignas(32) char data[32];
    #ifdef AVX1
        alignas(32) uint32_t lanes[8];
        __m128i xmmi[2];
        __m256 ymm;
    #endif
    #ifdef AVX2
        __m256i ymmi;
    #endif
    };

v1c
Постоялец

#22
0:08, 28 янв 2026

Оказалось что SSE ветку можно оптимизировать, т. к. _mm_cmpeq_epi8 возвращает 16-битную маску, а не 32-битную. Можно слить их в одну маску в обоих случаях:

int mask = _mm_movemask_epi8(cmp0) |
        _mm_movemask_epi8(cmp1) << 16;
return mask ? _tzcnt_u32((uint32_t)mask) : npos;

int mask = _mm_movemask_epi8(cmp0) |
        _mm_movemask_epi8(cmp1) << 16;
return mask ? 31 - _lzcnt_u32((uint32_t)mask) : npos;

Таким образом SSE ветка всего на 3-4 инструкции длиннее AVX.

innuendo
Постоялец

#23
12:02, 30 мар 2026

v1c
Это все очень круто ... Сколько денег принесло решение через sse avx?

v1c
Постоялец

#24
13:59, 30 мар 2026

innuendo
> Это все очень круто ... Сколько денег принесло решение через sse avx?
Долго же тебя в бане держали. Деньги я получаю от пассивного дохода, а движок пишу для души. Кто-то же должен писать нормальный код в конце концов.

innuendo
Постоялец

#25
14:10, 30 мар 2026

v1c
Вот интересно , если кто-то будет разбираться и переисполтзовать твой код ... Куда конкретно тебя пошлют и на сколько :)

v1c
Постоялец

#26
19:44, 30 мар 2026

innuendo
> Вот интересно , если кто-то будет разбираться и переисполтзовать твой код ... Куда конкретно тебя пошлют и на сколько :)
А может оно быстрее чем Unity? Тогда ещё и спасибо скажут.

innuendo
Постоялец

#27
11:53, 31 мар 2026

v1c
Ты хоть сделал проверочку на нужные sse avx по ЦПУ?

ronniko
Участник

#28
13:41, 31 мар 2026

сделал проверочку на нужные sse avx по ЦПУ

Согласен.
И суй в указатель нужную функцию под avx или sse.

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

#29
16:57, 31 мар 2026

Нельзя было просто использовать кастомную хэш-функцию для строк-путей? Которая равноценно оценивала бы / и \ ?

Страницы: 1 2 3 4 Следующая »

ПрограммированиеФорумОбщее