Быстрая загрузка 350M номеров в двойной массив [] в С#

Ответ 1

Первый вопрос, на который вы, возможно, уже ответили, - "это нужно предварительно вычислить?". Есть ли какой-нибудь алгоритм, который вы можете использовать, который позволит рассчитать требуемые значения по требованию, чтобы избежать этой проблемы? Предполагая, что...

Это всего лишь 2,6 ГБ данных - на 64-битном процессоре у вас не будет проблем с крошечным количеством данных. Но если вы работаете на пятилетнем компьютере с 10-летней ОС, то это не стартер, так как многие данные сразу заполнят доступный рабочий набор для 32-разрядного приложения.

Один подход, который будет очевидным в С++, - это использовать файл с отображением памяти. Это приводит к тому, что данные отображаются в вашем приложении так, как если бы он находился в ОЗУ, но ОС фактически разбивает его на части только по мере его доступа, поэтому используется очень мало реальной ОЗУ. Я не уверен, что вы могли бы сделать это прямо из С#, но вы могли бы легко сделать это в С++/CLI, а затем получить доступ к нему с С#.

В качестве альтернативы, если на вопрос "нужно ли вам все это в ОЗУ одновременно" ответили "да", тогда вы не можете использовать какой-либо подход к виртуализации, поэтому...

Загрузка в несколько потоков не поможет - вы будете связаны с I/O, поэтому у вас будет n потоков, ожидающих данных (и попросив жесткий диск искать между кусками, которые они читают), а не один thread waiitng для данных (который читается последовательно, без поисков). Таким образом, потоки просто вызовут больше усилий и, следовательно, могут замедлить работу. (Единственный случай, когда разделение данных может помочь, - это разделить его на разные физические диски, чтобы можно было читать разные куски данных - не делайте этого в программном обеспечении, покупайте RAID-массив)

Единственное место, где может помочь многопоточность, - это сделать загрузку в фоновом режиме, пока остальная часть вашего приложения запустится, и разрешить пользователю начать использовать часть данных, которые уже загружены, а остальная часть буфера заполняется, поэтому пользователю (надеюсь) не придется много ждать, пока данные загружаются.

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

Однако вы можете значительно ускорить это, сжимая данные. Существует несколько общих подходов, учитывая:

• Если вы знаете что-то о данных, вы можете придумать схему кодирования, которая делает данные меньше (и, следовательно, быстрее загружается). например если значения имеют тенденцию быть близкими друг к другу (например, представьте точки данных, описывающие синусоидальную волну - значения варьируются от очень малых до очень больших, но каждое значение только когда-либо небольшое приращение от последнего), вы можете представляют "дельта" в поплавке, не теряя точности исходных двойных значений, вдвое уменьшая размер данных. Если есть какая-либо симметрия или повторение данных, которые вы можете ее использовать (например, представьте себе, что вы сохраняете все позиции для описания целого круга по сравнению с хранением одного квадранта и используете немного тривиальной и быстрой математики, чтобы отразить его 4 раза - простой способ округлить объем ввода/вывода данных). Любое уменьшение размера данных приведет к соответствующему сокращению времени загрузки. Кроме того, многие из этих схем позволят данным оставаться "закодированными" в ОЗУ, поэтому вы будете использовать гораздо меньше ОЗУ, но все же сможете быстро извлекать данные, когда это было необходимо.

• Кроме того, вы можете легко обернуть свой поток с помощью общего алгоритма сжатия, такого как Deflate. Это может не сработать, но, как правило, стоимость декомпрессии данных на ЦП меньше времени ввода-вывода, которое вы сохраняете, загружая меньше исходных данных, поэтому результатом является то, что он загружается значительно быстрее. И, конечно же, сохраните нагрузку на дисковое пространство.

Ответ 2

