Быстрый Array.Split - .NET

Уже задавал вопрос на StackOverflow, но тамошний коллективный разум ничего действенного не подсказал.

Дело вот в чем. Есть массив байтов (размер -- от нескольких байт до нескольких сотен килобайт). Нужно максимально быстро разбить его на куски. Критерий разбиения в моем случае -- по символу \n (0xA):

1, 2, 3, 10, 4, 10, 5, 6, 10, 7, 10 -> 1, 2, 3;  4;  5, 6;  7

По показаниям dotTrace:

"Наивная" версия -- 20 001 мс. на 2 312 вызовов:

public unsafe static Segment[] Split(this byte[] _src, byte value)
{
    var _ln = _src.Length;

    fixed(byte *src = _src)
    {
        if(_ln == 0) return new Segment[] { };

        var segments = new LinkedList<Segment>();// Segment[c];
        var l = 0;
        var j = 0;
        var last = 0;
        var i = 0;

        for(i = 0; i < _ln; i++)
        {
            l++;
            if(src[i] != value) continue;

            segments.AddLast(new Segment(_src, last, l));

            l = 0;
            last = i + 1;
        } // for

        if(last != i)
            segments.AddLast(new Segment(_src, last, _ln - last));

        return segments.ToArray();
    }
}

Оптимизация, предложенная Euphoric -- 4 696 мс на 2 312 вызовов:

public static unsafe Segment[] Split2(byte[] _src, byte value)
{
    var _ln = _src.Length;

    if (_ln == 0) return new Segment[] { };

    fixed (byte* src = _src)
    {
        var segments = new LinkedList<Segment>(); // Segment[c];

        byte* last = src;
        byte* end = src + _ln - 1;
        byte lastValue = *end;
        *end = value; // value-termination

        var cur = src;
        while (true)
        {
            if (*cur == value)
            {
                int begin = (int) (last - src);
                int length = (int) (cur - last + 1);
                segments.AddLast(new Segment(_src, begin, length));

                last = cur + 1;

                if (cur == end)
                {
                    if (lastValue != value)
                    {
                        *end = lastValue;
                    }
                    break;
                }
            }
            cur++;
        }

        return segments.ToArray();
    }
}

Почти в 5 раз быстрее, но все равно ужасно медленно.

Возможно, у вас будут какие-то предложения? Или переписать все на Managed C++ (или как там его нынче называют)?

Здравствуйте, Нахлобуч, Вы писали:

Н>Есть массив байтов (размер -- от нескольких байт до нескольких сотен килобайт). Нужно максимально быстро разбить его на куски.
Н>"Наивная" версия -- 20 001 мс. на 2 312 вызовов:
Н>Оптимизация, предложенная Euphoric -- 4 696 мс на 2 312 вызовов:

Не совсем понятно на каких данных вы вызывали. Вот мой вариант (извините, не знаю что за Segment вы использовали, я просто взял byte[]):

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace testSplit
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("prepare all data...");
            var rnd = new Random();
            var testData = new List<byte[]>();
            for (int iter = 0; iter < 2000; iter++) {
                byte[] arr = new byte[rnd.Next(100000, 200000)];
                for (int i = 0; i < arr.Length; i++)
                    arr[i] = (byte)rnd.Next(256);
                testData.Add(arr);
            }
            Console.WriteLine("Test started!");

            var watch = System.Diagnostics.Stopwatch.StartNew();

            for (int i = 0; i < 2000; i++) {
                var res = Split(testData[i], 10);
            }

            watch.Stop();
            Console.WriteLine("Elapsed sec: "+ (double)watch.ElapsedMilliseconds / 1000);
            Console.ReadKey();
        }

        static List<byte[]> Split(byte[] arr, byte divisor)
        {
            int len;
            var res = new List<byte[]>();
            int SegmentStart = -1;
            for (int i = 0; i < arr.Length; i++) {
                if (arr[i] == divisor) {
                    len = i - SegmentStart - 1;
                    if (len == 0)
                        res.Add(null);
                    else{
                        var seg = new byte[len];
                        Array.Copy(arr, SegmentStart+1, seg, 0, len);
                        res.Add(seg);
                    }
                    SegmentStart = i;
                }
            }
            len = arr.Length - SegmentStart - 1;
            if (len > 0) {
                var seg = new byte[len];
                Array.Copy(arr, SegmentStart + 1, seg, 0, len);
                res.Add(seg);
            }
            return res;
        }
    }
}

