> >> ... Mathematica 6 addresses this problem by
> >> rejecting all recursive definitions. ...
OK, I took this to mean that Mathematica 6 rejects all recursive
definitions, absolutely, not just its compiler (which had the *bug*
in earlier versions), presumably so that interpreted and compiled
behaviour will be consistent. On that basis I wrote:
> > IMO that's a showstopper, a complete language rejector!
> From: Jon Harrop <use...@[EMAIL PROTECTED]
>
> To be fair, this only affects compiled anonymous functions.
> Mathematica can still interpret recursive functions but it is
> very slow (~1,000x slower than a compiled language in general).
Are you talking about the earlier versions that merely had a bug,
or the new major-version 6 which "rejects all recursive
definitions" in the words of the other poster?
> >> My PhD was largely on wavelets so I obtained Wolfram Research's
> >> own ($595!) WaveletExplorer add-on only to discover that they deal
> >> solely with discrete wavelets and completely ignore continuous
> >> wavelets.
> > Why didn't you ask around on newsgroups for consumer feedback, like
> > the book reviews on Amazon.com, before making such a significant
> > purchase for which you'd need a requisition rather than take
> > (shake?) out of the petty cash jar (piggy bank?)?
> Probably wouldn't have done much good, as it happens. Computer
> scientists seem to be blissfully unaware of continuous wavelets and
> often teach and learn that only discrete wavelets are significant.
Well, with nearly six hundred dollars to spend, you should at least
have *tried* to get some useful info prior to purchase. Try both
newsgroups or other public sources (has anybody purchased Wolfram
Research's WaveletExplorer, and if so have you checked whether it
handles continuous wavelets), and asking sales representatives at
Wolfram Research itself (get something in writing, even if by
e-mail, that says it does indeed handle continuous wavelets as an
informal guarantee that it'll be of use to you). Since you got
burned, have you tried to get your money refunded?
> >> Also, I needed textbook data structures and algorithms during my
> >> PhD and found that Mathematica not only lacked them but could not
> >> be used to implement them efficiently. Given that an efficient set
> >> union is impossible for Mathematica users, for example, I would not
> >> say that its standard library is comprehensive even in the context
> >> of mathematics, let alone general-purpose computing.
> > If what you say is true, that's pretty awful. What low-level
> > primitive is missing such that you can't even efficiently roll your
> > own?
> Compilation. :-)
> I ****ted my ray tracer benchmark to Mathematica for a laugh and
> it runs 30x slower than OCaml's interpreted bytecode, let alone its
> optimizing native-code compiler.
I take it your benchmark is recursive? Is there any reason you
couldn't have re-written it slightly to emulate stacks by linked
lists, thereby avoided recursion, so that you could have gotten it
compiled?
Note that there are multiple levels of interpreting. Reference to
Lisp and Java and Basic are useful here:
- Source-text-level interpreting, as with the original BASIC
interpretor for the 8080 CPU: The raw text is re-parsed every
time a line of code is re-executed. The only things that help at
all are that every line of code starts with a keyword such as
LET or GOSUB etc. allowing dispatching to special-purpose
parsers for each type of statement, every variable is either a
single letter (for integers) or a dollar sign and single letter
(for floating-point), and there is no syntax extending beyond
single lines of text.
- Parse-tree interepreting, such as what was done by Lisp EVAL
(hence within the Read-Eval-Print loop, all code called by it
except anything that was previously compiled)) before the advent
of JIT (Just In Time) compilation by the REP loop. Parsing was
done just once at READ time. Function definitions as well as
toplevel forms were all parse trees (CONS-cell nested lists)
rather than raw text strings.
- Byte-code dispatching/coding, such as the JVM (Java Virtual
Machine), where a rather efficient direct-dispatching mechanism
dominates the "interpreting" algorithm. On some architectures,
byte-code software actually runs faster than machine code
because both the commonly used parts of the byte interpretor and
the byte-code version of the active parts of the application
reside in *fast*cache* most of the time, reducing the number of
times main-memory (RAM) needs to be used. This works because
byte-code is much more compact than machine code, because byte
code needs handle only the primitives of that one high-level
language rather than also all the alternatives provided by the
design team of the CPU itself.
Consequently the "let alone ..." remark may be out of line. If
byte-code is the fastest available for large software programs
where cache performance dominates over instruction execution per
se, then perhaps the benchmark is running only 30x as slow as the
fastest possible on that architecture? Do you have a direct
comparison of byte-code and native-code (both with OCaml) to tease
out the full truth of these comparisons? (Just curious.)
> > What do you classify as "efficient" for set union? Do you have
> > in mind using lists (with duplicates already eliminated) for
> > emulating each set, and a hash table for registering all the
> > elements in each set, and thereby being able to efficiently detect
> > which elements are in both sets (for example by mapping down the
> > elements of the smaller set checking if they are also in the
> > hashtable of the larger set), hence need to be put just once in the
> > union?
> I would copy the OCaml implementation and use immutable balanced
> binary trees.
I presume you mean the algorithms where trees are updated by
creating new structure for all the parts that changed and sharing
any sub-trees that haven't changed? Thus you can collate two trees
(for all the usual purposes: all the nontrivial boolean functions:
and ior xor eqv nand nor andc1 andc2 orc1 orc2; all the nontrivial
predicates: equal notequal subset notsubset backsubset
notbacksubset eithersubset neithersubset) making just one pass over
most/all of the nodes (in some cases you can skip a whole sub-tree
in one of the given trees if there's a gap between adjacent
elements in the other tree)?
I suppose in theory you can re-write those algorithms to emulate
the stack via linked lists, then you will be able to compile the
code in Mathematica? That would be a big pain of course, but has
anybody tried it?
It would actually be of general interest to compare true
machine-stack recursion against emulation of recursion via pu****ng
and popping on linked lists, where both modes are available for use
by compiled code, to see whether there's any signficant speed
advantage to true machine-stack recursion. It would be especially
interesting to try the comparison on systems that have multiple
processors, where the application programmer has control over when
thread-splitting may occor in the algorithm:
For example, with a recursive algorithm (defun myfun (tree) ...)
that at one point says:
(cons (myfun (car tree)) (myfun (cdr tree)))
it might instead say:
(thread-split-let ((val1 (myfun (car tree)))
(val2 (myfun (cdr tree))))
(cons val1 val2))
Likewise an interative version of the algorithm that looked like this:
(let ((todostack (list tree)) (resultsstack (list)))
(loop ... ;various code for pu****ng incompleted second branches
; onto todostack and later pu****ng unused return values
; onto resultstack, something like that anyway, I haven't
; written this kind of code in like forever
))
might be converted for multiple threads by not using a todostack at
all, instead always calling thread-split-let to descend deeper into
the two branches of the given tree in parallel.
Threads are a standard part of Java. Maybe I should try writing
this in Java? First I need to implement thread-split-let of course!
For my benchmark, I need an algorithm where traversing the two
trees, not performing calculations, dominates the process. Thus my
divide-and-conquer version of factorial would *not* be a good
example. Maybe something like give two large sets (as trees), or
other large collection of data stored in a tree, which are almost
identical, find all the (very small number of) differences. To make
reasonable data, I'd read in a corpus of text, building a
left-context tree from it, then read in a little bit more text,
which includes just a few additinal left contexts, then compare the
old and new tree to show what new contexts were added? Only that
final comparison (find all differences) would be timed.
In any case, four comparisons on any given machine architecture:
- Normal recursion
- Thread-splitting recursion
- Stack emulation of recursion, single thread
- Stack emulation of recursion, splitting threads
Does anybody have access to a quad-core or larger machine running
the JVM which could be applied to this benchmark, where all cores
are kept busy all the time whenever enough threads are active, if I
ever get around to writing it in Java?
> Mathematica does have something like that: hierarchical
> namespaces and it can recognise packages when they're stored in
> the correct location on disk.
Ah, that sounds somewhat like the Java model for dealing with
hierarchial namespace.
|
