What is a midstate? How does using a midstate speed up hashing? This defines "midstate" as the "precomputed hash state after hashing the first half of the data."

I've heard "midstate" used in the context of speeding up hashing. How does using a midstate speed up hashing?
People often talk about SHA256 like it's a single operation, but it isn't. Rather, the input is broken up into 64-byte chunks, and then each chunk is put into a compression function. The state of the hash partway through hashing something does not depend on future parts of the data. Since the nonce is found in the second chunk, changing the nonce doesn't change the the state of the hash function after hashing the first chunk.

This is useful in other applications. For example, if you're hashing a large file, it means that you can hash it without loading the entire file into memory at once or loading it from disk multiple times.

The practical consequence of this for Bitcoin miners is that 99.99999998% of the time, you only need 2 iterations of the SHA256 compression function to check a possible block solution, instead of 3. In other words, you can mine 50% faster. Of course, since everyone else does this, that just means that the difficulty is higher for everyone.

midstate is literally the state midway through hashing.

See also: Did Satoshi intend to allow midstate computation to speed up hashing?