It turns out that choroba's regex method performs the best for larger data sets and the index method for small sets.

#!/usr/bin/perl
use Benchmark qw ( :hireswallclock cmpthese timethese );
use strict;
use warnings;

# medium data set
our $records = "Key\n" . join ( "\n", 1..200000 );

# small data set
# our $records = 'Key
# 1
# 2
# 3
# 4
# 5';

sub choroba {
    local $records = $records;
    $records =~ s/^    # beginning of the string
              .*   # whatever except newline 
              \n   # newline
             //x;
    #print $records, "\nchoroba\n";
}

sub si_lence {
    local $records = $records;
    $records = substr($records, 4); 
    #print $records, "\nsi_lence\n";
}

sub space_monk {
    local $records = $records;
    my @lines = split /^/, $records;
    shift @lines; # remove first line
    #print @lines;
    #print "\nspace_monk\n";
}

my $results = timethese(
    -5,
    {
        'choroba'        => 'choroba',
        'si_lence'       => 'si_lence',
        'space_monk'     => 'space_monk',
    }
);

cmpthese($results);

__END__

**** Results with small data set

Benchmark: running choroba, si_lence, space_monk for at least 5 CPU se
+conds...
   choroba: 6.08126 wallclock secs ( 6.09 usr +  0.00 sys =  6.09 CPU)
+ @ 958995.90/s (n=5843162)
  si_lence: 6.28688 wallclock secs ( 6.28 usr +  0.00 sys =  6.28 CPU)
+ @ 1221333.07/s (n=7671193)
space_monk: 5.64815 wallclock secs ( 5.64 usr +  0.00 sys =  5.64 CPU)
+ @ 324712.99/s (n=1831706)
                Rate space_monk    choroba   si_lence
space_monk  324713/s         --       -66%       -73%
choroba     958996/s       195%         --       -21%
si_lence   1221333/s       276%        27%         --


**** Results with medium data set

Benchmark: running choroba, si_lence, space_monk for at least 5 CPU se
+conds...
   choroba: 5.05257 wallclock secs ( 2.20 usr +  2.83 sys =  5.03 CPU)
+ @ 1639.44/s (n=8248)
  si_lence: 5.87241 wallclock secs ( 3.84 usr +  2.02 sys =  5.86 CPU)
+ @ 862.29/s (n=5053)
space_monk: 5.16132 wallclock secs ( 5.03 usr +  0.09 sys =  5.12 CPU)
+ @  3.51/s (n=18)
             Rate space_monk   si_lence    choroba
space_monk 3.51/s         --      -100%      -100%
si_lence    862/s     24442%         --       -47%
choroba    1639/s     46560%        90%         --
[download]