[Lib2geom-devel] Path storage idea

[Krzysztof K. <twe...@gm...>]

The current storage for path data is a bit wasteful and stores every
segment endpoint in a path twice. Here is my proposal for an
alternative implementation. I'm not yet convinced whether this would
be a worthwhile improvement, so discussion is welcome.

Path data would be stored in a series of structured like this:

struct PathStorage {
    int32_t type;
    int32_t length;
    double final_x;
    double final_y;
};

"type" would contain the type of the segment - moveto, linear, bezier,
arc, sbasis, and so on. "length" would contain the total size of the
current segment. final_x and final_y would contain the coordinates of
the final point. This way every type of segment would have the final
point in the same place, simplifying access to this data from Curve
classes.

After PathStorage, the memory would contain additional parameters,
such as the intermediate Bezier control points, arc parameters, sbasis
coefficients, and so on. This could be accessed by static_cast to an
appropriate derived type. The next PathStorage structure start at the
address of the current structure + length.

Each Curve class would have a constructor such as this:

BezierCurve(PathStorage *data);

The passed "data" would have to point one segment before the
represented curve, so that the curve class could access its initial
point (stored as the final point of the previous segment).

Normal constructors that instantiate standalone curves would allocate
storage for two PathStorage structures, a moveto and a segment
matching the curve type. The curve class would also set a flag
indicating that it is supposed to free this memory on destruction.

In the above scenario, the amount of memory consumed by standalone
curves on a 64-bit machine would increase by 32 bytes: 16 bytes for
the four additional ints in the path data, and a pointer and a flag
for each curve object (the flag would probably take 8 bytes due to
alignment). However, a Path could only store the PathStorage data, and
construct the curve objects on demand, saving 24 bytes per segment
(-16 by not storing each endpoint twice, -8 by not storing a pointer
to each curve object, -8 by not storing the curve object's vptr, +8
for the two ints per segment).

The disadvantage is that iterating over paths would require a memory
allocation for every segment access, since the on-demand objects
cannot be put on the stack and returned by value - we need to return
the correct type. It would also mean that the iterators on Path would
have to return a smartpointer to a dynamically allocated object,
rather than a reference.

Regards, Krzysztof