Overlapping ExRule and RRule causes really bad performance

[wangjohn]

I've run into an issue where overlapping RRules and ExRules cause really poor performance. I'm not sure there's much to be done here because it would take some introspection to understand that the rrules and exrules overlap with each other, but I figured I should file a report here since it is pretty bad behavior.

Here's an example benchmark that causes what I'm describing:

func rruleSet(rules []string) *rrule.Set {
  res, err := rrule.StrToRRuleSet(strings.Join(rules, "\n"))
  if err != nil {
    panic(err)
  }
  return res
}

func BenchmarkRRuleOccurrences(t *testing.B) {
  fixtures := []struct {
    Set      *rrule.Set
  }{
    {
      Set: rruleSet([]string{
        "RRULE:FREQ=DAILY;DTSTART=20190211T000000Z",
        "EXRULE:FREQ=DAILY;DTSTART=20190211T000000Z",
      }),
    },
  }

  for _, fixture := range fixtures {
    next := fixture.Set.Iterator()
    next()
  }
}

This results in very slow computation of the next item, as seen below:

goos: darwin
goarch: amd64
BenchmarkRRuleOccurrences-4            1        17931085411 ns/op
PASS
ok                                                                        17.986s

If you remove the ExRule or change it slightly (like by adding INTERVAL=2), the benchmark will run in a couple of milliseconds.

My main concern is that I can't do set.Before(X) and return a result quickly, since the underlying implementation of Before uses set.Iterator(). Even after the cursor inside of the iterator has passed the X date, we have to still wait for the iterator to find a new result.

Again, I don't think it's easy to fix this issue without a good bit of work, but I did want to call it out.

[damoye]

This issure is very interesting. Because the Iterator keeps finding the next time and can't find one. So it run to the max time and return. The result is right, but it costs a lot of time.

[damoye]

We can't do some check in the input to fix this issue. Because there is so many ways to make an overlapping. For example one rrule is overlapped by another two exrule.

[rickywiens]

I wonder if we could set some sort of maximum time in the future that the iterator would go to without finding a recurrence before exiting?

The max date in go is 219250468-12-04 15:30:07 +0000 UTC. It seems a little bit unreasonable to go that far into the future looking for a recurrence. Can we assume that if we've iterated for some sort of reasonable amount of time it is very unlikely we are going to find an occurrence and exit the iterator?

[zensh]

@rickywiens I add a default until time as a boundary.