Different approach to calculating recurrences

[douglm]

Others may already have approached this issue in some manner...

Bedework - along with a number of implementations - precalculates a fixed number of recurrence instances for indexing. For the web service a lot of time is spent delivering date limited ranges of expanded recurrences.

Theoretically I could expand on retrieval but retrievals within a time-range work very fastwith indexed instances that way and it makes filtering easy.

For a recurrence master I do calculate the latest instance and index that value along with the master so it always shows up in searches.

The down side of this is

1. the amount of time it takes when adding/updating and
2. It imposes limits on the recurrence.

I just reindexed a large set of data and calculating recurrences takes 5-10% of the cpu.

If I were to try to do that on retrieval I have to work my way from the start and go through increasingly large amounts of instances till I reach the date range.

There are some ways to mitigate - on indexing add a bunch of checkpoints and start the process from the closest preceding. This might actually increase my indexing time slightly but I wouldn't need the instances to be stored.

However, maybe there are ways to figure out such a checkpoint almost immediately from the rules.

As a first step adding a list of checkpoints to the master would help. Currently recur just increments the seed (which currently is always the master start until it's not before the period start. For weekly events over years this is an increasingly heavy load.

The seed MUST be a valid time/date according to the rules and master start. Would it be possible to speed up the above process by making multiple steps at once, e.g if it's weekly and the period start is a year from now can we jump 50 weeks say? Does DST and leap years have some effect here etc?

The checkpoint calculation doesn't have to create a valid instance - just a valid start point. exdates, multiple rrules and overrides all get applied later. And the checkpoints would need to be associated with each rrule.

I'm hoping someone will tell me I missed something obvious...

[benfortuna]

I'm not sure if it's relevant to mention, as I haven't really explored generation of large amounts of recurrences, but we did add support for Java streams in iCal4j recurrence calculation:

Recurl.getDatesAsStream()

This MAY be more efficient than iterating through a large number of instances for a given date range, as a quick example I've added a test that filters the final year of a 30 year date range:

https://github.com/ical4j/ical4j/blob/develop/src/test/groovy/net/fortuna/ical4j/model/RecurSpec.groovy#L500