Memory allocation error and solutions

edited March 2014 in Ruby Scripting

I am trying to boolean some large-vertex-count polygons with some other large-vertex-count polygons, and am getting memory allocation errors.

To reproduce the problem on a simpler script I wrote the following. Note my observations in the comments on the 7th line.

layout_view = RBA::Application.instance.main_window.current_view  
layout = layout_view.active_cellview.layout
out_cell = layout_view.active_cellview.cell
out_layer = layout.layer(1,0) # Use this if you're not sure if there are any shapes on that layer in the current view, and don't mind creating the layer if it doesn't exist
dbu = layout.dbu

# Number of points along the base of the inner polygon. 
# If this is 10**5 it works and runs in about 0.5 seconds.
# If this is 10**6 it works and runs in about 5 seconds.
# If this is 10**7 it hits an error:. 
#   "Caught the following exception: bad allocation in EdgeProcessor::boolean_p2p (Class RuntimeError). Press 'Ok' to continue and 'Cancel' to stop in the debugger"
# If this is 10**8 it doesn't return anything even after waiting 10 minutes (it just hangs), and doesn't complain about any memory allocation errors (though, perhaps I didn't wait long enough).
n = 10**5

# Create the inner polygon (a rectangle with many jagged-edge points along the base)
pts_inner = []
x_max = n*0.001
y_max = 10
pts_inner.push(RBA::Point.new(x_max/dbu,y_max/dbu))
pts_inner.push(RBA::Point.new(0.0/dbu,y_max/dbu))
curr_x = 0
curr_y = 0
n.times { |i|
  pts_inner.push(RBA::Point.new(curr_x/dbu,curr_y/dbu))
  curr_x += 0.001
  if i % 2 == 0
    curr_y = 1
  else
    curr_y = 0
  end
}
poly_inner = RBA::Polygon.new(pts_inner)

# Create the outer polygon (a box)
extra = 1
left = -extra
bottom = -extra
right = x_max + extra
top = y_max + extra
poly_outer = RBA::Polygon.new(RBA::Box.new(left/dbu,bottom/dbu,right/dbu,top/dbu))

ep = RBA::EdgeProcessor::new
outer_minus_inner = ep.boolean_p2p([poly_outer],[poly_inner], RBA::EdgeProcessor::ModeANotB, false, false)
outer_minus_inner.each { |p|
  out_cell.shapes(out_layer).insert(p)
}

Now, I searched on this forum and as I understand it: If I'm using 32-bit windows version, I have some sort of 2 GB limit on filesize. Not sure how this relates to memory consumption by a script though. Nonetheless, I'm now using 64-bit and get the same error. The previous posts suggest 64-bit has no KLayout-imposed limit, but just a hardware limit based on the RAM for whatever computer you are using.

So, I need to use a computer with more memory or I need to do something more clever. The former is not an option so let's look at the latter. One forum post suggested I could write some script to "tile" it and do it piecemeal, however I'm not sure how I could do that. Could you perhaps offer an example with the above script, showing how to tile it?

Thanks!

