feat: iterableEquals performance optimizations
#203
Conversation
|
Would you mind running the benchmarks before and after and including the results in the description? |
|
Done, and I've refactored the comments so the build respect lint rules |
|
I've added tests for the Queues to cover all cases. |
Thanks! I’ll review later today 🙏 |
| expect(iterableEquals(queue1, queue2), isTrue); | ||
| }); | ||
|
|
||
| test('returns false for two different Queues', () { |
There was a problem hiding this comment.
I'd also add a third queue with a different length just to make sure that case is correctly handled.
iterableEquals performance optimizations
|
@Danilospano00 I just took a closer look and it looks like when you run in AOT, there is actually a regression. Before: After:
|
|
Need to profile it more to see what's going on but I don't think we should ship a regression in AOT so I think this needs a bit more tweaking before it's ready to merge. |
Status
READY
Breaking Changes
NO
Description
This PR optimizes the iterableEquals function to improve performance when comparing List types by using direct indexing. It also ensures efficient comparison for other Iterable types using iterators, while maintaining the function's compatibility with various iterable structures.
Todos
Steps to Test or Reproduce
Steps to Test or Reproduce
The updated iterableEquals function improves performance by handling List types separately.
Old Version: Uses elementAt(i) for all Iterable types, which is efficient only for List. For other iterables like LinkedList or Queue, elementAt(i) can be inefficient (O(n)), potentially leading to O(n²) performance for large iterables.
New Version: Specifically optimizes List comparison by using direct indexing (O(1)), making it faster for lists. For other Iterable types, it uses iterators, ensuring linear time complexity (O(n)) for all cases. This avoids the performance bottleneck of elementAt(i).
In summary, the new version is more efficient, especially for List types, and ensures better performance for all Iterable structures by using the appropriate methods for each.
Benchmark on MAC m3:
Before
After