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

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

Expand Messages
  • Gwen Shapira
    ... So your code is CPU bound and you are counting on the C optimizer to reduce the CPU usage? The reason I m drilling down into the details is that I ve been
    Message 1 of 4 , Aug 26, 2010
    • 0 Attachment
      > 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?

      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 :)

      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.

      I'm curious how it works in other areas that I'm less familiar with.
      Could you post benchmarks? Do you have profiler output for your
      program (i.e. where time is spent before and after)?

      Chen
    • 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 2 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 3 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.