comment on

As you might expect, I've created improved versions of my original Perl and C++ solutions posted in the root node. Since I'm all out of fresh ideas to try, I'll post my improved solutions here. Further performance improvement suggestions are welcome.

Improved Perl Version llil2.pl

# llil2.pl
# Example run: perl llil2.pl tt1.txt tt2.txt tt3.txt >out.txt

use strict;
use warnings;

# --------------------------------------------------------------------
+--
# LLiL specification
# ------------------
# A LLiL-format file is a text file.
# Each line consists of a lowercase name a TAB character and a non-neg
+ative integer count.
# That is, each line must match : ^[a-z]+\t\d+$
# For example, reading the LLiL-format files, tt1.txt containing:
#   camel\t42
#   pearl\t94
#   dromedary\t69
# and tt2.txt containing:
#   camel\t8
#   hello\t12345
#   dromedary\t1
# returns this hashref:
#   $hash_ret{"camel"}     = 50
#   $hash_ret{"dromedary"} = 70
#   $hash_ret{"hello"}     = 12345
#   $hash_ret{"pearl"}     = 94
# That is, values are added for items with the same key.
#
# To get the required LLiL text, you must sort the returned hashref
# descending by value and insert a TAB separator:
#   hello\t12345
#   pearl\t94
#   dromedary\t70
#   camel\t50
# To make testing via diff easier, we further sort ascending by name
# for lines with the same value.
# --------------------------------------------------------------------
+--

# Function get_properties
# Read a list of LLiL-format files
# Return a reference to a hash of properties
sub get_properties
{
   my $files = shift;    # in:  reference to a list of LLiL-format fil
+es
   my %hash_ret;         # out: reference to a hash of properties
   for my $fname ( @{$files} ) {
      open( my $fh, '<', $fname ) or die "error: open '$fname': $!";
      while (<$fh>) {
         chomp;
         my ($word, $count) = split /\t/;
         $hash_ret{$word} += $count;
      }
      close($fh) or die "error: close '$fname': $!";
   }
   return \%hash_ret;
}

# ----------------- mainline -----------------------------------------
+--

@ARGV or die "usage: $0 file...\n";
my @llil_files = @ARGV;

warn "llil2 start\n";
my $tstart1 = time;
my $href    = get_properties( \@llil_files );
my $tend1   = time;
my $taken1  = $tend1 - $tstart1;
warn "get_properties : $taken1 secs\n";

my $tstart2 = time;
# Using two sorts is waaay faster than one in Perl for some reason! (s
+ee [id://11148545])
for my $key ( sort { $href->{$b} <=> $href->{$a} } sort keys %{$href} 
+) {
   print "$key\t$href->{$key}\n";
}
my $tend2  = time;
my $taken2 = $tend2 - $tstart2;
my $taken  = $tend2 - $tstart1;

warn "sort + output  : $taken2 secs\n";
warn "total          : $taken secs\n";
[download]

Improved C++ Version llil2.cpp

// llil2.cpp. C++ 11 version of Perl llil.pl.
// llil2.cpp is faster than llil.cpp while also clarifying limits:
//   - all keys should be less than 200 or so characters in length
//   - numbers are 64 bit integers (max: 9,223,372,036,854,775,807)
// g++ compile on Linux:
//    g++ -o llil2 -std=c++11 -Wall -O3 llil2.cpp
// This g++ command also works with mingw C++ compiler (https://source
+forge.net/projects/mingw-w64)
// that comes bundled with Strawberry Perl (C:\Strawberry\c\bin\g++.ex
+e).
// Example run: llil2 tt1.txt tt2.txt tt3.txt >out.txt

#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cstdio>

#include <string>
#include <vector>
#include <set>
#include <map>

#include <algorithm>
#include <utility>

#include <iostream>
#include <fstream>
#include <sstream>

static_assert(sizeof(size_t) == sizeof(int64_t), "size_t too small, ne
+ed a 64-bit compile");

// -------------------------------------------------------------------
+---------

// Crude hack to see Windows Private Bytes in Task Manager by sleeping
+ at
// program end (see also sleep hack at end of main)
//    #include <chrono>
//    #include <thread>

// For some performance hacks to speed up C++ I/O see:
//   https://www.reddit.com/r/rust/comments/9xedap/how_to_achieve_fast
+_stdinstdout_io_suitable_for/
// The only one we use here is to prefer "\n" to std::endl to reduce s
+tdout flushing

// -------------------------------------------------------------------
+---------

typedef long long llil_int_type;
using str_int_type     = std::pair<std::string, llil_int_type>;
using map_str_int_type = std::map<std::string, llil_int_type>;
using vec_str_int_type = std::vector<str_int_type>;

// Mimic the Perl get_properties subroutine --------------------------
+--

// Limit line length and use lower level ANSI C functions to try to bo
+ost I/O performance
// TODO (maybe):
//   - reading: Try ::setvbuf(fh, NULL, _IOFBF, 65536) or some such on
+ input files
//   - writing: Try ::setvbuf(stdout, stdout_buf, _IOFBF, sizeof(stdou
+t_buf)) on stdout
//              ... or instead of writing to stdout, take an output fi
+le as a program argument
#define MAX_LINE_LEN_L 255

