Ambushed

This morning started like any other morning. I got up and read the Bible, this time I'm in Luke 6 reading about what a great guy Jesus was, yadda yadda. Then things took a turn...

Looking at his disciples, he said:

"Blessed are you who are poor,

for yours is the kingdom of God.

Blessed are you who hunger now,

for you will be satisfied.

Blessed are you who weep now,

for you will laugh.

Blessed are you when men hate you,

when they exclude you and insult you

and reject your name as evil, because of the Son of Man.

Rejoice in that day and leap for joy, because great is your reward in heaven. For that is how their fathers treated the prophets.

But woe to you who are rich,

for you have already received your comfort.

Woe to you who are well fed now,

for you will go hungry.

Woe to you who laugh now,

for you will mourn and weep.

Woe to you when all men speak well of you,

for that is how their fathers treated the false prophets.

Errrr. To be honest I identify more with the latter half. Hmm, surely Jesus had some hidden subtext that lets me off the hook. Let's plough on.

But I tell you who hear me: Love your enemies, do good to those who hate you, bless those who curse you, pray for those who mistreat you. If someone strikes you on one cheek, turn to him the other also. If someone takes your cloak, do not stop him from taking your tunic. Give to everyone who asks you, and if anyone takes what belongs to you, do not demand it back. Do to others as you would have them do to you.
If you love those who love you, what credit is that to you? Even 'sinners' love those who love them. And if you do good to those who are good to you, what credit is that to you? Even 'sinners' do that. And if you lend to those from whom you expect repayment, what credit is that to you? Even 'sinners' lend to 'sinners,' expecting to be repaid in full. But love your enemies, do good to them, and lend to them without expecting to get anything back. Then your reward will be great, and you will be sons of the Most High, because he is kind to the ungrateful and wicked. Be merciful, just as your Father is merciful.

Oh COME ON, this is just unrealistic. You expect me to willingly take damage from bad guys, to get hurt? .... Wait, don't answer that. ... Maybe it's just a suggestion....

Why do you call me, 'Lord, Lord,' and do not do what I say? I will show you what he is like who comes to me and hears my words and puts them into practice. He is like a man building a house, who dug down deep and laid the foundation on rock. When a flood came, the torrent struck that house but could not shake it, because it was well built. But the one who hears my words and does not put them into practice is like a man who built a house on the ground without a foundation. The moment the torrent struck that house, it collapsed and its destruction was complete.

Ah ... er ... ow! ow ow ow! Gaaah! Help!

When I think of "the wise man build his house upon the rock" I usually think of the charming Sunday School ditty, but this morning it gives me a feeling of being mugged. Maybe how the disciples felt as they said "Lord, increase our faith!"

Gloomocracy IV

A friend pointed me at a particularly egregious example of gloom-centric reporting.

Paragraph two gives an initial summary of the study, saying it "showed more mistakes happened in the care of New Zealanders than were made in German or British health services". Paragraph three follows with more bad news. Some other bad-news anecdotes follow.

Finally in paragraph eight we hear more about the study. It turns out that the study covered six countries: the above three plus the USA, Canada and Australia. Indeed, the NZ error rate was lower than in the USA, Canada and Australia. Then we're also told that NZ, along with Australia, Germany and Britain, had easier access to doctors than in the USA and Canada.

This is a classic example of picking out the negative details and writing a story around them. Well done, Eleanor Wilson, our dour citizens silently acknowledge you.

Frame Display Lists

I'm reworking how frame painting works in Gecko.

Currently painting is a two-phase process. The view manager creates a display list of "views" (roughly corresponding to positioned elements and other elements that need complex rendering) that intersect the dirty region. This display list is sorted by z-order according to the CSS rules. Then we optimize the display list, removing views that are covered by other opaque views. Then we step through the display list from bottom to top and paint the frames associated with each view. Frame painting handles some more z-ordering issues using "paint layers". E.g. a background layer contains block backgrounds, a float layer contains floats, and a foreground layer contains text. We traverse each frame subtree three times, once for each layer.

This approach has some problems. We don't implement CSS z-order perfectly because of the way z-order handling is split between views and frames. It's unnecessarily complex. We paint some unnecessary areas because we only handle opaque covering at the view level; if a frame without a view is opaque and covers content underneath it, we don't take advantage of that. It's not as fast as it could be because of the three traversals of each relevant frame subtree. Painting outlines properly with this scheme would require an additional paint layer, requiring four traversals. We also need to fix a bug by making elements with negative z-index paint in front of the background of their parent stacking context ... this would require a fifth paint layer or some other hack. And it's not very extensible to handle new quirks the CSS WG might throw at us.

So I'm working on a patch to replace all this with a display list of frames --- actually, parts of frames, since different rendered parts of a frame can have different z-positions. I call these parts "display items". Because a frame subtree may distribute display items to different z-levels in the parent, we actually pass in a list of display lists, each corresponding roughly to a paint layer. Once we've built a complete display list we can optimize it and finally paint the visible items.

