Хранение больших интерполяционных таблиц

Я разрабатываю приложение, которое использует очень большие таблицы поиска для ускорения математических вычислений. Самая большая из этих таблиц — int[], в которой около 10 миллионов записей. Не все таблицы поиска являются int[]. Например, один из них — это словарь с примерно 200 000 статей. В настоящее время я создаю каждую таблицу поиска один раз (что занимает несколько минут) и сериализую ее на диск (со сжатием), используя следующий фрагмент:

    int[] lut = GenerateLUT();
    lut.Serialize("lut");

где Serialize определяется следующим образом:

    public static void Serialize(this object obj, string file)
    {
        using (FileStream stream = File.Open(file, FileMode.Create))
        {
            using (var gz = new GZipStream(stream, CompressionMode.Compress))
            {
                var formatter = new BinaryFormatter();
                formatter.Serialize(gz, obj);
            }
        }
    }

Раздражение, которое у меня возникает, заключается в том, что при запуске приложения десериализация этих таблиц поиска занимает очень много времени (более 15 секунд). Этот тип задержки будет раздражать пользователей, поскольку приложение будет непригодным для использования, пока не будут загружены все таблицы поиска. В настоящее время десериализация выглядит следующим образом:

     int[] lut1 = (Dictionary<string, int>) Deserialize("lut1");
     int[] lut2 = (int[]) Deserialize("lut2");
 ...

где Deserialize определяется как:

    public static object Deserialize(string file)
    {
        using (FileStream stream = File.Open(file, FileMode.Open))
        {
            using (var gz = new GZipStream(stream, CompressionMode.Decompress))
            {
                var formatter = new BinaryFormatter();
                return formatter.Deserialize(gz);
            }
        }
    }

Сначала я подумал, что причиной замедления может быть сжатие gzip, но его удаление сократило лишь несколько сотен миллисекунд из подпрограмм сериализации/десериализации.

Может ли кто-нибудь предложить способ ускорить время загрузки этих таблиц поиска при первоначальном запуске приложения?


person snazzer    schedule 20.07.2009    source источник


Ответы (5)


Во-первых, десериализация в фоновом потоке предотвратит «зависание» приложения в это время. Одного этого может быть достаточно, чтобы позаботиться о вашей проблеме.

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

При этом, в зависимости от схемы использования, база данных может быть лучшим подходом. Вы всегда можете сделать что-то, более ориентированное на базу данных, и лениво построить таблицу поиска из БД (т. е. поиск — это поиск в LUT, но если поиск не существует, загрузите его из БД и сохраните это в таблице). Это сделало бы запуск мгновенным (по крайней мере, с точки зрения LUT) и, вероятно, по-прежнему обеспечивало бы достаточно быстрый поиск.

person Reed Copsey    schedule 21.07.2009

Я предполагаю, что очевидное предложение состоит в том, чтобы загрузить их в фоновом режиме. Как только приложение запущено, пользователь открыл свой проект и выбрал любую операцию, которую он хочет, ждать осталось не так много из этих 15 секунд.

person Draemon    schedule 20.07.2009
comment
Я согласен с этим, но это все еще своего рода обходной путь. Что касается моего приложения, графический интерфейс достаточно прост, чтобы пользователь был готов выполнить вычисление менее чем за 5 секунд. Итак, на данный момент я стремлюсь к времени загрузки 5 секунд или меньше (где таблицы поиска будут загружаться в фоновом режиме менее чем за 5 секунд). - person snazzer; 21.07.2009

О каком количестве данных мы здесь говорим? По моему опыту, чтение гигабайта с диска в память занимает около 20 секунд. Поэтому, если вы читаете больше половины гигабайта, вы почти наверняка сталкиваетесь с аппаратными ограничениями.

Если скорость передачи данных не является проблемой, то фактическая десериализация требует времени. Если у вас достаточно памяти, вы можете загрузить все таблицы в буферы памяти (используя File.ReadAllBytes()), а затем десериализовать из потока памяти. Это позволит вам определить, сколько времени занимает чтение и сколько времени занимает десериализация.

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

person Jim Mischel    schedule 21.07.2009
comment
Общий объем данных таблиц поиска на диске составляет менее 100 мегабайт, поэтому я думаю, что ограничения на передачу данных можно исключить. - person snazzer; 21.07.2009

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

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

person Joel Coehoorn    schedule 21.07.2009

Зачем их застегивать?

Диск больше, чем оперативная память.

Прямое двоичное чтение должно быть довольно быстрым.

person Mike Dunlavey    schedule 21.07.2009