Re: Compile function and AppendTo for lists (vrs. 8.0.4)
- To: mathgroup at smc.vnet.net
- Subject: [mg124656] Re: Compile function and AppendTo for lists (vrs. 8.0.4)
- From: "Oleksandr Rasputinov" <oleksandr_rasputinov at hmamail.com>
- Date: Sun, 29 Jan 2012 05:15:10 -0500 (EST)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <jg0mpr$ot7$1@smc.vnet.net>
On Sat, 28 Jan 2012 11:39:39 -0000, Patrick Scheibe
<pscheibe at trm.uni-leipzig.de> wrote:
Dear Patrick
>> 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.
>
> yes, I have seen this but left the "Most[{0}] type enforcement" for the
> sake of simplicity out. I think anyway that all this compiled Bag is at
> the line where there is absolutely no official information from Wolfram
> available. So I wanted to present this as short as possible so that
> noone is feared to try it.
>
> But of course you are absolutely right, that it is overkill to use real,
> when integers are sufficient. Btw, have you seen, that even with a Real
> bag you can assign True and False and get 1.0 and 0.0?
>
In fact I think True -> 1.0 and False -> 0.0 casting is the behaviour of
the virtual machine rather than Bags per se, and this will depend as a
result on the types of the registers holding the Bag itself as well as the
expression being placed into or taken out of it. For instance:
f = Compile[{},
Module[{p = 0., q = 1.}, p = True; q = False; {p, q}]
];
f[]
->
{1., 0.}
The type, if any, of Bags is a more involved question. I am leaning toward
the view that Bags do not have any associated type, and that it is just
that when being put together or taken apart the pieces have to be of types
commensurate with the virtual machine registers that they occupy. In fact
it is possible to stuff a Bag held in a Real register with Bags of
Integers--just not Integers directly. These nested Bags can then be
unpacked into Integer registers and an Integer result returned.
Unfortunately this is not that easy to achieve in practice and seems
sensitive to implementation details; for example, see the following code
that works in version 7 (and 5.2) but returns an incorrect result in 8:
f = Compile[{},
Module[{bag = Internal`Bag at Most[{0.}], parts = {0.}},
Internal`StuffBag[bag, Internal`Bag[{1, 2, 3}]];
Internal`StuffBag[bag, Internal`Bag[{4, 5, 6}]];
Internal`StuffBag[bag, Internal`Bag[{7, 8, 9}]];
parts = Internal`BagPart[bag, All];
Table[Internal`BagPart[parts[[i]], All], {i, 1, Length[parts]}]
]
]
7 gives: {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
8 gives: {{1., 2., 3.}, {1., 2., 3.}, {1., 2., 3.}} (which I think is a
symptom of calling Internal`BagPart on corrupted Bags.)
On the other hand, if the Bags are declared as Integers, the correct
result is also given by version 8. However, a mixture of Real and Integer
bags within the same Bag (e.g., try changing 5 to 5. in the above) appears
to confuse the result entirely in both versions (the result appears to be
pointer casts with values being interpreted as the wrong type), and is apt
to crash the kernel. Another thing that crashes the kernel is using
Internal`BagPart with a part specification other than All in versions
prior to 8. A final observation (for the time being) is that what happens
in the VM, stays in the VM: it is not possible (and probably dangerous to
attempt) to stuff a bag created in compiled code using a MainEvaluate call.
> This
>
>> first, Internal`BagLength is not supported
>
> I knew because I was looking what is possible and what is not. But the
> third arguments to BagPart is new to me and a precious information. I'm
> really interested in to what else is possible.
>
I found this when I tried supplying a third argument in the hope that
Internal`BagPart might work like Part (in that a sequence of part
specifications allows the extraction of more deeply nested parts).
Obviously that is not the case, but knowing about the existence of the
third argument might be useful anyway. As for what else is possible, I
don't know.
Regarding some other miscellaneous data structures (although these ones
cannot be compiled), you might like to investigate the NIntegrate`Heap*
and System`Utilities`HashTable* families of functions. The former has been
discussed by Anton Antonov in his presentation "A Parallel Heap Object:
Mathematica Message Passing Implementations" for the Wolfram Technology
Conference 2007 (he also gives source code which can be used in its own
right, although the NIntegrate` implementation uses different syntax, e.g.
the ordering function comes first, so its correct usage will require some
experimentation); the latter, as far as I know, has never been discussed
but it is clear how it should work. For anyone who cares, both of these
objects are atomic (i.e. AtomQ is True), but they do have meaningful
InputForms.
Best,
O. R.
> Cheers
> Patrick
>
>
>> 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