Can I overallocate CPaths for reuse or for use in builders?

[schellingerhout]

I just need a second set of eyes on ConvertCPathsToPathsT to verify that I am not going down a path (I made a pun) that will get me into trouble.

Since the internal code used Paths<T> all that is needed in conversion from CPaths is the number of paths and then the number of vertices of each path. This means that "A: Array size (as distinct from the size in memory)" is not used for input, which is fantastic for me. I can then over allocate and create a builder without separate memory tracking. I can reuse a block of memory for paths.

/*
CPaths
__________________________________________
| counters | path1 | path2 | ... | pathC |
| A, C     |       |       | ... |       |
------------------------------------------
CPath
_______________________________________________________________
| counters | vertex1      | vertex2      | ... | vertexN      |
| N, 0     | x1, y1, (z1) | x2, y2, (z2) | ... | xN, yN, (zN) |
------------------------------------------------------------

*/
template <typename T>
static Paths<T> ConvertCPathsToPathsT(T* paths)
{
  Paths<T> result;
  if (!paths) return result;
  T* v = paths; ++v;  // v starts at A, after ++v its at "C" ... seems like "A" is never used for input
  size_t cnt = static_cast<size_t>(*v++); // "C" is dereferenced cast to size_t. advanced v is now at "N" of first path
  for (size_t i = 0; i < cnt; ++i)
  {
    size_t cnt2 = static_cast<size_t>(*v);  // "N" is deferenced cast to size_t, 
    v += 2; // 0 is skipped and v is now at the first vertex
    Path<T> path;
    path.reserve(cnt2);
    for (size_t j = 0; j < cnt2; ++j)
    {
      T x = *v++, y = *v++;
#ifdef USINGZ
      z_type z = Reinterpret<z_type>(*v++);
      path.push_back(Point<T>(x, y, z));
#else
      path.push_back(Point<T>(x, y));
#endif
    }
    result.push_back(path);
  }
  return result;
}

Why is this important to know? Memory allocation is one of the slowest operations that you can do in code. Any time you can use a pool or pre-allocate, or over allocate and reuse, you gain time. Why not lie about the size in the "A" field?, because then I have to write a separate memory tracking or box this into another structure that holds the "real" count. If the array holds its real size in "A", but allows that to be independent of the used size its exactly what I need to keep things simple

This invariant should be acceptable
A >= CPaths_Header_Size + CPath_Header_Size * NumberofPaths + NumberOfVertices * Dimensionality,
where CPaths_Header_Size and CPath_Header_Size is two (A, C) and (N, 0) respectively.

[LarsSkiba]

It seems like you are optimizing a potential bottleneck without having a measurement. For complex algorithms with millions of offsets and boolean operations, I've never noticed that memory allocation is the bottleneck.

ClipperLib will do a lot more internal allocations then will ever happen here.

Also keep in my resizing result is incredibly efficient because the stored Path(s) will be moved, not copied.

[schellingerhout]

This is the external structure created and passed to Clipper. Clipper copies the data from it. Internally Clipper uses std::vector that does what I describe above (over allocates and copies data to a new array when values are added beyond capacity). What I am talking about here is the external data structure only used to pass information to Clipper. Clipper copies from this structure as you can see above, so I am not talking about Clipper performance, I am talking about consumer application performance.

Pool allocation is a common practice in high performance code. For instance, in game development it's not uncommon to create a large memory block initially, segment it and reuse sections for the audio buffer, vertices and textures.

All that said I decided to use a negative offset pointer to keep track of memory overallocation and not rely on "A", why? because its more expensive to calculate the one past end pointer for my custom iterators, with "A" that is quick and easy to get. I did something similar to Delphi's dynamic arrays. If you are interested in how those work you can see how Delphi does this with the negative offset TDynArrayRec, (see system,.pas) which is stored in memory right before the first entry of the array.

[schellingerhout]

I believe the answer to my original question is "yes", since the conversion code does not read the value, but calculates "A" for output. However, since things may change in the future, and I don't want to depend on the way the code is written I rather use a negative offset pointer for capacity.

Here is my solution with a negative offset record TPathsHiddenFields stored before TPaths.. If you are interested in what I did here, it's a simplified version of

https://github.com/AngusJohnson/Clipper2/blob/65bcbf95e5bbd279fe469af1ab83365a336bae83/DLL/Delphi_interface/Clipper.DLL.Data.pas

Angus declined that change due to support for older versions of Delphi without generics. Since I will never use double vertices, I also abandoned generics but never re-issued a PR for adding the simpler pointer wrappers. They are in the PR history at least for those interested

  TClipperData = Record // Typespace record (no longer a templated space as in the old PR)
   ...
    PPathsHiddenFields = ^TPathsHiddenFields;

    // our own fields in front of TPaths
    TPathsHiddenFields = Record
      Capacity: Int64; // actual element capacity
    End;

    PPathsWithHiddenFields = ^TPathsWithHiddenFields;

    TPathsWithHiddenFields = Record
       Hidden: TPathsHiddenFields;
       Paths: TPaths;
    End;
    ...
 end;
 ...   
 class function TClipperData.TPaths.CreateWithCapacity(const Capacity: integer): PPaths;
var
  PathsWithHiddenFields: PPathsWithHiddenFields;
begin
  PathsWithHiddenFields := PPathsWithHiddenFields(AllocMem(SizeOf(TPathsHiddenFields) + (Capacity * SizeOf(Int64))));

  PathsWithHiddenFields.Hidden.Capacity := Capacity;
  PathsWithHiddenFields.Paths.ElementCount := 0;

  result := @PathsWithHiddenFields.Paths;
end;

// PRE: We created this data not the Clipper DLL. Calling this on DLL return results will return garbage
function TClipperData.TPaths.GetCapacity: int64;
begin
  result := PPathsHiddenFields(pByte(@Self) - SizeOf(TPathsHiddenFields)).Capacity;
end;