2
$\begingroup$

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm from the literature. Our algorithm is in MATLAB, and the comparing one is in C++, and the code is publicly available. We did not re-implement the C++ code, to avoid any decrease in the efficiency of their algorithm, and to save time as well.

Now the reviewer is responding: ``It is probable that there is a significant difference in performance between MATLAB and C++. The authors should make it clear if and how the results were normalized to ensure a fair comparison.''

So my question is this: Is there any (scientific) ratio or similar comparison between the efficiency of MATLAB and C++?

When we opted to use the available code, we thought it is completely OK since MATLAB is known to be slower. So using the comparing algorithm in a faster environment is OK. I should add that our algorithm is now performing much better than the comparing one.

PS: I asked the same question in Computer Science but some guy referred me to this community.

$\endgroup$
  • $\begingroup$ "Matlab is known to be slower": it's not necessarily so. For instance, if you compare matrix multiplication in Matlab and a simple hand-written implementation in C++, Matlab wins hand down because it relies on heavily optimized BLAS/MKL libraries. And if 90% of CPU time in your algorithm is spent doing a single large matrix multiplication, it will be the same. For linear algebra primitives, it's not the final programming language that matters, it's the quality of the libraries. $\endgroup$ – Federico Poloni May 15 at 6:42
3
$\begingroup$

So, you are comparing a generally slower Matlab implementation of algorithm A to a generally faster C++ implementation of algorithm B, and still getting the advantage for A. I would say, congratulations, you certainly have a stronger point now, since the "competing" algorithm is given an advantage.

It's worth no note though, that implementation in C++ is not automatically guaranteed to be fast, since it can use bad design, wrong memory access patterns, and even ruin the theoretical complexity of the algorithm in the worst (no so rare, unfortunately) cases. Simultaneously, a Matlab implementation does not have to be slow.

Here, we have at least two questions that discuss a general case:

Anyway, you have four options, in my mind:

  1. Do not change any code. Do not do any new numerical experiments. Explain the testing environment in detail and discuss the advantages of your algorithm.
  2. Do not change any code. Perform a sample "renormalization experiment" on the algorithm C. Take an algorithm that is relevant to your field and you can find a C++ and Matlab implementations of that you expect to be of good quality. Compare the timings and deduce a very shaky, subjective, but relevant to your application area comparison metric. Use that metric only to inform the users about a possible scaling factor range for your Matlab code to even further strengthen your thoughts on the proposed algorithm advantage. Do not renormalize your results.
  3. Reimplement your algorithm A in C++, then you will have a similar environment, and also will be comparing against some publicly-available reference code.
  4. Reimplement their algorithm B in Matlab, then you will have a similar environment; however, you will be comparing two closed-source implementations (solvable) that are done by you.

In the ideal world of infinite available time, I would opt into option 3, and tune up my C++ implementation. Option 4 is slightly worse but has a hidden advantage of comparing codes written by the same developer in a familiar language.

In your situation, I might be totally fine with option 1. Timing comparisons of algorithm implementation are not the best source of data, and usually, give only a rough idea about the algorithm strength. Therefore, the reviewer is probably asking for a detailed description of the test environment.

Things to keep in mind:

  • Compare the theoretical asymptotic complexities of algorithm A and algorithm B. If they are the same, then you are competing in the constants and lower-order terms. In this case, the timing results are slightly more important. However, a more detailed theoretical analysis (for judging constants, lower-order terms, and relevant problem sizes) would go a much longer way.
  • A clear description of the implementation details, test environments, and reproducibility of your experiments will help both to get the paper published and the readers to get the maximum benefits out of it.
  • Consider making the source code of your algorithm A open-source and refer to it in the paper.
$\endgroup$
  • 2
    $\begingroup$ I second Anton's ultimate recommendation. If Matlab is moving faster than C++ you should look to declare victory and move on. If the asymptotic complexity (in space and/or time) of your algorithm is better, that can explain the difference. Another possibility is that you're using a lot of linear algebra, which Matlab has been heavily optimized for. Either way, you should open source your code. $\endgroup$ – Richard May 14 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.