Errors in Compile

Question

I defined a function

getCell[sp_, i_, j_, x_] := Block[{target, n, m, k, l, k2, l2, cells},
  n = Dimensions[sp][[1]];
  m = Dimensions[sp][[2]];
  cells = {};
  Do[
   Do[
    (* This is one neighbor *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
     AppendTo[cells, {k2, l2}]],
    {l, -1, 1}],
   {k, -1, 1}];
  If[Dimensions[cells][[1]] != 0,
   target = RandomSample[cells, 1][[1]],
   (* The default, if none was found, is to return the cell itself, 
   just for convenience *)
   target = {i, j}
   ];
  Return[target];
  ]

getCell given a square matrix sp filled with Integers attempts to find a cell neighboring [[i,j]] that contains a value equal to x. If it finds such a cell, it returns the coordinates of that cell; if not, it returns the input coordinates {i,j}.

I now wanted to compile getCell to try to speed it up, but when I do so by putting Compile around the function and inserting type definitions, I get several error messages:

Compile::cset: Variable cells of type {_Integer,1} encountered in assignment of type {_Integer,2}. >>

Compile::cpts: The result after evaluating Insert[cells,{k2,l2},-1] should be a tensor. Nontensor lists are not supported at present; evaluation will proceed with the uncompiled function. >>

Compile::cset: Variable target of type {_Integer,2} encountered in assignment of type {_Integer,0}. >>

Compile::cset: Variable target of type {_Integer,2} encountered in assignment of type {_Integer,1}. >>

Does anyone know what I might be doing wrong, and how I could get this simple function compiled?

Answer 1

Note: instead of picking random element I just pick the first it runs into, random version at the end

getCell = 
 Compile[{{sp, _Integer, 2}, {i, _Integer}, {j, _Integer}, {x, _Integer}}, 
  Block[{ n, m, k2, l2, cell},

   {n, m} = Dimensions[sp];
   cell = {i, j};
   Do[(*This is the neighborhood *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, cell = {k2, l2}; 
     Break[]]
    , {l, -1, 1}, {k, -1, 1}];
   cell
   ]]

When you get that type of errors about tensor sizes not matching think about what shapes your data has and if Mathematica knows about it. If it's not an argument that you need to specify shape of you can do that by putting the specification as the last Compile argument, see the docs for details.

Often the easiest is to explicitly assign the variable a value(see below)

What I changed:

• Explicitly added {sp,_Integer,2} so Mathematica knows what it is. This is the one that matters.
• Merged the Do loops into one
• Removed k and l from Block variables since Do localizes them automatically
• Assigned {m,n} simultaneously
• There is no need to explicitly state Return what the last function returned gets returned (unless it is suppressed with a ; in which case it gives Null

An example, finding neighboring 0:

m = 5;
r = RandomInteger[{0, 1}, {m, m}];
pos = RandomInteger[{1, m}, 2];
cell = getCell[r, pos[[1]], pos[[2]], 0];

s = Grid[r, 
  ItemStyle -> {Automatic, Automatic, {pos -> Red, cell -> Blue}}]

To actually get a random one you can make sure that cells is treated correctly by initializing as a nx2 value:

getCell = 
 Compile[{{sp, _Integer, 2}, {i, _Integer}, {j, _Integer}, {x, _Integer}}, 
  Block[{n, m, k2, l2, cells},

   {n, m} = Dimensions[sp];

   cells = {{i, j}};

   Do[(*This is the neighborhood *)
    k2 = Mod[i + k, n, 1];
    l2 = Mod[j + l, m, 1];
    If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
     AppendTo[cells, {k2, l2}]]
    , {l, -1, 1}, {k, -1, 1}];

   If[Length[cells] == 1, {i, j}, RandomChoice[Rest[cells]]]
   ]] 

Here I do that by just starting with {i,j} in it and appending the positions it finds, at the end I pick randomly out of everything but the first value.

Since you are compiling it in the first place I guess you will be running the function a lot and want speed, there are some easy ways to get a nice speedup, the first is compiling to C and the second is to make the function listable.

Say for a given matrix you want to find the nearest 0 neighbor for a list of positions.

getCellListableC = 
  Compile[{{sp, _Integer, 2}, {pos, _Integer, 1}, {x, _Integer}}, 
   Block[{n, m, k2, l2, cells, i, j},

    {n, m} = Dimensions[sp];
    {i, j} = pos;
    cells = {{i, j}};

    Do[(*This is the neighborhood *)
     k2 = Mod[i + k, n, 1];
     l2 = Mod[j + l, m, 1];
     If[(k2 != i || l2 != j) && sp[[k2, l2]] == x, 
      AppendTo[cells, {k2, l2}]]
     , {l, -1, 1}, {k, -1, 1}];

    If[Length[cells] == 1, {i, j}, RandomChoice[Rest[cells]]]
    ],
   CompilationTarget -> "C",
   RuntimeOptions -> "Speed",
   RuntimeAttributes -> Listable];

m = 5000;
n = 1000;
r = RandomInteger[{0, 2}, {m, m}];
pos = RandomInteger[{1, m}, {n, 2}];

(* Functions i compare to are as the ones above with different Compile options *)
(* Compiled, but not CompilationTarget->"C" *)
AbsoluteTiming[getCell[r, #[[1]], #[[2]], 0] & /@ r;]
(* {0.085699, Null} *)

AbsoluteTiming[getCellC[r, #[[1]], #[[2]], 0] & /@ r;]
(* {0.077503, Null} *)

(* Take advantage of Listability *)
AbsoluteTiming[getCellListable[r, pos, 0];]
(* {0.008890, Null} *)

AbsoluteTiming[getCellListableC[r, pos, 0];]
(* {0.004517, Null} *)

Note especially how Listable improves speed.

Another thing is to always look at after compiling is:

<< CompiledFunctionTools`
CompilePrint[getCellListableC]

If you see MainEvaluate that means that part isn't compiled, and figure out how to avoid that. Another thing is CopyTensor wherever that occurs a list is copied, you will see that in this code due to the Append (among others).