Re: [Caml-list] How to do this properly with OCaml?

[skaller <skaller@users.sourceforge.net>]

[-- Attachment #1: Type: text/plain, Size: 2267 bytes --]

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 <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]