Re: Increase in efficiency with Module

*To*: mathgroup at smc.vnet.net*Subject*: [mg40117] Re: Increase in efficiency with Module*From*: "Carl K. Woll" <carlw at u.washington.edu>*Date*: Fri, 21 Mar 2003 02:36:58 -0500 (EST)*Organization*: University of Washington*References*: <8EB1C3634596D6118952006008F711CD5BCD2F@debis.com> <b5bjlf$5rk$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Hi, Since this thread seems to have transformed itself into a speed contest, I thought I would throw in my 2 cents. Here is my attempt: h[a_]:=(s+=Tr[Sign[a-First[a]]];Rest[a]) carl[t_]:=Block[{s=0}, Nest[h,t,Length[t]]; s] Comparing to ftauc3PP (the fastest so far according to Bobby) we have: test=Table[Random[],{1000}]; In[105]:= ftauc3PP[test]//Timing carl[test]//Timing Out[105]= {0.265 Second, 9362} Out[106]= {0.094 Second, 9362} So, my uncompiled code is almost 3 times faster than ftauc3PP. Carl Woll Physics Dept U of Washington "Dr Bob" <drbob at bigfoot.com> wrote in message news:b5bjlf$5rk$1 at smc.vnet.net... > On lists of size 1000, the three fastest are now ftauc3, ftauc3P (5% > faster), and ftauc3PP (another 8% faster). > > Bobby > > On Wed, 19 Mar 2003 09:11:54 +0100, Wolf, Hartmut <Hartmut.Wolf@t- > systems.com> wrote: > > > Bobby, > > > > yes, I've missed a minor point, which I did not correct, as this had not > > been the focus of the discussion: > > > > In[1]:= ry = Table[Random[], {1000}]; > > In[3]:= > > ftaucSCP = Compile[{{ry, _Real, 1}}, Module[{a = 0, n = Length[ry]}, > > Do[Do[If[ry[[i]] < ry[[j]], ++a, If[ry[[i]] > ry[[j]], --a]], {j, i + 1, > > n}], {i, 1, n - 1}]; a]]; > > In cases like this use PreDecrement and PreIncrement, instead of > > Decrement > > or Increment. This gives another performance boost of a percent or a > > fraction. I'm not very experienced with the Mathematica Compiler (which, > > BTW, generates special code to be interpreted, not C code), however my > > observation is that code which is nearest to plain C-code compiles > > fastest. > > And the rule I put up above is an old rule for C programming. Nowadays, > > however, a modern C-compiler recognizes the situation and optimizes the > > generated machine code accordingly. And also, the extra machine cycle (a > > register move) (if it were) needed for a++, compared to ++a gets > > unnoticed > > with a modern CPU (their problems are now quite different). But this does > > not apply to mathematica compiled code, as it is interpreted, sic! > > > > > > In[4]:= Do[ftauc3[ry], {10}] // Timing > > Out[4]= {12.168 Second, Null} > > In[5]:= Do[ftaucSCP[ry],{10}]//Timing > > Out[5]= {11.616 Second, Null} > > > > > > Applying this to your code: > > > > In[20]:= > > ftauc3P = Compile[{{ry, _Real, 1}}, Block[{i = 0, j, a = 0, n = > > Length@ry}, Do[j = ++i; > > Do[a += Sign[ry[[++j]] - ry[[i]]], {n - i}], > > {n - 1}]; > > a]]; > > > > In[21]:= Do[ftauc3P[ry], {10}] // Timing > > Out[21]= {11.837 Second, Null} > > > > > > The warning as not to use external functions does not apply to your code, > > as > > Sign is one of those functions which are compiled inline. > > > > Other improvement (Do loops) of your code: > > > > In[30]:= > > ftauc3PP = Compile[{{ry, _Real, 1}}, > > Block[{a = 0, n = Length[ry]}, > > Do[ > > Do[a += Sign[ry[[j]] - ry[[i]]], {j, i + 1, n}], > > {i, 1, n - 1}]; > > a]]; > > > > > > In[31]:= Do[ftauc3PP[ry],{10}]//Timing > > Out[31]= {10.686 Second, Null} > > > > That seems to be it! > > > > > > > > Hartmut > > > > > > > >> -----Original Message----- > >> From: Dr Bob [mailto:drbob at bigfoot.com] To: mathgroup at smc.vnet.net > >> Sent: Tuesday, March 18, 2003 9:55 PM > >> To: Wolf, Hartmut; mathgroup at smc.vnet.net; aehirsh at stanford.edu > >> Subject: [mg40117] Re: Increase in efficiency with Module > >> > >> > >> I timed the two original codes, my slightly modified version of that > >> (treat), Hartmut's two functional codes, and his fastest code, ftaucSC. > >> There's a near tie between treat, ftaucSC, and the original ftauc (in > >> that order). I didn't use Real random numbers, since ties seem to be a > >> significant factor in the original code, but the winning functions are > >> the same with Reals anyway. > >> > >> Some might find the following a useful guide to timing functions. I > >> randomize the order in which functions are timed for each random > >> dataset, output means and standard errors sorted from fastest to > >> slowest, and show how to eliminate slow functions before going on to > >> larger data sets and greater numbers of trials. > >> > >> <<Statistics`DescriptiveStatistics` > >> allNames={"ftauc2","functional","functional2","ftauc","ftaucSC" > >> ,"treat"}; > >> randomTrial[functions_List,n_Integer]:=Module[{data=Table[Random[Integer,50 > > ],{\ > >> n}],order,results}, > >> order=Ordering[Random[]&/@functions]; > >> results=First@Timing[#@data]&/@functions[[order]]; > >> results[[Ordering@order]]/Second > >> ] > >> randomTrials[names:{__String},size_Integer,trials_Integer]:= > >> TableForm[ > >> Transpose@Module[{functions=ToExpression/@names,times,ranking},times=\ > >> Transpose@Table[randomTrial[functions,size],{trials}]; > >> means=Mean/@times; > >> ranking=Ordering@means; > >> times=times[[ranking]]; > >> {names[[ranking]],Mean/@times,StandardErrorOfSampleMean/@times} > >> ],TableHeadings\[Rule]{None,{"Function","Mean","Std Error"}}] > >> > > [...] > > > >> treat=Compile[{{ry,_Real,1}},Block[{i=0,j,a=0,n=Length@ry}, > >> Do[i++;j=i+1; > >> Do[a+=Sign[ry[[j]]-ry[[i]]];j++,{n-i}],{n-1}];a]]; > > [...] > > > >> > >> randomTrials[fastest, 1000, 100] > >> > >> TableForm[ > > {{"Function", "Mean", "Std Error"}, {"treat", 0.27246999999999955, > > 0.0009006681021902752}, > > {"ftaucSC", 0.29871000000000036, 0.0009034496179205452}, {"ftauc", > > 0.3101900000000001, 0.0011866849675129872}}, > >> TableHeadings -> {None, {"Function", "Mean", "Std Error"}}] > >> > >> Bobby > >> > >> On Tue, 18 Mar 2003 02:21:27 -0500 (EST), Wolf, Hartmut <Hartmut.Wolf@t- > >> systems.com> wrote: > >> > >>> > >>>> -----Original Message----- > >>>> From: Aaron E. Hirsh [mailto:aehirsh at stanford.edu] To: mathgroup at smc.vnet.net > >>> To: mathgroup at smc.vnet.net > >>>> Sent: Monday, March 17, 2003 9:35 AM > >>>> To: mathgroup at smc.vnet.net > >>>> Subject: [mg40117] Increase in efficiency with Module > >>>> > >>>> > >>>> I would be grateful if someone could explain the difference in > >>>> efficiency between the following two simple programs. ry is a list of > >>>> length n. For n = 1000, the program using Module takes 1 second on my > >>>> laptop, whereas the program without Module takes 75 seconds. > >>>> > >>>> ftauc = Compile[{{ry, _Real, 1}, {n, _Real, 0}}, > >>>> Module[{i, j, a}, i = 1; > >>>> a = 0; > >>>> Do[ j = i + 1; Do[ > >>>> If[ry[[i]] < ry[[j]], a++, If[ry[[i]] > ry[[j]], a--]]; > >>>> j++, {n - i}]; > >>>> i++, {n - 1}]; a > >>>> ]] > >>>> > >>>> ftauc2 = Compile[{{ry, _Real, 1}, {n, _Real, 0}}, > >>>> i = 1; > >>>> a = 0; > >>>> Do[j = i + 1; > >>>> Do[ > >>>> If[ry[[i]] < ry[[j]], a++, If[ry[[i]] > ry[[j]], a--]]; > >>>> j++, {n - i}]; > >>>> i++, {n - 1}]; a > >>>> ] > >>>> > >>>> thank you, > >>>> -- > >>>> > >>>> Aaron E. Hirsh > >>>> Center for Computational Genetics and Biological Modeling > >>>> Department of Biological Sciences > >>>> Stanford University > >>>> tel. (650) 723-4952 > >>>> fax. (650) 725-0180 > >>>> > >>> > >>> Aaron, > >>> > >>> if you inspect the compiled code ftauc[[4]] and ftauc2[[4]] you see > >>> considerable differences which are obviously caused by access to the > > global > >>> variables i, j and a (in ftauc). I cannot go through theses statements > >>> line by line, merely refer to > >>> http://library.wolfram.com/database/Conferences/4682/ > >>> > >>> Although, this appears to be out of date now, a key sentence therein > > still > >>> holds: "The main obstacle to achieving a speedup ... is when the > >>> compiled > >>> code has to externally evaluate a function". From the compiled code for > >>> ftauc2, I suppose, that access and updates of the global variables > >>> i,j,a is done by calling an (external) function. > >>> > >>> Further: "In structures such as Module or Block, local variables can be > >>> declared. The compiled code will store value of such a variable in a > >>> register, which can then be updated whenever the variable gets a new > >>> value. > >>> > >>> > >>> Such use local variables! > >>> > >>> > > [...] > >>> -- > >>> Hartmut Wolf > >>> > > [...] > >> -- majort at cox-internet.com > >> Bobby R. Treat > >> > > > > > > > > -- > majort at cox-internet.com > Bobby R. Treat > >

**Re: Increase in efficiency with Module**

**Re: a challenge/problem.**

**Re: Increase in efficiency with Module**

**Comparison of Mathematica on Various Computers**