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

Re: "ocaml_beginners"::[] compare_val dominating runtime? (over 5mins of it)

Expand Messages
  • Jon Harrop
    ... That s weird - it is actually slightly slower here. That s probably because I altered the problem though... -- Dr Jon D Harrop, Flying Frog Consultancy
    Message 1 of 21 , Sep 3, 2005
    • 0 Attachment
      On Saturday 03 September 2005 09:37, Radu Grigore wrote:
      > That is probably a typo since
      >
      > let def_hash (i, j, k) = i + (j lsl 10) + (k lsl 20)
      >
      > works almost twice as fast.

      That's weird - it is actually slightly slower here. That's probably because I
      altered the problem though...

      --
      Dr Jon D Harrop, Flying Frog Consultancy Ltd.
      Objective CAML for Scientists
      http://www.ffconsultancy.com/products/ocaml_for_scientists
    • Chris Campbell
      Wow!!! Thanks Jon. It appears I made an error in translating the bit twiddling functions in the C code. // flip the given bit of i inline int FLIP(int i, int
      Message 2 of 21 , Sep 3, 2005
      • 0 Attachment
        Wow!!! Thanks Jon.

        It appears I made an error in translating the bit twiddling functions
        in the C code.

        // flip the given bit of i
        inline int FLIP(int i, int bit)
        {
        return i^1<<bit;
        }

        I translated that as i lxor (1 lsr b) by mistake. Small typo,
        dramatic impact. I think I'll nominate myself for thedailywtf.

        The algorithm now does 1150 cubes not 80k. Checking the C++ app I
        found generates 1052, so it's on par with it (I expect it to be
        identical given the same partitioning size).

        I can only say I'm sorry about this. It's quite an embarrising error.

        The error was present in both the old version and the new one because
        I just copied those over. :(


        On 03/09/05, Jon Harrop <jon@...> wrote:
        > On Friday 02 September 2005 22:39, Chris Campbell wrote:
        > > The algorithm is actually quite simple. Compute value of the surface
        > > function at the four corners of each of the 6 faces of a cube. If a
        > > face has atleast one corner of different sign from the others add the
        > > cube beside that face (if it hasn't been done already). The different
        > > sign indicates the face intersects the surface along atleast one edge
        > > (the surface is defined to be all points where the surface function is
        > > 0).
        > >
        > > The part that isn't implemented is tetrahedral decomposition which
        > > computes the triangles in a cube containing atleast one such edge.
        >
        > Is that marching cubes/tetrahedra? It would be great to publish an open-source
        > 3D tesselator!

        I know it's not marching cubes (even though US patents don't apply in
        UK they still leave a bad taste in the mouth so I avoided it, plus it
        has ambigious cases), but I'm not 100% sure if it is called marching
        tetrahedra or not. I only know it from J Bloomenthals Graphics Gem
        paper (http://www.unchainedgeometry.com/jbloom/pdf/polygonizer.pdf).

        > > Sure. http://www.cyberdanx.co.uk/polygonizer.tar.gz
        >
        > Wow! Lots more advice from you.

        In the code? It's mostly there for my benefit. :) Looking at the c
        version made my head hurt and it took a long time to understand what
        it does because of all the data structures are managed all over the
        place (it's spaghetti). That sort of code tends to obscure the
        algorithm. :)

        > First, two mutually-recursive bits of advice for you:
        >
        > 1. Don't annotate types unless you have to.
        > and
        > 2. Don't optimise prematurely.
        >
        > You have added explicit type annotations for almost everything. 99% of them
        > simply clutter up the code. One of the main advantages of OCaml, and the
        > source of its brevity, is type inference.

        Went from one extreme to the other... I'll restrain myself in future. :)


        > Note that OCaml has flattened out the LatticeHashType module name (only the
        > top-most module name remains, Polygonalizer, in the profile). This "equal"
        > function may appear to be fully type annotated to the untrained eye. However,
        > my spidey sense tells me that "a=b" is doing a structural comparison of a
        > pair of 3-tuples which ocamlopt will dispatch to polymorphic comparison
        > (compare_val).
        >
        > If you tweak this code to:
        >
        > let equal ((i1,j1,k1):t) ((i2,j2,k2):t) = i1=i2 && j1=j2 && k1=k2
        >
        > Then OCaml is only comparing integers and the program becomes 3x faster!

        :s

        That's suprising. I would have expected that it was fully type
        annotated, but then I thought the types in mli files would have an
        impact on polymorphic code being generated...

        Thanks Jon.


        Chris
      • Chris Campbell
        Incase anyone wonders how fast it is now... 0.12s
        Message 3 of 21 , Sep 3, 2005
        • 0 Attachment
          Incase anyone wonders how fast it is now...

          0.12s

          :'(
        • David Thomas
          That makes more sense to me, 31 bit int and all... thanks :) ... ____________________________________________________ Start your day with Yahoo! - make it your
          Message 4 of 21 , Sep 3, 2005
          • 0 Attachment
            That makes more sense to me, 31 bit int and all...
            thanks :)

            --- Radu Grigore <radugrigore@...> wrote:

            > --- David Thomas <David_HD@...> wrote:
            > > --- Jon Harrop <jon@...> wrote:
            > > > let def_hash (i,j,k) = i + (j lsl 10) + (k lsl
            > 10)
            > > Any particular reason behind that in particular?
            >
            > That is probably a typo since
            >
            > let def_hash (i, j, k) = i + (j lsl 10) + (k lsl
            > 20)
            >
            > works almost twice as fast.
            >
            >
            > __________________________________________________
            > Do You Yahoo!?
            > Tired of spam? Yahoo! Mail has the best spam
            > protection around
            > http://mail.yahoo.com
            >




            ____________________________________________________
            Start your day with Yahoo! - make it your home page
            http://www.yahoo.com/r/hs
          • David Thomas
            It seems to me that it would depend on how often j + k = n, for the same n. The more often, the more collisions. ...
            Message 5 of 21 , Sep 3, 2005
            • 0 Attachment
              It seems to me that it would depend on how often j + k
              = n, for the same n. The more often, the more
              collisions.

              --- Jon Harrop <jon@...> wrote:

              > On Saturday 03 September 2005 09:37, Radu Grigore
              > wrote:
              > > That is probably a typo since
              > >
              > > let def_hash (i, j, k) = i + (j lsl 10) + (k lsl
              > 20)
              > >
              > > works almost twice as fast.
              >
              > That's weird - it is actually slightly slower here.
              > That's probably because I
              > altered the problem though...
              >
              > --
              > Dr Jon D Harrop, Flying Frog Consultancy Ltd.
              > Objective CAML for Scientists
              >
              http://www.ffconsultancy.com/products/ocaml_for_scientists
              >


              __________________________________________________
              Do You Yahoo!?
              Tired of spam? Yahoo! Mail has the best spam protection around
              http://mail.yahoo.com
            • Chris Campbell
              I completely rewrote it using some of the tips in here and it now performs very well... well under a second. Could probably render each frame like the c++
              Message 6 of 21 , Sep 5, 2005
              • 0 Attachment
                I completely rewrote it using some of the tips in here and it now
                performs very well... well under a second. Could probably render each
                frame like the c++ program does. Now I have just one problem
                remaining concerning the normals (half faceted, half smooth). I'll put
                it up somewhere once I fix that.

                Thanks for everyones help.
              Your message has been successfully submitted and would be delivered to recipients shortly.