Xah Lee wrote:
> Interesting.
>
> well... but what could be some examples?
Sure. The last time I was helping someone to debug a mysterious 100x
performance degradation in their Mathematica code it turned out to be a
numerical routine calling Fourier that was underflowing machine-precision
floats. When Mathematica notices this it silently moves to
arbitrary-precision floats throughout the FFT and everything grinds to a
halt.
When I implemented this commercial product:
http://www.ffconsultancy.com/products/CWT/
part of the internals required an intricate understanding of exactly how
and
when the Mathematica implementation chooses to reevaluate large arrays.
When you're dealing with a Gb of data that is an overwhelming concern and
the product could never have worked without this knowledge. When I worked
at Wolfram Research I described this to them and it turned out they were
not even aware of those performance characteristics themselves.
> For example, for complex math
> functions such as Integrate or Solve, you can't know the time behavior
> in advance.
Sure.
> And for simpler things like Sort, basically one can assume
> it has time behavior of the current knowldege.
Yes.
Consider:
First2[h1_, h2_, t___] := {h1, h2}
What is the asymptotic complexity of that function? The last time I
looked,
Mathematica eagerly copied the entire array "t" only to dispose of it
immediately. So that function is O(n) when you would expect it to be O(1).
> thinking about this... i don't remember Perl, Python, PHP, emacs lisp,
> Javascript's manuals ever talk about a function's time complexity.
> (maybe once or twice)
The C++ STL does. Our products certainly do:
http://www.ffconsultancy.com/products/signal_processing_net/
> (For Integrate, Solve, or other complex functions, one should know the
> time complexity of course since there's the source code, but my guess
> is that when the function is sufficiently complex, it's impractical to
> actually know. I mean, say a function that are thousands of lines or
> calls other libs ... when is the last time you actually do analysis to
> know a big subroutine's complexity?
Yes, I do that all the time. You have to do that to write
production-quality
code.
> When you use a complex regex in
> perl, do you actually do mathematical analysis just so you know what's
> your function's time complexity?
I've never used regular expressions in performance-critical code but I use
pattern matching daily and I absolutely know my functions' time
complexities when its relevant, yes.
> Basically, if you coded it, you deal with the complexity issue at the
> time of creating a algorithm, then after that if the program runs well
> of any reasonable tests, it's good to go. That's how software are
> practically developed.)
When you say "deal with the complexity issue" you mean "optimize the
code".
You can't optimize code if you can't predict performance, i.e. you must
know the performance characteristics of the language.
This is well known. Look at the literature on why ML tried to avoid
non-linear patterns, for example.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
|
