Skip to content

BUG: O(n²) bubble sort in fetcher batch ordering #1080

@andrinoff

Description

@andrinoff

Describe the bug

fetcher/fetcher.go:505-511 sorts each batch by UID using nested loops:

for i := 0; i < len(batchEmails); i++ {
    for j := i + 1; j < len(batchEmails); j++ {
        if batchEmails[j].UID > batchEmails[i].UID {
            batchEmails[i], batchEmails[j] = batchEmails[j], batchEmails[i]
        }
    }
}

Quadratic on every batch. The default chunk size is 50 so it's not catastrophic, but with a larger limit it becomes the dominant cost of the fetch.

Expected behavior

Replace with sort.Slice(batchEmails, func(i, j int) bool { return batchEmails[i].UID > batchEmails[j].UID }).

Metadata

Metadata

Assignees

Labels

bugSomething isn't workinggood first issueGood for newcomers

Type

No type

Projects

Status

Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions