Why CompilationTarget->"C" doesn't improve computation time

Question

I wrote a simple code to test the computation time under CompilationTarget->"C". I get barely any improvement on the computation time from mathKernel computation time.

The code is as following ..

binarysearch = 
  Compile[{{givenvalue, _Real}, {givenarray, _Integer, 1}},
   Module[{rowmin, rowmax, rowmid, tempvalue, positionofval = 0, 
     valuemin, valuemax},
    rowmin = 1;
    rowmax = Length[givenarray];
    tempvalue = IntegerPart[givenvalue];
    If[rowmax == 1,
     If[tempvalue == givenarray[[1]], positionofval = 1];
     ];
    While[rowmin < rowmax,
     valuemin = givenarray[[rowmin]];
     valuemax = givenarray[[rowmax]];
     If[tempvalue > valuemax || tempvalue < valuemin,
      Break[];
      ];
     If[tempvalue == valuemin,
      positionofval = rowmin;
      Break[];
      ];
     If[tempvalue == valuemax,
      positionofval = rowmax;
      Break[];
      ];
     If[tempvalue > valuemin && tempvalue < valuemax,
      If[rowmax - rowmin <= 1,
       Break[];
       ];
      rowmid = IntegerPart[(rowmin + rowmax)/2];
      If[tempvalue >= givenarray[[rowmid]],
       rowmin = rowmid,
       rowmax = rowmid;
       ];
      ];
     ];
    positionofval
    ], CompilationTarget -> "C"
   ];

The computation time is as follows