Ну, я сделал небольшой тест, и я определенно рекомендую использовать файлы с памятью. Я создал файл, содержащий удвоенные значения 350 Мбайт (как было упомянуто ранее до 2.6 ГБ), а затем проверял время, необходимое для сопоставления файла в памяти, а затем доступ к любому из элементов.

Во всех моих тестах на моем ноутбуке (Win7,.Net 4.0, Core2 Duo 2.0 ГГц, 4 ГБ ОЗУ) потребовалось меньше секунды, чтобы отобразить файл, и в этот момент доступ к любому из элементов занял практически 0 мс (все время находится в проверке индекса). Затем я решил пройти все номера 350M, и весь процесс занял около 3 минут (включая пейджинг), поэтому, если в вашем случае вы должны повторить, это может быть другой вариант.

Тем не менее, я закрыл доступ, например, для целей, которые вы должны проверить перед использованием этого кода, и это выглядит как

public class Storage<T> : IDisposable, IEnumerable<T> where T : struct
{
    MemoryMappedFile mappedFile;
    MemoryMappedViewAccessor accesor;
    long elementSize;
    long numberOfElements;

    public Storage(string filePath)
    {
        if (string.IsNullOrWhiteSpace(filePath))
        {
            throw new ArgumentNullException();
        }

        if (!File.Exists(filePath))
        {
            throw new FileNotFoundException();
        }

        FileInfo info = new FileInfo(filePath);
        mappedFile = MemoryMappedFile.CreateFromFile(filePath);
        accesor = mappedFile.CreateViewAccessor(0, info.Length);
        elementSize = Marshal.SizeOf(typeof(T));
        numberOfElements = info.Length / elementSize;
    }

    public long Length
    {
        get
        {
            return numberOfElements;
        }
    }

    public T this[long index]
    {
        get
        {
            if (index < 0 || index > numberOfElements)
            {
                throw new ArgumentOutOfRangeException();
            }

            T value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            return value;
        }
    }

