Skip to main content

Posts

Showing posts from June, 2015

Bash Inefficient Matrix Multiplication

Bash can only handle integer arithmetic. To process floats, you need to shell out to 'bc' or some other external utility. The core multiplication changes to:

result=`echo "$result + $m * $n" | bc`;
Boy, does that slow things down! For each multiplication, you're launching a shell, invoking a program, returning results. The result is 800 multiplications a second. Note this is running on integer matrices, there remain unresolved problems processing floats.


One obvious problem is shelling out for every multiplication. More efficient is to accumulate the expression to calculate, and just invoke the external calculator once. Now we only shell out N^2 times, instead of N^3, so increasing matrix size leads to better performance, up to a limit. the 32x32 matrix gives 18x performance compared to the simpler version. This implies the 32x reduction in shelling out is offset by the cost of building the expression. By the time we reach 100x100, overhead costs are overwhe…

BASH Matrix Multiplication

tl;dr Bash is not the language for math-intensive operations.



REPS=$1; FILE_1=$2; FILE_2=$3 OUTFILENAME=$4; readonly COLS=`head -1 $FILE_1 | wc -w`; readonly ROWS=`cat $FILE_1 | wc -l`; # echo "rows is $ROWS; cols is $COLS" if [[ $ROWS != $COLS ]]; then echo "Expecting square matrices, " \ "but rows = $ROWS, cols = $COLS\n"; exit 1; fi # -------------------------------------------------- # SUBROUTINES # function outputMatrix() { local matrixname=$1; local matrix; local elem; echo "matrix is '$matrixname'."; eval matrix=\( \${${matrixname}[@]} \); local i=0; for elem in "${matrix[@]}"; do echo -n "$elem "; if (( ++i == $COLS )); then echo ''; i=0; fi done } function multiply() { declare -a product; local M=$1 N=$2; local i j k idx1 idx2 idx3; for ((i=0; i < $ROWS; i++ )); do for ((j=0; j<$COLS; j++)); do …

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' …

Linpack FLOPS Benchmark

The numbers I've been reporting for Javascript and Perl performance need a context. Are they running on a Commodore 64, or a super-computer? Nope, it's my laptop, and here's what Linpack has to report about it: 4 core, 8 thread (Intel core i7) at 3.389 GHz. Peak performance is 46 GFLOPS.

Javascript and Perl are both single-threaded, so you only get 1/8 peak performance, 5 3/4 GFLOPS. That's still 1000 times the performance we actually achieve on more convenient languages. You have to sacrifice some things to gain benefits. On the optimistic side, a moderately fast modern computer sunning Perl or Javascript is almost as fast as  Sparc-10 running LINPACK.
Intel(R) LINPACK data Current date/time: Fri Jun 12 01:19:06 2015 CPU frequency: 3.389 GHz Number of CPUs: 1 Number of cores: 4 Number of threads: 8 Parameters are set to: Number of tests : 15 Number of equations to solve (problem size) : 1000 2000 5000 10000 15000 18000 20000 22000…

Perl Floating Point-Multiplication Benchmark

I was worried whether I was making basic errors in testing the Perl version, so I decided to use the Benchmark module to get the numbers. I copied the matmult.pl file and added use Benchmark ':all' to the header of the file. The main() routine got changed to :
my $time = $ARGV[0] || 5; my %vars = ( 2 => [], 5 => [], 10 => [], 32 => [], 100 => [], ); for my $size ( keys %vars ) { my $filestub = q{F_} . $size . q{x} . $size . q{.}; $vars{$size}[0] = readMatrix( $filestub . '1' ); $vars{$size}[1] = readMatrix( $filestub . '2' ); } say "Processing for $time seconds each size ", "will take @{[5 * $time]} seconds."; say scalar localtime; cmpthese( -$time, { 'F_2x2' => sub { matmult( $vars{2}[0], $vars{2}[1]); }, 'F_5x5'…

Perl Float Matrix Multiplication

Floating point performance compared to integer multiplication on Perl


This is much the same as Perl Integer performance, and disappointly inferior to Javascript. Not a whole lot worse, comparable, really, but MY language should be better than the OTHER language! :-)


Perl Matrix Multiplication

Here's the Perl script for matrix multiplication. It's derived from the RosettaCode site with slight modifications ... I didn't like some things about their way of doing things, but it's much the same in the end.
#! /usr/bin/perl5.20.2 use 5.020; use warnings; use strict; use English; use Time::HiRes qw(gettimeofday tv_interval); use autodie; use Data::Dumper; # ------------------------------------------------------- # SUBROUTINES # # ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ # matmult - multiple matrices. Copied from # RosettaCode.orgwiki/Matrix_multiplication#Perl. # sub matmult { my ( $M, $N ) = @_; my ( $rows, $cols ) = (scalar @$M, scalar @{$N->[0]} ); my $prod = []; my $k = @$N - 1; for my $i ( 0..$rows - 1 ) { for my $j ( 0 .. $cols - 1 ) { $prod->[$i][$j] += $M->[$i][$_] * $N->[$_][$j] for 0..$k; } } return $prod; } # ⋯ ⋯ ⋯ …

Node JS Multiplying Float Matrices

I don't know why I wrote such stupid code for readMatrix.js. I guess when someone uses a new language their brain cells seize up, effective function becomes impossible.

After tests I ran on Friday, I wanted to see how Javascript does with floating point numbers? JS only supports 64 bit floating-point numbers, but there must be special code in their to make integers look like integers ... unless their isn't.

When I went to update my code to support numbers with fractions, my first thought was to flag whether a decimal point had been seen and then keep track of the value by which to divide, multiplying by ten for each fractional digit. I quickly realized I was sinking into the mire of coding stupidity; JS must have a function to convert strings into integers or floats, and indeed it has parseInt() andparseFloat(). But in my research I discovered ( or re-discovered ) that there's no need for the conversion. Like Perl, JS allows arithmetic on the string representation of numbe…

Node JS As The Universal Shell Scripting System

For the past 20 years, I've focused on programming in real languages for real applications, as opposed to web stuff, :-). When I have dealt with the web, it's been using server-side scripts. Definitely not that Javascript crud. Mind you, back when I worked for a porn website, they also came up with a JS based website, Simple.com, long before other people were doing all-JS interfaces.

But the time has come to re-evaluate ... well, everything. Javascript can be checked for validity and style using JSHint & JSLint; it can be debugged. There are frameworks and layers that make it possible to do useful things easily, treating old JS as a sort of widely-supported low-level language on which to implement more elegant systems.

One of these new paradigms is the implementation of node.js to run JS programs on the server, rather than in a web page. Node uses the Google's V8 Javascript engine from the Chrome browser, which means a large corporation ensures high performance on Wind…