Performance Improvements in Maple 2021Maple 2021 improves the performance of many routines.map and some related commandsGMP UpdateBinomial CoefficientsMultinomial CoefficientsThe Units[Simple] packageGraphTheory PolyhedralSets

<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk0"><Hyperlink hyperlink="true" linktarget="Help:map"><Font underline="true" foreground="[10,129,180]">map</Font></Hyperlink> and some related commands</Text-field>For Maple 2021, the map command and some other built-in commands related to it (such as element-wise operators and zip) have been sped up significantly for common operations. In particular, there is a facility that recognizes some operations that are frequently mapped, and uses a faster implementation for these operations in cases where that is applicable. Here are some examples. We ran these on one particular machine in Maple 2020 and 2021. To be precise, we ran each call to CodeTools:-Usage in a new session, defining L each time, rather than in a single session as you see in this worksheet. The numbers shown after each command give the factor of reduction in memory used, the speedup in CPU time, and the speedup in real time.The following were computed for L := [seq(-10^6..10^6)]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(`-`, L)146362map(abs, L)8.22928map(has, L, 42)104242map(hastype, L, posint)103534map(type, L, posint)104040map(`+`, L, 42)4.51414map(`-`, L, 42)4.51515map(`*`, L, 42)4.51515map(`/`, L, 1/3)4.51313map(`^`, L, 2)1.56.56.6

The following were computed for L := [seq(true, 1..10^6), false]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(`not`, L)105556map(`and`, L, true)80000 *5454map(`or`, L, true)104746map(`xor`, L, true)155659

Note: The result (*) in the preceding table occurs because Maple manages to do this with almost no memory used in the current implementation.The following were computed for L := [seq([i,i+1], i = -10^6..10^6)]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(has, L, 42)102817map(hastype, L, posint)102213map(type, L, posint)103421map(op, L)3.34526map2(op, 1, L)103220map2(op, 2, L)103521map(min, L)2.71.71.7map(max, L)2.71.71.7map(`?[]`, L, [1])136640map(`?[]`, L, [2])136741

The following were computed for L := [seq(i = i+1, i = -10^6..10^6)]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(lhs, L)8.03321map(rhs, L)8.02617

The following were computed for L := [seq({i, 42}, i = -10^6..10^6)]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(`intersect`, L, {2})4.02.02.1map(`union`, L, {2})1.71.61.6map2(member, 3, L)103220

The following were computed for L := [seq("abc", 1..10^6)]OperationFactor of Reduction in Memory UsedSpeedup in CPU TimeSpeedup in Real Timemap(`?[]`, L, [1])132829

The differences in speedup between CPU time and real time, where present, are almost entirely caused by a reduction in garbage collection. Garbage collection is parallelized, so it takes more CPU time than real time; a reduction in garbage collection therefore benefits the CPU time more than the real time.
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk1">GMP Update</Text-field>The version of the GMP library used for large integer arithmetic by Maple has been upgraded to version 6.2.0. This adds improved support for new hardware, leading to small performance improvements for various integer operations. Micro benchmarks for the basic integer operations (addition, multiplication, gcd, etc) show speedups in the range 5-10%.
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk2">Binomial Coefficients</Text-field>The underlying algorithm to compute NiMtSSliaW5vbWlhbEc2IjYkSSJhR0YlSSJiR0Yl for integer values of NiNJImFHNiI= and NiNJImJHNiI= in the binomial command has been improved in Maple 2021. Previously a recurrence formula was used that minimized the size of intermediate calculations, but could be very slow for large values of NiNJImJHNiI=. Now the result is either computed more directly, or computed using the GMP implementation of binomial. The following computation is about 100 times faster in Maple 2021 than in Maple 2020.CodeTools:-Usage( binomial( 200001, 50001 ) ):The old binomial algorithm was highly optimized for computing, in order, sequences of binomial coefficients where the value of NiNJImFHNiI= is fixed. That remains about the same speed in the new implementation.CodeTools:-Usage( seq( binomial( 100000, i ), i = 1 .. 100000) ):But now, it is also fast for sequences that are out of order or with fixed values of NiNJImJHNiI=. The following sequences are extremely slow to compute in previous versions of Maple.a := 10^5-4; the_bs := Statistics:-Shuffle( [seq(i, i=1..a, 10^4)] ):CodeTools:-Usage( seq( binomial( a, b), b in the_bs) ):Computing a 10000 element sequence is only about 100 times the cost of computing the first element.CodeTools:-Usage( seq( binomial( 10000+i, 5000 ), i = 1 .. 9999) ):
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk3">Multinomial Coefficients</Text-field>The algorithm for computing multinomial coefficients in the command combinat:-multinomial has been improved so that it is computed using the binomial command and thus is now much faster than the previous algorithm which used a formula in terms of factorials. Examples like the following are now at least three times faster than in Maple 2020.CodeTools:-Usage(combinat:-multinomial(104000, 11000, 21000, 31000, 41000)):The following example is 10 times faster in Maple 2021 than in Maple 2020.CodeTools:-Usage( combinat:-multinomial(1501500, seq(2000 .. 1000, -1)) ):And special cases are now identified and computed almost instantly, avoiding the large factorial and integer division computations that result from a computation directly from the factorial formula.combinat:-multinomial(10^10+2, 10^10, 1, 1);
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk4">The Units[Simple] package</Text-field>Operations on numeric expressions (or more precisely, complex extended numeric expressions) in the Simple Units environment, provided by the Units[Simple] package, are much faster in Maple 2021. Here is an example.with(Units):CodeTools:-Usage(Vector(10^4,i->sin(1.0*i),datatype=float[8])):This example is 15 to 20 times faster and uses 15 to 20 times less memory than in Maple 2020.
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk5">GraphTheory </Text-field>A number of commands in the GraphTheory package perform faster in Maple 2021 compared to previous versions of Maple. These performance improvements are noted in the What's New in Graph Theory? help page.
<Text-field style="Heading 2" layout="Heading 2" bookmark="bkmrk6">PolyhedralSets</Text-field>The Project command in the PolyhedralSets package now uses a faster algorithm that checks for redundant constraints. For more information, see What's New in Polyhedral Sets?