casouri / vundo

Visualize the undo tree.
413 stars 20 forks source link

Avoid O(n^2) list lookups in vundo--mod-list-from #21

Closed ideasman42 closed 2 years ago

ideasman42 commented 2 years ago

Loop over all list items without using index lookups since large indices require stepping over all prior elements each time.


Although I didn't run into a bottleneck here, in general I try to avoid O(n^2) complexity unless the size of lists is known ahead of time to be under a fixed size. For undo data though it can be quite large, especially when undo data is saved to disk between editing files.

Note that I realize this is somewhat personal preference as it can be convenient to treat this as in indexed array, however I think the pros outweigh the cons in this case particular case.

If indexing elements is preferred an alternative to this patch could be to create vector from the list so looking up very large lists doesn't risk running into performance bottlenecks.

casouri commented 2 years ago

Thanks, that's a good catch. I'm happy to merge this.

casouri commented 2 years ago

Merged (with changes).