Overwriting vs. Lookup

I was reading through the SparseArray class in android, and came across the following method:

public void removeAt(int index) {
    if (mValues[index] != DELETED) {
        mValues[index] = DELETED;
        mGarbage = true;
    }
}

Clearly this could as well has been written:

public void removeAt(int index) {      Or   public void removeAt(int index) {
    if (mValues[index] != DELETED) {            mValues[index] = DELETED;
        mValues[index] = DELETED;               mGarbage = true;
        if (!mGarbage)                      }
            mGarbage = true;         
    }                                
}                                    

It would seem the android developers believed the array lo开发者_如何学Cokup mValues[index] was faster than an array write, but the variable lookup wasn't faster than a variable write.

Is this really true? Does it depend on the VM, or is it general knowledge in compiled languages too?

Certainly the right-hand side version is not equivalent - because then mGarbage is set to true whether or not the value has changed.

The left-hand side is equivalent to the original, but it's pointless.

Basically I think you've missed the side-effect of checking whether or not the existing value was allows DELETED: it allows mGarbage to be set to true only if the method has actually had an effect. That has nothing to do with the performance of reading from the array.

It depends a lot on the VM and I'd guess that this specific code is tuned for the Dalvik VM (or it's just whatever Apache Harmony happened to implement).

One thing to remember is that a write always implies some cost related to caching and cross-thread interaction (i.e. you might need memory barriers for it to work correctly), while a read is much easier to do.

The assumption is probably true, although it will depend a lot on the processor and JVM implementation.

The general reason is less to do with arrays vs. variables but more to do with memory access patterns:

• mGarbage is very likely to be locally cached if it's a field value of the current object, either in a register or L1 cache. You probably just rest the object into cache in order to do something like a virtual method lookup a few cycles ago. There won't be much difference between a read or a write when something is locally cached.
• mValues[index] is an array lookup that is less likely to be locally cached (particularly if the array is large or only gets accessed sporadically). Reads from non-local caches will usually be faster than writes because of locking / memory contention issues so it makes sense to do a read only if you can get away with it. This effect becomes stronger the more cores you have in your machine and the more concurrency you have in your code.