I'm getting the idea that the gas needed to execute a contract will be somehow influenced by the amount of storage used.
Looking at the "Name Registrar" example contract, the part where the name is deregistered:
;; Otherwise, just deregister any name sender has, if they are registered.@(caller)
Would that be reducing the effective amount of storage used by the contract and therefore the reducing the amount of gas needed to execute it?