GiNaC as the symbolic manipulation engine in Sage
|
View:
New views
16 Messages
—
Rating Filter:
Alert me
|
 |
GiNaC as the symbolic manipulation engine in Sage
by Burcin Erocal
::
Rate this Message:
|
|
|
Re: GiNaC as the symbolic manipulation engine in Sage
by Jens Vollinga
::
Rate this Message:
|
|
|
|
|
|
|
|
|
Re: GiNaC as the symbolic manipulation engine in Sage
by Burcin Erocal
::
Rate this Message:
|
|
|
A bad idea: GiNaC as the symbolic manipulation engine in Sage
by Alexei Sheplyakov-2
::
Rate this Message:
Hello!
On Mon, Aug 11, 2008 at 10:30:59AM +0200, Burcin Erocal wrote: > While GiNaC seems to be the best option for Sage, GiNaC is a special purpose symbolic manipulation library. The purpose of GiNaC is to do "simple" manipulations with "large" expressions using a common programming language (as opposed to ill designed, unstable ones as offered by most of CASes). So, I don't think GiNaC is a good choice for Sage (which attempts to be a general purpose _interactive_ CAS). > I think all these problems can be resolved with some effort Don't take me wrong, but I think it's better to put this effort elsewhere. I.e. most of "issues" you've mentioned are design decisions. > and even the speed of basic arithmetic in GiNaC can be improved with > modifying it's data structures. No matter what data representation you choose, there are always some expensive operations. Sure, one can optimize data structures so that some particular operation is fast (at the expence of slowing down other operations). So, to write a good code one need to be aware of the complexity of operations and use expensive operations consciously. To be more specific, here is an example. Let's construct the expression A_N = \sum_{i = 0}{N} (x+y)^i (with N = 10000). A naive way: $ cat testadd_dumb.cpp #include <ginac/ginac.h> #include <cstdlib> // for atoi using namespace GiNaC; using namespace std; ex do_dumb(const ex& base, const unsigned max_degree) { ex e = 0; for (unsigned i = 0; i <= max_degree; i++) e += pow(base, i); return e; } int main(int argc, char** argv) { unsigned max_degree = 10000; if (argc > 1) max_degree = atoi(argv[1]); const symbol x("x"), y("y"); ex base = x+y; ex e = do_dumb(base, max_degree); return 0; } $ g++ -O2 -march=k8 -finline-limit=2000 testadd_dump.cpp -lginac $ time ./a.out real 0m4.916s user 0m4.644s sys 0m0.272s It's very slow, because every += operation calls add:eval() method, which puts the terms of the sum into a canonical order. A better variant is $ cat testadd.cpp #include <ginac/ginac.h> #include <cstdlib> // for atoi() using namespace GiNaC; using namespace std; // same as in above Maxima code: first construct all terms, // than make a sum of them. ex do_smart(const ex& base, const unsigned max_degree) { exvector v; v.reserve(max_degree + 1); for (unsigned i = 0; i <= max_degree; i++) v.push_back(pow(base, i)); return (new add(v))->setflag(status_flags::dynallocated); // setflag incantation tells GiNaC to manage memory for us. } int main(int argc, char** argv) { unsigned max_degree = 10000; if (argc > 1) max_degree = atoi(argv[1]); const symbol x("x"), y("y"); ex base = x+y; ex e = do_smart(base, 10000); return 0; } Here the sum is constructed in a one shot, so terms are sorted only once instead of 10000 times, so the program works *much* faster: $ g++ -O2 -march=k8 -finline-limit=2000 testadd.cpp -lginac $ time ./a.out real 0m0.078s user 0m0.064s sys 0m0.016s The same applies to Maxima. Constructing the sum in a proper way takes a reasonable time: $ cat testadd.mac args : []; for i from 0 thru 10000 do ( args : cons((x+y)^i, args) )$ expr : apply("+", args)$ $ time ( maxima --batch=testadd.mac >/dev/null ) real 0m0.519s user 0m0.428s sys 0m0.092s N.B. The timing is not quite fair, since it includes the startup time. > Sage via the maxima interface didn't finish this task in < 5 minutes. I guess that's because you (or Sage) do it in an extremly inefficient manner. In other words, if you use Maxima, write the code the Maxima way, not the Mathematica (Maple, whatever) one, and everybody will be happier. BTW, the same applies to almost every piece of a software. > - cln duplicates functionality which is provided by different libraries > already distributed with Sage (mpfr, mpir, flint) The libraries duplicating CLN functionality [1] typically have several serious drawbacks: a. The syntax is really awkward (to put it very mildly). For example, instead of a simple z = x+a*y; one need to write several lines of unreadable code. b. The user is responsible for memory management. This is absolutely inacceptable. None of these libraries gives any considerable performance gain, so why bother? [1] As a matter of fact, CLN existed *long* before the libraries you've mentioned were developed. > at a considerable speed penalty. Could you please give any benchmark backing up this claim? > - Creating symbolic functions at runtime is not supported. That's a design decision. > - IIRC, GiNaC documentation suggests the printing order for the > variables is stable between different sessions, regardless of > creation order. Could you please point out which document (and where) says that? The order of expressions (in particular, symbols) is not stable. This is a price for a fast comparison of expressions. Anyway, since GiNaC is non-interactive, the order of terms doesn't actually matter: typically the output of a program is a small expression (quite often it is a single number), and the big intermediate expressions are not going to be examined by human (except for debugging). > - It takes ages to build > The packages above took ~25 minutes to build on my desktop machine Just for the record: building GiNaC and CLN takes ~30 minutes on my old Duron 800 box with 640 Mb of RAM. I wonder what kind of machine do you use as a desktop. That said, patches reducing the build time are wellcome (if they don't reduce the performance and don't make the code more complicated). > - cln seems to support on only gcc, 1. CLN maintainers accept patches to support other platforms. 2. Cleaning up CLN from non-portable code is in my TODO list (although the priority is *very* low). 3. gcc is available for (almost) every architecture, so who cares, anyway? Best regards, Alexei -- All science is either physics or stamp collecting. _______________________________________________ GiNaC-list mailing list GiNaC-list@... https://www.cebix.net/mailman/listinfo/ginac-list |
|
|
Re: A bad idea: GiNaC as the symbolic manipulation engine in Sage
by Jens Vollinga
::
Rate this Message:
|
|
|
Re: A bad idea: GiNaC as the symbolic manipulation engine in Sage
by Burcin Erocal
::
Rate this Message:
|
|
|
Re: GiNaC as the symbolic manipulation engine in Sage
by Alexei Sheplyakov-2
::
Rate this Message:
Hi,
On Mon, Aug 11, 2008 at 11:39:42AM +0200, Jens Vollinga wrote: > It would be quite useful for ginac if the numeric class that wraps the > cln library would allow for other libraries as well, What is the point of that? As I've already mentioned, those libraries provide very unnatural syntax, and leave the memory management as an "exercise for the reader". > even pure C double precision ones. I think wrapping doubles (and integers) is not a good idea. A better option is to make them immediate using the same tricks as CLN [1]. This idea is particulary attractive for x86_64 CPUs. Here we have extra 16 bits for type tags. We can use these to encode the whole GiNaC class hierarcy, so our custom RTTI would be *really* fast. [1] http://www.ginac.de/~kreckel/talks/ICMS2006.pdf > > - The gethash() function of GiNaC objects doesn't return stable > > results, which is probably the cause of the problem above. We need a > > stablehash() function. > > Yes, the two points above are related and I am to a certain point responsible > for that mess. Not really. Ordering of symbols always was unstable, so was the ordering of expressions. New tinfo mechanism just made that instability more explicit. > Now, these tinfo numbers also go into the hash calculation and the term > ordering ... I think a custom printing function is a better approach. Any attempt to "stabilize" the hash function (i.e. comparing symbol names instead of their serials, comparing class names instead of tinfos, etc.) would substantially slow it down, which means virtually every operation would be much slower. Best regards, Alexei -- All science is either physics or stamp collecting. _______________________________________________ GiNaC-list mailing list GiNaC-list@... https://www.cebix.net/mailman/listinfo/ginac-list |
|
|
Re: [sage-devel] Re: GiNaC as the symbolic manipulation engine in Sage
by Burcin Erocal
::
Rate this Message:
|
|
|
Term ordering stability, tinfo keys and all that.
by Alexei Sheplyakov-2
::
Rate this Message:
On Mon, Aug 11, 2008 at 04:50:54PM +0200, Jens Vollinga wrote:
> well, I don't quite agree but maybe I am misinterpreting the quotation > marks ;-). If you want to handle large expression, then use FORM. No way. Its programming language is extremly brain dead. It has a lot of stupid "features", i.e. it unconditionally expands every expression. It lacks basic polynomial operations (gcd, collect, to name few). FORM is impossible to extend. Last, but not least, FORM is a proprietary software. > what a simple manipulation is depends on whom you ask. Sure, hence the quotation marks. An example of a "simple" manipulation is reading an input expression, or adding several expressions and collecting similar terms. Apparently not every CAS is able to to this, see e.g. http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=407109 > > The order of expressions (in particular, symbols) is not stable. This is > > a price for a fast comparison of expressions. > Additional nitpicking: that is not quite true. I don't agree. The purpose of custom GiNaC RTTI ("tinfo keys") is exactly fast ordering of expressions. A long(er) explanation follows. The purpose of hash function is to quickly guess if two expressions are NOT the same in order to minimize the number of (expensive) element-to-element comparison operations. Notice that two expressions of different type are always different. Hence the need for an efficient ordering operation for _types_. IOW, we need a fast RTTI. Standard C++ library provides RTTI, but in ancient versions of GNU C++ library ordering operation (i.e. typeinfo::before() method) was very slow, because it was implemented as a comparison of (mangled) type names. Hence GiNaC invented its own (fast) RTTI with tinfo keys. As a side note, RTTI implementation in the up to date versions of GNU libstdc++ is much better. It uses the technique similar to GiNaC's tinfo keys, although it's a bit more complicated (since it needs to handle multiple inheritence and other obscure stuff). As a matter of fact, using it instead of our custom RTTI doesn't yeld any measurable overhead. So we can stick with standard C++ RTTI. This won't solve term ordering "issue", but writing new GiNaC classes would be easier. > I mentioned the reasons for non-stability in my last email. The only missing part is why GiNaC needs those "tinfo keys" in first place... Best regards, Alexei -- All science is either physics or stamp collecting. _______________________________________________ GiNaC-list mailing list GiNaC-list@... https://www.cebix.net/mailman/listinfo/ginac-list |
|
|
|
|
|
Re: A bad idea: GiNaC as the symbolic manipulation engine in Sage
by Alexei Sheplyakov-2
::
Rate this Message:
On Mon, Aug 11, 2008 at 05:09:30PM +0200, Burcin Erocal wrote:
> Are you denying that GiNaC is the best "symbol manipulation engine" > I can find? That depends on a definition of a "symbol manipulation engine", i.e. what kind of features do you expect from it (i.e. GiNaC does not implement polynomial factorization, which is necessary for symbolic integration). Also to use GiNaC (or Maxima) in an efficient manner you need to forget your Mathematica (Maple, whatever) experience and learn from scratch. > Your statements also seem to suggest that there is something wrong with > interactive use. GiNaC is not designed for this kind of use. Interactive manipulation is kind of pointless if the expressions in question consists of 10^6 -- 10^8 of terms, isn't it? > OK, so I chose a bad example for a benchmark, and this was pointed out > before. I think the benchmark is OK. My point is a bit different: the method you've used to construct the sum is very inefficient, at least for GiNaC and Maxima. Apparently it's also inefficient for Mathematica (I guess it's also inefficient for almost any CAS too, but I can't tell for sure): $ cat mma_bench1.m A = 0; For[i = 0, i <= 10000, i = i + 1, A = A + (x+y)^i; ]; $ time math < mma_bench.m >/dev/null real 0m15.535s user 0m15.509s sys 0m0.016s Hence Mathematica provides a more efficient method, it's called Sum: $ cat mma_bench2.m A = Sum[(x+y)^i, {i, 0, 10000}]; $ time math < mma_bench2.m >/dev/null real 0m0.035s user 0m0.028s sys 0m0.004s The point is: although both methods are correct, the non-obvious one performs _3 orders of magnitude_ better. Likewise, GiNaC (and Maxima) also provide efficient methods for doing some operations. You might want to learn them before doing some changes to data structures. > When I said modifying data structures, I meant that you can keep the > arguments of an operator in a different structure, instead of a list. I understand (BTW GiNaC uses arrays for that, not lists). > This would probably only make sense on very large expressions, and at > this point, I don't know what the penalty for smaller expressions would > be. I don't agree. I think the large expression should be kept as flat as possible for (at least) two reasons: 1. Otherwise eval() and other inherently recursive functions/methods would run out of stack. 2. Any other structure requires more memory to store the same terms. > As for different ways of storing the arguments of an operator, we can > look at methods for storing and calculating with polynomials. One > method is to use a hash table to keep the monomials The same method was used in ancient versions of GiNaC. That was a bad idea. It makes code much more complicated and does not really improve performance (in some situation it's even worse). N.B. You might want to grep GiNaC source for EXPAIRSEQ_USE_HASHTAB. To reiterate, a flat N-ary tree (which is what GiNaC::expairseq essentially is) seems to be the best way to store big expressions. > I got the above timing on this machine: > > $ cat /proc/cpuinfo | grep name > model name : Intel(R) Pentium(R) D CPU 3.40GHz Although the build time depends on optimization options and a number of other factors, 25 minutes is way too long for such a box (even if you build both static and shared libraries). Unless you use some insane optimization options, this looks like a compiler and/or linker bug (see e.g. http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=376066). What are exactly the compiler and binutils versions (as in g++ --version; ld --version)? Anyway, there are a number of ways to speed up the build. Jens already mentioned --disable-static. Another useful option is to run build in a parallel manner, i.e. invoking make as make -j N where N \approx number of CPU cores + 1, and appending '-pipe' option to CXXFLAGS. Note: this is useful even if your CPU is single core, because CLN consists of lots of small source files. Yet another method is to use a fast(er) shell, such as ash or pdksh, i.e. SHELL=/bin/ash CONFIG_SHELL=/bin/ash /bin/ash configure --disable-static This works because GNU libtool (which is responsible for building GiNaC and CLN, as well as a number of other Free and even not so free libraries) is a shell script. Of course, ash is not suitable as an interactive shell, but it's very good at parsing/running big scripts (such as GNU libtool). @developers: libtool version 2.2 is reportedly much faster than 1.5 (which is what we use), so we might want to upgrade to that version when releasing next version of GiNaC. Best regards, Alexei -- All science is either physics or stamp collecting. _______________________________________________ GiNaC-list mailing list GiNaC-list@... https://www.cebix.net/mailman/listinfo/ginac-list |
signature.asc (844 bytes)