3
$\begingroup$

The task

Consider two tables, Tab1,Tab2, that include some real-number data. I need to evaluate the product of some boolean conditions on the value of some function coordx that uses the data (an ith row of Tab1 and a jth row of Tab2), and then sum the resulting values over the rows of Tab1, Tab2.

Let us consider the following example definitions:

Tab1 = Table[{i*Exp[-i^((1/10.))], Sin[i^2.]^2, 1/i^2., (
    1. + 2*i*3*i^2)/i^3, (55. + i^3.1)/i^4}, {i, 1, 10^3}];
Tab2 = Table[{13.*ArcTan[i], 17*Cos[Exp[-i^(1/8.)]], 18. Sin[Sqrt[i]],
     13.*ArcTan[i] + 17*Cos[Exp[-i^(1/8.)]], 13.*ArcTan[i], 
    17*Cos[Exp[-i^(1/8.)]], 18. Sin[Sqrt[i]], 
    13.*ArcTan[i] + 17*Cos[Exp[-i^(1/8.)]], 13.*ArcTan[i], 
    17*Cos[Exp[-i^(1/8.)]], 18. Sin[Sqrt[i]], 
    13.*ArcTan[i] + 17*Cos[Exp[-i^(1/8.)]]}, {i, 1, 10^4, 1}];
coordx[a_, M_, b_] = (
  Abs[a]^M*b + Cos[1.03 b]*Exp[-a])/(a^2 + b^2 + 10^-3)^0.5;

My implementation and its problem

Let us start with one boolean condition to be summed. So far, I have come up with two different implementations: "pretty",

AccPretty = Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 2}, {xmin, _Real}, {xmax, _Real}, {indexE, _Integer}, {indexE1, _Integer}, {M, _Real}},
  Module[{count, coordx1},
   count = 0;
   Do[
    coordx1 = coordx[Tab1[[i]][[indexE]], M, Tab2[[j]][[indexE1]]];
    count += Boole[xmin < coordx1 < xmax], {i, 1, Length[Tab1]}, {j, 
     1, Length[Tab2]}];
   count/(Length[Tab2] Length[Tab1])
   ], CompilationTarget -> "C", RuntimeOptions -> "Speed"]/.DownValues@coordx//ReleaseHold

and "ugly", where I first compile the boolean condition (as a function of the ith row of Tab1 and jth row of Tab2), and then compile the sum:

booleanCondition = 
 Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 2}, {i, _Integer}, {j, _Integer}, {indexE, _Integer}, {indexE1, _Integer}, {M, _Real}, {xmin, _Real}, {xmax, _Real}}, 
     Boole[xmin < 
       coordx[Tab1[[i]][[indexE]], M, Tab2[[j]][[indexE1]]] < xmax], 
     CompilationTarget -> "C", RuntimeOptions -> "Speed"] /. 
   DownValues@coordx // ReleaseHold
AccUgly = 
 Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 
       2}, {indexE, _Integer}, {indexE1, _Integer}, {M, _Real}, \
{xmin, _Real}, {xmax, _Real}}, 
     1/(Length[Tab1]*Length[Tab2])
       Sum[booleanCondition[Tab1, Tab2, i, j, indexE, indexE1, M, 
        xmin, xmax], {i, 1, Length[Tab1]}, {j, 1, Length[Tab2]}], 
     CompilationTarget -> "C", RuntimeOptions -> "Speed"] /. 
   DownValues@booleanCondition // ReleaseHold

The ugly implementation has a disadvantage that it would quickly become unreadable in the case when many boolean conditions on different quantities have to be imposed.

However, the evaluation of AccPretty is longer than AccUgly:

AccPretty[Tab1, Tab2, 0.1, 2, 1, 2, 5] // AbsoluteTiming
AccUgly[Tab1, Tab2, 0.1, 2, 1, 2, 5] // AbsoluteTiming

{2.04872, 0.002}

{1.1129, 0.002}

The difference in timing grows once the complexity of the summation increases. Namely, let us introduce the following acceptances where now two boolean conditions have to be evaluated:

AccPretty = 
 Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 
       2}, {xmin, _Real}, {xmax, _Real}, {indexE, _Integer}, \
{indexE1, _Integer}, {M, _Real}}, 
     Module[{count, coordx1, coordx2}, count = 0;
      Do[
       coordx1 = coordx[Tab1[[i]][[indexE]], M, Tab2[[j]][[indexE1]]];
       coordx2 = 
        coordx[Tab1[[i]][[indexE1]], 0.3*M, Tab2[[j]][[indexE]]];
       count += 
        Boole[xmin < coordx1 < xmax && 
          0.5*xmin < coordx2 < 2*xmax], {i, 1, Length[Tab1]}, {j, 1, 
        Length[Tab2]}];
      count/(Length[Tab2]*Length[Tab1])], CompilationTarget -> "C", 
     RuntimeOptions -> "Speed"] /. DownValues@coordx // ReleaseHold

and

booleanCondition = 
 Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 
       2}, {i, _Integer}, {j, _Integer}, {indexE, _Integer}, \
{indexE1, _Integer}, {M, _Real}, {xmin, _Real}, {xmax, _Real}}, 
     Boole[xmin < 
        coordx[Tab1[[i]][[indexE]], M, Tab2[[j]][[indexE1]]] < xmax &&
        0.5*xmin < 
        coordx[Tab1[[i]][[indexE1]], 0.3*M, Tab2[[j]][[indexE]]] < 
        2*xmax], CompilationTarget -> "C", 
     RuntimeOptions -> "Speed"] /. DownValues@coordx // ReleaseHold