Т.е. 2000 массивов, каждый по 100-200КБ. Результат:

prepare all data...
Test started!
Elapsed sec: 0.33

Н>Почти в 5 раз быстрее, но все равно ужасно медленно.

Согласен

ужасно медленно! (это при том, что я даже не касаюсь всяких fixed/unsafe). Может, я чо в алгоритме напортачил?
Система: Win7 x86, i7, 4GB RAM, .NET 4.5

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

M>Согласен

ужасно медленно! (это при том, что я даже не касаюсь всяких fixed/unsafe). Может, я чо в алгоритме напортачил?

Где сравнение с версиями автора?

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

H>Где сравнение с версиями автора?

Где-где... в beyond compare!

Сравнение чего с чем?

Здравствуйте, Нахлобуч, Вы писали:

Н>Дело вот в чем. Есть массив байтов (размер -- от нескольких байт до нескольких сотен килобайт). Нужно максимально быстро разбить его на куски. Критерий разбиения в моем случае -- по символу \n (0xA):

Н>

1, 2, 3, 10, 4, 10, 5, 6, 10, 7, 10 -> 1, 2, 3;  4;  5, 6;  7

Ты делаешь вот что.
1. Проходишь по массиву (этого не избежать)
2. Найдя кусок, копируешь его (я так полагаю, так как конструктора Segment я не вижу) и добавляешь в LinkedList. Одно копирование.
3. По окончании проходишь по LinkedList, выделяешь память и копируешь в массив. Я не знаю реализации LinkedList.ToArray, но скорее всего там свои переаллокации массива, то есть вначале создается массив некоторой длины, а потом, когда его (если) не хватит, создается массив большей длины и копируется текущий в него. Еще одно, а то и не одно копирование. Плюс проход по списку.

В рамках чистого С задача решается на порядок проще. Пункты 2 и 3 просто отсутствуют. Надо создать список из пар (указатель, длина) и заполнить их : 0-й -(начало исходного массива, длина первого куска), 1-й — (начало второго куска, длина второго куска) и т.д. После этого задача фактически решена — каждый указатель показывает на свой массив, длина известна. Копирование данных полностью отсутствует.

Увы, я не знаю, как сделать это в C#, потому что тебе нужен массив Segment[], а два разных массива в C# не могут ссылаться на одно и то же место в памяти (в отличие от указателей C, которые могут).

Если можно отступить от требования создать Segment[], то можно реализовать то, о чем я написал, но вместо указателей использовать индексы. То есть будут пары (индекс начала куска, длина куска). Из этой пары по исходному массиву всегда можно получить данные куска без копирования их. Правда, придется сохранить исходный массив.

Я похожую задачу решал когда-то. Был большой массив байтов (текстовый файл размером в сотни Мб) и его надо было разбить на строки. Прошел по нему, заменил \n на \0 , по ходу действия собрал указатели на начала строк в массив и , пожалуйста — массив указателей на строки ASCIIZ, после чего я его отсортировал тут же на месте, не передвинув ни одного байта строк

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

PD>Здравствуйте, Нахлобуч, Вы писали:

PD>Увы, я не знаю, как сделать это в C#, потому что тебе нужен массив Segment[], а два разных массива в C# не могут ссылаться на одно и то же место в памяти (в отличие от указателей C, которые могут).

В шарпе указатели на элементы массива вполне нормально заменяются индексами этих элементов. Собственно Segment автора — это по сути класс содержащий ссылку на массив, индекс начального элемента в массиве и длину сигмента. Так что весь свой алгоритм один в один переносится на шарп.

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

J>В шарпе указатели на элементы массива вполне нормально заменяются индексами этих элементов.

Они везде нормально заменяются (при линейной памяти). Указатель == указатель_на_начало + индекс, а указатель_на_начало == const. В С/C++ тоже иногда лучше оперировать индексом, например, если возможны ручные переаллокации.
>Собственно Segment автора — это по сути класс содержащий ссылку на массив, индекс начального элемента в массиве и длину сигмента.

