On Jan 18, 2010, at 11:17 PM, Niko Kiirala wrote:
For example, for some certain amount of stored values, array walk can outperform hash map when searching for a key. However, this is _not_ contrary to Big-O predictions! The fact that linear search of an array is O(n) and searching hash map for a key is O(1) tells that hash map will be faster for any _large enough_ amount of stored values. Also, for small amounts of values the time taken will usually be small either way, so the difference is likely to be irrelevant.
Well... I was actually talking about something slightly different.
That being how modern CPU's and their complex behavior can take what seems like a straightforward application of abstract analysis and turn it into something completely different. So a naive application of computer science can be broken by actually application of computer engineering.
Of course, if one does a breakdown of the complexities of cache behavior and such (treating the internals of the CPU as just more software, etc), I would expect things would be seen to match the science predictions.
To clarify things, we can consider that in this case "Big-O predictions" to refer to "Programmers trying to predict performance of actual code based on a simplistic model of their algorithms, while forgetting to factor in items such as the fact that CPU's are themselves running their own software also, etc." (and not really "a fatal flaw in computer science principals")