Looking for a Compilable Form of DeleteDuplicates

Union is Compilable but DeleteDuplicates Isn't?!

First, DeleteDuplicates is not compilable in that it does not appear in the list CompileCompilerFunctions[] 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.

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.)

• Do the integers you talk about have a pre-specified, not too large range? Are they always greater than 0? Sep 12 at 8:51
• @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. Sep 12 at 14:17
• @MichaelE2 Your other answer is for a compilable form of DeleteCases. I am looking for a compilable form of DeleteDuplicates. Sep 14 at 15:52
• Sorry about that. Sep 14 at 15:56

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 = InternalBag[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 = CompileGetElement[lis, i]; v1 = CompileGetElement[val, 1]; v2 = CompileGetElement[val, 2]; pos1 = v1 + min + 1; pos2 = CompileGetElement[quos, v2 + min + 1]; bits = present[[pos1, pos2]]; loc = CompileGetElement[locs, v2 + min + 1]; If[BitAnd[bits, loc] === 0, InternalStuffBag[bag, v1]; InternalStuffBag[bag, v2]; present[[pos1, pos2]] = BitOr[bits, loc]; ], {i, Length[lis]} ]; Partition[InternalBagPart[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  • 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 CCompilerDriverCreateLibrary ... error: use of undeclared identifier 'P1'. However, replacing deleteIntegerPairDuplicates with DeleteDuplicates or simply removing CompilationTarget -> "C" (which I need) produces no error. Sep 16 at 21:35 • Ah, see my latest edit. We need another option in CompilationOptions setting. Sep 16 at 21:41 • 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. Sep 16 at 22:00

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

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