Вот в этом не уверен, так как конструктора Segment не вижу. Тут оба варианта возможны, а какой именно сейчас реализован — только ТС знает.

>Так что весь свой алгоритм один в один переносится на шарп.

О чем я и говорю.

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

PD>Вот в этом не уверен, так как конструктора Segment не вижу. Тут оба варианта возможны, а какой именно сейчас реализован — только ТС знает.

В вопросе на SO есть ссылка — http://pastie.org/4592828

... << RSDN@Home (RF) 1.2.0 alpha 5 rev. 67>>

Здравствуйте, Нахлобуч, Вы писали:

Н>Возможно, у вас будут какие-то предложения?

По алгоритму. Пройти один раз, выявить в списке пары (индекс начала; размер). На их основании за раз создать массив массивов фиксированного размера и заполнить его массивами фиксированного размера.

Как вариант, выявить максимальный размер из пар и создать двумерный массив по максимуму, затем его просто заполнить. Будет одно распределение памяти вместо неескольких.

... << RSDN@Home 1.2.0 alpha 5 rev. 66>>

Здравствуйте, Нахлобуч, Вы писали:

Н>Возможно, у вас будут какие-то предложения? Или переписать все на Managed C++ (или как там его нынче называют)?

У меня самый обычный код без ансейфа быстрее работает:

public static Segment[] Split3(byte[] buffer, byte value)
{
        if (buffer.Length == 0)
        {
                return new Segment[0];
        }

        List<Segment> list = null;

        int start = 0;
        int length = 0;
        for (int i = 0; i < buffer.Length; i++)
        {
                if (buffer[i] == value)
                {
                        if (length != 0)
                        {
                                if (list == null)
                                {
                                        list = new List<Segment>(16);
                                }
                                list.Add(new Segment(buffer, start, length));
                        }
                        start = i + 1;
                        length = 0;
                }
                else
                {
                        length++;
                }
        }
        if (length != 0)
        {
                if (list == null)
                {
                        list = new List<Segment>(16);
                }
                list.Add(new Segment(buffer, start, length));
        }
        return list.ToArray();
}

Split1: 1875
Split2: 1803
Split3: 1029

Скрытый текст


