If git status has to run diff on all the files in the HEAD commit to those in staging area/index and another one on staging area/index and working directory, how is it fairly fast?

One reason is about the structure of the index, commits, etc.

• Every file in a commit is stored in tree object
• The index is then a flattened structure of tree objects
• All files in the index have pre-computed hashes
• The diff operation then, is comparing the hashes

Another reason is caching

• Index caches information on working directory
• When Git has the information for certain file cached, there is no need to look at the working directory file