Message Boards Message Boards

GROUPS:

Using DataStructures in FunctionCompile?

Posted 1 month ago
336 Views
|
1 Reply
|
2 Total Likes
|

This is a cross post from StackExchange.

I am trying to do the equivalent of Select on a "FixedArray" data structure.

Here is what I have tried so far:

fixedArrayDS = CreateDataStructure["FixedArray", 2^10];
vanillaArray = RandomReal[{0, 1}, fixedArrayDS["Length"]];
Do[fixedArrayDS["SetPart", i, vanillaArray[[i]]], {i, Length[vanillaArray]}]

I'd like to do the equivalent of this for a "FixedArray":

Select[vanillaArray, # < 0.5 &]

without extracting all the elements (i.e, this: Select[fixedArrayDS["Elements"], # < 0.5 &] is considered "cheating")

Let's try to compile a function to do this (I am trying to teach myself how to use FunctionCompile with data structures). Sow and Reap seems a plausible way to do this.

select = FunctionCompile[
  Function[
   {Typed[fa, "FixedArray"], Typed[bound, "Real64"]},
   Last[
    Reap[
     Do[
      If[fa["Part", i] < bound, Sow[fa["Part", i]]],
      {i, 1, fa["Length"]}
      ]
     ]
    ]
   ]
  ]

doesn't work and comes back with a TypeError stating that a version of Reap can't be found that takes one argument. I'll come back to why Reap isn't going to work later and a hypothesis about using KernelFunction later.

Setting up some sanity checks. Test and see if this is the correct syntax for FunctionCompile on this data structure.

first = FunctionCompile[
  Function[
   {Typed[fa, "FixedArray"], Typed[multiplier, "Real64"]},
   fa["Part", 1] multiplier
   ]
  ]

this works

first[fixedArrayDS, 1]

so the FunctionCompile syntax seems to be correct.

Another sanity check. See if Compile works with Reap and Sow:

cf = Compile[{{l, _Real, 1}, {b, _Real}},
  Last[Reap[
    Do[
     If[l[[i]] < b, Sow[l[[i]]]],
     {i, 1, Length[l]}
     ]
    ]
   ]
  ]

which works, but is slower than the built-in Select (probably because it is a single thread?):

RepeatedTiming[cf[vanillaArray, .5]]

Back to the original problem. Getting clues from Tom Wickham Jones' talk in 2020. Reap is not going to work because it isn't in the following list:

Needs["Compile`Utilities`Support`"]
Compile`Utilities`SupportedSymbols[]

Perhaps using KernelFunction in the FunctionCompile would work--but how would I use Type for Reap?

Another solution might be to use another data structure that has a rapid Append:

select = FunctionCompile[
  Function[
   {Typed[fa, "FixedArray"], Typed[bound, "Real64"]},
   Block[{collection = CreateDataStructure["DynamicArray"]},
    Do[
     If[fa["Part", i] < bound, collection["Append", fa["Part", i]]],
     {i, 1, fa["Length"]}
     ];
    collection
    ]
   ]
  ]

But, this doesn't compile either.

Finally, there is a hint that there is a solution for this task that might be in development. See around minute 51:30 in the TWJ talk linked above; it appears there is a package for using Iterators that would be a natural implementation for select.

Needs["IteratorTools`"]

But it looks like it didn't ship with 12.3.

There is an instructive answer that gives a working syntax and demonstrates the speed-up of using FunctionCompile with a DataStructure here; stack exchange answer by Ilian.

My take-away is that one can get much faster code, but with a moderate learning curve for implementation. I think it’s likely that tutorials are coming soon.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract