Информация об изменениях

Сообщение Re: 5 вариантов unescape - угадайте какой самый быстрый (нео от 06.12.2019 8:30

Изменено 06.12.2019 8:31 Sinclair

Старый текст
Новый текст
Разница

Re: 5 вариантов unescape - угадайте какой самый быстрый (неожида

Здравствуйте, Shmj, Вы писали:

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

AVXUnescape()

        [Benchmark]
        public unsafe string AVXUnescape()
        {
            if (!Avx2.IsSupported)
                return UnsafeCharArrayScan();        // fallback для процессоров без AVX2. По-хорошему, надо деградировать постепенно.
            var slash = stackalloc ushort[1] { '\\' };
            var nchar = stackalloc ushort[1] { 'n' };
            var slashes = Avx2.BroadcastScalarToVector256(slash);
            var nchars = Avx2.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);  // вычисляем смещение src 

                while (i + 16 <= escaped.Length)  // проверяем, что остаток больше либо равен длине векторного регистра
                {
                    while (((k + i) & 0xf) > 0)   // медленный поиск для выравнивания по 32-byte boundary
                    {
                        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); // чтение с выравниванием выигрывает примерно 30% времени от обычного
                    var slashbits = (uint)Avx2.MoveMask(Avx2.CompareEqual(current, slashes).AsByte());
                    var ncharbits = (uint)(Avx2.MoveMask(Avx2.CompareEqual(current, nchars).AsByte()));

                    if (slashbits == 0 && ncharbits == 0) // no slashes, no n chars
                    {
                        Avx2.Store(trg + j, current);
                        i += 16; j += 16;
                        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)  // no \\, nor \n - plain copy
                        {
                            Avx2.Store(trg + j, current);
                            i += 16; j += 16;
                            trailingSlash = (slashbits & 0xF0000000) == 1;
                        }
                        else
                        {
                            var n = snpos;
                            while (n >= 4)
                            {
                                var ls = (ulong*)(src + i);
                                var lt = (ulong*)(trg + j);
                                *lt = *ls;
                                n -= 4;
                                i += 4; j += 4;
                            }
                            if (n >= 2)
                            {
                                var qs = (uint*)(src + i);
                                var qt = (uint*)(trg + j);
                                *qt = *qs;
                                n -= 2;
                                i += 2; j += 2;
                            }
                            if (n > 0)
                            {
                                trg[j] = src[i];
                                j++; i++;
                            }
                            trg[j++] = '\n';
                            i += 2;
                        }
                        continue;
                    }

                    var dspos = (int)Bmi1.TrailingZeroCount(doubleslashbits) / 2;
                    if (slashncharbits != 0 && snpos < dspos)
                    {
                        var n = snpos;
                        while (n >= 4)
                        {
                            var ls = (ulong*)(src + i);
                            var lt = (ulong*)(trg + j);
                            *lt = *ls;
                            n -= 4;
                            i += 4; j += 4;
                        }
                        if (n >= 2)
                        {
                            var qs = (uint*)(src + i);
                            var qt = (uint*)(trg + j);
                            *qt = *qs;
                            n -= 2;
                            i += 2; j += 2;
                        }
                        if (n > 0)
                        {
                            trg[j] = src[i];
                            j++; i++;
                        }
                        trg[j++] = '\n';
                        i += 2;
                    }
                    else
                    {
                        var n = dspos + 1; 
                        while (n >= 4)
                        {
                            var ls = (ulong*)(src + i);
                            var lt = (ulong*)(trg + j);
                            *lt = *ls;
                            n -= 4;
                            i += 4; j += 4;
                        }
                        if (n >= 2)
                        {
                            var qs = (uint*)(src + i);
                            var qt = (uint*)(trg + j);
                            *qt = *qs;
                            n -= 2;
                            i += 2; j += 2;
                        }
                        if (n > 0)
                        {
                            trg[j] = src[i];
                            j++; i++;
                        }
                        i++;
                    }
                }

                // 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);
            }
        }

Результаты моего лэптопа — https://files.rsdn.org/5743/TestUnescape.UnescapeTests-report.html.
За единицу взят предыдущий победитель: 7601511.1
N = количество повторов (в оригинале — 2000000, я сократил).
Scale — это коэффициент уменьшения плотности спецсимволов. В оригинале их напихано очень часто; я проверял, как зависит производительность от их частоты. В пределе, при очень больших Scale, в строке вообще не встречается ни \ ни n, и алгоритм вырождается в тупое копирование строки. При scale = 1 частоты совпадают с исходными.
Вот, собственно, код инициализации:

UnescapeTests()

        public UnescapeTests()
        {
            var sb = new StringBuilder(N * 7);

            sb.Append("start:");

            for (int i = 0; i < N; i++)
            {
                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\");

                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\");

                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\n");

                if (_r.Next(1, 4 * Scale) == 1)
                    sb.Append("\n");

                sb.Append("word");
            }

            _escaped = sb.ToString()
                         .Replace("\\", "\\\\")
                         .Replace("\n", "\\n");
        }

