Improve performance of icalendar-recur.el and its tests

As discussed in Bug#80520.

* test/lisp/calendar/icalendar-recur-tests.el
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/3)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/29)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/30)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/31)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/33)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/34)
(icalendar-test-rrule-test-rfc5545-sec3.8.5.3/38): Mark tests expensive.

Abstract the implementation of intervals in icalendar-recur.el.  Don't
store interval NEXT-LOW when it's the same as HIGH.  This reduces
allocations, and shaves about ~20% off the full test suite.

* lisp/calendar/icalendar-recur.el
(icalendar-recur-make-interval)
(icalendar-recur-interval-low)
(icalendar-recur-interval-high)
(icalendar-recur-interval-next): Implement intervals and subintervals as
vectors.  Only store NEXT-LOW when it's non-nil.
(icalendar-recur-find-absolute-interval)
(icalendar-recur-find-daily-interval)
(icalendar-recur-find-weekly-interval)
(icalendar-recur-find-monthly-interval)
(icalendar-recur-find-yearly-interval)
(icalendar-recur-next-interval)
(icalendar-recur-previous-interval)
(icalendar-recur-refine-byyearday)
(icalendar-recur-refine-byweekno)
(icalendar-recur-refine-bymonth)
(icalendar-recur-refine-bymonthday)
(icalendar-recur-refine-byday)
(icalendar-recur-refine-byhour)
(icalendar-recur-refine-byminute)
(icalendar-recur-refine-bysecond)
(icalendar-recur-subintervals-to-date-times)
(icalendar-recur-subintervals-to-dates)
(icalendar-recur-recurrences-in-interval)
(icalendar-recur-recurrences-in-window)
(icalendar-recur--key-from-interval): Use new interval constructor and
accessors.  Don't generate NEXT-LOW when it's the same as HIGH.
* lisp/calendar/icalendar-utils.el (icalendar-dates-until): Use new
interval constructor and accessors.
* test/lisp/calendar/icalendar-recur-tests.el
(icalendar-test-recur-find-secondly-interval)
(icalendar-test-recur-find-minutely-interval)
(icalendar-test-recur-find-hourly-interval)
(icalendar-test-recur-find-daily-interval-w/date)
(icalendar-test-recur-find-daily-interval-w/date-time)
(icalendar-test-recur-find-weekly-interval-w/date)
(icalendar-test-recur-find-weekly-interval-w/date-time)
(icalendar-test-recur-find-monthly-interval)
(icalendar-test-recur-find-yearly-interval)
(icalendar-test-recur-refine-byyearday)
(icalendar-test-recur-refine-bymonth)
(icalendar-test-recur-refine-bymonthday)
(icalendar-test-recur-refine-byday)
(icalendar-test-recur-refine-byhour)
(icalendar-test-recur-refine-byminute)
(icalendar-test-recur-refine-bysecond)
(icalendar-test-recur-subintervals-to-dates)
(icalendar-test-recur-subintervals-to-date-times)
(icalendar-test-rrule-test): Use new interval constructor and accessors.

Rearrange loops when refining subintervals, so that the loop always runs
once but doesn't run a second no-op iteration.  Astonishingly this cuts
the running time of the full test suite by almost 50%.

* lisp/calendar/icalendar-recur.el (icalendar-recur-refine-byyearday)
(icalendar-recur-refine-byweekno)
(icalendar-recur-refine-bymonth)
(icalendar-recur-refine-bymonthday)
(icalendar-recur-refine-byday)
(icalendar-recur-refine-byhour)
(icalendar-recur-refine-byminute)
(icalendar-recur-refine-bysecond): Tighten up loop bounds when refining
subintervals.

Improve performance of `icalendar-recur-tz-observance-on'.  This also
brings about a ~20% performance gain.

* lisp/calendar/icalendar-recur.el
(icalendar-recur-tz-observance-on): Eliminate calculation of previous
interval recurrences when it's unnecessary.  Add a cheap upper bound check to
prevent fully computing recurrences for irrelevant observances.
(icalendar-recur--w/in-locally-p):
(icalendar-recur--w/in-abs-p): New helper functions for the upper bound check.

Other more minor changes:

Improve performance in `icalendar-recur-refine-byday'

* lisp/calendar/icalendar-recur.el (icalendar-recur-refine-byday): Avoid
calculating Gregorian from absolute date unless it's necessary.

Improve performance of BYSETPOS filtering in icalendar-recur.el:
η-reduce `icalendar-recur-make-bysetpos-filter'.
Thanks to Mattias Engdegård for the suggestion and implementation.

* lisp/calendar/icalendar-recur.el
(icalendar-recur-make-bysetpos-filter): Rename to
`icalendar-recur-bysetpos-filter' and avoid `seq-map-indexed'.
(icalendar-recur-recurrences-in-interval): Use new function.
* test/lisp/calendar/icalendar-recur-tests.el
(icalendar-test-recur-bysetpos-filter): Use new function.

Improve sorting performance:
Thanks to Mattias Engdegård for the suggestion and implementation.

* lisp/calendar/icalendar-recur.el (icalendar-recur-refine-byyearday):
(icalendar-recur-refine-byweekno):
(icalendar-recur-refine-bymonthday):
(icalendar-recur-refine-byday): Use :key instead of :lessp in `sort'
calls.

Eliminate `apply-partially' and `seq-take':
Thanks to Mattias Engdegård for the suggestion and implementation.

* lisp/calendar/icalendar-recur.el
(icalendar-recur-recurrences-in-window): Eliminate `apply-partially'.
(icalendar-recur-recurrences-in-interval): Eliminate
`apply-partially' and replace `seq-take' with `take'.

Reduce consing:

* lisp/calendar/icalendar-recur.el
(icalendar-recur-subintervals-to-dates):
(icalendar-recur-recurrences-in-window):
(icalendar-recur-recurrences-in-window-w/end-times):
(icalendar-recur-recurrences-to-count): Replace `append' with `nconc'.

Avoid a few uses of `seq-filter' in common functions in icalendar-ast.el:

* lisp/calendar/icalendar-ast.el (icalendar-ast-node-children-of):
Reimplement filter imperatively.

0 files changed, 0 insertions, 0 deletions