In[583]:= Do[binarysearch[2.493699`*^6, array], {100000}] // Timing

Out[583]= {1.09763, Null}

array is

array={256265,260105,261889,341249,492033,579329,779521,1195009,1270529,1346049,1510401,2730497,2863105,5436929,8972034,8972290,9448962,9620226,9959170,9959938,10400002,10400258,10401026,10401538,10402562,10402818,10403074,10404610,10404866,10405122,10405890,10406146,10406402,10406658,10409218,10409474,10411266,10411522,10411778,10412546,10412802,10413058,10413314,10413570,10413826,10416642,10416898,10417154,10417410,10417666,10418690,10418946,10419202,10419458,10419970,10420738,10420994,10421250,10421762,10422018,10422274,10422530,10422786,10423042,10423810,10424066,10424322,10424578,10424834,10425090,10425346,10425602,10426114,10426370,10426626,10427138,10427394,10427650,10427906,10428162,10428418,10428674,10428930,10429186,10429442,10429698,10430210,10430466,10430722,10430978,10431234,10432258,10432514,10433026,10433282,10433538,10433794,10434050,10434306,10434562,10435074,10435842,10436098,10436354,10436610,10436866,10437122,10437378,10437634,10437890,10438146,10438402,10438658,10439426,10439682,10440194,10440706,10440962,10441218,10441986,10442242,10442498,10443010,10443266,10443778,10444034,10444290,10444546,10444802,10445314,10445570,10446338,10447362,10449410,10449666,10449922,10450178,10450434,10450690,10450946,10451202,10451458,10654466,10654722,10654978,10655234,10655490,10655746,10656002,10656258,10656514,10657282,10658050,10658306,10658562,10658818,10659330,10659842,10660098,10660354,10660610,10660866,10661122,10661378,10661634,10661890,10662146,10662402,10663426,10663682,10663938,10664706,10664962,10665218,10665474,10666754,10667010,10667522,10667778,10668034,10670338,10671106,10673154,10673410,10673666,10673922,10674178,10674946,10675202,10675458,10676994,10677250,10677506,10677762,10678018,10678274,10680834,10681090,10681346,10681602,10682626,10682882,10683138,10683394,10684930,10686466,10686978,10687234,10688770,10689026,10689538,10690818,10691074,10691330,10692098,10692354,10694402,10695682,10695938,10696194,10696450,10696706,10698242,10699266,10700034,10700290,10700802,10701570,10702594,10702850,10703362,10703618,10703874,10704642,10704898,10705154,10705410,10705666,10705922,10706178,10708226,10708482,10710018,10710274,10712066,10712322,10713858,10715138,10715394,10716418,10716674,10716930,10717442,10717698,10720514,10720770,10723586,10723842,10725890,10726658,10726914,10727170,10730242,10731010,11316738,11317250,11317506,11319810,11320834,11324930,11325698,11326722,11326978,11333890,11334146,11334402,11334658,11337986,11338242,11342338,11342594,11351554,11351810,11352066,11352322,11355138,11355394,11359490,11359746,11360770,11361026,11363586,11363842,11364866,11365122,11365634,11365890,11366658,11366914,11368450,11368706,11371266,11371522,11374850,11375106,11376898,11379714,11381506,11382786,11383554,11383810,11384066,11384834,11385602,11390210,11390466,11390722,11391234,11394050,11395586,11396098,11396354,11396610,11396866,11397122,11397378,11403266,11403522,11404802,11405826,11406594,11406850,11407106,11407362,11407618,11408642,11412738,11413250,11414018,11414786,11415298,11415554,11415810,11416066,11416834,11417090,12321794,12327426,12337154,12342530,12346626,12352514,12704514,12708098,12708354,12708610,12709890,12710146,12710658,12710914,12712706,12712962,12713218,12713474,12713730,12713986,12715266,12715522,12715778,12716034,12716290,12716546,12716802,12717314,12717826,12718082,12718338,12719106,12719362,12720386,12721410,12721666,12721922,12722178,12722434,12722690,12722946,12723202,12723458,12723714,12723970,12724226,12724482,12724738,12727042,12730626,12730882,12731138,12731394,12731650,12731906,12732674,12732930,12733186,12733442,12733698,12733954,12734978,12735490,12735746,12737026,12737282,12738306,12738562,12738818,12739074,12748034,12748290,12773890,12774146,12784898,12785410,12788482,12789250,12808450,12808706,12835586,12835842,12840706,12840962,12841218,12842754,12846082,12846338,14147074,14150146,18628354,18630658,18630914,18631682,18631938,18634754,18635010,18637058,18637314,18637570,18637826,18640130,18640386,18640898,18641154,18641922,18646274,18647042,18647298,18647810,18648066,18648322,18648578,18649090,18649346,18650114,18650370,18670082,18670338,18670594,18670850,18672642,18672898,18673666,18673922,18674178,18699010,18699266,18701314,18701570,18703362,18703618,26675714,26675970,26711554,26711810,26712066,26712322,26714370,26714626,26714882,26715138,26715394,26715650,26715906,26716162,26716418,26716674,26716930,26717186,26717442,26717698,26717954,26718210,26994178,26994434,26994690,26994946,26995202,26995458,26995714,26995970,26996226,26996482,26996738,26996994,26997250,26997506,26997762,26998018,26998274,26998530,26998786,26999042,27827458,27827714,27827970,27828226,27828482,27828738,27828994,27829250,27829506,27829762,27830018,27830274,27830530,27830786,27831042,27831298,27831554,27831810,27832066,27832322,27832578,27832834,27833090,27833346,27833602,27833858,27834114,27834370,27834626,27879426,27879682,27896834,27897090,27897346,27897602,27897858,27898114,27898370,27898626,27898882,27899138,27899394,29758722,29758978,29759234,29759490,29759746,29760002,29760258,29760514,29760770,29761026,29761282,29761538,29761794,29762050,29762306,29762562,29762818,29763074,29763330,29763586,29763842,29764098,29764354,29764610,29764866,29765122,29765378,29765634,29765890,29766146,29766402,29766658,29766914,29767170,29767426,29767682,29767938,29768194,29768450,29768706,29768962,29769218,30484226,30484482,30485762,30486018,30486274,30486530,30486786,30487042,30487298,30487554,30487810,30488066,30488322,30488578,30488834,30489090,30489346,30489602,30489858,30490114,30490370,30490626,30490882,30491138,30491394,30491650,30491906,30492162,30492418,30492674,30492930,30493186,30493442,30493698,30493954,30494210,30494466,30494722,30494978,30495234,30495490,30495746,38241026,38241282,38241538,38241794,38242050,38242306,38242562,38242818,38243074,38243330,38243586,38243842,38244098,38244354,38244610,38244866,38245122,38245378,38245634,38245890,38246146,38246402,38246658,38246914,38247170,38247426,38247682,38247938,38248194,38248450,38248706,38248962,38249218,38249474,38249730,38249986,38250242,38250498,38250754,38251010,38251266,38251522};

When CompilationTarget -> "C" is omitted, the computation time comes out to be

In[588]:= Do[binarysearch[2.493699`*^6, array], {100000}] // Timing

