Matrix multiplication

[Steven D'Aprano]

On Tue, 04 Jan 2011 13:22:33 +0100, Zdenko wrote:

> I wrote these two codes for example:
> 
> this one is naive way of matrix multiplication using one thread
[...]
> this one is using two threads, each one is multiplying half of matrix
[...]
> why is second one more than twice slower than first when it should be
> faster. I suspect that problem is in simultaneous access to matrix C but
> i don't know how to solve this.

Can I suggest that your timing code leaves something to be desired?

* You time too much. You're interested in how long it takes to multiply 
two matrices, but you time how long it takes to do much more than just 
the multiplication: your timing code covers the time it takes to create 
the class object (which will be trivial), and build the matrix (non-
trivial), as well as perform the multiplication.

* Your perform the timing test once, which makes it subject to sampling 
errors. (Although if the process takes a long time, say, multiple 
seconds, the sampling error will *probably* be small relative to the 
measured time. But not always.)

* You use time.clock, but without knowing which operating system you are 
running, it's impossible to tell whether you should be using time.time 
instead.

Whether these issues will actually make a practical difference in this 
*specific* case, I don't know, but as a general rule, the most accurate 
way to perform these sorts of timing tests is with the timeit module. 
Something like this:


A = ... # initialise matrix A
B = ... # and B
C = ... # and the result

def mult1(A, B, C):
    # Multiply matrices A and B using 1 thread.
    t = MyThread()
    t.start()
    t.join()

def mult2(A, B, C):
    # Multiply matrices A and B using 2 threads.
    t1 = MyThread()
    t2 = MyThread()
    t1.start()
    t2.start()
    t1.join()  # Block until thread 1 is done.
    t2.join()  # Now block until thread 2 is done.

setup1 = "from __main__ import A, B, C, mult1"
setup2 = "from __main__ import A, B, C, mult2"

from timeit import Timer
t1 = Timer("mult1(A, B, C)", setup1)
t2 = Timer("mult2(A, B, C)", setup2)


# Now perform the timing tests.
best1 = min(t1.repeat())
best2 = min(t2.repeat())

By default, Timer.repeat will measure the time taken by one million 
iterations of the code snippet, and take three measurements. You almost 
always only care about the smallest measurement -- any larger times will 
represent sampling error.

If it takes too long to time one million iterations, either make the 
matrices smaller, or pass keyword arguments number and/or repeat to the 
repeat method:

# best of five measurements of one hundred iterations
best1 = min(t1.repeat(number=100, repeat=5))



-- 
Steven