namespace ConsoleApplication17
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = new byte[] { 1, 2, 3, 10, 4, 10, 5, 6, 10, 7, 10 };

            var result = Split1(array, 10);
            result = Split2(array, 10);
            result = Split3(array, 10);

            var sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < 10000000; i++)
            {
                result = Split1(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split1: {0}", sw.ElapsedMilliseconds);
            sw.Reset();

            sw.Start();
            for (int i = 0; i < 10000000; i++)
            {
                result = Split2(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split2: {0}", sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            for (int i = 0; i < 10000000; i++)
            {
                result = Split3(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split3: {0}", sw.ElapsedMilliseconds);
            Console.ReadLine();
        }

        public static unsafe Segment[] Split1(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            fixed (byte* src = _src)
            {
                if (_ln == 0) return new Segment[] { };

                var segments = new LinkedList<Segment>();// Segment[c];
                var l = 0;
                var j = 0;
                var last = 0;
                var i = 0;

                for (i = 0; i < _ln; i++)
                {
                    l++;
                    if (src[i] != value) continue;

                    segments.AddLast(new Segment(_src, last, l));

                    l = 0;
                    last = i + 1;
                } // for

                if (last != i)
                    segments.AddLast(new Segment(_src, last, _ln - last));

                return segments.ToArray();
            }
        }

        public static unsafe Segment[] Split2(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            if (_ln == 0) return new Segment[] { };

            fixed (byte* src = _src)
            {
                var segments = new LinkedList<Segment>(); // Segment[c];

                byte* last = src;
                byte* end = src + _ln - 1;
                byte lastValue = *end;
                *end = value; // value-termination

                var cur = src;
                while (true)
                {
                    if (*cur == value)
                    {
                        int begin = (int) (last - src);
                        int length = (int) (cur - last + 1);
                        segments.AddLast(new Segment(_src, begin, length));

                        last = cur + 1;

                        if (cur == end)
                        {
                            if (lastValue != value)
                            {
                                *end = lastValue;
                            }
                            break;
                        }
                    }
                    cur++;
                }

                return segments.ToArray();
            }
        }

        public static Segment[] Split3(byte[] buffer, byte value)
        {
            if (buffer.Length == 0)
            {
                return new Segment[0];
            }

            List<Segment> list = null;

            int start = 0;
            int length = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    if (length != 0)
                    {
                        if (list == null)
                        {
                            list = new List<Segment>(16);
                        }
                        list.Add(new Segment(buffer, start, length));
                    }
                    start = i + 1;
                    length = 0;
                }
                else
                {
                    length++;
                }
            }
            if (length != 0)
            {
                if (list == null)
                {
                    list = new List<Segment>(16);
                }
                list.Add(new Segment(buffer, start, length));
            }
            return list.ToArray();
        }
    }

    public class Segment
    {
        public Segment(byte[] buffer, int start, int length)
        {
            Buffer = buffer;
            Start = start;
            Length = length;
        }

        public byte[] Buffer { get; set; }
        public int Start { get; set; }
        public int Length { get; set; }
    }
}

... << RSDN@Home (RF) 1.2.0 alpha 5 rev. 67>>

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

В принципе, как написал Pavel Dvorkin, пары хранить необязательно, достаточно хранить индексы голов сегментов в одномерном массиве, остальное всё вычисляется. Плюс одно поле под опеределение максимального размера сегмента для распределения результирующего двумерного массива за один раз. Цена, как обычно, память за быстродействие.

... << RSDN@Home 1.2.0 alpha 5 rev. 66>>

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

R>У меня самый обычный код без ансейфа быстрее работает:

Самое забавное, что если выкинуть все "оптимизации" и сделать сегмент структурой, то код становится сопоставим с unsafe:

        public static Segment[] Split4(byte[] buffer, byte value)
        {
            var list = new LinkedList<Segment>();

            int start = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    //if (start < i) // у топикстартера сегменты с нулевой длиной добавляются тоже.
                    //{
                    list.AddLast(new Segment(buffer, start, i - start));
                    //}
                    start = i + 1;
                }
            }

            //if (start < buffer.Length)
            //{
            list.AddLast(new Segment(buffer, start, buffer.Length - start));
            //}

            return list.ToArray();
        }

Split1: 8094    3960
Split2: 2912    3960
Split3: 7423    3946
Split4: 2892    3960

