On Sun, 2005-07-31 at 01:06 +0100, Jon Harrop wrote: > Yes, I think the only advantage of extensible arrays is a slightly improvement > in the constant prefactor in the complexity of some algorithms. Not quite, simply because 'complexity' is not the only thing of importance, since it only applies to asymptotic behaviour, which of no interested to clients of algorithms, only algorithm providers: clients are interested in performance and limits on problems which can realistically be solved on their hardware, which is bounded in memory, and limited by processing speed -- please take that as a definition of 'client', ok? Here, the 'constant prefactor' can degrade and lead to quite significant differences: for example (a) doubling the amount of store your major data structure needs is only a 'constant' factor, but may make solution of a problem you are interested in swap from being barely possible to out of the question. (b) because of caching effects, the performance over ranges of problem size may not be 'linear' in the theoretical complexity: doubling the number of indirections could spill a fully 'in cache' intense computation out to the next level of caching and lead to an order of magnitude performance loss on just the size of problem you're interested in: I have been in several 'industrial' situations where this has actually happened, eg in a telco where a transaction rate of 60 calls/second for a switch was achieved but they needed more like 600 calls/second .. buying 40 servers instead of 4 isn't something you wish to tell your prospective clients they must do to use your software... :) Another scenario, recently discussed, where this happens is in games: close to the hardware solutions for graphics are often unnecessary but done anyway because programmers don't understand performance characteristics of their code, but sometimes there are places where there is just no other way to build a viable product. In these types of situations, it is better if the vendor doesn't try to tell the application developer what they really need: better to let the application developer make their own mistakes :) -- John Skaller