Is your compiler running on an interpreted language? I think to make this sort of product fast requires JIT compiling the users expressions, and doing some sort of whole program analysis to pull out the dependencies between cells.
The sheets I'm working with have around a million expressions, and there are large sparse regions, so the data structures have to be a bit compact.
I would like to do a write-up about it at some point though, if for no other reason but to show the Open Document or LibreOffice people what could be improved about the formats.