Skip to content

perf: Optimize diff algorithm with insights from #646 #658

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 10 commits into from
Jan 27, 2023
Merged

perf: Optimize diff algorithm with insights from #646 #658

merged 10 commits into from
Jan 27, 2023

Conversation

yihuang
Copy link

@yihuang yihuang commented Jan 11, 2023 •
edited
Loading

it's being running on our testnet, not finished yet, but so far so good, the result is identical to previous version.

EDIT: the task previously takes 19hours to run, now takes 14h20m, not bad.

@yihuang yihuang requested a review from a team January 11, 2023 02:40
@yihuang yihuang changed the title Optimize diff algorithm with insightes from #646 Optimize diff algorithm with insights from #646 Jan 11, 2023
@yihuang yihuang changed the title Optimize diff algorithm with insights from #646 perf: Optimize diff algorithm with insights from #646 Jan 17, 2023
@yihuang
Copy link
Author

yihuang commented Jan 17, 2023 •
edited
Loading

What do you think about this change, @tac0turtle @cool-develope , the existing round-trip test is pretty exhaustive, and I've done complete run on our testnet data, so the correctness should be pretty solid.
ideally can we backport 0.19.x as well ;D

cool-develope
cool-develope reviewed Jan 19, 2023
View reviewed changes
diff.go Outdated
newLeafNodes []*Node
// orphaned leaf nodes in previous version, which represents all deletions and updates.
// both `newLeafNodes` and `orphanedLeafNodes` are ordered by key.
orphanedLeafNodes []*Node
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

for me, newLeaves makes sense than newLeafNodes

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

sounds good, done.

@cool-develope
Copy link
Contributor

I am still worried about the memory usage if we use extractStateChanges for the two versions which are far away.
Could we modify it as an iterator or callback way?

@yihuang
Copy link
Author

yihuang commented Jan 19, 2023

I am still worried about the memory usage if we use extractStateChanges for the two versions which are far away. Could we modify it as an iterator or callback way?

I'll see what I can do.

@tomtau tomtau mentioned this pull request Jan 26, 2023
Merged
13 tasks
@yihuang
Copy link
Author

yihuang commented Jan 26, 2023

I am still worried about the memory usage if we use extractStateChanges for the two versions which are far away. Could we modify it as an iterator or callback way?

done, it's still not strictly constant memory, but I guess it's the best we can do here.

@yihuang yihuang requested a review from cool-develope January 26, 2023 10:48
yihuang
yihuang commented Jan 26, 2023
View reviewed changes
cool-develope
cool-develope approved these changes Jan 26, 2023
View reviewed changes
Copy link
Contributor

@cool-develope cool-develope left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM!

@yihuang
Copy link
Author

yihuang commented Jan 26, 2023

can we backport to 0.19.x @tac0turtle

@tac0turtle tac0turtle merged commit c90c009 into cosmos:master Jan 27, 2023
@tac0turtle
Copy link
Contributor

@Mergifyio backport release/v0.19.x

@mergify mergify bot mentioned this pull request Jan 27, 2023
Merged
@mergify
Copy link
Contributor

mergify bot commented Jan 27, 2023

backport release/v0.19.x

✅ Backports have been created

mergify bot pushed a commit that referenced this pull request Jan 27, 2023
@tac0turtle @mergify
perf: Optimize diff algorithm with insights from #646 (#658)
c78396a 
Co-authored-by: Marko <marbar3778@yahoo.com>
(cherry picked from commit c90c009)
tac0turtle pushed a commit that referenced this pull request Jan 27, 2023
@mergify
perf: Optimize diff algorithm with insights from #646 (backport #658) (…
a5366e7 
…#665)

Co-authored-by: yihuang <huang@crypto.com>
@yihuang yihuang deleted the optim_diff branch January 27, 2023 13:58
ankurdotb pushed a commit to cheqd/iavl that referenced this pull request Feb 28, 2023
@mergify @ankurdotb
perf: Optimize diff algorithm with insights from cosmos#646 (backport c…
73e787d 
…osmos#658) (cosmos#665)

Co-authored-by: yihuang <huang@crypto.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
1 more reviewer

@cool-develope cool-develope cool-develope approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees

@cool-develope cool-develope

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@yihuang @cool-develope @tac0turtle