Loading ...
Sorry, an error occurred while loading the content.

Re: [hackers-il] Re: Reply to Chen regarding Porting the Black Hole Solver to C

Expand Messages
  • Shlomi Fish
    Hi all, ... Now that I ve converted the program to C here is a Perl 5-vs.-C benchmark: {{{ shlomif[black-hole]:$trunk/black-hole-solitaire$ sudo_renice time
    Message 1 of 4 , Sep 16, 2010
    • 0 Attachment
      Hi all,

      On Saturday 28 August 2010 22:21:10 Shlomi Fish wrote:
      > Resending because YahooGroups rejected my message (silently).
      >
      > On Thursday 26 August 2010 21:40:37 Gwen Shapira wrote:
      > > > So here is my reply: my code is not slow as Perl code goes, but it
      > > > still often takes many seconds to solve a given deal of Black Hole
      > > > Solitaire. As I'd like to run the solver on a range of deals in order
      > > > to collect some statistics, I expect the Perl code to be too slow for
      > > > that. The code is algorithmic and I'd expect that executing the
      > > > bytecode by the Perl 5 backend to incur a large amount of overhead.
      > >
      > > So your code is CPU bound and you are counting on the C optimizer to
      > > reduce the CPU usage?
      >
      > I believe that is the case. I have very little I/O there - mostly just
      > parsing the input, and outputting the solution to the STDOUT.
      >
      > > The reason I'm drilling down into the details is that I've been
      > > interested in the question of "In what conditions can a program be
      > > made faster by switching to a different language?" and you seem to
      > > have a perfect test case :)
      >
      > Heh, yes.
      >
      > > In my world code is usually made faster by making it do less physical
      > > IO or less logical IO (aka use less memory) or by resolving
      > > concurrency issues. All those problems are rarely solved by switching
      > > to a different language - although some folks seem to solve
      > > concurrency problems by using Erlang.
      >
      > Memory (RAM/Swap/etc.) access may be a huge factor in the run-time of the
      > program, but it is also something that C is much better at.
      >
      > > I'm curious how it works in other areas that I'm less familiar with.
      > > Could you post benchmarks?
      >

      Now that I've converted the program to C here is a Perl 5-vs.-C benchmark:

      {{{
      shlomif[black-hole]:$trunk/black-hole-solitaire$ sudo_renice time bash
      benchmark-perl.bash
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      127.13user 1.44system 2:07.96elapsed 100%CPU (0avgtext+0avgdata
      3785616maxresident)k

      0inputs+216outputs (0major+519908minor)pagefaults 0swaps
      shlomif[black-hole]:$trunk/black-hole-solitaire$ sudo_renice time bash
      benchmark-c.bash
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      4.98user 0.31system 0:05.30elapsed 99%CPU (0avgtext+0avgdata
      454512maxresident)k
      0inputs+320outputs (0major+113825minor)pagefaults 0swaps
      shlomif[black-hole]:$trunk/black-hole-solitaire$
      }}}

      So, the C solver runs at 5.3 seconds while the Perl solver takes 2:07.96
      minutes (~24 times slower).

      Just for the record, here are the benchmarking scripts I've used:

      [benchmark-perl.bash]
      #!/bin/bash
      export PATH="$HOME/apps/perl/modules/local/bin:$PATH"
      export PERL5LIB="$HOME/apps/perl/modules/lib/perl5/site_perl/5.10.1/"
      (
      seq 1 20
      ) |
      (
      while read T ; do
      echo "$T"
      make_pysol_freecell_board.py -F -t "$T" black_hole |
      black-hole-solve - > "$T".results.txt
      done
      ) 2>&1 | tee -a black_hole_range_LOG
      [/]

      [benchmark-c.bash]
      #!/bin/bash
      export PATH="/home/shlomif/apps/test/bhs/bin/:$PATH"
      (
      seq 1 20
      ) |
      (
      while read T ; do
      echo "$T"
      make_pysol_freecell_board.py -F -t "$T" black_hole |
      black-hole-solve - > "$T".results.txt
      done
      ) 2>&1 | tee -a black_hole_range_LOG
      [/]

      On one occasion I was told that perl 5 was 100 times slower than C, and on a
      different one that it was 1,000 times slower, and 24 times slower is still a
      very dramatic difference.

      Regards,

      Shlomi Fish

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      My Public Domain Photos - http://www.flickr.com/photos/shlomif/

      <rindolf> She's a hot chick. But she smokes.
      <go|dfish> She can smoke as long as she's smokin'.

      Please reply to list if it's a mailing list post - http://shlom.in/reply .
    Your message has been successfully submitted and would be delivered to recipients shortly.