MathGroup Archive 2012

[Date Index] [Thread Index] [Author Index]

Search the Archive

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

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}},

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>  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 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

  • Prev by Date: Re: Trying to close some loose plotting
  • Previous by thread: Re: Compile function and AppendTo for lists (vrs. 8.0.4)
  • Next by thread: Animating morphing Bezier curves; saving points