static void get_properties(
   int                nfiles,      //  in: the number of input files
   char*              fname[],     //  in: the input file names
   map_str_int_type&  hash_ret)    // out: a hash of properties
{
   FILE* fh;
   char line[MAX_LINE_LEN_L+1];
   char* word; char* count;
   for (int i = 0; i < nfiles; ++i) {
      fh = ::fopen(fname[i], "r");
      if (fh == NULL) {
         std::cerr << "Error opening '" << fname[i] << "'\n";
         return;
      }
      while ( ::fgets(line, MAX_LINE_LEN_L, fh) != NULL ) {
         word  = ::strtok(line, "\t");
         count = ::strtok(NULL, "\n");
         hash_ret[word] += ::atoll(count);
      }
      ::fclose(fh);
   }
}

// -------------------------------------------------------------------
+--

int main(int argc, char* argv[])
{
   if (argc < 2) {
      std::cerr << "usage: llil2 file1 file2 ... >out.txt\n";
      return 1;
   }

   std::cerr << "llil2 start\n";
   time_t tstart1 = ::time(NULL);

   // Create the hash of properties
   map_str_int_type hash_ret;
   get_properties(argc - 1, &argv[1], hash_ret);
   time_t tend1 = ::time(NULL);
   long taken1  = static_cast<long>(::difftime(tend1, tstart1) + 0.5);
   std::cerr << "get_properties : " << taken1 << " secs\n";

   // Sort descending by value, i.e. mimic this Perl code in C++:
   //   sort { $href->{$b} <=> $href->{$a} || $a cmp $b } keys %{$href
+}
   time_t tstart2 = ::time(NULL);
   vec_str_int_type v( hash_ret.begin(), hash_ret.end() );
   std::sort( v.begin(), v.end(),
      [](const str_int_type& left, const str_int_type& right) { return
+ right.second != left.second ? right.second < left.second : left.firs
+t < right.first; }
   );

   // Output the merged properties
   for ( auto const& n : v ) { std::cout << n.first << '\t' << n.secon
+d << '\n'; }

   time_t tend2 = ::time(NULL);
   long taken2  = static_cast<long>(::difftime(tend2, tstart2) + 0.5);
   long taken   = static_cast<long>(::difftime(tend2, tstart1) + 0.5);
   std::cerr << "sort + output  : " << taken2 << " secs\n";
   std::cerr << "total          : " << taken << " secs\n";

   // Hack to see Private Bytes in Windows Task Manager (uncomment nex
+t line so process doesn't exit too quickly)
   //   std::this_thread::sleep_for(std::chrono::milliseconds(90000000
+));

   return 0;
}
[download]

Performance Analysis

Performance of my second Perl version improved from:

get_properties : 11 secs
sort + output  : 74 secs
total          : 85 secs
[download]

to:

get_properties : 11 secs
sort + output  : 25 secs
total          : 36 secs
[download]

update (much later in llil2grt.pl) to:

get_properties : 10 secs
sort + output  : 20 secs
total          : 30 secs
[download]

Performance of my second C++ version improved from:

get_properties : 9 secs
sort + output  : 7 secs
total          : 16 secs
[download]

to:

get_properties : 6 secs
sort + output  : 6 secs
total          : 12 secs
[download]

Memory use (Windows Private Bytes) was 2,896,104K for the Perl version (update: 2,657,968K), 1,176,048K for the C++ std::unordered_map version (update: 1,218,720K for std::map).

Update: Surprisingly, making a one line change in llil2.cpp above from:

using map_str_int_type = std::unordered_map<std::string, llil_int_type
+>;
// to (llil2a.cpp):
using map_str_int_type = std::map<std::string, llil_int_type>;
[download]

resulted in a significant speed improvement in llil2a (with similar Windows Private Bytes):

get_properties : 4 secs
sort + output  : 5 secs
total          : 9 secs
[download]

My second Perl version improved from 85 seconds to 36 seconds (update: much later to 30 seconds in llil2grt). Incredibly, this spectacular performance improvement is entirely due to a very surprising one line change from:

sort { $href->{$b} <=> $href->{$a} || $a cmp $b } keys %{$href}
[download]

to:

sort { $href->{$b} <=> $href->{$a} } sort keys %{$href} )
[download]

When more is known of the reason for this incredible difference, I'll update this node.

In contrast, I had to work a lot harder to improve the performance of my C++ version, switching in desperation to some ugly lower level ANSI C functions in its get_properties function. For cheap thrills, I also switched from a 32-bit to a 64-bit integer counter llil_int_type. I suspect future minor performance tweaks may come from further improving I/O (e.g. by fiddling with file buffering and buffer sizes).

As described here this is by far Perl's best performance so far in my three serious Rosetta nodes:

For the simple GoL algorithm, C++ was 12.5 times faster, memory use was 2.8 times less.
For the complex GoL algorithm, C++ was 212.5 times faster; memory use was 10.1 times less.
For the Long List is Long algorithm (this node), C++ was 3 times faster; memory use 2.2 times less.

I suspect this is because Long List is Long seems to be mostly I/O bound, while the GoL algorithms were mostly CPU bound.

Updated: Changed std::unordered_map to std::map in llil2.cpp above.

In reply to Re: Rosetta Code: Long List is Long (Updated Solutions) by eyepopslikeamosquito
in thread Rosetta Code: Long List is Long by eyepopslikeamosquito

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


"be consistent"
	PerlMonks