исходники

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication17
{
    class Program
    {
        static void Main(string[] args)
        {
            int arraySize = 1000 * 1000;
            int repeatCount = 4000;
            byte[] array = new byte[arraySize];
            new Random(0).NextBytes(array);

            var result = Split1(array, 10);
            result = Split2(array, 10);
            result = Split3(array, 10);


            var sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < repeatCount; i++)
            {
                result = Split1(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split1: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            sw.Reset();

            sw.Start();
            for (int i = 0; i < repeatCount; i++)
            {
                result = Split2(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split2: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            sw.Reset();
            sw.Start();
            for (int i = 0; i < repeatCount; i++)
            {
                result = Split3(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split3: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);

            sw.Reset();
            sw.Start();
            for (int i = 0; i < repeatCount; i++)
            {
                result = Split4(array, 10);
            }
            sw.Stop();
            Console.WriteLine("Split4: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);

            Console.ReadLine();
        }

        public static unsafe Segment[] Split1(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            fixed (byte* src = _src)
            {
                if (_ln == 0) return new Segment[] { };

                var segments = new LinkedList<Segment>();// Segment[c];
                var l = 0;
                var j = 0;
                var last = 0;
                var i = 0;

                for (i = 0; i < _ln; i++)
                {
                    l++;
                    if (src[i] != value) continue;

                    segments.AddLast(new Segment(_src, last, l));

                    l = 0;
                    last = i + 1;
                } // for

                if (last != i)
                    segments.AddLast(new Segment(_src, last, _ln - last));

                return segments.ToArray();
            }
        }

        public static unsafe Segment[] Split2(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            if (_ln == 0) return new Segment[] { };

            fixed (byte* src = _src)
            {
                var segments = new LinkedList<Segment>(); // Segment[c];

                byte* last = src;
                byte* end = src + _ln - 1;
                byte lastValue = *end;
                *end = value; // value-termination

                var cur = src;
                while (true)
                {
                    if (*cur == value)
                    {
                        int begin = (int)(last - src);
                        int length = (int)(cur - last + 1);
                        segments.AddLast(new Segment(_src, begin, length));

                        last = cur + 1;

                        if (cur == end)
                        {
                            if (lastValue != value)
                            {
                                *end = lastValue;
                            }
                            break;
                        }
                    }
                    cur++;
                }

                return segments.ToArray();
            }
        }

        public static Segment[] Split3(byte[] buffer, byte value)
        {
            if (buffer.Length == 0)
            {
                return new Segment[0];
            }

            List<Segment> list = null;

            int start = 0;
            int length = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    if (length != 0)
                    {
                        if (list == null)
                        {
                            list = new List<Segment>(16);
                        }
                        list.Add(new Segment(buffer, start, length));
                    }
                    start = i + 1;
                    length = 0;
                }
                else
                {
                    length++;
                }
            }
            if (length != 0)
            {
                if (list == null)
                {
                    list = new List<Segment>(16);
                }
                list.Add(new Segment(buffer, start, length));
            }
            return list.ToArray();
        }

        public static Segment[] Split4(byte[] buffer, byte value)
        {
            var list = new LinkedList<Segment>();

            int start = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    //if (start < i)
                    //{
                    list.AddLast(new Segment(buffer, start, i - start));
                    //}
                    start = i + 1;
                }
            }

            //if (start < buffer.Length)
            //{
            list.AddLast(new Segment(buffer, start, buffer.Length - start));
            //}

            return list.ToArray();
        }
    }

    public struct Segment
    {
        public Segment(byte[] buffer, int start, int length)
        {
            Buffer = buffer;
            Start = start;
            Length = length;
        }

        private readonly byte[] Buffer;
        private readonly int Start;
        private readonly int Length;
    }
}

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

Я думаю основной затык по памяти.
Пробуем unsafe, чтение порциями.

Вот мои результаты. Правда обработка хвостов кривая (неправильная, но на время не влияет в общем-то). =)
Сильно не проверял.

AnyCPU (X64):

 Split1: 3547   3960
 Split2: 3296   3960
 Split3: 3074   3946
 Split4: 4009   3960
 Split5: 2425   3959   // читаем uint, LinkedList 
 Split6: 4328   3959   // читаем ulong
Split5L: 2162   3959   // читаем uint, List

x86:

 Split1: 3414   3960
 Split2: 3196   3960
 Split3: 7551   3946   // ох, другой JIT - другие результаты =)
 Split4: 3221   3960
 Split5: 3538   3959
 Split6: 4320   3959
Split5L: 2905   3959

