Vectorization

From Ufldl

Jump to: navigation, search
(Created page with "When working with learning algorithms, very often having a faster piece of code means that you'll make progress faster on the problem. For example, if your learning algorithm ta...")
 
Line 1: Line 1:
-
When working with learning algorithms, very often having a faster piece of code
+
When working with learning algorithms, having a faster piece of code often
-
means that you'll make progress faster on the problem.  For example, if your
+
means that you'll make progress faster on your project.  For example, if your
learning algorithm takes 20 minutes to run to completion, that means you can
learning algorithm takes 20 minutes to run to completion, that means you can
-
"try" at most one new idea every 20 minutes.  If your code takes 20 hours to
+
"try" up to 3 new ideas per hour.  But if your code takes 20 hours to
-
run, that pretty much means you can "try" only one idea a day, since that's
+
run, that means you can "try" only one idea a day, since that's
-
how long you have to wait before your code finishes and you get feedback on how
+
how long you have to wait to get feedback from your program.  In this latter
-
well it did.  If you can speed up your code so that it takes on 10 hours to
+
case, if you can speed up your code so that it takes only 10 hours to run,  
-
run, that can literally double your productivity as a researcher!
+
that can literally double your personal productivity!
-
'''Vectorization''' refers to a powerful way to speed up your algorithm, by
+
'''Vectorization''' refers to a powerful way to speed up your algorithms.  
-
taking advantage of highly-optimized linear algebra packages. Specifically,
+
Numerical computing and parallel computing researchers have put decades of work
-
numerical computing and parallel computing researchers have put decades of work
+
into making certain numerical operations (such as matrix-matrix multiplication,
into making certain numerical operations (such as matrix-matrix multiplication,
-
matrix-matrix addition, matrix-vector multiplication) fast.  Thus, if you can
+
matrix-matrix addition, matrix-vector multiplication) fast.  The idea of
-
express your learning algorithm in terms of these highly optimized operations,
+
vectorization is that we would like to express our learning algorithms
-
you can make your code run much faster than if you were end up implicitly
+
in terms of these highly optimized operations.
-
implementing some of these operations yourself.
+
-
Concretely, if <math>\textstyle x \in \Re^{n+1}</math> and <math>\textstyle \theta \in \Re^{n+1}</math> are vectors and you need to compute <math>\textstyle z = \theta^Tx</math>,
+
For example, if <math>x \in \Re^{n+1}</math> and <math>\textstyle \theta \in \Re^{n+1}</math> are vectors  
-
you can implement
+
and you need to compute <math>\textstyle z = \theta^Tx</math>,
 +
you can implement (in Matlab):
<syntaxhighlight lang="matlab">
<syntaxhighlight lang="matlab">
z = 0;
z = 0;
Line 25: Line 24:
end;
end;
</syntaxhighlight>
</syntaxhighlight>
-
or you can simply implement
+
or you can more simply implement
<syntaxhighlight lang="matlab">
<syntaxhighlight lang="matlab">
z = theta' * x;
z = theta' * x;
</syntaxhighlight>
</syntaxhighlight>
-
The second piece of code is not only simpler, but it will run \emph{much} faster.
+
The second piece of code is not only simpler, but it will also run ''much'' faster.  
-
More generally, a good rule-of-thumb for coding Matlab and Octave is:
+
More generally, a good rule-of-thumb for coding Matlab/Octave is:
-
::'''Whenever possible, avoid using an explicit for-loop in your code.'''
+
::'''Whenever possible, avoid using explicit for-loops in your code.'''
 +
In particular, the first code example used an explicit <tt>for</tt> loop.  By
 +
implementing the same functionality without the <tt>for</tt> loop, we sped
 +
it up significantly.  A large part
 +
of vectorizing our Matlab/Octave code will focus on getting rid of <tt>for</tt> loops,
 +
since this lets Matlab/Octave extract more parallelism from your code, while
 +
also incurring less computational overhead from the interpreter.
-
[Is multi-threading enabled by default in Matlab?]
+
In terms of a strategy for writing your code, initially you may find that vectorized code is harder to write, read, and/or debug,
-
 
+
and that there may be a tradeoff in ease of programming/debugging vs. running
-
 
+
time.  Thus, for your first few programs, you might choose to first implement  
-
Sometimes, using the vectorization methods describe here can make your code
+
your algorithm without too many vectorization tricks, and verify that it is working correctly
-
significantly harder to program, read, and/or debug (though as you gain
+
-
familiarity with these methods, you'll also find vectorized code easier to
+
-
read).  Thus, there's a tradeoff in ease of programming/debugging and running
+
-
time.  In particular, if the first time you write your program you use all the
+
-
vectorization tricks, your code may be much harder to read and thus you may
+
-
miss bugs or have a harder time finding bugs.
+
-
 
+
-
Thus, sometimes you may first choose to implement your algorithm without too
+
-
many vectorization tricks first, and verify that it is working correctly
+
(perhaps by running on a small problem).  Then only after it is working, you
(perhaps by running on a small problem).  Then only after it is working, you
can vectorize your code one piece at a time, pausing after each piece to verify
can vectorize your code one piece at a time, pausing after each piece to verify
that your code is still computing the same result as before.  At the end, you'll
that your code is still computing the same result as before.  At the end, you'll
then hopefully have a correct, debugged, and vectorized/efficient piece of code.
then hopefully have a correct, debugged, and vectorized/efficient piece of code.
 +
 +
After you become familiar with the most common vectorization methods and tricks,
 +
you'll find that it usually isn't much effort to vectorize your code. Doing
 +
so will make your code run much faster and, in some cases, simplify it too.
 +
 +
 +
{{Vectorized Implementation}}
 +
 +
 +
{{Languages|矢量化编程|中文}}

Latest revision as of 13:07, 7 April 2013

Retrieved from "http://ufldl.stanford.edu/wiki/index.php/Vectorization"
Personal tools