Понятно, что по соображениям воспроизводимости Random инициализируется константой. (42).

Re: 5 вариантов unescape - угадайте какой самый быстрый (нео

Здравствуйте, Shmj, Вы писали:

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

AVXUnescape()

        [Benchmark]
        public unsafe string AVXUnescape()
        {
            if (!Avx2.IsSupported)
                return UnsafeCharArrayScan();        // fallback для процессоров без AVX2. По-хорошему, надо деградировать постепенно.
            var slash = stackalloc ushort[1] { '\\' };
            var nchar = stackalloc ushort[1] { 'n' };
            var slashes = Avx2.BroadcastScalarToVector256(slash);
            var nchars = Avx2.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);  // вычисляем смещение src 

                while (i + 16 <= escaped.Length)  // проверяем, что остаток больше либо равен длине векторного регистра
                {
                    while (((k + i) & 0xf) > 0)   // медленный поиск для выравнивания по 32-byte boundary
                    {
                        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); // чтение с выравниванием выигрывает примерно 30% времени от обычного
                    var slashbits = (uint)Avx2.MoveMask(Avx2.CompareEqual(current, slashes).AsByte());
                    var ncharbits = (uint)(Avx2.MoveMask(Avx2.CompareEqual(current, nchars).AsByte()));

                    if (slashbits == 0 && ncharbits == 0) // no slashes, no n chars
                    {
                        Avx2.Store(trg + j, current);
                        i += 16; j += 16;
                        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)  // no \\, nor \n - plain copy
                        {
                            Avx2.Store(trg + j, current);
                            i += 16; j += 16;
                            trailingSlash = (slashbits & 0xF0000000) == 1;
                        }
                        else
                        {
                            var n = snpos;
                            while (n >= 4)
                            {
                                var ls = (ulong*)(src + i);
                                var lt = (ulong*)(trg + j);
                                *lt = *ls;
                                n -= 4;
                                i += 4; j += 4;
                            }
                            if (n >= 2)
                            {
                                var qs = (uint*)(src + i);
                                var qt = (uint*)(trg + j);
                                *qt = *qs;
                                n -= 2;
                                i += 2; j += 2;
                            }
                            if (n > 0)
                            {
                                trg[j] = src[i];
                                j++; i++;
                            }
                            trg[j++] = '\n';
                            i += 2;
                        }
                        continue;
                    }

                    var dspos = (int)Bmi1.TrailingZeroCount(doubleslashbits) / 2;
                    if (slashncharbits != 0 && snpos < dspos)
                    {
                        var n = snpos;
                        while (n >= 4)
                        {
                            var ls = (ulong*)(src + i);
                            var lt = (ulong*)(trg + j);
                            *lt = *ls;
                            n -= 4;
                            i += 4; j += 4;
                        }
                        if (n >= 2)
                        {
                            var qs = (uint*)(src + i);
                            var qt = (uint*)(trg + j);
                            *qt = *qs;
                            n -= 2;
                            i += 2; j += 2;
                        }
                        if (n > 0)
                        {
                            trg[j] = src[i];
                            j++; i++;
                        }
                        trg[j++] = '\n';
                        i += 2;
                    }
                    else
                    {
                        var n = dspos + 1; 
                        while (n >= 4)
                        {
                            var ls = (ulong*)(src + i);
                            var lt = (ulong*)(trg + j);
                            *lt = *ls;
                            n -= 4;
                            i += 4; j += 4;
                        }
                        if (n >= 2)
                        {
                            var qs = (uint*)(src + i);
                            var qt = (uint*)(trg + j);
                            *qt = *qs;
                            n -= 2;
                            i += 2; j += 2;
                        }
                        if (n > 0)
                        {
                            trg[j] = src[i];
                            j++; i++;
                        }
                        i++;
                    }
                }

                // 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);
            }
        }

Результаты моего лэптопа — https://files.rsdn.org/5743/TestUnescape.UnescapeTests-report.html.
За единицу взят предыдущий победитель: https://rsdn.org/forum/dotnet/7601511.1
N = количество повторов (в оригинале — 2000000, я сократил).
Scale — это коэффициент уменьшения плотности спецсимволов. В оригинале их напихано очень часто; я проверял, как зависит производительность от их частоты. В пределе, при очень больших Scale, в строке вообще не встречается ни \ ни n, и алгоритм вырождается в тупое копирование строки. При scale = 1 частоты совпадают с исходными.
Вот, собственно, код инициализации:

UnescapeTests()

        public UnescapeTests()
        {
            var sb = new StringBuilder(N * 7);

            sb.Append("start:");

            for (int i = 0; i < N; i++)
            {
                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\");

                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\");

                if (_r.Next(1, 3 * Scale) == 1)
                    sb.Append("\\n");

                if (_r.Next(1, 4 * Scale) == 1)
                    sb.Append("\n");

                sb.Append("word");
            }

            _escaped = sb.ToString()
                         .Replace("\\", "\\\\")
                         .Replace("\n", "\\n");
        }

Понятно, что по соображениям воспроизводимости Random инициализируется константой. (42).