# InternalBag inside Compile

Since InternalBag, InternalStuffBag and InternalBagPart can be compiled down, it is a precious source for various applications. There were already many questions why AppendTo is so slow, and which ways exist to make a dynamically grow-able array which is faster. Since inside Compile many tricks can simply not be used, which is for instance the case for Sow and Reap, this is a good alternative.

A fast, compiled version of AppendTo: For a comparison I will use AppendTo directly for an easy loop. Ignore the fact that this would not be necessary here, since we know the number of elements in the result list. In a real application, you maybe wouldn't know this.

appendTo = Compile[{{n, _Integer, 0}},
Module[{i, list = Most[{0}]},
For[i = 1, i <= n, ++i,
AppendTo[list, i];
];
list
]
]


Using InternalBag is not as expensive, since in the above code, the list is copied in each iteration. This is not the case for InternalBag.

stuffBag = Compile[{{n, _Integer, 0}},
Module[{i, list = InternalBag[Most[{0}]]},
For[i = 1, i <= n, ++i,
InternalStuffBag[list, i];
];
InternalBagPart[list, All]
]
]


Comparing the run time of both functions uncovers the potential of InternalBag:

First[AbsoluteTiming[#[10^5]]] & /@ {appendTo, stuffBag}

(*
{4.298237, 0.003207}
*)


## Usage and features

The following information was collected from different sources. Here is an article from Daniel Lichtblau who was kind enough to give some insider information. A question on MathGroup led to a conversation with Oleksandr Rasputinov who knew about the third argument of InternalBagPart. Various other posts on StackOverflow exist which I will not mention explicitly. I will restrict the following to the usage of InternalBag and Compile together. While we have 4 functions (InternalBag, InternalStuffBag, InternalBagPart, InternalBagLength), only the first three can be compiled. Therefore, one has to explicitly count the elements which are inserted into the bag if needed (or use Length on All elements).

• InternalBag[] creates an empty bag of type real. When an Integer is inserted it is converted to Real. True is converted to 1.0 and False to 0.0. Other types of bags are possible too. See below.
• InternalStuffBag[b, elm] adds an element elm to the bag b. It is possible to create a bag of bags inside compile. This way it is easy to create a tensor of arbitrary rank.
• InternalBagPart[b,i] gives the i-th part of the bag b. InternalBagPart[b,All] returns a list of all. The Span operator ;; can be used too. InternalBagPart can have a third argument which is the used Head for the returned expression.
• Variables of InternalBag (or general inside Compile) require a hint to the compile for deducing the type. A bag of integers can be declared as list = InternalBag[Most[{0}]]
• To my knowledge supported number-types contain Integer, Real and Complex.

## Examples

The important property of the following examples is that they are completely compiled. There is no call to the kernel, and using the InternalBag in such a way should most likely speed things up.

The famous sum of Gauss; adding the numbers from 1 to 100. Note that the numbers are not explicitly added. I use the third argument to replace the List head with Plus. The only possible heads inside Compile are Plus and Times and List.

sumToN = Compile[{{n, _Integer, 0}},
Module[{i, list = InternalBag[Most[{0}]]},
For[i = 1, i <= n, ++i,
InternalStuffBag[list, i];
];
InternalBagPart[list, All, Plus]
]
];
sumToN[100]


Creating a rank-2 tensor by creating the inner bag directly inside the constructor of the outer one:

tensor2 = Compile[{{n, _Integer, 0}, {m, _Integer, 0}},
Module[{list = InternalBag[Most[{1}]], i, j},
Table[
InternalStuffBag[
list,
InternalBag[Table[j, {j, m}]]
],
{i, n}];
Table[InternalBagPart[InternalBagPart[list, i], All], {i, n}]
]
]


An equivalent function which inserts every number separately

tensor2 = Compile[{{n, _Integer, 0}, {m, _Integer, 0}},
Module[{
list = InternalBag[Most[{1}]],
elm = InternalBag[Most[{1}]], i, j
},
Table[
elm = InternalBag[Most[{1}]];
Table[InternalStuffBag[elm, j], {j, m}];
InternalStuffBag[list, elm],
{i, n}];
Table[InternalBagPart[InternalBagPart[list, i], All], {i, n}]
]
]


A Position for integer matrices:

position = Compile[{{mat, _Integer, 2}, {elm, _Integer, 0}},
Module[{result = InternalBag[Most[{0}]], i, j},
Table[
If[mat[[i, j]] === elm,
InternalStuffBag[result, InternalBag[{i, j}]]
],
{i, Length[mat]}, {j, Length[First[mat]]}];
Table[
InternalBagPart[pos, {1, 2}],
{pos, InternalBagPart[result, All]}]
], CompilationTarget -> "C", RuntimeOptions -> "Speed"
]


This last example can easily be used to measure some timings against the kernel function:

times = Table[
Block[{data = RandomInteger[{0, 1}, {n, n}]},
Transpose[{
{n, n},
Sqrt[First[AbsoluteTiming[#[data, 1]]] & /@ {position, Position}]
}]
], {n, 100, 1000, 200}];

ListLinePlot[Transpose[times]]


## Open Questions

• Are there simpler/other ways to tell the compiler the type of a local variable? What bothers me here is that this is not really explained in the docs. It is only mentioned shortly how to define (not declare) a tensor. When a user wants to have an empty tensor, it is completely unintuitive that he has to use a trick like Most[{1}]. Declaring variables would be one of the first things I need, when I would be new to Compile. In this tutorial, I didn't find any hint to this.
• Are there further features of Bag which may be important to know in combination with Compile?
• The timing function of position above leaks memory. After the run {n, 100, 3000, 200} there is 20GB of memory occupied. I haven't investigated this issue really deeply, but when I don't return the list of positions, the memory seems OK. Actually, the memory for the returned positions should be collected after the Block finishes. My system here is Ubuntu 10.04 and Mathematica 8.0.4.
-

I am somewhat reluctant to offer this as an answer since it is inherently difficult to comprehensively address questions on undocumented functionality. Nonetheless, the following observations do constitute partial answers to points raised in the question and are likely to be of value to anyone trying to write practical compiled code using Bags. However, caution is always highly advisable when using undocumented functions in a new way, and this is no less true for Bags.

### The type of Bags

1. As far as the Mathematica virtual machine is concerned, Bags are a numeric type, occupying a scalar Integer, Real, or Complex register, and can contain only scalars or other Bags. They can be created empty, using the trick described in the question, or pre-stuffed:

• with a scalar, using InternalBag[val] (where val is a scalar of the desired type)
• with several scalars, using InternalBag[tens, lvl], where tens is a full-rank tensor of the desired numeric type and lvl is a level specification analogous to the second argument of Flatten. For compiled code, lvl $\ge$ ArrayDepth[tens], as Bags cannot directly contain tensors.
2. InternalStuffBag can only be used to insert values of the same type as the register the Bag occupies, a type castable to that type without loss of information (e.g. Integer to Real, or Real to Complex), or another Bag. Tensors can be inserted after being flattened appropriately using the third argument of StuffBag, which behaves in the same way as the second argument of Bag as described above. Attempts to stuff other items (e.g. un-flattened tensors or values of non-castable types) into a Bag will compile into MainEvaluate calls; however, sharing Bags between the Mathematica interpreter and virtual machine has not been fully implemented as of Mathematica 8, so these calls will not work as expected. As this is relatively easy to do by mistake and there will not necessarily be any indication that it has happened, it is important to check that the compiled bytecode is free of such calls.

Example:

cf = Compile[{},
Module[{b = InternalBag[{1, 2, 3}, 1]},
InternalStuffBag[b, {{4, 5, 6}, {7, 8, 9}}, 2];
InternalBagPart[b, All]
]
]


cf[] gives:

{1, 2, 3, 4, 5, 6, 7, 8, 9}


### Nested Bags

These are created simply by stuffing one Bag into another, and do not have any special type associated with them except the types of the registers containing the pieces. In particular, there is no "nested Bag type". Per the casting rules given above, it is theoretically possible to stuff Integer Bags into a Real Bag and later extract them into Integer registers (for example). However, this technique is not to be recommended as the result depends on the virtual machine version; for instance, the following code is compiled into identical bytecode in versions 5.2, 7, and 8, but gives different results:

cf2 = Compile[{},
Module[{
br = InternalBag@Most[{0.}],
parts = Most[{0.}],
bi = InternalBag@Most[{0}]
},
InternalStuffBag[bi, Range[10], 1];
InternalStuffBag[br, bi];
parts = InternalBagPart[br, All];
InternalBagPart[First[parts], All]
]
]


The result from versions 5.2 and 7:

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}


The result from version 8:

{1.}


Stuffing Bags of mixed Real and Integer types into a Real Bag produces even less useful results, since pointer casts are performed by InternalBagPart without regard to the original type of each constituent Bag, resulting in corrupted numerical values. However, nesting bags works correctly in all versions provided that the inner and outer bags are of identical types. It is also possible to stuff a bag into itself to create a circular reference, although the practical value of this is probably quite limited.

### Miscellaneous

1. Calling InternalBagPart with a part specification other than All will crash Mathematica kernels prior to version 8.
2. InternalBag accepts a third argument, which should be a positive machine integer. The purpose of this argument is not clear, but in any case it cannot be used in compiled code.
-
So Internal'Bag is MMA's version of a smart array? It strikes me as odd that List needs to be copied just to append an element (also, how do you create in-line code with a back-tick?) –  VF1 Nov 10 '12 at 1:10
@VF1 I am not exactly sure what a smart array is, but InternalBag is a (singly) linked list. List is in general a hybrid between a linked list and an array, but in the VM it is implemented as just a standard array. In top-level Mathematica you can build linked lists using Lists, and this does not incur any copies, but by appending you run into issues due to the immutability of expressions, so that the copies are necessary. –  Oleksandr R. Nov 10 '12 at 1:18
That's what I meant by a smart array - linked list (or arraylist) –  VF1 Nov 10 '12 at 2:16

About your question regarding the definition of the type of local variables in Compile, Compile has an optional third argument that allows you do this in the same manner you specify arguments. It helps the compiler solve some type ambiguity issues sometimes as by default a local variable is considered a Real number.

This can be the case if a local variable is the result of another external function and the compiler cannot infer properly the type of the result of this external function. For example

f = Compile[{x, y}, {x, y}]
ff = Compile[{x,y}, x]

g =
Compile[x,
Module[{y},
y = h[3., 4.];
y[[1]] = 2+x;
y
]
,
{{h[__], _Real, 1}}
]

h = f;
g[1.] (*works*)

h = ff;
g[1.] (*error*)


Without {{h[__], _Real, 1}} the compilation of g would produce an error.

-
+1 Although I new this, I never got this running with the declaration of local variables. I didn't know that you have to put y={} together with the type specification. How would I use this to define a Bag of integers, or a Bag of Bags of integers? I would have to know the true internal structure of the pattern or not? –  halirutan Jan 28 '12 at 14:37
The y={} is just for this example, you don't need to always initialize your local variable when you declare it if you specify the type. I would be surprised that you could have a type related to bags, the only official ones are Integer, Real, Complex, and True | False. In such Mathematica experiments I don't know anything better then try and fail ... but never fail to try ! –  faysou Jan 28 '12 at 19:20
But the simple example Compile[{}, Module[{y}, y], {{y, _Real, 1}}] fails. Indeed, it seems this type specification at the end is completely ignored and your example only works because of the y={} and because you chose type Real. Try this Compile[{}, Module[{y = {}}, AppendTo[y, 1]], {{y, _Integer, 1}}] and you see, that the type is {Real} although I specified Integer and appended an integer. –  halirutan Jan 28 '12 at 21:02
Faysal, do you know any examples where adding a third argument to Compile has any effect? Would you consider updating your answer? I feel there should probably be a separate Q&A about this, but I was curious if you knew more. –  Jacob Akkerboom Feb 28 at 13:13
I've updated the answer, feel free to add any other example you may find relevant for the use of this third argument in Compile. –  faysou Mar 4 at 10:05