#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw(shuffle sum max);
use Time::HiRes qw(gettimeofday tv_interval);
use FindBin;
use lib "$FindBin::Bin/../lib";
#use lib "$FindBin::Bin/../t/lib";
#use BitStreamTest;
use Data::BitStream;
# Time with small, big, and mixed numbers.
sub ceillog2 {
my $v = shift;
$v--;
my $b = 1;
$b++ while ($v >>= 1);
$b;
}
my $add_golomb = 0;
my @encodings;
@encodings = qw|
Gamma
Delta
Omega
EvenRodeh
Levenstein
Fibonacci
FibGen(12)
Unary
Unary1
Baer(0)
Baer(-2)
Baer(2)
BoldiVigna(4)
Golomb(3)
Rice(2)
ARice(2)
Golomb(177)
GammaGolomb(3)
ExpGolomb(3)
StartStop(0-0-2-4-14)
StartStepStop(3-2-20)
GoldbachG1
GoldbachG2
BlockTaboo(00)
BlockTaboo(111)
Comma(2)
BinWord(20)
|;
@encodings = qw|Unary Gamma Delta Omega Fibonacci|;
my $list_n = 2048;
my @list_small;
my @list_medium;
my @list_large;
{
push @list_small, 0 for (1 .. $list_n);
push @list_small, 1 for (1 .. ($list_n /2));
push @list_small, 2 for (1 .. ($list_n /4));
push @list_small, 3 for (1 .. ($list_n /8));
push @list_small, 4 for (1 .. ($list_n /16));
push @list_small, 4 for (1 .. ($list_n /32));
push @list_small, 5 for (1 .. ($list_n /64));
foreach my $n (6 .. 32) {
push @list_small, $n for (1 .. ($list_n /128));
}
}
print "Lists hold ", scalar @list_small, " numbers\n";
srand(15);
{
foreach my $i (1 .. scalar @list_small) {
# skew to smaller numbers
my $d = rand(1);
if ($d < 0.25) { push @list_medium, int(rand(32)); }
elsif ($d < 0.50) { push @list_medium, int(rand(256)); }
elsif ($d < 0.75) { push @list_medium, int(rand(1024)); }
else { push @list_medium, int(rand(2048)); }
}
foreach my $i (1 .. scalar @list_small) {
#push @list_large, 500+int(rand(65000));
# skew to smaller numbers
my $d = rand(1);
if ($d < 0.25) { push @list_large, int(rand(32)); }
elsif ($d < 0.50) { push @list_large, int(rand(256)); }
elsif ($d < 0.75) { push @list_large, int(rand(16000)); }
elsif ($d < 0.98) { push @list_large, int(rand(65000)); }
else { push @list_large, int(rand(1_000_000)); }
}
}
@list_small = shuffle(@list_small);
@list_medium = shuffle(@list_medium);
@list_large = shuffle(@list_large);
# average value
my $avg_small = int((sum @list_small) / scalar @list_small);
my $avg_medium = int((sum @list_medium) / scalar @list_medium);
my $avg_large = int((sum @list_large) / scalar @list_large);
# bytes required in fixed size (FOR encoding)
my $bytes_small = int(ceillog2(max @list_small) * scalar @list_small / 8);
my $bytes_medium = int(ceillog2(max @list_medium) * scalar @list_medium / 8);
my $bytes_large = int(ceillog2(max @list_large) * scalar @list_large / 8);
if ($add_golomb) {
push @encodings, 'golomb(' . int(0.69 * $avg_medium) . ')';
push @encodings, 'golomb(' . int(0.69 * $avg_large) . ')';
}
my $tot_encode_time = 0;
my $tot_decode_time = 0;
print "Small (avg $avg_small, $bytes_small binary):\n";
time_list($_, @list_small) for (@encodings);
print "Medium (avg $avg_medium, $bytes_medium binary):\n";
time_list($_, @list_medium) for (@encodings);
print "Large (avg $avg_large, $bytes_large binary):\n";
time_list($_, @list_large) for (@encodings);
#print "total encode: $tot_encode_time\n";
#print "total decode: $tot_decode_time\n";
sub time_list {
my $encoding = shift;
die "'$encoding' is unsupported"
unless Data::BitStream::code_is_supported($encoding);
my @list = @_;
my $s1 = [gettimeofday];
#my $stream = stream_encode_array('wordvec', $encoding, @list);
#die "Stream ($encoding) construction failure" unless defined $stream;
my $stream = Data::BitStream->new;
die "Stream construction failure" unless defined $stream;
$stream->code_put($encoding, @list);
#foreach my $v (@list) { $stream->code_put($encoding, $v); }
my $e1 = int(tv_interval($s1)*1_000_000);
my $len = $stream->len;
my $s2 = [gettimeofday];
#my @a = stream_decode_array($encoding, $stream);
$stream->rewind_for_read;
my @a = $stream->code_get($encoding, -1);
#my @a=(); while (defined (my $v = $stream->code_get($encoding))) {push @a,$v;}
my $e2 = int(tv_interval($s2)*1_000_000);
foreach my $i (0 .. $#list) {
die "incorrect $encoding coding for $i" if $a[$i] != $list[$i];
}
# convert total uS time into ns/value
$e1 = int(1000 * ($e1 / scalar @list));
$e2 = int(1000 * ($e2 / scalar @list));
printf " %-21s: %8d bytes %8d ns encode %8d ns decode\n",
$encoding, int(($len+7)/8), $e1, $e2;
$tot_encode_time += $e1;
$tot_decode_time += $e2;
1;
}