Performance improvements for Calendar.RecurrenceRule

[hristost]

Currently, we compute recurrences of dates by using the API for matching date components. Although this works well, we also end up creating multiple sequences for matching date components for cases where a single sequence would suffice. This is by design: since each field of the recurrence rule can have multiple values (e.g. an event repeating Tuesdays and Fridays), we can not represent these in a single DateComponents.

For some cases, this results in up to 4x runtime penalty for finding recurrences as opposed to using Calendar.dates(byMatching:). In the benchmark below computing the next thousand Thanksgivings, we have:

• one base sequence to find yearly recurrences of a date (e.g. June 10 2024, June 10 2025)
• for each yearly recurrence, we use Calendar.nextDate(after:, matching:) to find a date in the month of November. (e.g. November 10 2024, November 10 2025)
• for each date in November, we use component matching to find the fourth Thursday.

This results in a lot of redundant calculations. Since we also own enumerating by date components, we can use some of the internals to more efficiently calculate recurrences of dates, as opposed to using only public API.

Benchmarks for finding the next thousand Thanksgivings

nextThousandThanksgivings
╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕
│ Metric                    │      p0 │     p25 │     p50 │     p75 │     p90 │     p99 │    p100 │ Samples │
╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡
│ Malloc (total) *          │     426 │     426 │     426 │     426 │     426 │     426 │     426 │       6 │
├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ Throughput (# / s) (K)    │       2 │       2 │       2 │       2 │       2 │       2 │       2 │       6 │
├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ Time (total CPU) (μs) *   │     580 │     581 │     581 │     583 │     583 │     583 │     583 │       6 │
├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ Time (wall clock) (μs) *  │     582 │     584 │     584 │     586 │     586 │     586 │     586 │       6 │
╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛

nextThousandThanksgivingsUsingRecurrenceRule
╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕
│ Metric                    │      p0 │     p25 │     p50 │     p75 │     p90 │     p99 │    p100 │ Samples │
╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡
│ Malloc (total) *          │     861 │     861 │     861 │     861 │     861 │     861 │     861 │       2 │
├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ Time (total CPU) (μs) *   │    2121 │    2121 │    2121 │    2129 │    2129 │    2129 │    2129 │       2 │
├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│ Time (wall clock) (μs) *  │    2135 │    2136 │    2136 │    2140 │    2140 │    2140 │    2140 │       2 │
╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛

[hristost]

rdar://126761035