<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
thanks for the warm welcome and all the info.<br>
okay. here's my proposal.&nbsp; sorry in advance for the extreme length. <br>
<br>
only read if you're interested in cairo arcana-- <br>
i'll try to whip up a patch over the next few days,<br>
then let the code speak for itself.&nbsp; <br>
<br>
the general goal of my proposal is to unify path memory usage across
compilers, decrease potentially wasted space, and in, what i suspect
are the most frequent use cases, increase the number of paths cairo can
store in the same space it uses now.<br>
<br>
the general concept is to change the dual lists of ops and points into
a single unified command buffer stream.&nbsp; the following goes into
details about how it works now, how the command stream would work, and
how -- in most cases -- the command stream would save memory. there's a
couple implementation questions towards the end.<br>
<br>
<b>how it works now:</b><br>
<br>
cairo's
paths ( cairo_path_fixed_t ) store their path operations and path
points in chains of fixed size buffers ( cairo_path_buf_t )&nbsp; on all
platforms each buffer holds 512 bytes. there are always the same number
of points and ops in each structure, however the size of the ops vary
per compiler, and thus the number of items each structure can hold
varies. under visual c 6.1 ops take 4 bytes, while via gcc each op is 1
bytes. the former leads to 2 set of 38 items ( 38 points, 38 ops ), the
latter 2 sets of 51 items.<br>
<br>
with the existing algorithm whenever
a new path operation would overflow either the number of available
points or ops, a new buffer gets allocated. there is not a one to one
mapping between the number of ops and the number of points used in a
given path.&nbsp; each
operation takes different numbers of points: move to and lines to add 1
point, a curve to adds 3, the close path op adds no points. <br>
<br>
the
worst real world cases, memory usage wise, are curves. a new
buffer is needed under visual c after 12 curve segments; under gcc: 17.<br>
<br>
for
a buffer full of curves, visaul c produces 2 wasted points and 26
(38-12) wasted ops; gcc no wasted points, but 34 (51-17) wasted ops.
that's
a total of 112 (2*4 + 26*4) and 34 (34*1) wasted bytes respectively;
22% and 7% of path storage memory goes unused in the full curve case.&nbsp;
not terrible, especially under gcc, but i think there's a simple way to
use almost all the allocated space for path storage. <br>
<br>
<b>command buffers</b><br>
<br>
since
paths and ops are both integer types, it would be easy to store a
single command stream of uniform type combing the list of ops and
points.&nbsp; each op would take 1 command stream element, while each point
would take 2 elements ( 1 for x, 1 for y ).&nbsp; the entire command stream
would have 116 elements available in the space devoted formerly to the
separate point and op lists.<br>
<br>
if every operation that is
currently added to the list is directly followed by the points that use
it, a curve segment would have the stream: [ "CURVE",
curve-point-1,cp2,cp3, "CURVE",c2p1,c2p2,c2p3 ] each curve would take 7
(1+3*2) elements ( 28
bytes ) and cairo could store 16 curves with no wasted space. for
visual c: that's good ( 16 vs. 12 ), for gcc not so good ( 16 vs. 17
).&nbsp; Lines of course are even worse for gcc -- reducing it to 38 points
from 51 points.<br>
<br>
<b>command buffers + counts</b><br>
<br>
to get towards the storage savings that cairo
has under gcc, the next step would split the op element into two parts:
the operation key and a count tracking the number of times an operation
has been used without interruption.&nbsp; in the repeating curve segment
case the command stream would appear something like [ ("CURVE", X),
c1p1,c1p2,c1p3, c2p1,c2p2,c2p3, ... ] where X is the number of curve
segments in the current buffer. in this case: 38 curve segments could
fit.&nbsp; if the next path segment were also a curve there would be just 4
bytes
( 1 op + 38*3 points = 115 elements used; 116 total elements-115 used
els=1 wasted el; 1el*4bytes/el=4 ) of wasted space. [ the bookkeeping
needed -- an index to the current operation would be kept at the path,
not buffer, level ]<br>
<br>
that's great: 38 curves vs 12(or 17) - a win for all compilers.<br>
<br>
<b>two new commands</b><br>
<br>
the
downside appears again however in situations where there are lots of
changes in the segment type -- ex. "MOVE", "LINE", "MOVE", "LINE",
"MOVE", "LINE" --this scheme could only fit 19 (116/(2*(1+2))) such
paired segments, while currently under gcc can fit 25 (51/2).<br>
<br>
the next and final step, at the cost of making some changes outside of
the buffer code itself, would be to introduce two new commands
LINE_SEGMENT and CURVE_SEGMENT. (&nbsp; this makes the lists very
3d-accelerator like with their line strip / line list primitives ).&nbsp;
the segment commands would represent the "MOVE", "LINE" pair as a
single operation with two points., rather than 2 operations with 2
points.&nbsp; in the current buffer space cairo could store: 28 ((116-1)
/(2*4)) line list segments per buffer.<br>
<br>
this isn't quite as straight
forward as the other changes as there would probably have to be some
work to handle detecting line <span style="font-style: italic;">strip </span>startup
cases ( move-line-line-... ) cleanly ( similar to the existing move /
line startups ).&nbsp; a nice thing about this change though is that
separate strips would wind up shedding their separate initial move
operation; the move designated solely by the start of a new strip
operation.<br>
<br>
that said thrashing between strips and lists will still eat up memory
slightly faster than it used to.<br>
<br>
<b>overall gains</b><br>
<br>
i
think in the majority of cases these changes as a whole will save
memory for all compilers, but in between fully mixed and fully chained
paths, there's a lot of wiggle room.&nbsp; while i suspect most
use cases are composed of chains of similar primitives - i don't know
that for sure.&nbsp; <br>
<br>
there's some smaller possibility it might make
acceleration compatibility easier in some sense -- given the tighter
mapping to gl/d3d style primitive types -- though i don't really know
how/where that would actually play out.<br>
<br>
<b>how should chaining work?<br>
<br>
</b>one open question is how to chain together series
of same path operations that span multiple buffers.&nbsp; the two main
options are either store the complete chain length even if it crosses
buffers, or to store only the per buffer length, always terminating a
chain at the end of a buffer.&nbsp; the option still tops out at 65535
operations, and so some sort of chain continuation code would be needed
in either case.&nbsp; given that the second option likely makes more sense.&nbsp;
that said there could be some advantages in knowing the size of chains
up front.... not completely sure but easy to tweak later on.<br>
<br>
<b>are reversals a dead code path? <br>
</b><br>
while going over
the necessary changes again this morning i see that the buffer's prev
pointer allows _cairo_path_fixed_interpret() to traverse the op and
point list both forwards and backwards. <br>
<br>
while the reversal traversal
actually appears unused in current code, the command stream would
require a minor addition to support it. the operator elements would
further split into: command / repeat count / prev op index with no more
than 255 elements stored in a single chain. <br>
<br>
while generally i'm a firm believer in
removing unused code paths, i'd definitely want to hear from people
with more cairo experience than myself.&nbsp; if
reversal is unneeded that would nicely free up space for another
command stream element ^o^ <br>
<br>
if i'm wrong or insane on any front just let me know,<br>
-io.<br>
<a class="moz-txt-link-freetext" href="http://www.ionous.net">http://www.ionous.net</a><br>
<br>
Carl Worth wrote:
<blockquote cite="mid:874pioptmw.wl%25cworth@cworth.org" type="cite">
  <pre wrap="">On Fri, 24 Aug 2007 15:10:36 -0500, ionous wrote:
  </pre>
  <blockquote type="cite">
    <pre wrap="">hi . - i'm new to cairo but i've been looking through the source,
