C-подобные массивы в Perl - PullRequest
8 голосов
/ 16 марта 2012

Я хочу создавать и манипулировать большими массивами (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 ]

8 голосов
/ 16 марта 2012

Я не могу сказать, какую производительность вы получите, но я рекомендую использовать функцию 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 - это две трети скорости собственного массива. Предположительно это приемлемо.

7 голосов
/ 22 марта 2012

Требуемая команда 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%   --

И с 10 000 обновлений за раунд, 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.

4 голосов
/ 18 апреля 2012

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;

Эт, вуаля!

2 голосов
/ 18 апреля 2012

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

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%   -- 
2 голосов
/ 16 марта 2012

Packed :: Array в CPAN может помочь.

Packed :: Array предоставляет упакованный класс массива целых чисел со знаком.Массивы, созданные с использованием Packed :: Array, могут содержать только целые числа со знаком, которые соответствуют целым числам, встроенным в платформу, но занимают столько памяти, сколько фактически требуется для хранения этих целых чисел.Таким образом, для 32-разрядных систем вместо того, чтобы занимать около 20 байт на элемент массива, они занимают всего 4 *. 1006 *

2 голосов
/ 16 марта 2012

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

0 голосов
/ 12 мая 2013

Мой приведенный выше ответ может быть бесполезным ... это может помочь ...

 use PDL;
$x = sequence(45000,45000);

теперь, когда это не сработает, если у вас нет 16 ГБ ОЗУ и вы используете

$PDL::BIGPDL=1;
...