Separable Convolution

Yes, the separable convolution is slower when you convolve a single 3x3 input with a 3x3 kernel. It is faster when you convolve every 3x3 subrectange of a much larger input with the same kernel, which is the common case.

[size="1"]Post may contain wild guessing

This might be quite stupid question, but I don't really get why everybody says that "separable convolution works faster then simple 2D convolution, since with 2D one you have to make N*N multiplications and with separable one you have to make only N+N multiplications". Let's see now: Go here and look at the example at the bottom of the page. First - he does simple 2D convolution - and yes, of course I agree - he made N*N multiplications - so no problem here. But in the second he is presenting separable convolution and does (N*N)+N multiplications, moreover he needs this temporary buffer of N-size to hold the product of the first separable convolution!

I was laughing under my table, when I realized that separable convolution is obviously slower than simple 2D convolution. Try to convince me that I'm a naive idiot

I read through that article and what you just wrote, and I am trying to wrap my head around where the figure (N*N) + N comes from. Let's be a bit more careful with how we are counting the number of multiplications and try to work through this situation again:

Suppose that we are given a w-by-h image, which we shall convolve with a m-by-n kernel. Using the naive convolution method, we compute the convolution in a single pass by just multiplying and summing up all the elements over the support of the kernel. I hope that you agree this takes on the order of o(w * h * m * n) operations.

Next, suppose that we do a separable convolution; then in this case we do 2 passes over the image, one of size m-by-1 and one of size 1-by-n. By the same reasoning as above, this gives a total of O(w * h * (n + m)) operations, which is definitely much less than the first. Though it is true that you now have to use a secondary buffer to store the convolution, with some trickery the size of this secondary buffer can be reduced. In fact, with a bit of effort you can show that the amount of extra memory needed for a sequential implementation of a separable convolution is at most min(w * n, h * m) at no extra run time cost.