9
$\begingroup$

Union is Compilable but DeleteDuplicates Isn't?!

First, DeleteDuplicates is not compilable in that it does not appear in the list Compile`CompilerFunctions[] and it calls MainEvaluate in Compile. What is strange is that Union is compilable in this sense (appears on the list). Union does what DeleteDuplicates does and more.

The documentation center mentions DeleteDuplicates is "substantially" faster.

  • "DeleteDuplicates is similar to Union without sorting:... Avoiding the sort improves the speed substantially:"

Does anyone know why Union is compilable but the more basic DeleteDuplicates isn't?


Compilable Form of DeleteDuplicates

Secondly and more importantly, calling DeleteDuplicates in Compile with RuntimeAttributes -> {Listable} as well as Parallelization -> True is even more detrimental as an error is often thrown. The following is an example.

comp = Compile[{{list, _Integer, 2}, {c, _Integer}},
  DeleteDuplicates[list],
  RuntimeAttributes -> {Listable}, Parallelization -> True]
(*no error*)

list = {{4, 4}, {5, 5}, {3, 3}, {6, 6}};
c = 4;

comp[list, c]
(*no error*)

comp[list, {c, 1}]
(*throws error*)

The error thrown is below. The stuff inside CompiledFunction looks strange.

error message

Replacing DeleteDuplicates with Union results in no error and everything goes well. However, Union is overkill, as it does extraneous work.

I am looking for a compilable form of DeleteDuplicates that does not call MainEvaluate and is optimized in memory and speed. In particular, it should beat the same code with Union in its place. It should work with the settings RuntimeAttributes -> {Listable} and Parallelization -> True. Any ideas?

(If it matters, the particular context I am looking at is deleting duplicates in a list of pairs of integers greater than or equal to 0 and less than 204, as with list in my example above.)

$\endgroup$
4
  • $\begingroup$ Do the integers you talk about have a pre-specified, not too large range? Are they always greater than 0? $\endgroup$ Sep 12 at 8:51
  • $\begingroup$ @HenrikSchumacher In my specific case, all integers are greater than or equal to 0. I may be able to fidget things so that they are strictly greater than 0. Yes to your other question. They are all smaller than a known, relatively small, specifiable number as well. $\endgroup$ Sep 12 at 14:17
  • $\begingroup$ @MichaelE2 Your other answer is for a compilable form of DeleteCases. I am looking for a compilable form of DeleteDuplicates. $\endgroup$ Sep 14 at 15:52
  • $\begingroup$ Sorry about that. $\endgroup$
    – Michael E2
    Sep 14 at 15:56
7
$\begingroup$

We can build a primitive hash table to determine if an element has been seen.

First we key on the first element of each pair, then over the second element. We use a 2D integer array, where each values is stored with a single bit.

For your example our lookup array has dimensions $205 \times 4$ on a 64 bit machine.

With[{len = $SystemWordLength - 1},
deleteIntegerPairDuplicates = 
  Compile[{{lis, _Integer, 2}, {min, _Integer}, {max, _Integer}},
    Module[{rng, tbl1, present, bag, quos, locs, val, v1, v2, pos1, pos2, bits, loc},
      rng = max - min + 1;
      tbl1 = Table[0, {Quotient[rng, len] + 1}];
      present = Table[tbl1, {max - min + 1}];
      bag = Internal`Bag[Most[{0}]];
      
      (* precompute quotients and mods since 
          BitShiftRight and BitSet are not compilable! *)
      quos = Quotient[Range[rng], len] + 1;
      locs = 2^Subtract[Range[rng], len*Subtract[quos, 1]];

      Do[
        val = Compile`GetElement[lis, i];
        v1 = Compile`GetElement[val, 1];
        v2 = Compile`GetElement[val, 2];
        
        pos1 = v1 + min + 1;
        pos2 = Compile`GetElement[quos, v2 + min + 1];
        
        bits = present[[pos1, pos2]];
        loc = Compile`GetElement[locs, v2 + min + 1];
        
        If[BitAnd[bits, loc] === 0,
          Internal`StuffBag[bag, v1];
          Internal`StuffBag[bag, v2];
          present[[pos1, pos2]] = BitOr[bits, loc];
        ],
        {i, Length[lis]}
      ];
      
      Partition[Internal`BagPart[bag, All], 2]
    ],
    CompilationOptions -> {"ExpressionOptimization" -> True},
    CompilationTarget -> "C", 
    RuntimeOptions -> "Speed"
  ];
]

You can bake this into your other compiled routine through this option:

CompilationOptions -> {
  "InlineCompiledFunctions" -> True,
  "InlineExternalDefinitions" -> True
}

For the range $0$ to $204$, this routines seem on par with DeleteDuplicates and is noticeably faster than Union. Some benchmarks:

SeedRandom[1];
list = RandomChoice[Range[0, 204], {10^6, 2}];

res1 = deleteIntegerPairDuplicates[list, 0, 204]; // RepeatedTiming
{0.0341, Null}
res2 = DeleteDuplicates[list]; // RepeatedTiming
{0.04, Null}
res3 = Union[list]; // RepeatedTiming
{0.2, Null}
 res1 === res2
True
Sort[res1] === res3
True
$\endgroup$
3
  • $\begingroup$ There seems to be a case where your function doesn't work but DeleteDuplicates does. The code comp = Compile[{{n,_Integer},{listOfInts,_Integer,1},{listOfPairs, _Integer,2}},deleteIntegerPairDuplicates[Join[listOfPairs,{{1, 1}}],0,n],Parallelization ->True, CompilationTarget->"C",CompilationOptions->{"InlineCompiledFunctions" ->True}]; gives the error CCompilerDriver`CreateLibrary ... error: use of undeclared identifier 'P1'. However, replacing deleteIntegerPairDuplicates with DeleteDuplicates or simply removing CompilationTarget -> "C" (which I need) produces no error. $\endgroup$ Sep 16 at 21:35
  • $\begingroup$ Ah, see my latest edit. We need another option in CompilationOptions setting. $\endgroup$
    – Chip Hurst
    Sep 16 at 21:41
  • $\begingroup$ I also just changed len = $SystemWordLength to len = $SystemWordLength - 1. If len = $SystemWordLength and the outer Compile call isn't using RuntimeOptions -> "Speed", we get a failure due to machine overflow. $\endgroup$
    – Chip Hurst
    Sep 16 at 22:00
6
$\begingroup$

Not an answer at all, but too long for a comment.

In your very particular use case, SparseArray can delete the duplicates a bit faster:

list = RandomInteger[{1, 10}, {10000000, 2}];
aa = DeleteDuplicates[list]; // AbsoluteTiming // First
bb = SparseArray[list -> 1.]["NonzeroPositions"]; // AbsoluteTiming // First
Sort[aa] == Sort[bb]

0.271432

0.186625

True

$\endgroup$
2
  • $\begingroup$ Clever! I am hoping for a compilable form of DeleteDuplicates, and SparseArray is not compilable. Thank you nonetheless. $\endgroup$ Sep 13 at 2:46
  • $\begingroup$ Yes, I know that it isn't compilable. I just could not hesitate to post this. Abusing SparseArrays is some sort of sport on this site. You're welcome nonetheless. ;) $\endgroup$ Sep 14 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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