RE: CSS Engine Style Invalidation Strategy

>> * Each element has three sets of invalidating flags:
>> * Each set of invalidation flags contain four different flag sections:
>> o 64bits for IDs
>> o 64bits for Classes
>> o 64bits for Attributes
>> o 32bits for States (hover…)
>
> So just to make sure: this is at least 84 bytes per element just for
> these flags, right? (In practice, various state stuff doesn't actually
> fit in 32 bits; you need 64, so it would actually be 96 bytes.)

Yes, my full setup would cost 96 bytes per element (I was planning to leave the 32 last bits of the setup unused at the time for future extensions).


> How does this handle DOM insertions and removals?

The mail was so long I thought I could not have missed something. I was wrong, of course.

When an element is inserted, if the sibling-invalidation map of its previous sibling does not return zero, we reevaluate his next siblings. Otherwise we don't.

When an element is being removed, if its sibling-invalidation map does not return zero, we reevaluate his next siblings. Otherwise we don't.

At the cost of maintaining a flag that say "was any selector concerning a next-sibling successful in getting further than this element" you can also make a difference between the two elements features and compare that to the sibling-invalidation flag map (but if any selector successfully went ahead of the element, too many factors would make it impractical to guess further).


> At the cost of having to keep track during selector matching exactly how
> the element you're matching right now is related to the subject of the
> selector, plus the significantly increased memory usage from those flag
> sets, right?

Right.


>> * Is ineffective for documents with a lot of unused selectors
>
> Which are fairly common, actually.

Yes. I still believes it helps in this case but the benefits decrease quickly when the number of selector-related operation on an element increases (because the flags end up being polluted and almost all equal to one). Maybe some elements like HTML or BODY which happen rarely but are involved in a lot of operations could benefits from bigger flags.

I also had the idea of keeping track of classes that pollutes the flags of a lot of elements and remove them from the flag system (updating those classes just trigger an update anyway) but I wasn't sure how practical it was. Any class ever set on the BODY or HTML tag would fit in this category, I guess.


>> * Potentially triggers a lot of memory writes during selector matching
>> (is that an issue?)
>
> It sure can be if you want to parallelize selector matching; have to do
> it in a smarter way.

The solution for parallel matching is to have each thread create his own copy of the flags, and reduce them with the "OR" operator at the end (or when the thread finish his work, or ...)

Received on Tuesday, 30 July 2013 02:48:34 UTC