Tracking style sheet order and position in O(1) time.

[pygy]

I'm resuming work on a CSS-in-JS lib I wrote, and I take great care in making sure that users can take advantage of the cascade if they want to. My problem case is the following:

Suppose a sheet of the form:

const sheet = CSS(({bold})=>{[
  //header
  { color: 'red' }, 
  // dynamic bit there could be multiple ones,
  // keeping it simple for this example
  ()=> bold ? {fontWeight: 'bold'} : {},
  // footer
  { margin: 0 } 
]})
const classList = sheet({bold: true})

This would generate three sheets, inserted in order, with selectors defined as the hash of (source + positional metadata) i.e.

• h1 = hash(header)
• h2 = hash(footer + "after:" + h1)
• h3 = hash(dynamic + "after:" + h1 + "before:" + h2)

and it would return [h1, h2, h3].

When sheet({bold: false}) is invoked, I will only regenerate the dynamic part, and insert the corresponding sheet between the static parts (there's a reference counting and GC bit that a different can of worm, leaving it aside here).

This is where things become tricky if there are more than one dynamic sheets.

It is easy to do in O(1) time with actual <style> elements (just keep a reference to either the element for the static header or footer) but their performance sucks.

Using the CSSOM, I can keep a hash => index map, and when I insert the new dynamic bit I must update the indices of every subsequent StyleRule. Alternatively, I can [].indexOf.call(stylesheet, myStyleRule). Both operations are O(n) with regards to the number of rules, though, and that's bad.

The FrozenArray-based API has the same O(n) time profile. It would be nice to have a O(1) API that is otherwise fast.

With that being said, given how the cascade works, inserting a sheet in the middle of a list probably entails O(n) work in the background no matter what, with a constant factor that dwarfs finding an object in a list or keeping the index up to date entails. In that case, please ignore this.

edit: formatting

edit2: I know that it ties into #45, but that issue is getting long, and I wanted to discuss the big O aspects of the API specifically.

edit3: Even if the engine has to do O(n) work on insertion, said work could be postponed to reflow time, whereas when repainting an SPA, the sheet list could be updated several times. So this may be relevant anyway (e.g. for a large redraw in a SPA), even if the constant factor of the engine is larger.

[bzbarsky]

What range of lengths are we talking about here? My gut feeling is that as long as the number of sheets is "dozens" but not "hundreds" the O(n) vs O(1) bit does not matter that much because the various other overheads dominate...

[pygy]

It really depends on how much CSS there's on the page, and how dynamic the styles end up being.

An O(n) API makes this approach unworkable for larger apps (and thus a non-starter for ambitious projects, even if they start small).

A possible "solution" is to

• create larger classes (based on a hash of the whole sheet)
• not bother counting references, therefore leaking memory
• append the new classes

The drawback is that if the user uses a floating point number as a dynamic variable for some CSS value (because Murphy's law, even though a proper solution would have been a CSS variable), the memory consumption can skyrocket. So that's no solution either. Edit: I guess I could take the "hash the whole sheet" approach, and collect garbage asynchronously. I don't actually have any clue of the perf trade-offs of messing a lot with the cascade to ensure a minimal amount of styles are defined (with several classes per element, some of which are permanent, and some of which change often) vs doing larger grained updates, with a single class change... I'll benchmark, and I'll be back :-)

[bzbarsky]

I'd really like to understand the n involved here and what it represents. Especially because if the browser-internal processing is currently O(n) no matter what (as claimed above), it might be worth seeing what architectural changes could make that better...

[pygy]

n is the number of RuleSets, or the number of sheets in the page.

If you want both an o(1) API for insertions and indexability by number, you must recompute the index before allowing array-like access (that can be done lazily). I suppose that the CSSOM provides an array-like of rules because that is how they are represented internally (but I may be mistaken). Edit: also, in order to compute the cascade, the relative position of relevant rules must be known. I assume that an index is kept internally. Maybe you have a better structure than a plain array though.

I don't know how much pre-processing is invalidated (if any) when a new sheet or rule is added. Since the CSS engines were developed at a time when styles were mostly static, I suppose that optimizations based on that assumption still exist in them.

[bzbarsky]

n is the number of RuleSets, or the number of sheets in the page.

So when you say "RuleSet" you mean some collection of rules, right?

In all the cases I've seen so far the number of sheets in the page is in the "dozens" range (though some of those sheets can have thousands of rules). It sounds like your case is different?

I suppose that the CSSOM provides an array-like of rules because that is how they are represented internally

It provides that because that's a simple and easy to use API for consumers, mostly. Internal representations follow the spec here, not lead, assuming they are consistent.

The actual internal data structures for rules involve sorting by specificity (of the selector, so a single rule can appear in this list multiple times for different selectors it has), then secondarily sorting by order, across all sheets on the page. This is done lazily, with the input being the ordered set of rules from the various sheets; details vary across implementations.

I don't know how much pre-processing is invalidated (if any) when a new sheet or rule is added.

This probably varies across implementations, but "it depends". There are some optimizations for particular kinds of changes, for example, and some things are modified in-place rather than being invalidated; details vary across browsers.

The time-consuming part, though, is not the pre-processing but identifying the set of elements to restyle based on the style change and then restyling them.

Since the CSS engines were developed at a time when styles were mostly static

That time is still now, fwiw. The typical way CSS is used is that the CSS is static (inline style being an important exception), and DOM nodes are mutated to change which rules they match... And yes, CSS engines are generally built around this assumption.