3 ms·
Which same thing do you mean? I read your very interesting longer comment below, and you mentioned a lot of differences, and it's not clear which of them you m
by kragen 5y ago
Which same thing do you mean? I read your very interesting longer comment below, and you mentioned a lot of differences, and it's not clear which of them you mean arbitrary UI element sizes with scrollable overflow requires you to do. Do you mean that it requires you to use very slow layout algorithms? Maybe the problem there is that CSS wasn't designed to be efficiently implementable; I feel like CSS doesn't usually give me better layouts than LaTeX, which runs orders of magnitude faster than any CSS engine.
Is there a specific reason that scrollable overflow (rather than visible or hidden, which TeX can do) inherently makes the problem much harder than what TeX does? Naively I'd think making the overflow scrollable wouldn't affect the computational complexity at all, but clearly I know a lot less about the space than you do. Are there other things in CSS that are very useful for UI layout but very difficult to implement with submillisecond timing guarantees?
As I understand it, for example, iOS UI autolayout uses Cassowary, which uses the simplex algorithm and I think may at a better point in the expressiveness/performance tradeoff space than CSS. (Hilariously in this context, the original Cassowary paper https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf https://constraints.cs.washington.edu/solvers/cassowary-toch... has an overfull hbox.) But Cassowary is from 02002, and there have been a lot of advancements in constraint solving and optimization algorithms in the last 19 years, both in theory and in practice:
• Z3 wasn't released until 02012;
• SAT/SMT solvers in general have gotten astoundingly better (the SAT Competition started in 02002);
• there have been enormous advances in conic optimization (overview in https://arxiv.org/abs/1709.08841 https://arxiv.org/abs/1709.08841), including open-source libraries like CVXOPT that are widely used (in the context of conic optimization, anyway);
• for more general optimization, automatic differentiation has gone mainstream; and
• there have been huge advances in gradient-descent variants including AdaGrad (02011), RMSprop (02014?), and Adam (02014).
In general, gradient-descent solvers and the interior-point methods often used for conic optimization are anytime algorithms, so you can trade off responsiveness against stability/correctness. If your layout algorithm hasn't converged by the frame deadline, you can just draw the best layout it's come up with so far; it's guaranteed to have all the right stuff in it, just maybe overlapping or in the wrong place, probably only by a few pixels, and displaying something is often better than displaying nothing. The conic optimization algorithms can also guarantee that the layout they deliver is "feasible" in the sense of respecting all the hard constraints in the constraint set; it might just be suboptimal. (Gradient-descent algorithms don't really have hard constraints; they have to simulate them by adding heavy penalties to the loss function.)
I don't know of anybody actually applying this stuff to UI layout; do you?
- andrewmcwatters 5y agoI would say the most labor intensive aspect is that indefinite element boundaries require you to pretty much have backing layers that are tiled, or if you're OK with the trade off, because sometimes it is OK, to limit elements with scrollable panels to the viewport size, since that's generally what happens with framebuffers or rendertarget graphics APIs, I believe. You also don't always get to receive texture sizes based on your request, so you have to waste some space using power of 2 sizes sometimes. Yeah, layout algorithms add a lot of overhead and even the fastest ones today still add significant overhead that you have to account for versus manually placing elements by coordinates, scaled or not. I think TeX is faster generally speaking since it is concerned with fewer dimensions of layout. This is really what you want for a fast layout engine, but not what designers want for really rich UIs. It's hard for me to compare this without intuitively knowing it to be true, because I would need to measure the actual amount of layout CPU cycles, roughly, to get a sense of how efficient one over the other is. I'm not really sure about whether CSS inherently produces slower layouts. I wouldn't assume it would, but rather that specific portions of the box model are difficult or not possible to parallelize, and as a result become an obvious bottleneck. Scrollable overflows aren't inherently slow, although if you have internal target spaces that dynamically change in size very frequently, you would, as one would expect, be thrashing any allocated single framebuffers for that visible space if you took that strategy over tiled rendering. The best things about layouts in CSS is that CSS 2.1 is so old, everyone has been exposed to it a little bit, even if they can't formally implement it themselves. Developers generally have a little bit of a sense of what display properties do. That same oldness of CSS 2.1 unfortunately means that the algorithm for box layout hasn't been revisited by many people. If you took every person in the world who had actually implemented a significant portion of the box model rasterizer, we wouldn't easily fill a room. It's basically descriptive, and left as an exercise to the author to implement. People gave Microsoft a really hard time over this, understandably, but if you gave it a go yourself, you'd understand why. I'm unfortunately not intimately knowledgeable with Cassowary from an implementation point of view, but I have observed its design and would be very interested to see it placed side by side with a reference implementation of the box model layout, and flexbox in particular, but no one has created such an agnostic rasterizer platform to my knowledge other than browser authors themselves. I'd love to see more constraint solvers in the wild! We really need some variety out here. I believe some people in the WHATWG have been working on a standard to expose layout events to JavaScript, so maybe we'll have something a little bit more native than Cassowary implemented with JavaScript and `position: absolute` (which is totally an OK override to implement your own layout algorithm!). So while I am not aware of anyone applying this today, I do actively see the foundations making it possible. Anyway, basically game UIs use VBOs and no compositing, or viewport dimension constrained framebuffers and a lot of textures. Both of those strategies are nothing like the web, because the web uses tiled backing layers since you never know what a web developer is going to do. Are they going to create a 10000 pixel high rasterized document fragment? No idea. But if we don't tile it, it happens in software. That's slow, so no one does that anymore. The foundational difference in game UIs is usually in whether or not you're pushing a bunch of vertices and color data to the GPU alongside usually Freetype rasterized type, or a bunch of textures and color data alongside Freetype rasterized type. Yes, I know textures are accompanied by vertex data, too, but the general idea is that you're either reusing that texture data to do cool things like blurs, or you're not, and that's the gist of compositing, which is slow, but pretty. With browsers you make a bunch of usually 256 or 512(?) px wide and tall tiles, where geometry intersects you run some graphics commands that help draw that portion of the UI, and that's how your compositor works instead. I'm not sure what the industry has measured the ideal tile size to be these days, but I know that's on the mind of engineers, since you want to minimize redraw as much as possible.