You need to reduce the \linewidth before using \lstinputlisting, otherwise it uses the full normal line width.
You can do this using \parbox or minipage environment. For example the following code places the listing in a paragraph box with 48% of the normal line width. (Some people use \textwidth which is mostly the same.)
\parbox{.48\linewidth}{\lstinputlisting{file.c}}
The reason why your first example doesn't work is that lstlisting is a verbatim environment and therefore not allowed in arguments of other macros. This is because the code is read as part of the argument before \begin{lstlisting} is processed and tells LaTeX to thread the code verbatim!
If you want to have the code in the main file, you could store the listings in a box which is then used in the \subfloat. This requires minipage because \parbox would also read the listing as macro argument.
\documentclass{article}
\usepackage{xcolor}
\usepackage{subfig}
\usepackage{listings}
\lstset{%
language=C,
frame=single,
numbers=left,
numberstyle=\footnotesize,
tabsize=2,
keepspaces=true,
columns=fullflexible,
basicstyle=\ttfamily\scriptsize,
keywordstyle=\color{blue}
}
\newsavebox{\mylistingbox}
\begin{document}
\begin{figure}
\begin{lrbox}{\mylistingbox}%
\begin{minipage}{.45\linewidth}%
\begin{lstlisting}
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
for(int k = 0 ; k < N ; k++)
c[i][j] += a[i][k] * b[k][j];
\end{lstlisting}%
\end{minipage}%
\end{lrbox}%
%
\subfloat[small code]{\usebox{\mylistingbox}}%
%
\hfill
%
\begin{lrbox}{\mylistingbox}%
\begin{minipage}{.45\linewidth}%
\begin{lstlisting}
for(int ii = 0 ; ii < N ; ii+=B) {
for(int jj = 0 ; jj < N ; jj+=B) {
for(int kk = 0 ; kk < N ; kk+=B) {
for(int i = ii ; i < ii + B ; i++) {
for(int k = kk ; k < kk + B ; k++){
c_i = c[i];
a_ik = a[i][k];
b_k = b[k];
for(int j = jj ; j < jj + B ; j+=2){
c_i[j] += a_ik * b_k[j];
c_i[j+1] += a_ik * b_k[j+1];
}
}
}
}
}
}
\end{lstlisting}%
\end{minipage}%
\end{lrbox}%
%
\subfloat[Larger code]{\usebox{\mylistingbox}}%
\end{figure}
\end{document}
I reduces the font size here to fit both on the normal text width. For figures you could also extend it in the margin using the technique shown be me in Center figure that is wider than \textwidth and Place figures side by side, spill into outer margin.
In your case either use two box registers and then:
\makebox[1.2\textwidth]{\subfloat[Shorter code]{\usebox{\mylistingboxa}}\hfill\subfloat[Larger code]{\usebox{\mylistingboxb}}}
or add the following equivalent lines before and after the whole subfloat related code:
\hbox to 1.2\textwidth\bgroup\hss
% the whole box saving and \subfloat code above
\hss\egroup
If you want to be perfect, you use in all your graphics the same font (for example libertine) and font size (for example 12 pt) used in your document. So the best would be to prepare all graphics in a way, that they can included in your document without changing, scaling, etc. That has the advantage you can build all your images with the same resolution (for example 600 dpi).
If that is not possible, use the same kind of font (for example with or without serifes) and the same font size (I mean not the number here, I mean that it looks as tall/small as the other font).
If you have to change the fontsize, be not too small (everything, legend and numbers, must be readable!) and do not use a greater font size in your images.
For example with a fontsize of 12 pt in your document I would use as lower fontsize in the graphics 10 pt or 11 pt, not smaller.
If you have to scale your images prepare them (that could mean some trial and error runs ;-)) that they have an optimal font size for legend and numbers in the printed document.
Best Answer
I find no way but to manually set the height of both to some fixed length and then control the width of the second one (or the first one) until the output look right.
As you can see we could try to put in some automation (measure the height of teh first one, use this height for the second one or some such) in the process, but the presence of legend in the second one acts as a deterrent.
(I wish I could come up with a more intelligent answer.)