One nice thing about this approach is that we can use it for mouse event handling too. To figure out which frame the cursor is over we just build a display list for a single point and analyze it from the top down. We can get rid of all the GetFrameForPoint(Using) code and we get a guarantee that event handling stays consistent with painting.

This approach also lets us organize our painting --- er, display list construction --- more flexibly, because we don't have to specify what gets painted in the exact order it will be painted. For example currently we have a function PaintTextDecorationsAndChildren that paints overlines and underlines, then paints child inlines, then paints the strikeout, because that's what CSS requires. But it simplifies the code if the text-decoration code can be separated from the painting of children. I replace this with a function DisplayTextDecorations which creates overline, underline and strikeout display list items (as needed) and lets the caller put them in the right z-position, so this is separated from painting the children.

Of course this approach also lets us fix the bugs I mentioned above with outlines and negative z-index children. I also hope the performance will be better than what we have today, because we only need one traversal of the visible parts of the frame tree. We do a bit more work at each frame, but that should have decent memory locality.

One potential problem with this approach is the storage required by the display list. It's very short-lived --- it only exists while we do a single paint --- but potentially each frame could create a few display list items, and each item is about 24 bytes (more for 64bit). Think 10,000 visible frames in a very complex page and we're talking about 500K memory. That actually sounds OK to me --- except for Minimo, but Minimo devices probably won't be able to get so many frames on their small screens :-). Another way to think of it is that at worst, the display list might momentarily approximately double the space used for a document. In any case --- and here I invoke my last blog entry about optimization --- I think I can see how to compress the display list as we build it, to reduce the memory overhead substantially, though I won't be doing that until we really need to.

BTW over the years many people have asked for a Gecko API so that embedders can deconstruct exactly what's visible on the page in terms of content elements and the geometry and z-ordering of their boxes . This frame display list would be a good basis for that.

Oh, this also will make it easy and clean to implement SVG foreignobject the way I did for my XTech demo. I'm looking forward to having that in trunk cairo builds.

One complexity of CSS painting is that compositing ('opacity'), z-ordering and most clipping are done according to the content hierarchy, not the CSS box containment hierarchy. (E.g., an absolutely positioned box clips a fixed-position child, even though it's not the containing block for the fixed-position child.) This has been a source of many difficult bugs and some fragile, hairy code to figure out exactly what clip rect applies to a frame, when we were painting by traversing the view and frame hierarchies (and it's still wrong in tricky edge cases today). Now I'm able turn this around and take a reasonably simple approach: paint (er, build display lists) recursion always follows the content tree. This means we paint out of flow frames (absolute/fixed position elements and floats) when we encounter their placeholder frames. This helps eliminate a lot of existing code complexity.

"Premature Optimization Is The Root Of All Evil" Is The Root Of Some Evil

There's a folklore quote "premature optimization is the root of all evil", attributed to Tony Hoare and Donald Knuth. A variant is due to my PhD advisor's father Michael Jackson: "The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.". Unfortunately --- and I'm not the first to note this --- this advice, taken out of context and followed slavishly, often leads people into deep trouble. The problem is that it collides with another well-known feature of software development: it gets more expensive to make changes to the system later in its development, especially cross-cutting changes that impact module interfaces. If you leave optimization to late in development, then profile it and find that fixing the performance bottleneck requires a major change in your design, or forces major module interface changes, then you have a serious problem.

Clearly one should therefore design a system with an eye to where the bottlenecks may be, and try to ensure the design has enough flexiblity to capture the optimizations that will be required. This is dangerous and impossible to get right all the time, but such is life in software development. It is not enough to just think about high-level performance, because sometimes low-level coding issues do have a significant impact and they may be constrained by the design. For example in Gecko the designers created module interfaces that relied on using virtual method calls almost everywhere. Individual virtual calls are very cheap but used very frequently --- and without the support of advanced JIT compilation techniques --- they are a significant performance drag. In some cases, where actual polymorphism is in use, devirtualizing the calls requires significant and expensive restructuring of the code.

I find it useful to do a sort of "gedankenprofiling". Guess or measure some important workloads, then sketch out mentally how each workload will be processed by the proposed designs, focusing on the apparent bottlenecks. Try to guess how much cost per unit work will be incurred at the bottleneck by alternative designs. Do not choose the design that minimizes the cost; instead, choose the design of minimal complexity that can smoothly extend to the cost-minimal design. Then when you start implementing and measuring and discovering your mistaken assumptions, you have the best chance of still getting to a good place relatively cheaply.

Right now I'm redesigning the way we paint frames in Gecko and thinking a lot about how it will perform in various scenarios, and trying to put in just the right amount of flexibility to handle potential future issues. Fortunately I don't have to guess so much since we already know a lot about where our performance problems are.