Skip to main content

Better Performance Through Transposition

Both Perl and Javascript implement only one-dimensional arrays. To represent a matrix you need to nest arrays within arrays, typically one array for each row, within the overall matrix array.

Each element of the result matrix is the product of one row from the first matrix, and one column from the second. Going from one element to the next in the same row is much quicker than going to another row. The first matrix only changes rows once for each row, N changes, but the second matrix has N^3 changes of row, one for each multiplication.

If we were to transpose the second array, turn the rows into columns and columns into rows, the multiplication could be carried out by by scanning along a row instead of going from row to row.That reduces the cost to N^2. How much will that save us?

I transposed the second array while reading it in:

for my $size ( keys %vars ) {
   my $filestub = q{M_} . $size . q{x} . $size . q{.};
   my ( $f1, $f2 ) = ( $filestub . '1', $filestub . '2' );
   $vars{$size}[0] = readMatrix( $f1 );
   $vars{$size}[1] = transpose( readMatrix( $f2 ));
}

and use pairwise() from List::MoreUtils to multiply corresponding elements of the rows, and sum0() from List::Utils to add up the products.


for my $i ( 0..$rows - 1 ) {
    for my $j ( 0 .. $cols - 1 ) {
    prod[$i][$j] 
        = sum0 pairwise { $a * $b } M->[$i], N->[$j];
    }
}

The results were much the same for both integers and floats.

-➤   perl ./int_benchmark.pl
Processing for 5 seconds each size will take 25 seconds.
Wed Jun 17 15:25:14 2015
              Rate M_100x100   M_32x32   M_10x10     M_5x5     M_2x2
M_100x100   5.54/s        --      -97%     -100%     -100%     -100%
M_32x32      174/s     3046%        --      -97%     -100%     -100%
M_10x10     5114/s    92135%     2832%        --      -85%      -98%
M_5x5      34909/s   629461%    19913%      583%        --      -87%
M_2x2     274124/s  4943582%   157052%     5260%      685%        --
Wed Jun 17 15:25:46 2015

-➤   perl -E '
say "100 => ", 100**3 * 5.54   / 10**6;
say " 32 => ",  32**3 * 174    / 10**6;
say " 10 => ",  10**3 * 5114   / 10**6;
say "  5 => ",   5**3 * 34909  / 10**6;
say "  2 => ",   2**3 * 274124 / 10**6;
'
100 => 5.54
 32 => 5.701632
 10 => 5.114
  5 => 4.363625
  2 => 2.192992

Previous float results were 2.1, 4.1, 4.9, 5.2 and 5.4 MFLOPS for 2x2 ... 100x100 sized matrices. So 10,000 row changes or 1,000,000, it doesn't make much difference.

I modified the Javascript program to operate on a transposed second matrix, but since Javascript doesn't provide a pairwise() routine, I generated a dot-product() routine which takes two rows. But  both integer and float matrices produce much the same results as before ... +/- 10%. So transposing is irrelevant when there's so much other overhead in a scripting language.

Comments

Jakub Narebski said…
If you need performance with linear algebra / large data in Perl, why not use PDL?

Popular posts from this blog

Creating Perl5 Objects with Moxie

Having in the previous article prepared data types for car suits and card ranks, I can now combine them to provide a playing card class, using Stevan Little's Moxie module (version 0.04, so definitely early days.) The goal is to provide an object-oriented paradigm to the Perl 5 programming language which is more sophisticated, more powerful and less verbose than manually bless()-ing hashes. To achieve that goal it needs to be faster and light-weight compared to Moose. Currently, Moxie.pm and and MOP.pm are add-on modules, but eventually, when they are more complete, when the wrinkles have been ironed out, and when they have gained acceptance and a community of users, they might be merged into the Perl core.

One significant feature of Moxie is that it reduces boilerplate code. You don't have to specify warnigns or strict. As well, the features or the perl you are using are enabled, among them say, state, signatures, and post_deref.
A Simple Moxie Class package Card { …

Perl5, Moxie and Enumurated Data Types

Moxie - a new object system for Perl5 Stevan Little created the Moose multiverse to upgrade the Perl 5 programming language's object-oriented system more in line with the wonderfull world of Perl 6. Unfortunately, it's grown into a bloated giant, which has inspired light-weight alternatives Moos, Moo, Mo, and others. Now he's trying to create a modern, efficient OO system that can become built into the language.

I've seen a few of his presentations at YAPC (Yet Another Perl Conference, now known as TPC, The Perl Conference), among them ‎p5 mop final final v5 this is the last one i promise tar gz<. So I was delighted to recently see an announcement of the module Moxie, and decided to try implementing a card game.

While the package provides some POD documentation about the main module, Moxie, it doesn't actually explain the enum package, Moxie::Enum. But delving into the tests directory reveals its secrets.
Creating an Enum package Ranks { use Moxie::Enum; …

Adventures in Autovivification

Having recently started a new job, I was exposed to old code with multi-step tests against autovivification in multi-level hashes. You get used to the code you have seen, but in a new environment it‘s irritating and jarring.
Moose does not generally have the problem, first because class structure is pre-declared, because values are accessed using accessor functions rather than directly, and because responsibility is delegated down to attributes, avoiding long chains. On the other hand, Moose has it's own overhead, so hand-rolled objects, and bare structures still have their use.
If you don‘t protect against autovivification, then mis-spelling a key, or referencing keys which haven‘t been instantiated in this instance, causes those keys to instantly come into existence.
#!/usr/bin/perl use warnings; use strict; use Data::Dump 'dump'; use 5.024; my $var = {key1 => {key2 => {key3 => 'a'}}}; say dump $var; if ( $var->{key1}{key2}{key3b}[13]{foob…