Welcome back and thanks for another great comment.

I meant outer loops but didn’t make it clear so that my bad. You are right about the inner loop. I kind of count the inner loop as a part of the outer loop so speeding up inner loop helps both of them.

You are right about the microarchitectural effects but I would also argue that most microarchitectural effects become important because they occur in the hot kernels (i.e., loops). If a piece of code runs only once, an instruction TLB miss for that code is less of a problem. If the TLB miss occurs in a loop and continues to occur, that is something which becomes a problem. As I have learned in the last three days, I/O is a great counter example and perhaps you are also hinting in the direction.

A minor side note on “If something is not in a loop then the computation time for it is going to be in the seconds at most anyway, and that makes it something not worth optimizing for.” I think you meant to say nanoseconds and not seconds. Seconds is a very long time and I would optimize anything that takes even milliseconds.

Thanks.

Perhaps it is just a matter of terminology but I am unable to see the distinction that you are drawing between parallel programming and multithreaded programming.

Do you mean to say that multithreading is about having multiple threads on a single core while parallel programming is when there is actual concurrent execution?

It sounds interesting and I have never thought of it this way so I am really looking forward to hear a clarification from you.

Thanks.

I agree with most of what you say. Specific answers below:

1) True, I have always wondered if there is a better middle ground, something that isn’t exponential. Just for completion, I want to add two facts: (a) lists also waste space by saving points, (2) memory wastage for “unused” memory is can actually be zero overhead because it is in virtual memory which may never be pages if its never used. This is even more true for 64-bit addressing.

2) Hmm.. I could argue that you can also optimize arrays but from a practical standpoint, I totally agree.

3) I could not agree more. It shouldn’t replace the theory (my blog also has many analytic models:-) ) but it should make theory more realism aware. In fact, CS theory is actually tied to hardware IMO even today, but its tied to old hardware. The whole computes and memory concept is from hardware but when they were first generated, hardware used to be a lot simpler.

Thanks for the great comment. I really enjoy learning new insights.

Thanks for taking the time to run the study. Very powerful.

I generally think of servers as a loop because at a high-level it is running the same code over and over again for every transaction. It is in fact a loop but has a wait_for_work in there somewhere but I do not disagree with you.

Thanks again.

I think I am convinced about the I/O now. So it is I/O + loops then?

Aater

Not everything is a loop – and not all loops are worthy to be parallelized.