Arista Networks Interview Question
Country: United States
good answer ....it is depends on computer architecture.but i have small doubt ...i guess it may depend on how array elements are stored ....there are concepts ROW-MAJOR ,COLUMN-MAJOR ..do these concepts have any effect on the question.
If the memory is accessed sequentially, the code will probably be faster. Simple as that.
Row-major vs. column-major determines whether each row is stored as a contiguous chunk or whether each column is a contiguous chunk. Since contiguous memory locations should be read sequentially, the algorithm should read either row-by-row or column-by-column depending on whether the matrix is row-major or column-major. If the desired printouts are in row-major order, it'll be better to store the matrix in row-major order.
At the end of each 'for' block there is a comparison operation to check weather to continue or not. For the inner 'for' loop this check is always row*column times but we can save this for the outer 'for' loop. Hence func1() is better.
even if rows are 100,000 and cols are 10,000 -> first one is better.. due to cache performance (read above answer: eugene.yarovoi) and also disk performance (disk head) will be better - it will access in increasing order of memory -- rather than going back and forth.. all cols are always placed together : EG: say each data is 4 bytes, subsequent cols addresses will be baseaddr+4,+8+12,+16..-> easier to read... Consider if rows are accessed (in the inner loop) then baseaddr+40,000 bytes +80,000 bytes .. all the way and then again back at baseaddr+40004, +80004,+12004,...
Hmmm...it appears that not that many people who have answered so far have studied computer architecture.
- eugene.yarovoi January 19, 2012Performance will probably be better for the first function because the data being accessed is arranged sequentially (or mostly sequentially) in memory. This is faster because doing a read on one memory location will cause adjacent memory locations to be brought into the cache, so when they are read, they will be read much faster than if they weren't in the cache.
The reason everyone should really know about things like this is because the performance difference can be absolutely dramatic. About 5 years ago, I was working on optimizing the performance of a project that had code like in the second function. I was able to increase the speed of some loops just like that by a factor of 10 when programming in C by accessing memory sequentially.