Re: Compile function and AppendTo for lists (vrs. 8.0.4)

*To*: mathgroup at smc.vnet.net*Subject*: [mg124685] Re: Compile function and AppendTo for lists (vrs. 8.0.4)*From*: Fred Simons <f.h.simons at tue.nl>*Date*: Tue, 31 Jan 2012 05:38:35 -0500 (EST)*Delivered-to*: l-mathgroup@mail-archive0.wolfram.com

Dear Olek and Patrick, With a lot of interest I studied your contributions to the thread on compilation of AppendTo. I have to admit that Bag's are completely new to me, and that I am not familiar with modern programming languages either, so it took some time before I understood the (very good!) explanation of Daniel Lichtblau. My idea is that the result of a command like a = Bag[...] is that the bag is stored somewhere as a raw expression, whatever that may be, and that the value of a is only a pointer to that expression. Please correct me if I am wrong. An irrelevant remark: my experience is that Do is normally slightly faster than For, so I used the function AppendTo[$ContextPath, "Internal`"]; appendBag2a = Compile[{{k, _Integer, 0}}, Module[{p = Bag[Most[{0}]]}, Do[StuffBag[p, Bag[{1, i}]], {i, 1, k}]; Table[BagPart[BagPart[p, i], All], {i, 1, k}]]]; That works fine and fast, apart from the fact that on my computer Mathematica runs out of memory for k=10^6. I surmise that the reason is that at the end the variable p has about 10^6 pointers to different raw Bag expressions. So I tried to do it without all these pointers: uncompiled3[k_Integer] := Module[{p = Bag[]}, Do[StuffBag[p, {1, i}], {i, 1, k}]; BagPart[p, All]] I did not expect this function to be faster than appendBag2: In[8]:= appendBag2a[2 10^5]; // Timing uncompiled3[2 10^5]; // Timing Out[8]= {0.234,Null} Out[9]= {0.125,Null} Of course the next step is trying to compile this function. I did not manage to do that. The problem seems to be the initialization of the locale variable p. I tried compilation with the definitions p=Bag[], p=Bag[{}], p=Bag[Rest[{0}]], p=Bag[Rest[{{0,0}}]], or e.g. p=Bag[{{0,0}}] and taking the rest at the end. In all cases a numerical error was encounterd and the uncompiled function was used for evaluation. But the following implementation works fine: compiled4= Compile[{{k,_Integer}}, Module[{p=Bag[Rest[{0}]]},Do[StuffBag[p,1];StuffBag[p,i],{i,1,k}]; Partition[BagPart[p,All],2]]]; In[16]:= uncompiled3[2 10^5]; // Timing compiled4[2 10^5]; // Timing Out[16]= {0.109,Null} Out[17]= {0.016,Null} Moreover, even for k = 10^7, this function does not crash Mathematica: In[19]:= compiled4[10^7]; // Timing Out[19]= {0.687,Null} Kind regards, Fred Simons Eindhoven University of Technology Op 27-1-2012 12:12, Oleksandr Rasputinov schreef: > Patrick > > I like your "Bag-within-a-Bag" approach to avoid requiring support of > tensor bags. Indeed on further investigation it seems that these are not > > supported. > > Just to note that your example puts p in a Real register rather than an > Integer one, so the results are not of the expected type. Also, it is not > necessary to create and stuff Bags separately; one can create pre-stuffed > bags using Internal`Bag[contents]. Thus, one can simplify your example to > the following: > > appendBag2 = Compile[{{k, _Integer, 0}}, > Module[{p = Bag@Most[{0}] (* put into integer register *), i = 1}, > For[i = 1, i<= k, ++i, StuffBag[p, Bag[{1, i}]]]; > > Table[BagPart[BagPart[p, i], All], {i, 1, k}] > ] > ]; > > This does not gain (or lose) any performance over your code, but it is > shorter to write and uses less memory (because integers take up half the > > space that reals do). The latter consideration might be important given > that this function uses a tremendous amount of memory for long lists > (using reals with k = 10^6 requires about 9.6GB, even though the result is > only 16MB in size). > > Two miscellaneous notes about Bags that I am fairly sure have not been > mentioned anywhere else so far: first, Internal`BagLength is not supported > in compiled code; second, Internal`BagPart can take a third argument, > which is a function (instead of List) to wrap around the sequence of > parts, and this does work in compiled code provided that the function is > > either Plus or Times. > > Best, > > O. R. > > On Thu, 26 Jan 2012 08:30:01 -0000, Patrick Scheibe > <pscheibe at trm.uni-leipzig.de> wrote: > >> Hi, >> >> using Oleks Internal`Bag suggestion, think of a list as a bag of numbers >> and you can use this as replacement for the lists in your compile. Using >> Oleks append-to version as comparison >> >> appendTo = >> Compile[{{k, _Integer, 0}}, >> Module[{mat = {{0, 0}}, i = 0}, >> For[i = 1, i<= k, i++, AppendTo[mat, {1, i}]]; >> Rest[mat]]] >> >> and here is the Internal`Bag implementation >> >> AppendTo[$ContextPath, "Internal`"]; >> appendBag = Compile[{{k, _Integer}}, >> Module[{p = Bag[], i = 1, tmpBag}, >> For[i = 1, i<= k, ++i, >> tmpBag = Bag[]; >> StuffBag[tmpBag, 1]; >> StuffBag[tmpBag, i]; >> StuffBag[p, tmpBag]; >> ]; >> Table[BagPart[BagPart[p, i], All], {i, k}] >> ] >> ]; >> >> Speedtest shows >> >> In[55]:= First /@ {AbsoluteTiming[appendTo[10^5]], >> AbsoluteTiming[appendBag[10^5]]} >> >> Out[55]= {14.559237, 0.149063} >> >> that the bag implementation is about 100 times faster. Unfortunately >> there doesn't exist much documantation about this. One place to look is >> here http://stackoverflow.com/a/6795762/1078614 where Daniel gives some >> insights into the usage. >> >> Hope this helps. >> >> Cheers >> Patrick >> >> >> On Tue, 2012-01-24 at 05:06 -0500, kris wrote: >>> Hi >>> >>> I have some trouble with my code and would like ask for your help. In >>> general it is about appending data in form of a list to an existing >>> list in a compiled function. As far as I understand Mathematica is not >>> supporting what I am asking for. In order to understand the problem in >>> more detail I present some "toy" code below. >>> >>> test=Compile[{{k,_Integer}}, >>> Module[{mat={}}, >>> For[i=1,i<=k,i++, >>> AppendTo[mat,{1,i}]; >>> ]; >>> mat >>> ] >>> ]; >>> >>> test[2] >>> (*which produces an error*) >>> >>> Appending data in form of numbers for example works just fine but not >>> with lists. Can anybody explain why Mathematica does not support >>> appending lists to lists for compiled function? As an alternative I >>> tried Reap and Sow, which also produces an error. >>> >>> However, what seems funny is the following code: >>> >>> mat={}; >>> test=Compile[{{k,_Integer}}, >>> For[i=1,i<=k,i++, >>> AppendTo[mat,{1,i}]; >>> ]; >>> ]; >>> >>> test[2];mat >>> >>> The above code produces the result that I was looking for in a >>> cumbersome way. I would like to prefer compile code which produces the >>> same result without calling the list mat again. >>> >>> Thanks for help I do appreciate it. >>> Cheers, >>> Kris >