<!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. okay. here's my proposal.  sorry in advance for the extreme length. only read if you're interested in cairo arcana-- i'll try to whip up a patch over the next few days, then let the code speak for itself.  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. the general concept is to change the dual lists of ops and points into a single unified command buffer stream.  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. how it works now: cairo's paths ( cairo_path_fixed_t ) store their path operations and path points in chains of fixed size buffers ( cairo_path_buf_t )  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. 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.  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. 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. 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.  not terrible, especially under gcc, but i think there's a simple way to use almost all the allocated space for path storage. command buffers 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.  each op would take 1 command stream element, while each point would take 2 elements ( 1 for x, 1 for y ).  the entire command stream would have 116 elements available in the space devoted formerly to the separate point and op lists. 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 ).  Lines of course are even worse for gcc -- reducing it to 38 points from 51 points. command buffers + counts 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.  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.  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 ] that's great: 38 curves vs 12(or 17) - a win for all compilers. two new commands 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). 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. (  this makes the lists very 3d-accelerator like with their line strip / line list primitives ).  the segment commands would represent the "MOVE", "LINE" pair as a single operation with two points., rather than 2 operations with 2 points.  in the current buffer space cairo could store: 28 ((116-1) /(2*4)) line list segments per buffer. this isn't quite as straight forward as the other changes as there would probably have to be some work to handle detecting line strip startup cases ( move-line-line-... ) cleanly ( similar to the existing move / line startups ).  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. that said thrashing between strips and lists will still eat up memory slightly faster than it used to. overall gains 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.  while i suspect most use cases are composed of chains of similar primitives - i don't know that for sure.  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. how should chaining work? one open question is how to chain together series of same path operations that span multiple buffers.  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.  the option still tops out at 65535 operations, and so some sort of chain continuation code would be needed in either case.  given that the second option likely makes more sense.  that said there could be some advantages in knowing the size of chains up front.... not completely sure but easy to tweak later on. are reversals a dead code path? 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. 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. 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.  if reversal is unneeded that would nicely free up space for another command stream element ^o^ if i'm wrong or insane on any front just let me know, -io. <a class="moz-txt-link-freetext" href="http://www.ionous.net">http://www.ionous.net</a> 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>