Starting threads in Perl is rather expensive. It's far faster to reuse threads (e.g. using a worker model). You've indicated otherwise, but that simply points to a problem with the implementation you used.

use strict;
use warnings;
use feature qw( say );

use threads;

use Thread::Queue     qw( );
use Thread::Semaphore qw( );
use Time::HiRes       qw( time );

use constant MAX_WORKERS => 32;
use constant NUM_JOBS    => 1_000;

{
   my $sem = Thread::Semaphore->new(MAX_WORKERS);

   my $s = time;
   for my $job (1..NUM_JOBS) {
      $sem->down();
      $_->join() for threads->list(threads::joinable);
      async {
         # ...
         $sem->up();
      };
   }

   $_->join() for threads->list();
   my $e = time;
   say($e-$s);  # 5.88567113876343
}

{
   my $q = Thread::Queue->new();

   for (1..MAX_WORKERS) {
      async {
         while (defined( my $job = $q->dequeue() )) {
            # ...
         }
      };
   }

   my $s = time;
   $q->enqueue($_) for 1..NUM_JOBS;
   $q->end();
   $_->join() for threads->list();
   my $e = time;
   say($e-$s);  # 0.248196125030518
}
[download]

Things couldn't be any more ideal for creating threads (minimal amount of variables to clone), yet creating all those threads was 25x slower than reusing a few threads. (The factor will grow as the number of jobs increases.)