Branch prediction is not the only reason this is faster and probably not even the biggest reason.
Since the array is sorted,
if (data[c] >= 128)
will evaluate to true consecutively. When the cache requests something from memory, it will request blocks containing multiple words at a time. Since every data[c] that needs to be added to sum is in a contiguous piece of memory, the code is minimizing the number of times a block is transferred from memory to the cache. This is the concept of spatial locality[1].
No. The "true" or "false" value of a simple expression isn't stored in memory. It's stored as a bit in the status register as a side effect of the "cmp" instruction†. It is no faster for "cmp" to set "true" than it is to set "false".
† (CMP is actually setting carry, overflow, sign, zero, &c; "truth" or "falsity" is decided by the specific conditional jump, here JL, which checks if sign != overflow).
That's not what I was saying. I was indicating that more memory accesses would be required in unsorted data for the `sum += data[c]` computation, obviously overlooking that data[c] is already in a cache, and probably in a register as a result of the comparison with 128.
But that is true whether the array is sorted or not; the indexes (and therefore memory accesses) in the loop are still in order even if the contents of the array are not sorted.
For the record: I acknowledge that you were not wrong in the way I understood you to be wrong; I responded because I got the sense that the thread was now discussing the storage of boolean expression results, and klaxons inside my nerd brain started going off.
You're right, that's a pretty careless mistake. Considering that, the only way to stretch this into locality would be to assume that sum would be used in rapid enough succession so as to be able to live in a register instead of go back to a cache or even memory. That difference seems negligible, though.
I don't think this is true. The loop that sums the values always fetches the array items linearly. Whether they are sorted or not does not make any difference. Since the accumulator ('sum') can be kept in a register there should be no store operations in the inner loop, which means it reduces to simply reading consecutive memory, inspecting the values, and adding some of them to a register.
Branch mispredictions are the only likely cause for the runtime difference. It would be interesting to see whether using multiplexing (sum += data[c] > 128 ? data[c] : 0) or conditional assignments would make any difference. Some CPU's have opcodes for these that don't require branching, but I'm not sure whether they use the branch prediction logic.
In an optimized build data[c] is read from memory only once per loop iteration, so the memory read patterns are identical in the sorted and unsorted cases.
Comments
Branch prediction is not the only reason this is faster and probably not even the biggest reason.
Since the array is sorted,
will evaluate to true consecutively. When the cache requests something from memory, it will request blocks containing multiple words at a time. Since every data[c] that needs to be added to sum is in a contiguous piece of memory, the code is minimizing the number of times a block is transferred from memory to the cache. This is the concept of spatial locality[1].[1]http://en.wikipedia.org/wiki/Locality_of_reference#Locality_...
No. The "true" or "false" value of a simple expression isn't stored in memory. It's stored as a bit in the status register as a side effect of the "cmp" instruction†. It is no faster for "cmp" to set "true" than it is to set "false".
† (CMP is actually setting carry, overflow, sign, zero, &c; "truth" or "falsity" is decided by the specific conditional jump, here JL, which checks if sign != overflow).
That's not what I was saying. I was indicating that more memory accesses would be required in unsorted data for the `sum += data[c]` computation, obviously overlooking that data[c] is already in a cache, and probably in a register as a result of the comparison with 128.
Yes, the value is in a register.
But that is true whether the array is sorted or not; the indexes (and therefore memory accesses) in the loop are still in order even if the contents of the array are not sorted.
The counter also doesn't need cache; it gets assigned a register.
I know. Let me state it another way.
"I was wrong, but not in the way that you(tptacek) understood me to be."
For the record: I acknowledge that you were not wrong in the way I understood you to be wrong; I responded because I got the sense that the thread was now discussing the storage of boolean expression results, and klaxons inside my nerd brain started going off.
Eh, what new item is it requesting from memory inside the branch?
Whether the condition evaluates to true or false it has already retreived the value from the data array in order to test it against the condition.You're right, that's a pretty careless mistake. Considering that, the only way to stretch this into locality would be to assume that sum would be used in rapid enough succession so as to be able to live in a register instead of go back to a cache or even memory. That difference seems negligible, though.
You can just compile the code and look at it; yes, the sum gets a register.
I don't think this is true. The loop that sums the values always fetches the array items linearly. Whether they are sorted or not does not make any difference. Since the accumulator ('sum') can be kept in a register there should be no store operations in the inner loop, which means it reduces to simply reading consecutive memory, inspecting the values, and adding some of them to a register.
Branch mispredictions are the only likely cause for the runtime difference. It would be interesting to see whether using multiplexing (sum += data[c] > 128 ? data[c] : 0) or conditional assignments would make any difference. Some CPU's have opcodes for these that don't require branching, but I'm not sure whether they use the branch prediction logic.
In an optimized build data[c] is read from memory only once per loop iteration, so the memory read patterns are identical in the sorted and unsorted cases.