У меня возникла такая задача: нужно обработать файл с данными. Файл разбит на секции длиной около 1 МБ, каждая из них содержит в упакованном виде примерно 100000 записей.Число записей может меняться от секции к секции и записано в заголовке каждой из них. В процессе обработки секция распаковывается, и каждая запись превращается в 20 целых чисел. Для обработки нужно хранить текущую распакованную секцию и несколько предыдущих (где-то 5-10, но может быть и больше – заранее неизвестно, сколько). Вопрос в том, как выделять память для распаковки секций.
Проект, в рамках которого надо решить задачу, пишется на C# под VS 2008 (использование вставок из других языков категорически не приветствуется), основная система, под которой будет работать готовая программа – Windows 7, 64 bit (по крайней мере, пока). И, как обычно, обрабатывать нужно побыстрее.
Первый вопрос, который возникает – надо ли организовывать пул массивов для распаковки, или можно захватывать массив для каждой новой секции заново. Второй вопрос – какой должна быть структура этого массива, что лучше – работать с линейными массивами в 8 МБ длиной, или разбить массив на куски поменьше и организовать, например, массив массивов. Во втором случае – какой должна быть длина этих кусков.
Я взял несколько объектов:
Числа M и N для двумерного массива подбирались так, чтобы M*N=40000000 (что соответствует памяти на 20 секций).
Для каждого объекта измерялось среднее время на создание+заполнение+чтение (после чего объект забывался), а для контроля – время на заполнение+чтение (объект создавался только один раз). Время измерялось в наносекундах на обработанный элемент объекта. Измерение шло два раза: при работе на одном ядре процессора и при работе параллельно на 4 ядрах (во втором случае затраченное время на 4 не умножалось, т.е. результат, как правило, должен получиться меньше, чем в случае одного ядра).
Результаты выглядят так:
В каждой ячейке записано два времени — для одного и четырех ядер.
Что можно извлечь из этой таблички? Во-первых, оказывается, что время на захват памяти линейно зависит от длины массива: один линейный массив длиной 160 МБ захватывается в 100 раз дольше, чем массив длиной 1.6 МБ. Во-вторых, если мы хотим захватить один массив ненадолго, то короткие массивы имеют преимущество: их захват занимает 0.3нс/слово, в то время, как захват длинных – 1.8 нс/слово (разность 3-й и 4-й строчек). Здесь подтверждается часто упоминаемое утверждение, что объекты длиной меньше 88 КБ берутся из отдельного, более быстрого пула. Но если массивов много, картина становится противоположной: на длинные массивы приходится примерно 1.5 нс/слово, а на короткие – 5.8 нс/слово – почти в 4 раза больше! Так что если вам ненадолго нужен многомерный массив, то не стоит делать его ступенчатым с короткими внутренними массивами, лучше поискать другой вариант. Например, захватить одномерный массив и считать индексы.
Кроме того, видно, что моя реализация списка системе не понравилась совсем: когда его длина приблизилась к миллиону, время на создание одного элемента увеличилось примерно в 6 раз по сравнению с короткими списками.
Оптимальным для моей задачи, по-видимому, был бы захват длинных массивов (по одному на распакованную секцию) — если я захочу захватывать массивы каждый раз. Для файла длиной 1600 секций (это типичный размер) потеря времени составила бы 1.5*2*1.6=5 секунд. Правда, сейчас на один из вариантов обработки (без лишних захватов памяти) уходит всего 11 секунд, но есть над чем подумать: другие обработки будут дольше и сложнее. Не исключено, что придется и дальше повторно использовать память везде, где возможно, и не злоупотреблять динамической памятью. Но может быть, и нет.
Проект, в рамках которого надо решить задачу, пишется на C# под VS 2008 (использование вставок из других языков категорически не приветствуется), основная система, под которой будет работать готовая программа – Windows 7, 64 bit (по крайней мере, пока). И, как обычно, обрабатывать нужно побыстрее.
Первый вопрос, который возникает – надо ли организовывать пул массивов для распаковки, или можно захватывать массив для каждой новой секции заново. Второй вопрос – какой должна быть структура этого массива, что лучше – работать с линейными массивами в 8 МБ длиной, или разбить массив на куски поменьше и организовать, например, массив массивов. Во втором случае – какой должна быть длина этих кусков.
Я взял несколько объектов:
- Массив int [][] размером M*N
- Массив int[] длиной N
- Самодельный список длиной N элементов:
class list{ public list next; public int val; }
- Список List<int> длиной N элементов
Числа M и N для двумерного массива подбирались так, чтобы M*N=40000000 (что соответствует памяти на 20 секций).
Для каждого объекта измерялось среднее время на создание+заполнение+чтение (после чего объект забывался), а для контроля – время на заполнение+чтение (объект создавался только один раз). Время измерялось в наносекундах на обработанный элемент объекта. Измерение шло два раза: при работе на одном ядре процессора и при работе параллельно на 4 ядрах (во втором случае затраченное время на 4 не умножалось, т.е. результат, как правило, должен получиться меньше, чем в случае одного ядра).
Результаты выглядят так:
MxN | 8000x5000 | 2000x20000 | 1000x40000 | 100x400000 | 10x4000000 | 1x40000000 |
int[][] | 8.34/7.30 | 8.34/7.02 | 4.08/2.69 | 3.76/2.55 | 3.62/2.58 | 3.63/2.78 |
int[][],R+W | 2.57/1.60 | 2.64/1.60 | 2.22/1.04 | 2.20/1.00 | 2.18/1.00 | 2.09/1.03 |
int[],full | 1.94/1.04 | 1.85/0.96 | 3.4/1.58 | 3.44/2.69 | 3.60/3.63 | 3.60/2.78 |
int[],R+W | 1.58/0.46 | 1.56/0.47 | 1.56/0.47 | 1.57/0.63 | 1.83/0.93 | 2.00/1.05 |
list | 16.30/9.14 | 19.16/19.00 | 21.69/35.17 | 53.8/85.65 | 145/130 | |
list,read | 2.32/0.60 | 2.29/0.61 | 2.31/1.12 | 6.4/2.58 | 7.2/3.67 | |
List<int> | 8.95/4.21 | 11.06/4.74 | 11.98/5.03 | 11.85/6.38 | 11.85/6.98 | 13.71/8.10 |
List<int>,read | 2.95/0.88 | 2.96/0.92 | 2.96/0.92 | 2.96/0.92 | 3.13/1.05 | 4.13/1.65 |
В каждой ячейке записано два времени — для одного и четырех ядер.
Что можно извлечь из этой таблички? Во-первых, оказывается, что время на захват памяти линейно зависит от длины массива: один линейный массив длиной 160 МБ захватывается в 100 раз дольше, чем массив длиной 1.6 МБ. Во-вторых, если мы хотим захватить один массив ненадолго, то короткие массивы имеют преимущество: их захват занимает 0.3нс/слово, в то время, как захват длинных – 1.8 нс/слово (разность 3-й и 4-й строчек). Здесь подтверждается часто упоминаемое утверждение, что объекты длиной меньше 88 КБ берутся из отдельного, более быстрого пула. Но если массивов много, картина становится противоположной: на длинные массивы приходится примерно 1.5 нс/слово, а на короткие – 5.8 нс/слово – почти в 4 раза больше! Так что если вам ненадолго нужен многомерный массив, то не стоит делать его ступенчатым с короткими внутренними массивами, лучше поискать другой вариант. Например, захватить одномерный массив и считать индексы.
Кроме того, видно, что моя реализация списка системе не понравилась совсем: когда его длина приблизилась к миллиону, время на создание одного элемента увеличилось примерно в 6 раз по сравнению с короткими списками.
Оптимальным для моей задачи, по-видимому, был бы захват длинных массивов (по одному на распакованную секцию) — если я захочу захватывать массивы каждый раз. Для файла длиной 1600 секций (это типичный размер) потеря времени составила бы 1.5*2*1.6=5 секунд. Правда, сейчас на один из вариантов обработки (без лишних захватов памяти) уходит всего 11 секунд, но есть над чем подумать: другие обработки будут дольше и сложнее. Не исключено, что придется и дальше повторно использовать память везде, где возможно, и не злоупотреблять динамической памятью. Но может быть, и нет.