Out[588]= {1.56063, Null}

The same code, when written in C++, gives 40 times improvement on the computation time (0.028 sec).

givenvalue is not in the array, so that it runs the full loop. In the example, given in mathDocumentation, CompilationTarget -> "C" gives 20 times improvement in the computation time over mathKernel computation time.

Can any one let me know what am I doing wrong here.

Answer 1

Additional to your (maybe a bit too thorough) safety checks, Mathematica injects quite many more bound checks for the calls to Part in order to avoid segfaults.

Since you can provide guarantees for rowmin, rowmax and rowmid, you can skip the safety checks at least for the read operations (you don't have any write operations) by replacing

givenarray[[i]]

with the undocumented

Compile`GetElement[givenarray, i]

and(!) by supplying also the option RuntimeOptions -> "Speed" to Compile. If you want to see what difference this makes (and what code monstrosities Mathematica generates at times) you can look at the C code by using

ExportString[binarysearch, "C"]

The many safety checks (and maybe also the translation of loops into goto statements) make it hard for the compiler to vectorize the loops. (But vectorization would not be useful in case of a binary search, anyways.)

Moreover, the Do construct is typically very, very slow compared to a loop in C/C++. You can avoid it a little by adding the option RuntimeAttributes -> {Listable} and to call it on a packed array of arguments. Adding also Parallelization -> True allows Mathematica to run the loop in parallel (which does not help much here).

To avoid (very unlikely) integer overflows, I would suggest to compute rowmid as follows:

rowmid = rowmin + Quotient[(rowmax - rowin), 2];

This is how this could look like:

binarysearch1 = 
  Compile[{{givenvalue, _Real}, {givenarray, _Integer, 1}}, 
   Module[{rowmin, rowmax, rowmid, tempvalue, positionofval = 0, 
     valuemin, valuemax}, rowmin = 1;
    rowmax = Length[givenarray];
    tempvalue = IntegerPart[givenvalue];
    If[rowmax == 1, 
     If[tempvalue == Compile`GetElement[givenarray, 1], 
       positionofval = 1];];
    While[rowmin < rowmax, 
     valuemin = Compile`GetElement[givenarray, rowmin];
     valuemax = Compile`GetElement[givenarray, rowmax];
     If[tempvalue > valuemax || tempvalue < valuemin, Break[];];
     If[tempvalue == valuemin, positionofval = rowmin;
      Break[];];
     If[tempvalue == valuemax, positionofval = rowmax;
      Break[];];
     If[tempvalue > valuemin && tempvalue < valuemax, 
      If[rowmax - rowmin <= 1, Break[];];
      rowmid = IntegerPart[(rowmin + rowmax)/2];
      If[tempvalue >= Compile`GetElement[givenarray, rowmid], 
       rowmin = rowmid, rowmax = rowmid;];];];
    positionofval],
   CompilationTarget -> "C",
   RuntimeAttributes -> {Listable},
   Parallelization -> True,
   RuntimeOptions -> "Speed"
   ];

Test example:

rand = RandomReal[MinMax@array, 1000000];

pos = Table[binarysearch[r, array], {r, rand}]; // 
  AbsoluteTiming // First
pos1 = Table[binarysearch1[r, array], {r, rand}]; // 
  AbsoluteTiming // First
pos1par = binarysearch1[rand, array]; // AbsoluteTiming // First

pos == pos1
pos == pos1par

Running this on my 10-Core Apple M1 (of which Mathematica effectively uses only the 8 performance cores) and with CompilationTarget -> "WVM" set in the original binarysearch yields the following timings:

1.06696

0.12087

0.058534

True

True

Also remember, there is some overhead for the communication between Mathematica and the compiled library. For example, there is some (not absolutely necessary) heavy copying going on for returning the array of results.

In total I agree that this is a bit disappointing compared to plain C++. That's why I got into the habit of coding performance critical routines directly in C++ and use LibraryLink to communicate with Mathematica.