IGListKit
IGListKit copied to clipboard
Instagram
Implements experimental diff with optimized moves calculation to produce only minimal required moves
Changes in this pull request
Previously diff calculation resulted in redundant list of moves, for example diff for the following array pair: [ 0, 1, 2, 3, 4, 5 ] [ 5, 0, 1, 2, 3, 4 ]
produced moves: 5-0, 0-1, 1-2, 2-3, 3-4, 4-5
while the only required move was 5-0.
This leads to inefficient updates both by computation and memory consumption. This may also cause crashes in UICollactionView or UITableView batch updates.
Checklist
- [x] All tests pass. Demo project builds and runs.
- [x] I added tests and an experiment.
- [x] I added an entry to the
CHANGELOG.mdfor the enhancement. - [x] I have reviewed the contributing guide
| 1 Warning | |
|---|---|
| :warning: | All pull requests should have a milestone attached, unless marked #trivial. |
Generated by :no_entry_sign: Danger
This is pretty incredible! Really excited to test this out. Before I dive too deep on the technical details, I'd love to first config this so that we can run an A/B test on it to measure performance gains (or losses) in Instagram.
- Add an entry to the experiments options
- In the diffing algo, check the mask for this experimental feature
- If exists, do these move calculations
- Otherwise, fallback to previous versions
I know its a little more work, but it'll give us evidence to how much memory and compute time this was taking. Not to mention giving us an escape hatch if something goes wrong.
@rnystrom Here you go. It was quite a challenge to achieve this with a reasonable design, as I have very little experience with C++, so any suggestions for improvements are welcome.
Finally had a chance to run this in our project. Found a flaw in the algorithm which is now fixed, also the algorithm has become much simpler.
@tarbayev Can you rebase again onto the latest master? I am having issue importing this PR, thanks!
@TimOliver has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator.
@TimOliver has imported this pull request. If you are a Meta employee, you can view this diff on Phabricator.
@tarbayev Hi Nickolay! Sorry for the delay in getting back to you on this PR. I think this still has some value and I'd love to get it merged into IGListKit. Are you still open to that?
I'm happy to take what you've added here and rebase it myself if you're okay with that, and don't want to spend anymore time on it.
Thanks!
@TimOliver Hi Tim, At some point I decided to make a Swift version of the algorithm, which I called OptiDiff and also improved and simplified it quite a lot. Hence I don't want to spend any more time on this PR, but you're free to merge it as well as make a C++ implementation of the OptiDiff if you like.
Sen MİT için çalışıyorsun suçu bana mı attın dark bunu sevmedi
iPhone’umdan gönderildi
Tim Oliver @.***> şunları yazdı (8 May 2023 05:13):
@tarbayevhttps://github.com/tarbayev Hi Nickolay! Sorry for the delay
— Reply to this email directly, view it on GitHubhttps://github.com/Instagram/IGListKit/pull/1139#issuecomment-1537642717, or unsubscribehttps://github.com/notifications/unsubscribe-auth/A7KYAEHSVXBABQN3HD2P3MLXFBJC5ANCNFSM4EXVAFRQ. You are receiving this because you are subscribed to this thread.Message ID: @.***>
Yanlış yere daldın yüzme bilmiyorsun 😰
iPhone’umdan gönderildi
Nickolay Tarbayev @.***> şunları yazdı (8 May 2023 11:59):
@TimOliverhttps://github.com/TimOliver Hi Tim, At some point I decided to make a Swift version of the algorithm, which I called OptiDiffhttps://github.com/tarbayev/OptiDiff) and also improved and simplified it quite a lot. Hence I don't want to spend any more time on this PR, but you're free to merge it as well as make a C++ implementation of the OptiDiff if you like.
— Reply to this email directly, view it on GitHubhttps://github.com/Instagram/IGListKit/pull/1139#issuecomment-1538009444, or unsubscribehttps://github.com/notifications/unsubscribe-auth/A7KYAEH3PDJKKBARRFRSWNTXFCYVHANCNFSM4EXVAFRQ. You are receiving this because you are subscribed to this thread.Message ID: @.***>