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
>