C-подобные массивы в Perl
Я хочу создавать и манипулировать большими массивами (4 байта) целых чисел в памяти. Я имею в виду порядка сотен миллионов. Каждая клетка в массиве будет действовать как счетчик позиции на хромосоме. Все, что мне нужно, это чтобы он поместился в памяти и имел быстрый (O(1)) доступ к элементам. То, что я считаю, не является разреженной функцией, поэтому я не могу использовать разреженный массив.
Я не могу сделать это с обычным списком perl, потому что perl (по крайней мере, на моем компьютере) использует 64 байта на элемент, поэтому геномы большинства организмов, с которыми я работаю, слишком велики. Я пытался хранить данные на диске с помощью SQLite и хэширования, и хотя они работают, они очень медленные, особенно на обычных дисках. (Он работает достаточно хорошо, когда я работаю на 4-х дисковом рейде 0).
Я думал, что мог бы использовать массивы PDL, b/c PDL хранит свои массивы точно так же, как это делает C, используя только 4 байта на элемент. Тем не менее, я обнаружил, что скорость обновления крайне низкая по сравнению со списками Perl:
use PDL;
use Benchmark qw/cmpthese/;
my $N = 1_000_000;
my @perl = (0 .. $N - 1);
my $pdl = zeroes $N;
cmpthese(-1,{
perl => sub{
$perl[int(rand($N))]++;
},
pdl => sub{
# note that I'm not even incrementing here just setting to 1
$pdl->set(int(rand($N)), 1);
}
});
Возвращает:
Rate pdl perl
pdl 481208/s -- -87%
perl 3640889/s 657% --
Кто-нибудь знает, как увеличить производительность pdl set(), или знает другой модуль, который может это сделать?
7 ответов
Я не могу сказать, какую производительность вы получите, но я рекомендую использовать vec задокументированная здесь функция для разделения строки на битовые поля. Я экспериментировал и обнаружил, что мой Perl будет терпеть строку до 500_000_000 персонажи длинные. что соответствует 125 000 000 32-битных значений.
my $data = "\0" x 500_000_000;
vec($data, 0, 32)++; # Increment data[0]
vec($data, 100_000_000, 32)++; # Increment data[100_000_000]
Если этого недостаточно, возможно, в сборке Perl есть что-то, что контролирует ограничение. В качестве альтернативы, если вы думаете, что можете получить меньшие поля - скажем, 16-битный счет - vec будет принимать ширину поля любой степени от 2 до 32.
Редактировать: Я считаю, что ограничение размера строки связано с максимальным частным рабочим набором 2 ГБ в 32-разрядных процессах Windows. Если вы работаете в Linux или у вас есть 64-битный Perl, возможно, вам повезет больше, чем мне.
Я добавил в вашу программу тестов, как это
my $vec = "\0" x ($N * 4);
cmpthese(-3,{
perl => sub{
$perl[int(rand($N))]++;
},
pdl => sub{
# note that I'm not even incrementing here just setting to 1
$pdl->set(int(rand($N)), 1);
},
vec => sub {
vec($vec, int(rand($N)), 32)++;
},
});
давая эти результаты
Rate pdl vec perl
pdl 472429/s -- -76% -85%
vec 1993101/s 322% -- -37%
perl 3157570/s 568% 58% --
так используя vec на две трети скорость собственного массива. Предположительно это приемлемо.
Команда PDL, которую вы хотите indadd, (Спасибо Крису Маршаллу, PDL Pumpking, за то, что указал мне на это в другом месте.)
PDL разработан для того, что я называю "векторизованными" операциями. По сравнению с операциями C, операции Perl довольно медленные, поэтому вы хотите свести к минимуму количество вызовов метода PDL и заставить каждый вызов выполнять большую работу. Например, этот тест позволяет указать количество обновлений, которые нужно выполнить за один раз (в качестве параметра командной строки). Сторона perl должна выполнить цикл, но сторона PDL выполняет только пять или около того вызовов функций:
use PDL;
use Benchmark qw/cmpthese/;
my $updates_per_round = shift || 1;
my $N = 1_000_000;
my @perl = (0 .. $N - 1);
my $pdl = zeroes $N;
cmpthese(-1,{
perl => sub{
$perl[int(rand($N))]++ for (1..$updates_per_round);
},
pdl => sub{
my $to_update = long(random($updates_per_round) * $N);
indadd(1,$to_update,$pdl);
}
});
Когда я запускаю это с аргументом 1, я получаю еще худшую производительность, чем при использовании set, чего я и ожидал:
$ perl script.pl 1
Rate pdl perl
pdl 21354/s -- -98%
perl 1061925/s 4873% --
Это много земли для макияжа! Но держись там. Если мы делаем 100 итераций за раунд, мы получаем улучшение:
$ perl script.pl 100
Rate pdl perl
pdl 16906/s -- -18%
perl 20577/s 22% --
И с 10000 обновлений за раунд, PDL превосходит Perl в четыре раза:
$ perl script.pl 10000
Rate perl pdl
perl 221/s -- -75%
pdl 881/s 298% --
PDL продолжает работать примерно в 4 раза быстрее, чем обычный Perl для еще больших значений.
Обратите внимание, что производительность PDL может ухудшиться для более сложных операций. Это потому, что PDL будет выделять и разбирать большие, но временные рабочие пространства для промежуточных операций. В этом случае вы можете рассмотреть возможность использования Inline::Pdlpp, Тем не менее, это не инструмент для начинающих, так что не прыгайте туда, пока не решите, что это действительно лучшее для вас.
Другой альтернативой всему этому является использование Inline::C вот так:
use PDL;
use Benchmark qw/cmpthese/;
my $updates_per_round = shift || 1;
my $N = 1_000_000;
my @perl = (0 .. $N - 1);
my $pdl = zeroes $N;
my $inline = pack "d*", @perl;
my $max_PDL_per_round = 5_000;
use Inline 'C';
cmpthese(-1,{
perl => sub{
$perl[int(rand($N))]++ for (1..$updates_per_round);
},
pdl => sub{
my $to_update = long(random($updates_per_round) * $N);
indadd(1,$to_update,$pdl);
},
inline => sub{
do_inline($inline, $updates_per_round, $N);
},
});
__END__
__C__
void do_inline(char * packed_data, int N_updates, int N_data) {
double * actual_data = (double *) packed_data;
int i;
for (i = 0; i < N_updates; i++) {
int index = rand() % N_data;
actual_data[index]++;
}
}
Для меня функция Inline постоянно превосходит как Perl, так и PDL. Для больших значений $updates_per_roundскажем 1000, я получаю Inline::CВерсия примерно в 5 раз быстрее, чем чистый Perl, и в 1,2 - 2 раза быстрее, чем PDL. Даже когда $updates_per_round равно 1, где Perl легко превосходит PDL, встроенный код в 2,5 раза быстрее, чем код Perl.
Если это все, что вам нужно сделать, я рекомендую использовать Inline::C,
Но если вам нужно выполнить множество манипуляций с вашими данными, вам лучше всего использовать PDL для его мощности, гибкости и производительности. Смотрите ниже, как вы можете использовать vec() с данными PDL.
PDL::set() а также PDL::get() предназначены больше как учебное пособие, чем что-либо еще. Они представляют собой пессимальный способ доступа к переменным PDL. Вам было бы намного лучше использовать некоторые встроенные процедуры массового доступа. Сам конструктор PDL принимает списки Perl:
$pdl = pdl(@list)
и достаточно быстро. Вы также можете загрузить свои данные непосредственно из файла ASCII, используя PDL::rcolsили из двоичного файла, используя одну из многих процедур ввода-вывода. Если у вас есть данные в виде упакованной строки в машинном порядке, вы даже можете получить доступ к памяти PDL напрямую:
$pdl = PDL->new_from_specification(long,$elements);
$dr = $pdl->get_dataref;
$$dr = get_my_packed_string();
$pdl->upd_data;
Также обратите внимание, что вы можете "иметь свой торт и есть его", используя объекты PDL для хранения ваших массивов целых чисел, вычислений PDL (таких как indadd) для крупномасштабных манипуляций с данными, но и использовать vec() непосредственно на данных PDL в виде строки, которую вы можете получить через get_dataref метод:
vec($$dr,int(rand($N)),32);
Вам нужно будет bswap4 данные, если вы находитесь в системе с прямым порядком байтов:
$pdl->bswap4;
$dr = $pdl->get_dataref;
vec($$dr,int(rand($N)),32)++;
$pdl->upd_data;
$pdl->bswap4;
И вуаля!
PDL выигрывает, когда операции могут быть пронизаны, очевидно, он не оптимизирован для произвольного доступа и назначения. Возможно, кто-то с большим знанием PDL мог бы помочь.
Так как использовали целые числа, что должно быть хорошо для использования с хромосомами попробуйте это
use PDL;
use Benchmark qw/cmpthese/;
my $N = 1_000_000;
my @perl;
@perl = (0 .. $N - 1);
my $pdl;
$pdl = (zeroes($N));
cmpthese(-1,{
perl => sub{
$perl[int(rand($N))]++;
},
pdl2 => sub{
# note that I'm not even incrementing here just setting to 1
$pdl->set(int(rand($N)), 1);
$pdl2 = pack "w*", $pdl;
}
});
и результат, который я получил от этого, был...
Rate pdl2 perl
pdl2 46993/s -- -97%
perl 1641607/s 3393% --
который показывает большую разницу в производительности по сравнению с тем, когда я впервые попробовал этот код без добавления в мои 2 цента, которые я получил
Rate pdl perl
pdl 201972/s -- -86%
perl 1472123/s 629% --
Packed::Array на CPAN может помочь.
Packed::Array предоставляет упакованный класс целочисленных массивов со знаком. Массивы, созданные с использованием Packed::Array, могут содержать только целые числа со знаком, которые соответствуют целым числам, встроенным в платформу, но занимают столько памяти, сколько фактически требуется для хранения этих целых чисел. Таким образом, для 32-разрядных систем вместо 20 байтов на запись массива они занимают только 4.
Мой ответ выше может быть бесполезным... это может помочь...
use PDL;
$x = sequence(45000,45000);
Теперь это не будет работать, если у вас есть 16 ГБ оперативной памяти и использовать
$PDL::BIGPDL=1;