How much more can one say about how to multiply polynomials? Here's a summary of results of a few new programs I wrote or re-wrote for multiplication, written in Lisp. First, characterizing inputs. test(n,m,s,c) produces two univariate polynomials, the first with n terms, the second with m terms. These are sparse polynomials, with the gap between adjacent exponents a (pseudo) random integer between 1 and s. The coefficients are positive integers, each a random number between 1 and c. Example of the input format: 45x^10+25x^2+ 9 [note: 9 = 9x^0] looks like a pair of two vectors: ( #(0 2 10) . #(9 25 45)) Multiplying two polynomials with close spacing tends to make a denser answer. For example given polynomials of size 500 and 1000, a spacing of 5000 produces a very sparse answer in which almost no terms combine. That is, there are about 500,000 terms in the answer. Whereas a spacing of 5 produces an answer of about 4,500 terms, and of a similar degree. That is, it is dense. Polynomials in more than one variable can be mapped to univariate polynomials essentially by mapping ranges of exponents to variables: (x+y+z) --> (t + t^100 +t^10000). The times reported in these tests are for programs written in ANSI Standard Common Lisp and run on a Pentium D 3.0GHz computer running Allegro Common Lisp 8.0 on Windows XP. They were also run in GCL and SBCL implementations. Two kinds of spaces are reported in the benchmarking: Lisp "cons" cells and "other bytes". The "other bytes" account for space in arrays, big-numbers, hash tables, functions and symbols. The Lisp cons cells are 8 bytes in size and represent two pointers, used for constructing linked lists. Some of the programs use Lisp's built-in bignum facilities, and some use the open-source GMP library, which has clear advantages for large enough numbers. The GMP numbers are hooked into the Lisp garbage collection system: when they are no longer needed, they are de-allocated by a "finalization" call from the garbage collector. Unfortunately, the "other bytes" includes only the first 16 bytes of a GMP number, but subsequent operations on GMP numbers that force them to grow require that allocations be done from GMP memory, not accounted for in the statistics we collected. Note that because the Lisp GC watches out for these numbers, they need never be explicitly deallocated. Time is process CPU runtime, including garbage collection. In 32-bit Allegro Common Lisp, a cons cell takes 8 bytes. Thus 2.36k cons + 14k other bytes means a total of 32.9k bytes. Here are brief descriptions of the algorithms used. naive = the naive way of doing an nXm loop, inserting into a long linked list, each of the partial products as generated. An important optimization keeps track, in the inner loop, of where the last insertion was made and searches for the right insertion point from that place onward. naiveG is the same algorithm, but where the coefficients are GMP numbers. hash1 = a hash-table based algorithm in which all of the nXm elements are computed in the obvious order but each is inserted into a hash table, whose keys are the exponents. Lisp provides facilities for automatically growing hash tables when they get too full, so this program can be quite small. When an element is computed that hits a previously inserted exponent, the corresponding coefficient is added to that term. The hash table is dumped out into an array which is then sorted, so as to meet the same standard form for polynomials. hash1G is a GMP version. heap = an algorithm in which nxm elements are produced, but not in the same order as in the previous methods. Instead they are produced in the order in which they appear in the answer. In particular, all terms with exponent k are produced and added together before any terms with exponent k+1 or higher are produced. (Actually this is somewhat overstating the case. If n<=m, then n terms are computed and inserted into a "heap" (as heap sort)). This has been advocated by Michael Monagan and Roman Pearce in a recent paper as the right way to do sparse polynomial multiplication, (and division). We were motivated to try this out because of their paper, and were initially disappointed to find it was not fast. As shown in the benchmarks, we got it to appear to be the fastest by choosing a far sparser problem. Our initial implementation of this was programmatically neat, using functional arguments to produce "streams" of exponents and coefficients. In an attempt to squeeze out some efficiency, we changed the implementation to use a more conventional data layout. heapG is a GMP version of the same idea. heap2 uses an idea called "chaining" by Monagan and Pearce. It is like the heap program but does some cursory checking to see, before insertion of a new element Q, if an element can be found with the same exponent as Q, in which case that element is incremented, and Q's successor Q' is then inserted into the heap. (terminating when Q has no successor, or when Q' is just inserted as a new heap entry. A full check to see if Q can be chained is too expensive: it requires searching the heap until it can be proved that Q is not going to fit. A cursory check takes only log(n) checks for heap size n. [Richard Fateman: ``Comparing the speed of programs for sparse polynomial multiplication,'' ACM SIGSAM Bulletin, Vol 37, No. 1, March 2003, Pages 4--13.] [ Michael Monagan and Roman Pearce: ``Polynomial Division Using Dynamic Arrays, Heaps, and Packed Exponent Vectors'' Computer Algebra in Scientific Computing, LNCS 4770/2007 Springer. ISSN 0302-9743 (Print) 1611-3349 (Online) DOI 10.1007/978-3-540-75187-8 ISBN 978-3-540-75186-1 DOI 10.1007/978-3-540-75187-8_23 Pages 295--315].] test test test 5 5 5 500 1000 5 5 500 1000 5000 5 time cons other time cons other time cons other naiveG 0 2.36k 14k .69 sec 580.6k 3,402k 5.5 sec 1,382k 40.6m naive 0 .04k .2k .31 sec 8.8k 35k 4.0 sec 921k 3.7m hash1G 0 .02k 3k .42 sec 4.6k 694k 4.9 sec 461k 56.4m hash1 0 .00k 1k .94 sec .0k 276k 1.8 sec 0k 26.1m heapG 0 0.03k 1k .86 sec .6k 145k 1.9 sec 0.7k 10.5m heap 0 0.02k .7k .27 sec .1k 104k 0.6 sec .2k 10.5m heap2 0 0.02k .7k .45 sec .1k 104k 1.0 sec .2k 10.5m with 500 1000 5000 2^72, non-GMP space changes (though times don't much): coeffs 5: coeffs: 2^72 cons other cons other naive 921k 3.7m 922k 24.9m ;; this uses cons cells, the others use arrays. hash1 0 26.1m 0 40.7m heap 0 10.5m 0 31.7m If we use big enough coefficients, say 2^1000, we get almost the same times for all methods, because much of the time is taken with coefficient arithmetic. 500 1000 5 2^1000 naive 12.3 sec 9.1k cons 271m other hash1 13.4 sec 1.1k cons 271m other heap 13.5 sec 0.1k cons 171m other using GMP (storage of GMP numbers is not counted...) naiveG 6.6 sec 12.3k cons 389k other hash1G 6.8 sec 4.4k cons 630k other heapG 7.3 sec 0.6k cons 145k other however 500 1000 5000 2^1000 naiveG 16.2 sec 1,380.5k cons 40.5m other hash1G 14.9 sec 4.4k cons 56.3m other heapG 7.1 sec 1.3k cons 10.6m other Note: The 500 1000 5 {any} problems result in about 4,550 terms in the answer. The 500 1000 5000 {any} problems result in about 460,000 terms in the answer. The naiveG programs use more conses than naive because they are needed as part of the overhead of GMP numbers. We expect that by suitable modest restrictions, the programs can be made substantially faster. For example, restricting coefficients to fixnums or double-float, and restricting exponents to fixnums. For example, we tried running the naive program but with coefficients and exponents of polynomials declared to be fixnums: naive .027 sec rather than 0.49 sec Some conclusions: A heap method works to reduce memory usage and time when the answer is very very large. A naive algorithm is hard to beat when the answer is small. As we programmed it, the naive method uses far more memory than the hash method, which in turn, uses more than heap. The hash table re-allocation method might be something that could be tuned: typically it is substantially larger than necessary. The heap method uses nearly the minimum storage: the two input polynomials, a heap which is linear in the size of the smaller input, and an answer which is essentially just the size needed to store the answer. Further in favor of the heap method, the answer is produced in order, and so one a coefficient is produced, it need never be visited again, and could be relegated to out-of-cache storage. In favor of GMP, if the coefficients are large enough, GMP is faster. In this case, using coefficients that are 30 words long gives GMP a factor of two speedup over Allegro CL. For coefficients that are 2 words long, the GMP routines are twice as slow. We are attempting to set up a more precise accounting of cache operations, as we did in a previous paper, by using PAPI from UTK, but that software which allows one to count cache misses may not be compatible with our current testing setup, and we may need to find another computer and another operating system to get precise measures of L1 and L2 cache misses, and other such statistical data. All the lisp code is available from the author, or by internet, http://www.cs.berkeley.edu/~fateman/lisp/newmul.lisp .................. cl-user(184): :ld ; Fast loading c:\lisp\newmulg2.fasl [4] cl-user(185): (test0 5 5 5 5) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 0 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 0 msec user, 0 msec system ; real time 0 msec ; space allocation: ; 2,362 cons cells, 14,752 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 0 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 0 msec user, 0 msec system ; real time 0 msec ; space allocation: ; 23 cons cells, 2,624 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 0 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 0 msec user, 0 msec system ; real time 0 msec ; space allocation: ; 27 cons cells, 1,352 other bytes, 0 static bytes (#(8 12 13 14 15 16 17 18 19 20 ...) . #(12{g} 12{g} 35{g} 12{g} 12{g} 18{g} 35{g} 4{g} 12{g} 35{g} ...)) [4] cl-user(186): (test0 500 1000 5 5) [4] cl-user(186): mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 688 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 688 msec user, 0 msec system ; real time 687 msec ; space allocation: ; 580,593 cons cells, 3,402,192 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 422 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 422 msec user, 0 msec system ; real time 422 msec ; space allocation: ; 4,583 cons cells, 694,016 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 859 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 859 msec user, 0 msec system ; real time 859 msec ; space allocation: ; 634 cons cells, 145,104 other bytes, 0 static bytes (#(2 4 5 6 8 9 11 12 13 14 ...) . #(4{g} 4{g} 4{g} 4{g} 4{g} 4{g} 4{g} 4{g} 4{g} 4{g} ...)) [4] cl-user(187): (test0 500 1000 5 (expt 2 32)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 844 msec user, 0 msec system ; cpu time (gc) 593 msec user, 0 msec system ; cpu time (total) 1,437 msec user, 0 msec system ; real time 1,437 msec ; space allocation: ; 572,084 cons cells, 3,352,624 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 453 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 453 msec user, 0 msec system ; real time 454 msec ; space allocation: ; 4,509 cons cells, 637,200 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 860 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 860 msec user, 0 msec system ; real time 859 msec ; space allocation: ; 635 cons cells, 145,104 other bytes, 0 static bytes (#(2 3 5 6 8 9 10 11 13 14 ...) . #(1184792708281314456{g} 1184792708281314456{g} 327435571874654592{g} 327435571874654592{g} 1184792708281314456{g} 220841064087883602{g} 220841064087883602{g} 327435571874654592{g} 1184792708281314456{g} 1096650721386790848{g} ...)) [4] cl-user(188): (test0 500 1000 5000 5) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 49,923 msec user, 110 msec system ; cpu time (gc) 9,484 msec user, 0 msec system ; cpu time (total) 59,407 msec user, 110 msec system ; real time 59,704 msec ; space allocation: ; 58,316,886 cons cells, 341,648,224 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 3,047 msec user, 15 msec system ; cpu time (gc) 250 msec user, 0 msec system ; cpu time (total) 3,297 msec user, 15 msec system ; real time 3,312 msec ; space allocation: ; 459,201 cons cells, 62,758,256 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 890 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 890 msec user, 0 msec system ; real time 922 msec ; space allocation: ; 732 cons cells, 10,549,616 other bytes, 0 static bytes (#(1292 2789 5783 5888 7385 8912 10379 10409 10763 12702 ...) . #(9{g} 9{g} 9{g} 15{g} 15{g} 15{g} 15{g} 15{g} 9{g} 15{g} ...)) [4] cl-user(189): (test0 500 1000 5000 (expt 2 32)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 49,141 msec user, 16 msec system ; cpu time (gc) 7,406 msec user, 0 msec system ; cpu time (total) 56,547 msec user, 16 msec system ; real time 56,782 msec ; space allocation: ; 58,539,902 cons cells, 342,957,632 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 3,093 msec user, 15 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 3,093 msec user, 15 msec system ; real time 3,109 msec ; space allocation: ; 460,949 cons cells, 56,410,176 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 907 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 907 msec user, 0 msec system ; real time 906 msec ; space allocation: ; 733 cons cells, 10,549,616 other bytes, 0 static bytes (#(8561 9549 10619 12182 12673 13536 13661 14731 16096 16294 ...) . #(1973701193252874730{g} 6789130650209932751{g} 1817751523036319801{g} 7583675469438346193{g} 1973701193252874730{g} 8101247390839178952{g} 6789130650209932751{g} 1817751523036319801{g} 1973701193252874730{g} 7583675469438346193{g} ...)) [4] cl-user(190): (test0 500 1000 5000 (expt 2 72)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 48,373 msec user, 79 msec system ; cpu time (gc) 11,080 msec user, 0 msec system ; cpu time (total) 59,453 msec user, 79 msec system ; real time 59,844 msec ; space allocation: ; 58,495,199 cons cells, 342,687,432 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 3,422 msec user, 31 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 3,422 msec user, 31 msec system ; real time 3,453 msec ; space allocation: ; 460,598 cons cells, 56,379,200 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 1,046 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 1,046 msec user, 0 msec system ; real time 1,047 msec ; space allocation: ; 732 cons cells, 10,549,616 other bytes, 0 static bytes (#(8148 10858 11351 11899 14328 14609 15102 16649 17611 18079 ...) . #(515104168206599664350842837165393916970417{g} 515104168206599664350842837165393916970417{g} 515104168206599664350842837165393916970417{g} 3515968149433625707764398872914059821508316{g} 515104168206599664350842837165393916970417{g} 3515968149433625707764398872914059821508316{g} 3515968149433625707764398872914059821508316{g} 8844390725602737638209223446610054404928449{g} 515104168206599664350842837165393916970417{g} 3515968149433625707764398872914059821508316{g} ...)) [4] cl-user(191): .................tests with non-GMP arithmetic cl-user(20): :cf ;;; Compiling file newmul.lisp ;;; Writing fasl file newmul.fasl ;;; Fasl write complete Warning: While compiling these undefined functions were referenced: mularZ2 from position 398 in newmul.lisp cl-user(21): :ld ; Fast loading c:\lisp\newmul.fasl cl-user(22): (test0 500 1000 5000 5) mul-naive time - just use insertion into single list, not using GMP ; cpu time (non-gc) 4,032 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 4,032 msec user, 0 msec system ; real time 4,110 msec ; space allocation: ; 921,539 cons cells, 3,686,160 other bytes, 0 static bytes mul-hash1 time - hash1 not using GMP ; cpu time (non-gc) 1,765 msec user, 0 msec system ; cpu time (gc) 235 msec user, 0 msec system ; cpu time (total) 2,000 msec user, 0 msec system ; real time 2,000 msec ; space allocation: ; 20 cons cells, 26,086,832 other bytes, 0 static bytes mul-str time - heapmerge not using GMP ; cpu time (non-gc) 688 msec user, 0 msec system ; cpu time (gc) 265 msec user, 0 msec system ; cpu time (total) 953 msec user, 0 msec system ; real time 953 msec ; space allocation: ; 229 cons cells, 10,509,376 other bytes, 0 static bytes (#(6444 9121 9869 12546 13320 14307 14829 14992 15246 16745 ...) . #(16 8 12 6 8 12 20 20 16 6 ...)) cl-user(23): (test 500 1000 5 5) mul-hash1 time - best hash table version ; cpu time (non-gc) 93 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 93 msec user, 0 msec system ; real time 94 msec ; space allocation: ; 5 cons cells, 277,040 other bytes, 0 static bytes mul-str time - use simple streams, in a heap array, insert from top sometimes ; cpu time (non-gc) 282 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 282 msec user, 0 msec system ; real time 281 msec ; space allocation: ; 131 cons cells, 104,864 other bytes, 0 static bytes mul-naive time - just use insertion into single list ; cpu time (non-gc) 47 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 47 msec user, 0 msec system ; real time 47 msec ; space allocation: ; 9,053 cons cells, 36,224 other bytes, 0 static bytes (#(0 3 5 6 8 9 10 11 12 14 ...) . #(1 4 4 1 16 5 4 9 20 23 ...)) cl-user(24): (test0 500 1000 5 5) mul-naive time - just use insertion into single list, not using GMP ; cpu time (non-gc) 46 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 46 msec user, 0 msec system ; real time 47 msec ; space allocation: ; 8,827 cons cells, 35,328 other bytes, 0 static bytes mul-hash1 time - hash1 not using GMP ; cpu time (non-gc) 94 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 94 msec user, 0 msec system ; real time 94 msec ; space allocation: ; 5 cons cells, 276,144 other bytes, 0 static bytes mul-str time - heapmerge not using GMP ; cpu time (non-gc) 266 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 266 msec user, 0 msec system ; real time 266 msec ; space allocation: ; 131 cons cells, 104,864 other bytes, 0 static bytes (#(2 3 4 5 6 7 8 9 11 12 ...) . #(3 6 3 4 10 9 4 16 3 36 ...)) cl-user(25): ;;;; fixed gmp lisp2gmpz so as to not allocate arrays for each conversion... [1] cl-user(74): :ld ; Fast loading c:\lisp\simplegmp.fasl ; Fast loading from bundle code\llstructs.fasl. [1] cl-user(75): (test0 500 1000 5 (expt 2 1000)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 6,594 msec user, 31 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,594 msec user, 31 msec system ; real time 6,625 msec ; space allocation: ; 13,268 cons cells, 388,992 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 6,781 msec user, 16 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,781 msec user, 16 msec system ; real time 6,860 msec ; space allocation: ; 4,428 cons cells, 629,808 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 7,313 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 7,313 msec user, 0 msec system ; real time 7,328 msec ; space allocation: ; 674 cons cells, 145,360 other bytes, 0 static bytes (#(3 4 5 7 8 9 11 12 14 15 ...) . #(1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 1154124468038119198553274525436302008169707233613909230548198193560403101609939146803636930568147780229093515197267115450607881158704758325090762990957984426835606243474480729693645211813082909075613365787530231317339255590079009885214244493916531729287280417857119703912380070357219778815343596909891860432578523138556131044265560756168905703425759059337920769670636390779709523885936510317487013947995208663932275262433332872289339644020795297413288352384358253161149141864736144905216611528728852109506514599518647032681535052519219739537062330713374695394142666670029541576167024780161070459186424{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 6433392739254075367908373313228208022028777255325383390168487712884986049744605269373548565765586168037787113777775734054084506618751859296753328882790897399684368773780721246155549247142684775859785433102107265694639913893164316099251464039491328398733285177121876622285759290713268653920863113672369081264017120266561002689405012563914851236487961441872360708519865701098924640584547341269812192547565938520190981351166653353865513567628695993781220551348095838156352170293274146796970785642802859879230819488301536673132470461990982799910992642084150656685900633853100775190831169942860769274006622{g} 6433392739254075367908373313228208022028777255325383390168487712884986049744605269373548565765586168037787113777775734054084506618751859296753328882790897399684368773780721246155549247142684775859785433102107265694639913893164316099251464039491328398733285177121876622285759290713268653920863113672369081264017120266561002689405012563914851236487961441872360708519865701098924640584547341269812192547565938520190981351166653353865513567628695993781220551348095838156352170293274146796970785642802859879230819488301536673132470461990982799910992642084150656685900633853100775190831169942860769274006622{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 3515624836235514988336248348655074471954089456166956122177871347094978343891055770221601568148743086755483113932581035292143147680935296117341223244440100654325123121300153603296899643754770881397254753722457481605437770028037058994762760363254866212243458537541984826620532497421802056148360479928633166880556892575530317727701653791760748919851313062470156853623675866194084918614655476876435232014984949326737718894219375712387592707225253453438547690988198948270870713403432494875466556955038674142100640999864274649699374587859233177977119230530985856669795299538948038440516767941385596886850420{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 3515624836235514988336248348655074471954089456166956122177871347094978343891055770221601568148743086755483113932581035292143147680935296117341223244440100654325123121300153603296899643754770881397254753722457481605437770028037058994762760363254866212243458537541984826620532497421802056148360479928633166880556892575530317727701653791760748919851313062470156853623675866194084918614655476876435232014984949326737718894219375712387592707225253453438547690988198948270870713403432494875466556955038674142100640999864274649699374587859233177977119230530985856669795299538948038440516767941385596886850420{g} ...)) [1] cl-user(76): ; Fast loading c:\lisp\simplegmp.fasl ; Fast loading from bundle code\llstructs.fasl. [1] cl-user(75): (test0 500 1000 5 (expt 2 1000)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 6,594 msec user, 31 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,594 msec user, 31 msec system ; real time 6,625 msec ; space allocation: ; 13,268 cons cells, 388,992 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 6,781 msec user, 16 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,781 msec user, 16 msec system ; real time 6,860 msec ; space allocation: ; 4,428 cons cells, 629,808 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 7,313 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 7,313 msec user, 0 msec system ; real time 7,328 msec ; space allocation: ; 674 cons cells, 145,360 other bytes, 0 static bytes (#(3 4 5 7 8 9 11 12 14 15 ...) . #(1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 1154124468038119198553274525436302008169707233613909230548198193560403101609939146803636930568147780229093515197267115450607881158704758325090762990957984426835606243474480729693645211813082909075613365787530231317339255590079009885214244493916531729287280417857119703912380070357219778815343596909891860432578523138556131044265560756168905703425759059337920769670636390779709523885936510317487013947995208663932275262433332872289339644020795297413288352384358253161149141864736144905216611528728852109506514599518647032681535052519219739537062330713374695394142666670029541576167024780161070459186424{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 6433392739254075367908373313228208022028777255325383390168487712884986049744605269373548565765586168037787113777775734054084506618751859296753328882790897399684368773780721246155549247142684775859785433102107265694639913893164316099251464039491328398733285177121876622285759290713268653920863113672369081264017120266561002689405012563914851236487961441872360708519865701098924640584547341269812192547565938520190981351166653353865513567628695993781220551348095838156352170293274146796970785642802859879230819488301536673132470461990982799910992642084150656685900633853100775190831169942860769274006622{g} 6433392739254075367908373313228208022028777255325383390168487712884986049744605269373548565765586168037787113777775734054084506618751859296753328882790897399684368773780721246155549247142684775859785433102107265694639913893164316099251464039491328398733285177121876622285759290713268653920863113672369081264017120266561002689405012563914851236487961441872360708519865701098924640584547341269812192547565938520190981351166653353865513567628695993781220551348095838156352170293274146796970785642802859879230819488301536673132470461990982799910992642084150656685900633853100775190831169942860769274006622{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 3515624836235514988336248348655074471954089456166956122177871347094978343891055770221601568148743086755483113932581035292143147680935296117341223244440100654325123121300153603296899643754770881397254753722457481605437770028037058994762760363254866212243458537541984826620532497421802056148360479928633166880556892575530317727701653791760748919851313062470156853623675866194084918614655476876435232014984949326737718894219375712387592707225253453438547690988198948270870713403432494875466556955038674142100640999864274649699374587859233177977119230530985856669795299538948038440516767941385596886850420{g} 1238557634106682616124855813071755815752391238656304009390647897785444768851876119343814871785376861931812492426326297735654646186068693364873674108637908260242436396532687256459442641000628309979482219865955473171772261600527779091117905812411224514765554315719096373299488635027570313667113505954654048662593256710071502371491774838051936027325061507058252398394427986680014906676554180398854326512015555989376253986798532443406613221103827390159553452152152074890478130798762844194180517120016360609087814869987037907917702004043650078788381808545512569832183954976053129872413947398578341236655044{g} 3515624836235514988336248348655074471954089456166956122177871347094978343891055770221601568148743086755483113932581035292143147680935296117341223244440100654325123121300153603296899643754770881397254753722457481605437770028037058994762760363254866212243458537541984826620532497421802056148360479928633166880556892575530317727701653791760748919851313062470156853623675866194084918614655476876435232014984949326737718894219375712387592707225253453438547690988198948270870713403432494875466556955038674142100640999864274649699374587859233177977119230530985856669795299538948038440516767941385596886850420{g} ...)) [1] cl-user(76): :ld newmulg.fasl Error: Attempt to take the value of the unbound variable `[1]'. [condition type: unbound-variable] Restart actions (select using :continue): 0: Try evaluating [1] again. 1: Set the symbol-value of [1] and use its value. 2: Use a value without setting [1]. 3: Return to Debug Level 1 (an "abort" restart). 4: Return to Top Level (an "abort" restart). 5: Abort entirely from this (lisp) process. [2] cl-user(77): Error: Attempt to take the value of the unbound variable `3100775190831169942860769274006622{g}'. [condition type: unbound-variable] Restart actions (select using :continue): 0: Try evaluating 3100775190831169942860769274006622{g} again. 1: Set the symbol-value of 3100775190831169942860769274006622{g} and use its value. 2: Use a value without setting 3100775190831169942860769274006622{g}. 3: Return to Debug Level 2 (an "abort" restart). 4: Try evaluating [1] again. 5: Set the symbol-value of [1] and use its value. 6: Use a value without setting [1]. 7: Return to Debug Level 1 (an "abort" restart). 8: Return to Top Level (an "abort" restart). 9: Abort entirely from this (lisp) process. [3] cl-user(78): :reset cl-user(79): :ld newmulg2.fasl ; Fast loading c:\lisp\newmulg2.fasl cl-user(80): (test0 500 1000 5000 5) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 6,406 msec user, 15 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,406 msec user, 15 msec system ; real time 6,438 msec ; space allocation: ; 1,383,797 cons cells, 40,591,184 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP.................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ; cpu time (non-gc) 3,845 msec user, 78 msec system ; cpu time (gc) 390 msec user, 0 msec system ; cpu time (total) 4,235 msec user, 78 msec system ; real time 4,453 msec ; space allocation: ; 509,177 cons cells, 65,928,912 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 937 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 937 msec user, 0 msec system ; real time 938 msec ; space allocation: ; 732 cons cells, 10,549,616 other bytes, 0 static bytes (#(3766 4941 5459 5582 7586 8429 8761 9279 9402 9604 ...) . #(26{g} 26{g} 26{g} 26{g} 4{g} 5{g} 4{g} 4{g} 4{g} 5{g} ...)) cl-user(81): :ld simplegmp.fasl ; Fast loading c:\lisp\simplegmp.fasl ; Fast loading from bundle code\llstructs.fasl. cl-user(82): :reset cl-user(83): (test0 500 1000 5000 5) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 3,969 msec user, 31 msec system ; cpu time (gc) 1,609 msec user, 31 msec system ; cpu time (total) 5,578 msec user, 62 msec system ; real time 5,672 msec ; space allocation: ; 1,382,614 cons cells, 40,556,512 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 3,906 msec user, 63 msec system ; cpu time (gc) 1,000 msec user, 0 msec system ; cpu time (total) 4,906 msec user, 63 msec system ; real time 4,984 msec ; space allocation: ; 460,876 cons cells, 56,403,760 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 1,453 msec user, 0 msec system ; cpu time (gc) 500 msec user, 0 msec system ; cpu time (total) 1,953 msec user, 0 msec system ; real time 1,953 msec ; space allocation: ; 768 cons cells, 10,549,872 other bytes, 0 static bytes (#(6689 7888 9042 11489 12688 13353 13842 14154 15353 16507 ...) . #(2{g} 1{g} 5{g} 2{g} 1{g} 5{g} 5{g} 2{g} 1{g} 5{g} ...)) cl-user(84): (test0 500 1000 5000 (expt 2 1000)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 12,578 msec user, 375 msec system ; cpu time (gc) 3,625 msec user, 47 msec system ; cpu time (total) 16,203 msec user, 422 msec system ; real time 16,688 msec ; space allocation: ; 1,380,491 cons cells, 40,499,704 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 11,125 msec user, 531 msec system ; cpu time (gc) 3,219 msec user, 0 msec system ; cpu time (total) 14,344 msec user, 531 msec system ; real time 14,922 msec ; space allocation: ; 460,165 cons cells, 56,341,328 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 7,094 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 7,094 msec user, 0 msec system ; real time 7,140 msec ; space allocation: ; 1,270 cons cells, 10,549,616 other bytes, 0 static bytes (#(5203 5583 5656 7188 7568 7641 7805 8641 8752 9021 ...) . #(89702763772586384990514087570003968260464577381045188547287276598735090498678100599859041926800218592758423574976516975549881294928460229408691729041084675628264147365060515128158927296646309048563949264425992117953139060471455537779342642766718750795454557008024389409215941560338715644264326417075735155551781651893639475174458177750722988621272054644798879598329749631678762235421087151232978070061573632526525660721844305957755770907227378101513968506757584240546185668912558592140067589197151541890319207076188906095247445249107979616544557748701211780020735888998277819152377416326952478779787528{g} 89702763772586384990514087570003968260464577381045188547287276598735090498678100599859041926800218592758423574976516975549881294928460229408691729041084675628264147365060515128158927296646309048563949264425992117953139060471455537779342642766718750795454557008024389409215941560338715644264326417075735155551781651893639475174458177750722988621272054644798879598329749631678762235421087151232978070061573632526525660721844305957755770907227378101513968506757584240546185668912558592140067589197151541890319207076188906095247445249107979616544557748701211780020735888998277819152377416326952478779787528{g} 89702763772586384990514087570003968260464577381045188547287276598735090498678100599859041926800218592758423574976516975549881294928460229408691729041084675628264147365060515128158927296646309048563949264425992117953139060471455537779342642766718750795454557008024389409215941560338715644264326417075735155551781651893639475174458177750722988621272054644798879598329749631678762235421087151232978070061573632526525660721844305957755770907227378101513968506757584240546185668912558592140067589197151541890319207076188906095247445249107979616544557748701211780020735888998277819152377416326952478779787528{g} 16549544357404942942259908442181881662692406849897039466892415151412277844798491445303327637203441544178110305168591730031268325056134994068394768959042494976148071427622823006082575234137749849398650699584361996010271749812580490677616579499715587539905028873537748106617423507154810207438603016829309174820877013297060320316012666044777989092590979818475565102393382241844337491120247890831422420811037663135270827996475019424871806779084730125570493642050407510344636563642312068885714997911748989334439540373064790656356054725732231769810191920242391496787007576445096955223098242150772346825650997{g} 16549544357404942942259908442181881662692406849897039466892415151412277844798491445303327637203441544178110305168591730031268325056134994068394768959042494976148071427622823006082575234137749849398650699584361996010271749812580490677616579499715587539905028873537748106617423507154810207438603016829309174820877013297060320316012666044777989092590979818475565102393382241844337491120247890831422420811037663135270827996475019424871806779084730125570493642050407510344636563642312068885714997911748989334439540373064790656356054725732231769810191920242391496787007576445096955223098242150772346825650997{g} 16549544357404942942259908442181881662692406849897039466892415151412277844798491445303327637203441544178110305168591730031268325056134994068394768959042494976148071427622823006082575234137749849398650699584361996010271749812580490677616579499715587539905028873537748106617423507154810207438603016829309174820877013297060320316012666044777989092590979818475565102393382241844337491120247890831422420811037663135270827996475019424871806779084730125570493642050407510344636563642312068885714997911748989334439540373064790656356054725732231769810191920242391496787007576445096955223098242150772346825650997{g} 89702763772586384990514087570003968260464577381045188547287276598735090498678100599859041926800218592758423574976516975549881294928460229408691729041084675628264147365060515128158927296646309048563949264425992117953139060471455537779342642766718750795454557008024389409215941560338715644264326417075735155551781651893639475174458177750722988621272054644798879598329749631678762235421087151232978070061573632526525660721844305957755770907227378101513968506757584240546185668912558592140067589197151541890319207076188906095247445249107979616544557748701211780020735888998277819152377416326952478779787528{g} 35265754189066004816584279681699975964191456059088211061409065254490953218890997186371150940508399913764448179412356959600158423551403304716857272095522104089609551110576162488075769540763142297423744563353889036933264115359245137821439518295056308816761206622532846912876221205418563709279752856760842248161655465529352809652645416629995232146026671383722881546832830973848762675867488732433887248870590710549685206665031470437923971072665458141317232022917345478972284742571358205259713820990511355523353894799506264977581200791820672992789734301374839366911474731642847964111220438452581287093608564{g} 103554190696594703253989651134978205790097944563381894044722044026135102573186219761491255432431639822007776628104736735015087545474455329959216165530028404577770531337807566209823252739083847223018535012546145458498180190248182092748988100455291566721141682550094902655993227451522852589909064531667645529053369061698707110180743476841217082653422774277205485786166923625266297525268843829126043560822513611763964505939048554383501099739004363401612450430558484904536506574728523800372290638398780323284836002883630016371299679741805399786556164332647803816451464159848020348439053512795106750155332802{g} 35265754189066004816584279681699975964191456059088211061409065254490953218890997186371150940508399913764448179412356959600158423551403304716857272095522104089609551110576162488075769540763142297423744563353889036933264115359245137821439518295056308816761206622532846912876221205418563709279752856760842248161655465529352809652645416629995232146026671383722881546832830973848762675867488732433887248870590710549685206665031470437923971072665458141317232022917345478972284742571358205259713820990511355523353894799506264977581200791820672992789734301374839366911474731642847964111220438452581287093608564{g} ...)) cl-user(85): (test0 500 1000 5 (expt 2 1000)) mul-naiveG time - just use insertion into single list, using GMP ; cpu time (non-gc) 6,641 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,641 msec user, 0 msec system ; real time 6,640 msec ; space allocation: ; 13,211 cons cells, 387,232 other bytes, 0 static bytes mul-hash1G time - hash1 using GMP ; cpu time (non-gc) 6,796 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 6,796 msec user, 0 msec system ; real time 6,797 msec ; space allocation: ; 4,412 cons cells, 628,048 other bytes, 0 static bytes mul-strG time - heapmerge using GMP ; cpu time (non-gc) 7,313 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 7,313 msec user, 0 msec system ; real time 7,390 msec ; space allocation: ; 641 cons cells, 145,104 other bytes, 0 static bytes (#(7 8 11 12 13 14 15 16 17 18 ...) . #(19446401760983737918671044147831869485665826606155495203726487459540482805500098236499624285374831445039113516182931692746682296421311383559181511201324750139065532907306933598047212449533048454408878812233607370748670615889777829436801462939802821960003037171275672338105336614069884891257958251139215371762630018779837530004306112486456579514316644936704452837893756264718982208231439960106883068605231030436921063076269142191585074401657152640590711969896081377296253816551946263664366708025995699758797346026745306922842751289292519877964974596087928824087948909406352548531950789880239328637447247{g} 19446401760983737918671044147831869485665826606155495203726487459540482805500098236499624285374831445039113516182931692746682296421311383559181511201324750139065532907306933598047212449533048454408878812233607370748670615889777829436801462939802821960003037171275672338105336614069884891257958251139215371762630018779837530004306112486456579514316644936704452837893756264718982208231439960106883068605231030436921063076269142191585074401657152640590711969896081377296253816551946263664366708025995699758797346026745306922842751289292519877964974596087928824087948909406352548531950789880239328637447247{g} 10362487406730042257262082142033366236476789631876294355886452764646713738243405844385188438161182866084570747634375808017874224388801183483386685285130374397343663044624883236142222207713431594777305731914993967819905908417490713776483403178460751884157131025405080335437361625867378836921883976797905057544327975745155515016484040213357145104005059816019532779313040331560893074533290206987567623494941284729334790325414177271236074501899548941287804911308148363353005457312608872979183731108991957845612531375416817670982582485134576363853818880748980943971499302673387692609269452730868497701365144{g} 10362487406730042257262082142033366236476789631876294355886452764646713738243405844385188438161182866084570747634375808017874224388801183483386685285130374397343663044624883236142222207713431594777305731914993967819905908417490713776483403178460751884157131025405080335437361625867378836921883976797905057544327975745155515016484040213357145104005059816019532779313040331560893074533290206987567623494941284729334790325414177271236074501899548941287804911308148363353005457312608872979183731108991957845612531375416817670982582485134576363853818880748980943971499302673387692609269452730868497701365144{g} 19446401760983737918671044147831869485665826606155495203726487459540482805500098236499624285374831445039113516182931692746682296421311383559181511201324750139065532907306933598047212449533048454408878812233607370748670615889777829436801462939802821960003037171275672338105336614069884891257958251139215371762630018779837530004306112486456579514316644936704452837893756264718982208231439960106883068605231030436921063076269142191585074401657152640590711969896081377296253816551946263664366708025995699758797346026745306922842751289292519877964974596087928824087948909406352548531950789880239328637447247{g} 19446401760983737918671044147831869485665826606155495203726487459540482805500098236499624285374831445039113516182931692746682296421311383559181511201324750139065532907306933598047212449533048454408878812233607370748670615889777829436801462939802821960003037171275672338105336614069884891257958251139215371762630018779837530004306112486456579514316644936704452837893756264718982208231439960106883068605231030436921063076269142191585074401657152640590711969896081377296253816551946263664366708025995699758797346026745306922842751289292519877964974596087928824087948909406352548531950789880239328637447247{g} 20521400536568767928835030875829922455375058814045002361087788579288570153994225983536479295916400095111012147412060538996704488912700917256452904483795408034647711841432287147517907375604018375433299737103165296544737475759525206496107743624666044638874411771123012796255151190396041599920887710267454553350737967318537478828578488393569400793606946742757467378409001535772812359321654092820152882530725397758491468601972666096129163404138633237563781527679337221051543225811486750167035353700345484503865369102987435836382175239069606311203267323291002857648983748015902986534612381377286212652333716{g} 20521400536568767928835030875829922455375058814045002361087788579288570153994225983536479295916400095111012147412060538996704488912700917256452904483795408034647711841432287147517907375604018375433299737103165296544737475759525206496107743624666044638874411771123012796255151190396041599920887710267454553350737967318537478828578488393569400793606946742757467378409001535772812359321654092820152882530725397758491468601972666096129163404138633237563781527679337221051543225811486750167035353700345484503865369102987435836382175239069606311203267323291002857648983748015902986534612381377286212652333716{g} 10362487406730042257262082142033366236476789631876294355886452764646713738243405844385188438161182866084570747634375808017874224388801183483386685285130374397343663044624883236142222207713431594777305731914993967819905908417490713776483403178460751884157131025405080335437361625867378836921883976797905057544327975745155515016484040213357145104005059816019532779313040331560893074533290206987567623494941284729334790325414177271236074501899548941287804911308148363353005457312608872979183731108991957845612531375416817670982582485134576363853818880748980943971499302673387692609269452730868497701365144{g} 10362487406730042257262082142033366236476789631876294355886452764646713738243405844385188438161182866084570747634375808017874224388801183483386685285130374397343663044624883236142222207713431594777305731914993967819905908417490713776483403178460751884157131025405080335437361625867378836921883976797905057544327975745155515016484040213357145104005059816019532779313040331560893074533290206987567623494941284729334790325414177271236074501899548941287804911308148363353005457312608872979183731108991957845612531375416817670982582485134576363853818880748980943971499302673387692609269452730868497701365144{g} ...)) cl-user(86): (+ (* 8 2.36) 14) 32.879997 cl-user(87): :ld papi-pentium.fasl ;............... 8/31/08, chaining using only limited search for match... [1] cl-user(301): (test 500 1000 5000 5) mul-hash1 time - best hash table version ; cpu time (non-gc) 1,687 msec user, 0 msec system ; cpu time (gc) 110 msec user, 0 msec system ; cpu time (total) 1,797 msec user, 0 msec system ; real time 1,782 msec ; space allocation: ; 20 cons cells, 26,085,520 other bytes, 0 static bytes mul-heap time - use simple streams, in a heap array, insert from top sometimes ; cpu time (non-gc) 765 msec user, 0 msec system ; cpu time (gc) 63 msec user, 0 msec system ; cpu time (total) 828 msec user, 0 msec system ; real time 875 msec ; space allocation: ; 230 cons cells, 10,509,376 other bytes, 0 static bytes mul-heap2 time - use simple streams, in a heap array, insert from top sometimes, chaining ; cpu time (non-gc) 672 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 672 msec user, 0 msec system ; real time 641 msec ; space allocation: ; 229 cons cells, 10,509,376 other bytes, 0 static bytes mul-naive time - just use insertion into single list ; cpu time (non-gc) 2,501 msec user, 0 msec system ; cpu time (gc) 62 msec user, 0 msec system ; cpu time (total) 2,563 msec user, 0 msec system ; real time 2,578 msec ; space allocation: ; 921,162 cons cells, 3,684,656 other bytes, 0 static bytes (#(3024 5712 6602 7778 7810 8644 10498 11332 11388 11450 ...) . #(8 12 16 20 2 10 3 15 4 12 ...)) [1] cl-user(302): (test 500 1000 5 5) [1] cl-user(302): [1] cl-user(302): [1] cl-user(302): [1] cl-user(302): mul-hash1 time - best hash table version ; cpu time (non-gc) 78 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 78 msec user, 0 msec system ; real time 93 msec ; space allocation: ; 5 cons cells, 277,552 other bytes, 0 static bytes mul-heap time - use simple streams, in a heap array, insert from top sometimes ; cpu time (non-gc) 594 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 594 msec user, 0 msec system ; real time 547 msec ; space allocation: ; 131 cons cells, 104,864 other bytes, 0 static bytes mul-heap2 time - use simple streams, in a heap array, insert from top sometimes, chaining ; cpu time (non-gc) 421 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 421 msec user, 0 msec system ; real time 422 msec ; space allocation: ; 131 cons cells, 104,864 other bytes, 0 static bytes mul-naive time - just use insertion into single list ; cpu time (non-gc) 47 msec user, 0 msec system ; cpu time (gc) 0 msec user, 0 msec system ; cpu time (total) 47 msec user, 0 msec system ; real time 47 msec ; space allocation: ; 9,181 cons cells, 36,736 other bytes, 0 static bytes (#(1 4 6 7 9 10 11 12 14 15 ...) . #(6 12 2 6 4 12 6 8 18 6 ...)) [1] cl-user(303):