learning how it works, and have found a couple areas where i would like
to contribute if i can.
    </pre>
  </blockquote>
  <pre wrap=""><!---->
Welcome! We're always glad to accept a new memeber into the community,
and any contribution you make will be greatly appreciated.

  </pre>
  <blockquote type="cite">
    <pre wrap="">the first thing i wanted to play around with is a relatively minor, but
hopefully useful, memory optimization to path storage.  i've written up
a pretty complete description of the change  ( it's a tad long ^_^ ) but
should i post it here? should i just go ahead and make the changes then
post a patch?  what would be best?
    </pre>
  </blockquote>
  <pre wrap=""><!---->
If you've already got something written up, please feel free to post
it here. Patches are welcome here as well, but are certainly not a
prerequisite to discussion.

  </pre>
  <blockquote type="cite">
    <pre wrap="">i also would be interested, as i learn my way around,  in doing some (
no big commitments here ) code side documentation-- are there any
guidelines i should follow on that front?
    </pre>
  </blockquote>
  <pre wrap=""><!---->
Not much. We prefer C89-compatible comment delimiters, /* like this */
over the C99 things // like this
but there's not much else in the way of internal documentation
guidelines.

The public API is documented with (fairly minimal) gtkdoc-style
markup. Some of the internal documentation is as well, (in the
off chance that we'll ever generate formatted output from it). But I
think that generating formatted internal comments, (and hence
separating it from the code), would be quite useless. So I greatly
prefer to have markup-free comments in the code that are formatted to
be read as-is along with the code itself.

  </pre>
  <blockquote type="cite">
    <pre wrap="">( and thanks for cairo -- its very cool and very useful. )
    </pre>
  </blockquote>
  <pre wrap=""><!---->
You're quite welcome. I'm glad you're enjoying it, and I hope you'll
continue to have fun with it.

-Carl
  </pre>
</blockquote>
</body>
</html>