Скрытый текст

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication17
{
    class Program
    {
        static void Main(string[] args)
        {
            int arraySize = 1000 * 1000;
            int repeatCount = 4000;
            byte[] array = new byte[arraySize];
            new Random(0).NextBytes(array);

            /*
            var src = new byte[] { 1, 2, 10, 3, 4, 10, 4, 5, 10, 7, 8, 10, 9, 10, 1 };
            var refRes = SplitNaive(src, 10);
            foreach (var r in refRes)
            {
                Console.WriteLine("{0} {1}", r.Start, r.Length);
            }
            Console.WriteLine();

            var res = Split5(src, 10);
            foreach (var r in res)
            {
                Console.WriteLine("{0} {1}", r.Start, r.Length);
            }
            return;
            */

            // warmup
            var buf = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            var result = Split1(buf, 10);
            result = Split2(buf, 10);
            result = Split3(buf, 10);
            result = Split4(buf, 10);
            result = Split5(buf, 10);
            result = Split5(buf, 10);
            result = Split6(buf, 10);
            result = Split5L(buf, 10);

            var split1 = true;
            var split2 = true;
            var split3 = true;
            var split4 = true;
            var split5 = true;
            var split6 = true;
            var split5l = true;

            var sw = new Stopwatch();
            if (split1)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split1(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split1: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split2)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split2(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split2: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split3)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split3(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split3: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split4)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split4(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split4: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split5)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split5(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split5: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split6)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split6(array, 10);
                }
                sw.Stop();
                Console.WriteLine(" Split6: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            if (split5l)
            {
                sw.Start();
                for (int i = 0; i < repeatCount; i++)
                {
                    result = Split5L(array, 10);
                }
                sw.Stop();
                Console.WriteLine("Split5L: {0}\t{1}", sw.ElapsedMilliseconds, result.Length);
            }
            sw.Reset();

            Console.WriteLine("Press any enter... :)");
            Console.ReadLine();
        }

        public static unsafe Segment[] Split1(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            fixed (byte* src = _src)
            {
                if (_ln == 0) return new Segment[] { };

                var segments = new LinkedList<Segment>();// Segment[c];
                var l = 0;
                var j = 0;
                var last = 0;
                var i = 0;

                for (i = 0; i < _ln; i++)
                {
                    l++;
                    if (src[i] != value) continue;

                    segments.AddLast(new Segment(_src, last, l));

                    l = 0;
                    last = i + 1;
                } // for

                if (last != i)
                    segments.AddLast(new Segment(_src, last, _ln - last));

                return segments.ToArray();
            }
        }

        public static unsafe Segment[] Split2(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            if (_ln == 0) return new Segment[] { };

            fixed (byte* src = _src)
            {
                var segments = new LinkedList<Segment>(); // Segment[c];

                byte* last = src;
                byte* end = src + _ln - 1;
                byte lastValue = *end;
                *end = value; // value-termination

                var cur = src;
                while (true)
                {
                    if (*cur == value)
                    {
                        int begin = (int)(last - src);
                        int length = (int)(cur - last + 1);
                        segments.AddLast(new Segment(_src, begin, length));

                        last = cur + 1;

                        if (cur == end)
                        {
                            if (lastValue != value)
                            {
                                *end = lastValue;
                            }
                            break;
                        }
                    }
                    cur++;
                }

                return segments.ToArray();
            }
        }

        public static Segment[] Split3(byte[] buffer, byte value)
        {
            if (buffer.Length == 0)
            {
                return new Segment[0];
            }

            List<Segment> list = null;

            int start = 0;
            int length = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    if (length != 0)
                    {
                        if (list == null)
                        {
                            list = new List<Segment>(16);
                        }
                        list.Add(new Segment(buffer, start, length));
                    }
                    start = i + 1;
                    length = 0;
                }
                else
                {
                    length++;
                }
            }
            if (length != 0)
            {
                if (list == null)
                {
                    list = new List<Segment>(16);
                }
                list.Add(new Segment(buffer, start, length));
            }
            return list.ToArray();
        }

        public static Segment[] Split4(byte[] buffer, byte value)
        {
            var list = new LinkedList<Segment>();

            int start = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                if (buffer[i] == value)
                {
                    //if (start < i)
                    //{
                    list.AddLast(new Segment(buffer, start, i - start));
                    //}
                    start = i + 1;
                }
            }

            //if (start < buffer.Length)
            //{
            list.AddLast(new Segment(buffer, start, buffer.Length - start));
            //}

            return list.ToArray();
        }

        public static unsafe Segment[] Split5(byte[] buffer, byte value)
        {
            var result = new LinkedList<Segment>();

            var length = buffer.Length;
            fixed (byte* bbuf = buffer)
            {
                var qbuf = (uint*)bbuf;
                var qlen = length / sizeof(uint);
                var qrem = length % sizeof(uint);

                int start = 0;
                while (qlen > 0)
                {
                    uint q = *qbuf;

                    if ((q & 0x000000FF) == (uint)0x0A)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 1;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x0000FF00) == (uint)0x0A00)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 2;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x00FF0000) == (uint)0x0A0000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 3;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF000000) == (uint)0x0A000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 4;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    qbuf++;
                    qlen--;
                }

                // хвост
                if (qrem > 0)
                {
                    for (byte* rbuf = (byte*)qbuf; qrem > 0; rbuf++, qrem--)
                    {
                        if (*rbuf == 10)
                        {
                            var offset = (int)((byte*)qbuf - (byte*)rbuf) + 1;
                            result.AddLast(new Segment(buffer, start, offset - start));
                            start = offset;
                        }
                    }
                }
            }

            return result.ToArray();
        }

        public static unsafe Segment[] Split6(byte[] buffer, byte value)
        {
            var result = new LinkedList<Segment>();

            var length = buffer.Length;
            fixed (byte* bbuf = buffer)
            {
                var qbuf = (ulong*)bbuf;
                var qlen = length / sizeof(ulong);
                var qrem = length % sizeof(ulong);

                int start = 0;
                while (qlen > 0)
                {
                    ulong q = *qbuf;

                    if ((q & 0x000000FF) == (ulong)0x0A)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 1;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x0000FF00) == (ulong)0x0A00)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 2;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x00FF0000) == (ulong)0x000A0000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 3;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF000000) == (ulong)0x0A000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 4;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF00000000) == (ulong)0x0A00000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 5;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF0000000000) == (ulong)0x0A0000000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 6;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF000000000000) == (ulong)0x0A000000000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 7;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF00000000000000) == (ulong)0x0A00000000000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 8;
                        result.AddLast(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    qbuf++;
                    qlen--;
                }

                // хвост
                if (qrem > 0)
                {
                    for (byte* rbuf = (byte*)qbuf; qrem > 0; qrem--)
                    {
                        if (*rbuf == 10)
                        {
                            var offset = (int)((byte*)qbuf - (byte*)rbuf) + 1;
                            result.AddLast(new Segment(buffer, start, offset - start));
                            start = offset;
                        }
                    }
                }
            }

            return result.ToArray();
        }

        public static unsafe Segment[] Split5L(byte[] buffer, byte value)
        {
            var result = new List<Segment>();

            var length = buffer.Length;
            fixed (byte* bbuf = buffer)
            {
                var qbuf = (uint*)bbuf;
                var qlen = length / sizeof(uint);
                var qrem = length % sizeof(uint);

                int start = 0;
                while (qlen > 0)
                {
                    uint q = *qbuf;

                    if ((q & 0x000000FF) == (uint)0x0A)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 1;
                        result.Add(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x0000FF00) == (uint)0x0A00)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 2;
                        result.Add(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0x00FF0000) == (uint)0x0A0000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 3;
                        result.Add(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    if ((q & 0xFF000000) == (uint)0x0A000000)
                    {
                        var offset = (int)((byte*)qbuf - (byte*)bbuf) + 4;
                        result.Add(new Segment(buffer, start, offset - start));
                        start = offset;
                    }

                    qbuf++;
                    qlen--;
                }

                // хвост
                if (qrem > 0)
                {
                    for (byte* rbuf = (byte*)qbuf; qrem > 0; qrem--)
                    {
                        if (*rbuf == 10)
                        {
                            var offset = (int)((byte*)qbuf - (byte*)rbuf) + 1;
                            result.Add(new Segment(buffer, start, offset - start));
                            start = offset;
                        }
                    }
                }
            }

            return result.ToArray();
        }

        public unsafe static Segment[] SplitNaive(byte[] _src, byte value)
        {
            var _ln = _src.Length;

            fixed (byte* src = _src)
            {
                if (_ln == 0) return new Segment[] { };

                var segments = new LinkedList<Segment>();// Segment[c];
                var l = 0;
                var j = 0;
                var last = 0;
                var i = 0;

                for (i = 0; i < _ln; i++)
                {
                    l++;
                    if (src[i] != value) continue;

                    segments.AddLast(new Segment(_src, last, l));

                    l = 0;
                    last = i + 1;
                } // for

                if (last != i)
                    segments.AddLast(new Segment(_src, last, _ln - last));

                return segments.ToArray();
            }
        }

    }

    public struct Segment
    {
        public Segment(byte[] buffer, int start, int length)
        {
            Buffer = buffer;
            Start = start;
            Length = length;
        }

        public readonly byte[] Buffer;
        public readonly int Start;
        public readonly int Length;
    }
}

От:	Нахлобуч	https://hglabhq.com
Дата:	10.06.13 12:33
Оценка:

	От:	matumba
	Дата:	10.06.13 14:33
	Оценка:

От:	hardcase	http://nemerle.org
Дата:	10.06.13 14:44
Оценка:

	От:	matumba
	Дата:	10.06.13 15:28
	Оценка:

	От:	Pavel Dvorkin
	Дата:	10.06.13 17:43
	Оценка:

	От:	fddima
	Дата:	11.06.13 11:27
	Оценка:	18 (1) +1