5 ms·

How does ImmutableJS work? If it was turned into a straight list of immutable records, each comparison would be quicker but the complexity would remain the same

How does ImmutableJS work? If it was turned into a straight list of immutable records, each comparison would be quicker but the complexity would remain the same. You'd have to something like turn it into a tree to reduce the complexity.

rakoo 11y ago
With ImmutableJS, the first N records won't be compared at all because they're the same. Thus, if the time is spent in comparing the change in states as you implied, the comparison will be much quicker, and React will essentially not care about the already existing photos (as in, will not spend time there) but just create new ones. As someone else pointed out, the render function is another interesting part where time can most likely be wasted. Unfortunately there's no way for us to know more.
- ajanuary 11y ago
  It still needs to compare them, it will just do a reference comparison rather than a deep comparison on the fields. So again, it will be (a lot) quicker, but the complexity is still the same.
  - i_s 11y ago
    Yeah, but if you chunk the items (groups of 10, lets say) in components, you can return false from shouldComponentUpdate in all but the last component, and therefore be fast.
    - ajanuary 11y ago
      Yup, there is a bunch of things you can do to reduce the constants, but even with chunking the computational complexity is the same. In this case, it's not hard to reduce the constants to a point where the complexity doesn't really matter though.
      - BFay 11y ago
        Is the complexity actually quadratic, like amelius said? The diffing operation is linear according to React documentation: https://facebook.github.io/react/docs/reconciliation.html https://facebook.github.io/react/docs/reconciliation.html Is Array.prototype.concat linear, too? What about the ImmutableJS equivalent? I don't know a whole lot about algorithms, my intuition is that there would be a way to add an item to the end of the array without traversing the entire thing, but I guess it all depends on how the data structure is implemented.
        ajanuary 11y ago
        I've been pretty vague which probably isn't very helpful so I'll try to be a bit more precise: for a mutable implementation it's quadratic in the number of times render is called over the lifetime of the component; for an immutable implementation it's quadratic in the number of comparisons (inside shouldComponentUpdate) over the same lifetime. You can generalize both operations to "process component when building the component tree". Each time you add an item to a list of size n, it needs to process the previous n items. This forms the series 1+2+...+(n-1)+n, which is (n^2+n)/2. Obviously a reference comparison is a lot quicker than a render, so you get big speed wins using immutablejs that are definitely worth it, but it's still O(n^2) components processed.
        i_s 11y ago
        A component being processed via returning false from shouldComponentUpdate is very very different from a component being processed by running the render method and then doing a diff, so that is not a good model.
      - i_s 11y ago
        No it isn't, I'm talking about avoiding render computation, and then therefore the diffing. If 1 render method gets called that contains 10 elements, and 99 other render methods are not called because of returning false from shouldComponentUpdate, that is very different than 1 render method getting called with 1000 elements, and it is not just in the constants.
  - augustl 11y ago
    You're right. And there's no way around that other than not actually rendering more items than what are visible on the screen. Which is darn difficult on the web due to lack of APIs..
dugmartin 11y ago
ImmutableJS's lists are collections which are implemented behind the scenes as trees. When you append to an immutable list a new list is returned so the comparison in shouldComponentUpdate() becomes simply a reference comparison between the old and new list (return nextState.list !== this.state.list).
- ajanuary 11y ago
  That doesn't help reduce the computational complexity in this instance. After appending, the lists are different, so it renders the component, which starts iterating the children and checking each one in turn to see if it's changed. To reduce the computational complexity you'd need to do something like walking the tree that backs the list instead, so you can ask it "did any of the children under this node change?" which means you can start skipping the comparisons for big chunks of the list. I don't know if react and immutable.js can be combined in this way without significantly rewriting you or components. I suspect not.

rakoo 11y ago

With ImmutableJS, the first N records won't be compared at all because they're the same. Thus, if the time is spent in comparing the change in states as you implied, the comparison will be much quicker, and React will essentially not care about the already existing photos (as in, will not spend time there) but just create new ones. As someone else pointed out, the render function is another interesting part where time can most likely be wasted. Unfortunately there's no way for us to know more.

ajanuary 11y ago
It still needs to compare them, it will just do a reference comparison rather than a deep comparison on the fields. So again, it will be (a lot) quicker, but the complexity is still the same.
- i_s 11y ago
  Yeah, but if you chunk the items (groups of 10, lets say) in components, you can return false from shouldComponentUpdate in all but the last component, and therefore be fast.
  - ajanuary 11y ago
    Yup, there is a bunch of things you can do to reduce the constants, but even with chunking the computational complexity is the same. In this case, it's not hard to reduce the constants to a point where the complexity doesn't really matter though.
    - BFay 11y ago
      Is the complexity actually quadratic, like amelius said? The diffing operation is linear according to React documentation: https://facebook.github.io/react/docs/reconciliation.html https://facebook.github.io/react/docs/reconciliation.html Is Array.prototype.concat linear, too? What about the ImmutableJS equivalent? I don't know a whole lot about algorithms, my intuition is that there would be a way to add an item to the end of the array without traversing the entire thing, but I guess it all depends on how the data structure is implemented.
      - ajanuary 11y ago
        I've been pretty vague which probably isn't very helpful so I'll try to be a bit more precise: for a mutable implementation it's quadratic in the number of times render is called over the lifetime of the component; for an immutable implementation it's quadratic in the number of comparisons (inside shouldComponentUpdate) over the same lifetime. You can generalize both operations to "process component when building the component tree". Each time you add an item to a list of size n, it needs to process the previous n items. This forms the series 1+2+...+(n-1)+n, which is (n^2+n)/2. Obviously a reference comparison is a lot quicker than a render, so you get big speed wins using immutablejs that are definitely worth it, but it's still O(n^2) components processed.
        i_s 11y ago
        A component being processed via returning false from shouldComponentUpdate is very very different from a component being processed by running the render method and then doing a diff, so that is not a good model.
    - i_s 11y ago
      No it isn't, I'm talking about avoiding render computation, and then therefore the diffing. If 1 render method gets called that contains 10 elements, and 99 other render methods are not called because of returning false from shouldComponentUpdate, that is very different than 1 render method getting called with 1000 elements, and it is not just in the constants.
- augustl 11y ago
  You're right. And there's no way around that other than not actually rendering more items than what are visible on the screen. Which is darn difficult on the web due to lack of APIs..

dugmartin 11y ago

ImmutableJS's lists are collections which are implemented behind the scenes as trees. When you append to an immutable list a new list is returned so the comparison in shouldComponentUpdate() becomes simply a reference comparison between the old and new list (return nextState.list !== this.state.list).

ajanuary 11y ago
That doesn't help reduce the computational complexity in this instance. After appending, the lists are different, so it renders the component, which starts iterating the children and checking each one in turn to see if it's changed. To reduce the computational complexity you'd need to do something like walking the tree that backs the list instead, so you can ask it "did any of the children under this node change?" which means you can start skipping the comparisons for big chunks of the list. I don't know if react and immutable.js can be combined in this way without significantly rewriting you or components. I suspect not.