That's why I can't declare explicitly ahead, nor a clone of the current helps

You don't have to declare ahead, and only have to shared_clone (references to) "composite" fragments (arrays and hashes) which are being appended at each step. Here 3 workers are happily building (somewhat elaborate example, the best I came up with now) shared AoA, where, for simplicity and brevity, appended parts have rigid structure and depth is tracked, but that won't be necessary in practical implementation. Leading digit is creator worker ID, appended digits are IDs of workers which have seen this fragment, and demonstrably were able to modify it. And of course "locking" happens here because of coordinated sleeping pattern, also for simplicity. I hope I understood your requirements right, and building shared common structures in parallel will, indeed, lead to any speed gain.

use strict;
use warnings;
$| = 1;
use threads;
use threads::shared;
use Data::Dumper; $Data::Dumper::Indent = 0;

my $root = shared_clone [ threads-> tid ];
my $depth: shared = -1;

sub worker {
    my $i = threads-> tid;
    while ( 1 ) {
        my $ary = $root;
        for ( 0 .. $depth ) {
            $ary-> [0] .= $i;
            $ary = $ary-> [1] 
        }
        $ary-> [0] .= $i;
        $ary-> [1] = shared_clone [ $i ];
        $depth ++;
        print '*'; sleep 3;
    }
}

for ( 1 .. 3 ) {
    threads-> create( \&worker )-> detach;
    sleep 1
}

sleep 2;
print "\n", Dumper( $root ), "\n";

__END__

******
$VAR1 = ['0123123',['123123',['23123',['3123',['123',['23',[3]]]]]]];
[download]