    public void Dispose()
    {
        if (accesor != null)
        {
            accesor.Dispose();
            accesor = null;
        }

        if (mappedFile != null)
        {
            mappedFile.Dispose();
            mappedFile = null;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        T value;
        for (int index = 0; index < numberOfElements; index++)
        {
            value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            yield return value;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        T value;
        for (int index = 0; index < numberOfElements; index++)
        {
            value = default(T);
            accesor.Read<T>(index * elementSize, out value);
            yield return value;
        }
    }

    public static T[] GetArray(string filePath)
    {
        T[] elements;
        int elementSize;
        long numberOfElements;

        if (string.IsNullOrWhiteSpace(filePath))
        {
            throw new ArgumentNullException();
        }

        if (!File.Exists(filePath))
        {
            throw new FileNotFoundException();
        }

        FileInfo info = new FileInfo(filePath);
        using (MemoryMappedFile mappedFile = MemoryMappedFile.CreateFromFile(filePath))
        {
            using(MemoryMappedViewAccessor accesor = mappedFile.CreateViewAccessor(0, info.Length))
            {
                elementSize = Marshal.SizeOf(typeof(T));
                numberOfElements = info.Length / elementSize;
                elements = new T[numberOfElements];

                if (numberOfElements > int.MaxValue)
                {
                    //you will need to split the array
                }
                else
                {
                    accesor.ReadArray<T>(0, elements, 0, (int)numberOfElements);
                }
            }
        }

        return elements;
    }
}

Вот пример того, как вы можете использовать класс

Stopwatch watch = Stopwatch.StartNew();
using (Storage<double> helper = new Storage<double>("Storage.bin"))
{
    Console.WriteLine("Initialization Time: {0}", watch.ElapsedMilliseconds);

    string item;
    long index;

    Console.Write("Item to show: ");
    while (!string.IsNullOrWhiteSpace((item = Console.ReadLine())))
    {
        if (long.TryParse(item, out index) && index >= 0 && index < helper.Length)
        {
            watch.Reset();
            watch.Start();
            double value = helper[index];
            Console.WriteLine("Access Time: {0}", watch.ElapsedMilliseconds);
            Console.WriteLine("Item: {0}", value);
        }
        else
        {
            Console.Write("Invalid index");
        }

        Console.Write("Item to show: ");
    }
}

UPDATE Я добавил статический метод для загрузки всех данных в файл в массив. Очевидно, что этот подход требует больше времени (на моем ноутбуке занимает от 1 до 2 минут), но после этого производительность доступа - это то, что вы ожидаете от .Net. Этот метод должен быть полезен, если вам приходится часто обращаться к данным.

Использование довольно просто

double[] helper = Storage<double>.GetArray("Storage.bin");

НТН

Ответ 3

Звучит крайне маловероятно, что вы действительно сможете сопоставить это с непрерывным массивом в памяти, поэтому, предположительно, способ, которым вы распараллеливаете нагрузку, зависит от фактической структуры данных.

(Приложение: LukeH указал в комментариях, что в CLR на самом деле имеется жесткий 2GB-ограничение на размер объекта. Это подробно описано в этом другом вопросе SO).

Предполагая, что вы все читаете с одного диска, распараллеливание чтения диска, вероятно, является плохим. Если какая-либо обработка вам нужно делать с числами как после загрузки, вы можете захотеть запустить ее параллельно, в то же время, что вы читаете с диска.

Ответ 4

В типичном случае скорость загрузки будет ограничена скоростью хранения, с которой вы загружаете данные - т.е. жесткий диск.

Если вы хотите, чтобы он был быстрее, вам нужно использовать более быстрое хранилище, т.е. несколько жестких дисков, подключенных к схеме RAID.

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

Если ваши данные как-то предсказуемы, вам может понадобиться разработать схему пользовательского сжатия. F.E. если последовательные номера близки друг к другу, вы можете захотеть сохранить различия между числами --- это может помочь в эффективности сжатия.

Вам действительно нужна двойная точность? Может быть, поплавки будут выполнять эту работу? Может быть, вам не нужен полный диапазон удвоений? Например, если вам нужны полные 53 бит точности мантиссы, но вам нужно хранить только числа от -1,0 до 1,0, вы можете попытаться нарезать несколько бит на число, не сохраняя экспоненты в полном диапазоне.

Ответ 5

Создание этой параллели будет идеей плохой, если вы не используете SSD. Ограничивающим фактором будет диск IO - и если вы запустите два потока, голова будет прыгать назад и вперед между двумя просматриваемыми областями. Это замедлит его намного больше, чем любое возможное ускорение от распараллеливания.

Помните, что диски являются устройствами MECHANICAL и безумно медленны по сравнению с процессором. Если вы можете сделать миллион инструкций, чтобы избежать поиска одной головы, вы все равно выйдете вперед.

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

Ответ 6

Это звучит не очень хорошо для меня. 350 000 000 * 8 байтов = 2 800 000 000 байт. Даже если вам удастся избежать OutOfMemoryException, процесс может быть заменен в/из файла страницы в любом случае. Вы также можете оставить данные в файле и загрузить меньшие патроны по мере необходимости. Дело в том, что только потому, что вы можете выделить столько памяти, это не значит, что вы должны.

Ответ 7

С подходящей конфигурацией диска разделение на несколько файлов на дисках будет иметь смысл - и чтение каждого файла в отдельном потоке будет работать хорошо (если у вас какая-то полосатость - RAID любой:)), тогда это может иметь смысл чтение из одного файла с несколькими потоками).

Я думаю, что вы все-таки скрываетесь, чтобы ничего не предпринимать с помощью одного физического диска.

Ответ 8

Просто увидел:.NET 4.0 поддерживает файлы с отображением памяти. Это был бы очень быстрый способ сделать это, и никакой поддержки, необходимой для распараллеливания и т.д.