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

Re: Reply to Chen regarding Porting the Black Hole Solver to C

Expand Messages
  • Shlomi Fish
    Resending because YahooGroups rejected my message (silently). ... I believe that is the case. I have very little I/O there - mostly just parsing the input, and
    Message 1 of 4 , Aug 28, 2010
    • 0 Attachment
      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?

      Yes. Here you go:

      1. For PySolFC board No. 26464608654870335080 (which takes a very short time):

      {{{
      shlomif:$module$ time perl -Ilib ./scripts/black-hole-solve
      t/data/26464608654870335080.bh.board.txt
      Solved!
      2D
      3H
      2S
      3C
      4H
      5S
      6D
      7C
      8C
      9H
      TH
      9S
      8S
      9D
      TC
      JS
      QC
      KS
      QH
      JC
      TS
      JH
      QS
      KH
      AC
      2C
      3D
      4S
      5D
      6S
      7D
      6H
      5C
      4C
      3S
      2H
      AD
      KC
      AH
      KD
      QD
      JD
      TD
      9C
      8D
      7S
      8H
      7H
      6C
      5H
      4D

      real 0m0.568s
      user 0m0.538s
      sys 0m0.028s
      }}}

      2. For PySol FC board No. 2:

      {{{
      shlomif:$module$ make_pysol_freecell_board.py -F -t 2 black_hole | time perl
      -Ilib ./scripts/black-hole-solve -
      Solved!
      KH
      AD
      2H
      3D
      2S
      3S
      4H
      5S
      6C
      7D
      8H
      7H
      8D
      9D
      TH
      JH
      TS
      9S
      8S
      9H
      TC
      JC
      QS
      KS
      AH
      2D
      3H
      4D
      5H
      4S
      5D
      6S
      7C
      6H
      7S
      8C
      9C
      TD
      JS
      QH
      JD
      QC
      KD
      QD
      KC
      AC
      2C
      3C
      4C
      5C
      6D
      8.79user 0.07system 0:08.92elapsed 99%CPU (0avgtext+0avgdata
      131120maxresident)k
      0inputs+0outputs (0major+8266minor)pagefaults 0swaps
      }}}

      As you can see it takes much longer.

      > Do you have profiler output for your
      > program (i.e. where time is spent before and after)?
      >

      Well, I haven't converted my program to C yet. I'm attaching the
      Devel::NYTProf output of:

      $ perl -d:NYTProf -Ilib ./scripts/black-hole-solve 2.bh.board.txt

      As one can see from it, most of the time is spent in the loop, with one
      statement taking over 1 second in the total run (as they are run many times).
      The amount of code spent on reading the board or outputting the solution is
      very small.

      Regards,

      Shlomi Fish

      > Chen

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      "The Human Hacking Field Guide" - http://shlom.in/hhfg

      God considered inflicting XSLT as the tenth plague of Egypt, but then
      decided against it because he thought it would be too evil.

      Please reply to list if it's a mailing list post - http://shlom.in/reply .
    • 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 2 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.