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

Reply to Chen regarding Porting the Black Hole Solver to C

Expand Messages
  • Shlomi Fish
    Hi all, on Twitter I mentioned that I ve started porting my Black Hole Solitaire solver from Perl to C and that it will hopefully make it faster:
    Message 1 of 4 , Aug 25, 2010
    • 0 Attachment
      Hi all,

      on Twitter I mentioned that I've started porting my Black Hole Solitaire
      solver from Perl to C and that it will hopefully make it faster:

      http://twitter.com/shlomif/status/22027561541

      Chen replied thusly:

      http://twitter.com/gwenshap/status/22031112275

      {{{
      Why go to all the effort without knowing what causes your code to be slow and
      how C can help? Don't guess when you can measure!
      }}}

      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.

      My code is very minimal as it is, and it's not very complicated or
      sophisticated so I expect a conversion to C to yield great speed (and possibly
      also memory consumption) benefits.

      For more information see my:

      * http://en.wikibooks.org/wiki/Optimizing_Code_for_Speed

      I've replied to it here instead of on Twitter, because I didn't have enough
      character quota to express myself properly. (Also I thought it may be of
      interest to the list.).

      Regards,

      Shlomi Fish

      --
      -----------------------------------------------------------------
      Shlomi Fish http://www.shlomifish.org/
      List of Portability Libraries - http://shlom.in/port-libs

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