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

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

Expand Messages
  • 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 1 of 21 , Sep 3, 2005
      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 2 of 21 , Sep 3, 2005
        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 3 of 21 , Sep 3, 2005
          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 4 of 21 , Sep 3, 2005
            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 5 of 21 , Sep 5, 2005
              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.