Re[3]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.12.19 09:50
Оценка:
Здравствуйте, Shmj, Вы писали:
S>Это вы взяли готовый код для подобной задачи или писали с нуля для спорт. интереса?
C нуля для спорт. интереса.
Для продакшна такой код не готов по двум причинам:
1. Нет плавной деградации. Помимо AVX2, есть ещё AVX, SSE42, SSE4 и прочее.
2. Плохо, нечитаемо написан. Скажем, доработать его для unescaping-а символов типа \t будет ненамного легче, чем переписать с нуля.
Тут надо быть очень аккуратным — один лишний вызов изнутри цикла страшно портит перформанс. Я пробовал поиграть с AggressiveInlining — не очень успешно.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Shmj Ниоткуда  
Дата: 06.12.19 11:09
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>>Это вы взяли готовый код для подобной задачи или писали с нуля для спорт. интереса?

S>C нуля для спорт. интереса.

Похоже как дети в песочнице спорили кто дальше плюнет, пока не пришел взрослый дядя и не продемонстрировал свои возможности.
Re[5]: 5 вариантов unescape - угадайте какой самый быстрый (
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.12.19 11:25
Оценка:
Здравствуйте, Shmj, Вы писали:
S>Похоже как дети в песочнице спорили кто дальше плюнет, пока не пришел взрослый дядя и не продемонстрировал свои возможности.
Да ну что вы право. Это как раз игры в песочнице. Взрослые дяди занимаются всякими декодированиями из base64, которые работают на AVX512 быстрее, чем копирование памяти. И не делают детских ошибок — в коде было минимум 2 баги, которые просто не проявляются на тестовых данных.

Вот, после некоторого дополнительного тупления более простой и на ~10% более быстрый код, основанный на том, что даже при обнаружении \\ или \n у нас данные уже лежат в регистре current, поэтому мучительные копирования память-память нафиг не нужны:
  AVXUnescape2
        public unsafe string AVXUnescape2()
        {
            if (!Avx2.IsSupported)
                return UnsafeCharArrayScan();
            var slash = stackalloc ushort[1] { '\\' };
            var nchar = stackalloc ushort[1] { 'n' };
            var slashes = BroadcastScalarToVector256(slash);
            var nchars = BroadcastScalarToVector256(nchar);

            var result = new char[_escaped.Length];
            var escaped = _escaped.AsSpan();
            fixed (char* s = escaped, t = result)
            {
                var src = (ushort*)s;
                var trg = (ushort*)t;
                var i = 0;
                var j = 0;
                var trailingSlash = false;
                var k = (int)((((UIntPtr)(void*)src).ToUInt64() >> 1) & 0xF);

                while (i + 16 <= escaped.Length)
                {
                    while (((k + i) & 0xf) > 0)
                    {
                        if (trailingSlash)
                            switch (s[i])
                            {
                                case 'n':  // \n
                                    t[j - 1] = '\n';
                                    goto case '\\';
                                case '\\': // double-slash
                                    i++;
                                    trailingSlash = false;
                                    continue;
                            }

                        trailingSlash = s[i] == '\\';
                        t[j++] = s[i++];
                    }
                    var current = Avx2.LoadAlignedVector256(src + i);
                    var slashbits = (uint)Avx2.MoveMask(Avx2.CompareEqual(current, slashes).AsByte());
                    var ncharbits = (uint)Avx2.MoveMask(Avx2.CompareEqual(current, nchars).AsByte());

                    Avx2.Store(trg + j, current); // всегда пишем 16 символов пачкой; от результатов поиска зависят только инкременты i и j, и запись \n.

                    if (slashbits == 0 && ncharbits == 0) // no slashes, no Ns.
                    {
                        i += 16; j += 16;
            trailingSlash = false;
                        continue;
                    }

                    if (trailingSlash)
                    {
                        if ((slashbits & 1) > 0) // starting slash after trailing slash
                        {
                            i++;
                            trailingSlash = false;
                            continue;
                        }
                        if ((ncharbits & 1) > 0)
                        {
                            i++;
                            trailingSlash = false;
                            trg[j - 1] = '\n';
                            continue;
                        }
                    }

                    var doubleslashbits = (slashbits >> 2) & slashbits;
                    var slashncharbits = (ncharbits >> 2) & slashbits;

                    var snpos = (int)Bmi1.TrailingZeroCount(slashncharbits) / 2;

                    if (doubleslashbits == 0)
                    {
                        if (slashncharbits == 0)
                        {
                            i += 16; j += 16;
                            trailingSlash = (slashbits & 0x80000000) == 1;
                        }
                        else
                        {
                            j += snpos;
                            trg[j++] = '\n';
                            i += snpos + 1;
                            trailingSlash = false;
                        }
                        continue;
                    }

                    var dspos = (int)Bmi1.TrailingZeroCount(doubleslashbits) / 2;
                    if (slashncharbits != 0 && snpos < dspos)
                    {
                        j += snpos;
                        trg[j++] = '\n';
                        i += snpos + 1;
                        trailingSlash = false;
                    }
                    else
                    {
                        j += dspos;
                        i += dspos + 1;
                        trailingSlash = false;
                    }
                }

                // handle the remainder
                while (i < escaped.Length)
                {
                    if (trailingSlash)
                        switch (s[i])
                        {
                            case 'n':  // \n
                                t[j - 1] = '\n';
                                goto case '\\';
                            case '\\': // double-slash
                                i++;
                                trailingSlash = false;
                                continue;
                        }

                    trailingSlash = s[i] == '\\';
                    t[j++] = s[i++];
                }
                return new string(result, 0, j);
            }
        }
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Отредактировано 06.12.2019 11:25 Sinclair . Предыдущая версия .
Re[2]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Pavel Dvorkin Россия  
Дата: 07.12.19 11:39
Оценка:
Здравствуйте, Sinclair, Вы писали:

Можешь еще ускорить , перейдя на обработку в потоках по частям с последующим слиянием. Если памяти не жалко , конечно.
With best regards
Pavel Dvorkin
Re[3]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Ночной Смотрящий Россия  
Дата: 07.12.19 11:41
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Можешь еще ускорить , перейдя на обработку в потоках по частям с последующим слиянием.


Для строк типичного размера ускорения не будет, можешь сам попробовать.
... << RSDN@Home 1.3.17 alpha 5 rev. 62>>
Re[4]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Pavel Dvorkin Россия  
Дата: 07.12.19 14:16
Оценка:
Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Для строк типичного размера ускорения не будет, можешь сам попробовать.


Для строк типичного размера (десятки, сотня символов) — что ни делай, все равно.
With best regards
Pavel Dvorkin
Re[3]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Sinclair Россия https://github.com/evilguest/
Дата: 07.12.19 17:05
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Можешь еще ускорить , перейдя на обработку в потоках по частям с последующим слиянием. Если памяти не жалко , конечно.

Можно попробовать. Но у меня подозрение, что я и так упираюсь в memory bandwidth. Если это так, то доп. потоки только замедлят.
Вообще, моя SIMD версия хуже обычного по-словного unsafe при больших плотностях заменяемых символов и при вылете за L1 кэш.
Результат, который я опубликовал — врушный, я там неправильно инициализировал тесты.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Ночной Смотрящий Россия  
Дата: 07.12.19 20:19
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Для строк типичного размера (десятки, сотня символов) — что ни делай, все равно.


Тут топик наглядно демонстрирует, что это не так.
... << RSDN@Home 1.3.17 alpha 5 rev. 62>>
Re[3]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: PM  
Дата: 07.12.19 20:57
Оценка: +1
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Можешь еще ускорить , перейдя на обработку в потоках по частям с последующим слиянием. Если памяти не жалко , конечно.


Насколько я помню, многопоточность и SSE вместе нормально не работали из-за throttling. С AVX, похоже, тоже есть трудности:
https://lemire.me/blog/2018/04/19/by-how-much-does-avx-512-slow-down-your-cpu-a-first-experiment/

Intel’s latest processors have advanced instructions (AVX-512) that may cause the core, or maybe the rest of the CPU to run slower because of how much power they use.

Re[9]: 5 вариантов unescape - угадайте какой самый быстрый (
От: Mystic Artifact  
Дата: 13.12.19 19:46
Оценка: +1 -1
Здравствуйте, Mystic Artifact, Вы писали:

@Sinclair, а с чем не согласен?

Давайте измерять например процент branch prediction hit/miss, показателей вагон. Всё доступно. Но они не покажут ничего интересного по сути.

А советовать людям пользоваться говнофреймворком — я считаю неправильно. BenchmarkDotNet — поделка, которая выстрелила абсолютно незаслуженно. Я возбудился в этом топике потому что, вместо принятия объективной реальности и измерения секундомером, началась старая песня про то, что у вас секундомер неправильный и подсовывают какую-то ахинею, в виде другого секундомера, которая работает *только* для хэллоуворд. При этом, акцента на том, что оба секундомера исправны, нужно только ими правильно пользоваться — не делалось.

Так что нет. Гори огнем бенчмаркдотнет. Он в 99% нафиг не упал.

Более того, ТС это и показал.
Re[4]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Mystic Artifact  
Дата: 13.12.19 19:54
Оценка: +1
Здравствуйте, PM, Вы писали:

Там вроде бы три режима энергопотребления, и активное использование этой порнографии приводит к тому, что приводит. Это, в принципе, абсолютно нормально, но только если у тебя не 32+ ядра которые должны быть равномерно загружены. Все компиляторы, может быть кроме clang (не уверен), весьма сильно поумерили свой пыл в использовании инструкций о которых их не просят.
Re[2]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: AlexRK  
Дата: 13.12.19 21:08
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Неожиданно, самый быстрый вариант выглядит так:

S>[cut=AVXUnescape()]

Респектую. Я бы такое не написал. Слишком много низкоуровневой магии для меня.
Re[3]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Sinclair Россия https://github.com/evilguest/
Дата: 14.12.19 05:36
Оценка:
Здравствуйте, AlexRK, Вы писали:

ARK>Респектую. Я бы такое не написал. Слишком много низкоуровневой магии для меня.

Для меня — тоже. В этом коде минимум три бага
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: 5 вариантов unescape - угадайте какой самый быстрый (нео
От: Shmj Ниоткуда  
Дата: 14.12.19 22:26
Оценка:
Здравствуйте, Sinclair, Вы писали:

ARK>>Респектую. Я бы такое не написал. Слишком много низкоуровневой магии для меня.

S>Для меня — тоже. В этом коде минимум три бага

Придирки — ясно же что код тут писался на скорую руку.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.