7 ms·

Can you explain the assertion that DOM rendering is O(1)?

by z3ugma 11y ago

amelius 11y ago
Of course. For example, suppose that there is a button in your UI that changes color whenever you click on it. Changing the color of that button in response to a click can be done in a simple Javascript function that takes O(1) time. However, doing it the React way, all buttons on the screen have to be traversed, O(N), and diff/patched into a new DOM, which is heuristically O(1). However O(N+1) = O(N), so React takes O(N) time for something that can be done in O(1) time. Now, while React may still be fast enough in practice, I can't understand why computer scientists find the situation acceptable. It feels like using bubble sort instead of quicksort or mergesort because you expect your problem space to never grow.
- Callmenorm 11y ago
  I think its because there are tradeoffs for managing the complexity yourself. Using this same argument most abstractions which have performance overhead should be unacceptable. There are tradeoffs everywhere and I guess this is one that a lot of people have accepted.
  - amelius 11y ago
    See https://news.ycombinator.com/item?id=10219678 https://news.ycombinator.com/item?id=10219678
- exogen 11y ago
  It's because anyone who has done any complex web app development knows that you don't have one button changing color. You have 100+ UI components whose state may depend on one another, and as the DOM nodes composing those UI elements get state attached to them, it's EXTREMELY easy for them to both (1) get out of sync, and (2) thrash and re-render entire trees of the DOM unnecessarily. This is a real thing that happens frequently and is why people think JavaScript causes pages to be slow and janky. React lets developers pretend they CAN just re-render entire DOM trees from scratch without those consequences, as if they were serving up a fresh server-side render of the page. Also, suggesting that before React, web apps were updating all their DOM nodes in O(1) time is insane – even if it's not the absolute fastest, why does it compare so favorably in actual tests, then?
  - amelius 11y ago
    Yes, I understand all of this. It can work for small websites. However, the technique cannot uphold for larger systems. For example, consider writing a word-processor using this style of programming. If the user is writing a 10-chapter book, and every character entered by the user requires a visit of all characters in the book, that is not very usable. So even from a practical viewpoint (not just theoretical) it is not workable. Also, consider adding items in a streaming fashion (one-by-one). If there are N items to be added, then the amount of items visited by this scheme is 1+2+3+...+N, which amounts to O(N^2). This is quite ridiculous. Also don't forget about power consumption, which is of course very important for mobile applications. Finally, The solution is not satisfactory from an intellectual viewpoint. Instead of trying to be smart, we are lazy, and abuse abstractions to make our lives easier, and at the same time our software behave slower (especially now that progress in speedwise performance in hardware seems to have stopped).
    - anezvigin 11y ago
      > For example, consider writing a word-processor using this style of programming. Quip uses React.

Can you explain the assertion that DOM rendering is O(1)?

by z3ugma 11y ago

Can you explain the assertion that DOM rendering is O(1)?

Of course. For example, suppose that there is a button in your UI that changes color whenever you click on it. Changing the color of that button in response to a click can be done in a simple Javascript function that takes O(1) time. However, doing it the React way, all buttons on the screen have to be traversed, O(N), and diff/patched into a new DOM, which is heuristically O(1). However O(N+1) = O(N), so React takes O(N) time for something that can be done in O(1) time. Now, while React may still be fast enough in practice, I can't understand why computer scientists find the situation acceptable. It feels like using bubble sort instead of quicksort or mergesort because you expect your problem space to never grow.

Callmenorm 11y ago
I think its because there are tradeoffs for managing the complexity yourself. Using this same argument most abstractions which have performance overhead should be unacceptable. There are tradeoffs everywhere and I guess this is one that a lot of people have accepted.
- amelius 11y ago
  See https://news.ycombinator.com/item?id=10219678 https://news.ycombinator.com/item?id=10219678
exogen 11y ago
It's because anyone who has done any complex web app development knows that you don't have one button changing color. You have 100+ UI components whose state may depend on one another, and as the DOM nodes composing those UI elements get state attached to them, it's EXTREMELY easy for them to both (1) get out of sync, and (2) thrash and re-render entire trees of the DOM unnecessarily. This is a real thing that happens frequently and is why people think JavaScript causes pages to be slow and janky. React lets developers pretend they CAN just re-render entire DOM trees from scratch without those consequences, as if they were serving up a fresh server-side render of the page. Also, suggesting that before React, web apps were updating all their DOM nodes in O(1) time is insane – even if it's not the absolute fastest, why does it compare so favorably in actual tests, then?
- amelius 11y ago
  Yes, I understand all of this. It can work for small websites. However, the technique cannot uphold for larger systems. For example, consider writing a word-processor using this style of programming. If the user is writing a 10-chapter book, and every character entered by the user requires a visit of all characters in the book, that is not very usable. So even from a practical viewpoint (not just theoretical) it is not workable. Also, consider adding items in a streaming fashion (one-by-one). If there are N items to be added, then the amount of items visited by this scheme is 1+2+3+...+N, which amounts to O(N^2). This is quite ridiculous. Also don't forget about power consumption, which is of course very important for mobile applications. Finally, The solution is not satisfactory from an intellectual viewpoint. Instead of trying to be smart, we are lazy, and abuse abstractions to make our lives easier, and at the same time our software behave slower (especially now that progress in speedwise performance in hardware seems to have stopped).
  - anezvigin 11y ago
    > For example, consider writing a word-processor using this style of programming. Quip uses React.