Comments

  • edited November -1

    Hi David,

    that appears to be some extreme case - maybe the formation of the complex hole inside the polygon is requiring more memory than expected.

    In general, a lot of memory is consumed by the point array which is built before the polygon is made of that. You can try to release that memory by releasing the memory and forcing a garbage collect, but that appears not to have an effect on the process size. Maybe memory fragmentation is happening here.

    64bit should be one solution, but you need to make sure you run the 64bit executable. 64bit can run 32bit executables as well in WoW mode, but they will be subject to the same memory restrictions. There is a hardware limit of course too, so if you want to go even further, you should look for a more general solution.

    Looking at the output of your script I see a regular structure. That suggests, you could simplify the problem by producing slices (one slice per tooth) and putting them together later. That surely is more efficient than operations on big polygons.

    Matthias

  • edited November -1

    Thanks Matthias.

    Yes I admit I am pushing your excellent program to the limits, and I'm surprised it even makes it this far, because that is a heavy requirement!

    Definitely running 64 bit. I uninstalled 32-bit.

    Yes it's true that in this script I have a regular structure but this was only a short example to illustrate the question -- my actual script has very complicated shapes and difficult or impossible to split up in such a way. Here I am mostly trying to understand the limits so I can work around them.

    I will mention that anything the script tries to do, before getting to the EdgeProcessor part, even with all those points in memory, still runs really quickly. It is only when it hits the EdgeProcessor line that it struggles if the input and/or output polygons have too many points.

    If there were a way to split both inner and outer polygons - say, split them with vertical lines along the x = 10 um, 20 um, 30 um,... and get an array of polygons. Then operate on the x = 0..10 um polygons, then on the 10..20 um polygons, then on the 20..30 um polygons, etc.... That could be a nice solution. However I fail to find a way to split the a polygon along, say, x = 10um line and return a handle to the two resultant polygons. On L-Edit they have a function for this (splitting along a vertical or horizontal line) so I mention that only because I am familiar with it, but there may be better approaches. Any simple way to do that in Ruby code? If not maybe I just need to buy and install a ton of memory.

  • edited March 2014

    Never mind. Figured it out.

    I coded up the following "slicer" (1D tiling function) pasted below. Not the prettiest code but it works. There are a few limitations of the code though these can be fixed. First, it has problems if the slice locations v fall outside of the original polygon. Second, there are a few strange cases where it may not work. At any rate, this is good enough for me.

    Here is some example code which calls the .rb file pasted later:

    # Draw a polygon (make sure it is larger than the v positions below), select it, then run this script to slice it up and draw the slices
    
    layout_view = RBA::Application.instance.main_window.current_view  
    layout = layout_view.active_cellview.layout
    out_cell = layout_view.active_cellview.cell
    out_layer = layout.layer(1,0)
    dbu = layout.dbu
    poly = RBA::Polygon.new(RBA::Box.new(0/dbu,0/dbu,10/dbu,10/dbu))
    #out_cell.shapes(layout.layer(2,0)).insert(poly)
    filepath = 'C:/filepath/'
    filename = 'split vertically.rb'
    file = File.expand_path(filename, filepath)
    load file
    
    v = [1,2,10,11]
    direction = 'vertical'
    
    if layout_view == nil
      raise "No view selected"
    end
    
    layout_view.transaction("Split")
    begin
      layout_view.each_object_selected { |obj|
        if obj.shape.is_polygon?
          split_poly_arr, orig_poly = Split.split(v,obj.shape,direction)
          split_poly_arr.each { |p| out_cell.shapes(out_layer).insert(p) }
        else
          RBA::MessageBox::warning("Warning", "Found something other than a polygon. Ignoring.", RBA::MessageBox::Ok)
        end
      }
    ensure
      layout_view.commit
    end
    

    And here is the .rb file itself:

    class Split
    
      # Splits a polygon along vertical or horizontal lines at positions v, and returns the array of polygons produced.
    
    =begin # EXAMPLE USAGE.
      layout_view = RBA::Application.instance.main_window.current_view  
      layout = layout_view.active_cellview.layout
      out_cell = layout_view.active_cellview.cell
      out_layer = layout.layer(1,0)
      dbu = layout.dbu
      poly = RBA::Polygon.new(RBA::Box.new(0/dbu,0/dbu,10/dbu,10/dbu))
      #out_cell.shapes(layout.layer(2,0)).insert(poly)
      filepath = 'C:/Users/dnhutchi/KLayout/macros/Sandbox'
      filename = 'split vertically.rb'
      file = File.expand_path(filename, filepath)
      load file
    
      v = [1,2,10,11]
      direction = 'vertical'
    
      if layout_view == nil
        raise "No view selected"
      end
    
      layout_view.transaction("Split")
      begin
        layout_view.each_object_selected { |obj|
          if obj.shape.is_polygon?
            split_poly_arr, orig_poly = Split.split(v,obj.shape,direction)
            split_poly_arr.each { |p| out_cell.shapes(out_layer).insert(p) }
          else
            RBA::MessageBox::warning("Warning", "Found something other than a polygon. Ignoring.", RBA::MessageBox::Ok)
          end
        }
      ensure
        layout_view.commit
      end
    =end 
    
      def self.split(val, shape, horiz_or_vert, cellview = RBA::CellView::active)
    
        layout = cellview.layout
        out_cell = cellview.cell
        dbu = layout.dbu
    
        val.class == Fixnum ? (val_arr = [val]) : (val_arr = val)
        val_arr.map! { |v| v.to_f / dbu } # Convert to database units
    
        split_me = shape    # Keeps track of which shape we are splitting
        split_poly_arr = [] # The output array of post-split polygons
    
        poly1  = nil
        poly2  = nil
        first  = nil
        second = nil
        p "val_arr = #{val_arr}"
        val_arr.each { |v|
    
          # Get the points of the shape we will split
          pts = []
          split_me.each_point_hull { |pt| pts.push(pt) }
    
          # Repeat the 1st element again at the end of the array so that each_cons works correctly
          pts.push(pts[0]) 
    
          pts1 = []
          pts2 = []
          pts.each_cons(2) { |pn|
            p = RBA::Point.new(pn[0].x, pn[0].y)
            n = RBA::Point.new(pn[1].x, pn[1].y)
    
            p p.x.class
            p v.class
            p "Classes above"
    
            # See if the x coords of p and n straddle the v position or not
            if    horiz_or_vert == 'vertical' && (p.x <= v && n.x > v)
              new_pt = RBA::Point.new(v, (n.y-p.y).fdiv(n.x-p.x) * (v-p.x) + p.y) if horiz_or_vert == 'vertical'
              pts1.push(p)
              pts1.push(new_pt)
              pts2.push(new_pt)
            elsif horiz_or_vert == 'horizontal' && (p.y <= v && n.y > v)
              new_pt = RBA::Point.new((n.x-p.x).fdiv(n.y-p.y) * (v-p.y) + p.x, v) if horiz_or_vert == 'horizontal'
              pts1.push(p)
              pts1.push(new_pt)
              pts2.push(new_pt)
            elsif horiz_or_vert == 'vertical' && (p.x > v && n.x <= v)
              new_pt = RBA::Point.new(v, (n.y-p.y).fdiv(n.x-p.x) * (v-p.x) + p.y) if horiz_or_vert == 'vertical'
              pts2.push(p)
              pts2.push(new_pt)
              pts1.push(new_pt)
            elsif horiz_or_vert == 'horizontal' && (p.y > v && n.y <= v)
              new_pt = RBA::Point.new((n.x-p.x).fdiv(n.y-p.y) * (v-p.y) + p.x, v) if horiz_or_vert == 'horizontal'
              pts2.push(p)
              pts2.push(new_pt)
              pts1.push(new_pt)
            elsif horiz_or_vert == 'vertical' && (p.x <= v && n.x <= v)
              pts1.push(p)  
            elsif horiz_or_vert == 'horizontal' && (p.y <= v && n.y <= v)
              pts1.push(p)
            elsif horiz_or_vert == 'vertical' && (p.x > v && n.x > v)
              pts2.push(p)
            elsif horiz_or_vert == 'horizontal' && (p.y > v && n.y > v)
              pts2.push(p)
            else
              RBA::MessageBox::warning("Warning", "This shouldn't happen. Check the code..", RBA::MessageBox::Ok)
            end 
          }
          pts1.map! {|p| x = p.x.fdiv dbu; y = p.y.fdiv dbu; p = RBA::Point.new(x*dbu,y*dbu)}
          pts2.map! {|p| x = p.x.fdiv dbu; y = p.y.fdiv dbu; p = RBA::Point.new(x*dbu,y*dbu)}
    
          poly1 = RBA::Polygon.new(pts1)
          poly2 = RBA::Polygon.new(pts2)
    
          # See which one is on the left (or below) and which poly is on the right (or above) of the split line
          first, second = self.first_second(poly1,poly2,v,horiz_or_vert) 
    
          # Save the first polygon and prepare to split the second polygon
          split_poly_arr.push(first)
          split_me = second
        }
        split_poly_arr.push(second) # Add that final sub-polygon onto the array
        [split_poly_arr,shape]
      end
    
      # This method takes in two polygons and a split line at v, and figures out which one is on the left (or below) and which one is on the right (or above) of the split line
      def self.first_second(poly1,poly2,v,horiz_or_vert)
        dbu = RBA::Application.instance.main_window.current_view.active_cellview.layout.dbu
        # Get the points of the original shape
        pts1 = []
        pts2 = []
        poly1.each_point_hull { |pt| pts1.push(pt) }
        poly2.each_point_hull { |pt| pts2.push(pt) }
    
        pts1_is_first = false # "first" meaning either left or below. "second" would mean either right or above.
        pts2_is_first = false
    
        case horiz_or_vert
        when 'vertical'
    
          i = 0; while self.float_cmp(pts1[i].x.to_f*dbu,v) == 0 do; i += 1; end # Choose a point that is not on the cut line v # TODO: FIX THIS SO I'M NOT USING == TO COMPARE FLOATS!
          pts1_is_first = true if pts1[i].x < v
    
          i = 0; while self.float_cmp(pts2[i].x.to_f*dbu,v) == 0 do; i += 1; end
          pts2_is_first = true if pts2[i].x < v
    
        when 'horizontal' # Has not been tested yet
    
          i = 0; while self.float_cmp(pts1[i].y.to_f*dbu,v) == 0 do; i += 1; end # Choose a point that is not on the cut line v
          pts1_is_first = true if pts1[i].y < v
    
          i = 0; while self.float_cmp(pts2[i].y.to_f*dbu,v) == 0 do; i += 1; end
          pts2_is_first = true if pts2[i].y < v
    
        end
    
        if    pts1_is_first && !pts2_is_first
          first  = poly1
          second = poly2
        elsif !pts1_is_first && pts2_is_first
          first  = poly2
          second = poly1
        else
          RBA::MessageBox::warning("Warning", "This should not happen. Check the code for errors.", RBA::MessageBox::Ok)
        end
    
        [first, second]
      end
    
      def self.which_one(two_polygons,v,horiz_or_vert)
        the_shape_to_split = nil
    
        if two_polygons.length == 1
          the_shape_to_split = two_polygons[0]
        else
    
          dbu = RBA::Application.instance.main_window.current_view.active_cellview.layout.dbu
    
          # Figures out which of the two polygons should be cut by a vertical or horizontal line at v
          two_polygons.each { |poly|
    
            case horiz_or_vert
            when 'vertical'
              # Get the points of the original shape
              pts = []; poly.each_point_hull { |pt| pts.push(pt) }
    
              pts.each_cons(2) { |pn|
                p = pn[0]*dbu
                n = pn[1]*dbu
    
                # See if the x coords of p and n straddle the v position or not
                straddle = false
                straddle = true if (p.x < v && n.x > v) || (p.x > v && n.x < v)
                the_shape_to_split = poly if straddle
              }
    
            when 'horizontal' # I have not tested this case
              # Get the points of the original shape
              pts = []; poly.each_point_hull { |pt| pts.push(pt) }
    
              pts.each_cons(2) { |pn|
                p = pn[0]*dbu
                n = pn[1]*dbu
    
                # See if the x coords of p and n straddle the v position or not
                straddle = false
                straddle = true if (p.y < v && n.y > v) || (p.y > v && n.y < v)
                the_shape_to_split = poly if straddle
              }
            end
          }
        end
    
        the_shape_to_split # If this returns nil, then your split line does not intersect either polygon
      end
    
      def self.float_cmp(f1,f2,precision = 0.0001)
        # Acts like <=> for floats
        if (f1 - f2).abs < precision
          ret = 0
        elsif f1 < f2
          ret = -1
        elsif f1 > f2
          ret = 1
        else
          p 'error'
        end
        ret
      end
    
    end
    
  • edited November -1

    Hi David,

    thank you for that example. I have not figured out yet what causes the memory issue. Basically a 64bit machine should be able to address much more memory, but first, a 64bit binary also requires more (because pointers will be 8 byte instead of 4 for example) and second, there is always a limitation, at least at physical memory + swap.

    I somewhat think the problem is related to the big hole. When you use smaller boxes (i.e. horizontal slices) as the background for the subtraction and repeat the step with every slice it may work - but I have not tried that yet.

    Your latest code uses some interesting Ruby techniques and frankly I have not figured out how it works on first glance - but I'll study it :-)

    Thanks,

    Matthias

Sign In or Register to comment.