-1

Please, consider this generic piece of code:

for j = 0 to (Array.length myArray) - 1 do
    if property.(id) then
        (* do a bunch of stuff*)
done

Here, property is a very large array of boolean. In this experiment, we have 2 cases:

  • in the 1st, property.(id) is always true.

  • In the second, property.(id) can be either true or false.

We want that the 2nd case win, since it skips code execution. But this doesn't happen because of branch conditioning. We have also tried partitioning property instead of a if statement, but the 1st case still wins. (These are all suggestions by OCaml community members).

Our problem definition is: we can detect a property that allows us to skip part of the code. But using a large boolean array to save which element has this property makes the checking for the property itself slower than the saved code execution.

Thus, the question now is more general: what is the better way of implementing this problem?

We really appreciate any suggestion from the community.

jhonatanoliveira
  • 141
  • 1
  • 11
  • You write: "We want that the 2nd case win, since it skips code execution. But this doesn't happen because of branch conditioning. We have also tried partitioning property instead of a if statement, but the 1st case still wins." This can be true only if your "bunch of stuff" in the loop body is something rather fast. Is it indeed the case? You also write: "(These are all suggestions by OCaml community members)." It would help to give a pointer to these "suggestions". – FPstudent Aug 09 '16 at 23:12
  • @FPstudent, thanks for replying. We expect the 2nd case to win, since the *bunch of stuff* involves arithmetic operations. That is, we bet that checking a boolean expression would be faster than doing math operation. If that's not always the case, we are happy to report the negative results. We just want to make sure that the negative results aren't because of a poor implementation. The OCaml community suggestions were given during a conversation in their [IRC channel](https://kiwiirc.com/client/irc.freenode.net/?#ocaml). Unfortunately, I don't have a log of it. – jhonatanoliveira Aug 09 '16 at 23:46

2 Answers2

0

In my opinion, there are two possible solutions for your problem:

  • If you still want to use the for-loop, then I suggest using exception to exit the for-loop

    exception YourExn of something

try
  for j = 0 to (Array.length property) - 1 do
    if property.(id) then
      (* do a bunch of stuff*)
    else raise (YourExn result)
  done
with YourExn res -> (* do something *)

    exception YourExn of something

  • The other solution is to just write a recursive function instead of using for-loop. I suggest using this solution, as using recursive function is kind of a standard in functional programming.

    let rec traverse property id =
  if id > (Array.length property) then
    (* exit *)
  else if property.(id) then
    (* do a bunch of stuff*)
    traverse property (id + 1)
  else
    (* exit *) in

traverse property 0
Trung Ta
  • 1,582
  • 1
  • 16
  • 25
  • Thank you, @Trung Ta. The issue with your solution is the `if` itself: in both cases `if property.(id) then` will fall into that issue I described. – jhonatanoliveira Aug 12 '16 at 02:45
  • You can raise an exception inside the `if ... then` branch. It's a fastest way to exit a computation – Trung Ta Aug 12 '16 at 04:50
0

After reading a similar question here Why is it faster to process a sorted array than an unsorted array?, the best solution for my code is to write a branchless condition, as proposed in section So what can be done? of that answer.

Community
  • 1
  • 1
jhonatanoliveira
  • 141
  • 1
  • 11