AccUgly = 
 Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 
       2}, {xmin, _Real}, {xmax, _Real}, {indexE, _Integer}, \
{indexE1, _Integer}, {M, _Real}}, 
     1/(Length[Tab1]*Length[Tab2])
       Sum[booleanCondition[Tab1, Tab2, i, j, indexE, indexE1, M, 
        xmin, xmax], {i, 1, Length[Tab1]}, {j, 1, Length[Tab2]}], 
     CompilationTarget -> "C", RuntimeOptions -> "Speed"] /. 
   DownValues@booleanCondition // ReleaseHold

Now, the difference in performance is almost 4x!

AccPretty[Tab1, Tab2, 0.1, 2, 1, 2, 5] // AbsoluteTiming
AccUgly[Tab1, Tab2, 0.1, 2, 1, 2, 5] // AbsoluteTiming

{4.08982, 0.0010118}

{1.14582, 0.0010118}

Probably the reason can be traced to the necessity of defining two coordinates coordx1, coordx2, and not to evaluating two boolean conditions. This means that I define them inefficiently.

The question

I want to keep AccPretty instead of AccUgly given the transparency of the former, but the performance is essential. What may be a general reason for the slower evaluation of AccPretty (assuming it does not depend on the specific example)?

$\endgroup$
3
  • 2
    $\begingroup$ Please provide a complete, working example in your question so that others can try to investigate the issue without having to waste time on guessing valid inputs. $\endgroup$
    – Lukas Lang
    Mar 3, 2023 at 22:56
  • $\begingroup$ @LukasLang : done. $\endgroup$ Mar 3, 2023 at 23:00
  • $\begingroup$ @LukasLang : I have also updated the question body with some investigation on how by adding mode boolean conditions we would increase the difference in the performance of ugly and pretty. $\endgroup$ Mar 3, 2023 at 23:08

1 Answer 1

7
$\begingroup$

The issue seems to be that you use

coordx1 = coordx[Tab1[[i]][[indexE]], M, Tab2[[j]][[indexE1]]];

instead of

coordx1 = coordx[Tab1[[i, indexE]], M, Tab2[[j, indexE1]]];

This causes frequent calls to CopyTensor that slow everthing down. (You can see this when you look at the pseudocode produced by CompiledFunctionTools`CompilePrint[AccPretty].) I was actually very surprised that this happened! And for some reason that I don't understand, this happens here, but not in booleanCondition...

Anyways, the modified version is twice as fast as AccUgly. You can squeeze out quite a lot more by using

coordx1 =  coordx[Compile`GetElement[Tab1, i, indexE], M,  Compile`GetElement[Tab2, j, indexE1]];

instead. This (together with the option RuntimeOptions -> "Speed") deactivates the bound checks during the indexing.

Btw., we can simply parallelize the counting by defining the following function:

AccPretty3 = 
 Hold@Compile[{{Tab1, _Real, 1}, {Tab2, _Real, 
       2}, {xmin, _Real}, {xmax, _Real}, {indexE, _Integer}, {indexE1, _Integer}, {M, _Real}},
     Module[{count, coordx1},
      count = 0;
      Do[
       coordx1 = coordx[Compile`GetElement[Tab1, indexE], M, 
         Compile`GetElement[Tab2, j, indexE1]];
       count += Boole[xmin < coordx1 < xmax]
       , {j, 1, Length[Tab2]}];
      
      count
      ],
     CompilationTarget -> "C",
     RuntimeOptions -> "Speed",
     RuntimeAttributes -> {Listable},
     Parallelization -> True
     
     ] /. DownValues@coordx // ReleaseHold

and then running

Total[AccPretty3[Tab1, Tab2, 0.1, 2, 1, 2, 5]] / N[Length[Tab1] Length[Tab2]]

On my 8 core machine, this is about 75 times faster than the original version of AccPretty.

Edit

You want to count only some i you can introduce i as additional argument:

AccPretty4 = Hold@Compile[{{Tab1, _Real, 2}, {Tab2, _Real, 2},
      {i, _Integer},
      {xmin, _Real}, {xmax, _Real}, {indexE, _Integer}, {indexE1, _Integer}, {M, _Real}}, Module[{count, coordx1}, 
      count = 0;
      Do[
       coordx1 = 
        coordx[Compile`GetElement[Tab1, i, indexE], M, 
         Compile`GetElement[Tab2, j, indexE1]];
       count += Boole[xmin < coordx1 < xmax], {j, 1, Length[Tab2]}];
      count],
     CompilationTarget -> "C",
     RuntimeOptions -> "Speed",
     RuntimeAttributes -> {Listable},
     Parallelization -> True
     ] /. DownValues@coordx // ReleaseHold

Then you can run, for example, this:

AccPretty4[Tab1, Tab2, Range[begin, end], 0.1, 2, 1, 2, 5]
$\endgroup$
3
  • $\begingroup$ Thank you very much! How do you think, is it possible to adapt AccPretty3 to the case when I do not need to sum over all rows of Tab1, but only over some of them (say from i1 to i2)? $\endgroup$ Mar 4, 2023 at 14:18
  • $\begingroup$ Ah I see; there is nothing special in adopting. Thanks again! $\endgroup$ Mar 4, 2023 at 14:24
  • 1
    $\begingroup$ You're welcome. Please see my edit. $\endgroup$ Mar 4, 2023 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.