Threading seems to be the right idea here. It appears you have one input list, and some subset of them get pushed into the second array, and then some subset of those get pushed back into the first array, as well as some subsets of each being pushed back into its own array.

What this looks like to me is a queue. Put the list into the first queue, which is addressed by the first thread, and it can manage the entries, including possibly pushing into one of the two queues. And the second thread waits on the second queue, and pulls stuff off as it goes, enqueuing anything required. Thread::Queue should take care of most of this for you, as long as you don't have any other overlap in your variables.

You may get a bit simpler (there's nothing here that looks to gain from this option, but you've also omitted most of the code, so I can't be sure) by using Coro and Coro::Channel in similar ways, but this only really benefits you if your two threads are doing any significant amount of waiting on external events, such as downloading via HTTP. If you're already fully CPU bound but have more than one CPU available, threads are more likely to be more helpful. For those who are afraid of threads, Coro with AnyEvent::Fork::RPC may work - you'd essentially fork off the two worker threads and push data in and out of there, allowing both child processes to use a full CPU each.

Either one of these options, threads or Coro, may also further benefit from multiple worker threads - depending on how CPU-intensive everything is.

The best/simplest option, though, might be to simply try to stick to a single array, and figure out as you pull each item off the list what needs to be done with the object - your "third" idea. Having only a single queue just makes things conceptually easier. The problem here is if you need to set queue priorities - you'll need a priority queue instead of a straight list - so that you can deal with higher-priority items sooner. I'm not sure you do, but the concern you have about neglecting array2 indicates a possibility here that array2 is somehow higher priority. If array2 is strictly higher priority, then deal with it that way:

while(@array) {
  while (@array2) {
    my $item = shift @array2;
    my $result = do_stuff2($item);
    if ($result == 1) {
      push @array, $item
    } elsif ($result == 2) {
      push @array2, $item
    } # else done with item, discard.
  }
  my $item = shift @array;
  my $result = do_stuff($item);
  if ($result == 1) {
    push @array, $item
  } elsif ($result == 2) {
    push @array2, $item
  } # else done with item, discard.
}
[download]