958978 - Yearly recurrences with BYMONTH and more BYDAY are displayed wrongly if the last day of the month is not displayed in the view

Status: RESOLVED FIXED

(Calendar :: Internal Components, defect)

Description

[Decathlon]

Steps to reproduce:
- import the following calendar that represent the rule "Every day of January every year starting form the 1st of January 2014"

BEGIN:VCALENDAR
PRODID:-//Mozilla.org/NONSGML Mozilla Calendar V1.1//EN
VERSION:2.0
BEGIN:VEVENT
CREATED:20090529T202927Z
LAST-MODIFIED:20090529T203001Z
DTSTAMP:20090529T203001Z
UID:fbacc989-a182-4def-8c76-15219d8968aa
SUMMARY:Yearly every 
RRULE:FREQ=YEARLY;BYMONTH=1;BYDAY=SU,MO,TU,WE,TH,FR,SA
DTSTART;VALUE=DATE:20140101
DTEND;VALUE=DATE:20140102
TRANSP:TRANSPARENT
END:VEVENT
END:VCALENDAR

- select the month view and the month of December 2013 (it displays part of the first week of January 2014):
  -> in the view there is only the first occurrence of the 1st of January and, with
     the start of week on Monday, days 2, 3, 4, 5 are missing;

- change the view to "Multiweek" and then scroll the view week by week:
  -> in the view only the occurrences on Monday are displayed (along with the
     starting day on 1st of January), the occurrences of the others days are missing
     unless the 31 of January appears in the view, in this case all the occurrences
     are correctly displayed in the view.


This issue prevent to use the yearly rule with BYDAY=MO,TU,WE,TH,FR,SA,SU for the case "Every day" of a month.

Comment 1

[Decathlon]

Attachment: patch - v1

It seems that the function "next()" returns wrong days for the occurrences because the array impl.days (this.days in ical.js) is not sorted.
The array contains all the occurrences in the form of days of the year, but they are grouped and sorted according to the days of week existing in the rule  (see also http://mxr.mozilla.org/comm-central/source/calendar/base/modules/ical.js#5416 in ical.js)

With a rule like that one in the description, it results an array impl.days like this:

6, 13,20,27,7, 14,21,28,8, 15,22,29, 2,9,16,23,30, 3,0,17,24,31, 4,11,18,25,...
^           ^           ^
MO MO MO MO|TU TU TU TU|WE WE...

so the first occurrence is the day 6 instead of 2 and the "next" of the day 6 is 13 instead of 7 as is currently displayed in month-view.

Since the days are added in the array according to what it seems to be the most efficient way (a loop on the elements of BYDAY), the simplest solution for a fix seems sorting the array afterwards its building, that is what I've tried to do in this patch.


The alternatives could be either sorting the array every time that a new day is added by means of .sort()/qsort() (or a specific code) or building directly a sorted array. In this last case the loop should be done on the days of the month instead of on the weekdays inside the BYBDAY rule.
   
I've done an attempt of building directly a sorted array(see next comment). The way to do it is inevitably less efficient compared to the current code (apart from the kind of solution) and should be evaluated in some way if there is a performance gain compared to the .sort()/qsort() case.

Comment 2

[Decathlon]

Attachment: ArrayDirectlySorted-patch-ical.js

This patch builds the array already sorted, it works fine but actually I don't know if it's the best way to do it.
It searches the elements in BYDAY and then does a loop on the days of the month to see if each of them verifies the elements in BYDAY.
It's only for ical.js and I don't ask for review, I'm only asking your opinion Philipp if this way is preferable compared to the .sort()/qsort/() solution.

Comment 3

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Note that inserting into an already sorted array is more efficient with the binaryInsert function we have here: <http://mxr.mozilla.org/comm-central/source/calendar/base/src/calUtils.js#1816>. ICAL.js also has a similar function in ICAL.helpers.

Comment 4

[Decathlon]

Attachment: binsearchInsert - v1.patch

It seems that binaryInsert() can't be used from ical.js. 
ICAL.helpers doesn't have a binaryInsert but only a binsearchInsert(). Since it has to be used on a sorted array, it has to be applied every time we insert a new item in the array. Moreover it needs a check to avoid to insert a item twice or more (e.g. with rules such as BYDAY=MO,2MO) because this would generate an error.

Philipp, what do you think about this kind of approach?

For libical it needs something similar?

Comment 5

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Comment on attachment 8417010 [details] [diff] [review]
binsearchInsert - v1.patch

Review of attachment 8417010 [details] [diff] [review]:
-----------------------------------------------------------------

Generally I think this approach will work, but it would be nice to do some (manual) performance tests on common rules. If a lot of inserts are done and the number of elements in the array are generally low, it might be faster to just dump them in and sort the array using a different algorithm or possibly the standard Array sort afterwards.

Comment 6

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Ah, it looks like I've already said its more efficient :-D Sorry for the back and forth. Binary insert as you've done it should be fine, but if you are bored and would like to know whats really more efficient, then go ahead and test.

Comment 7

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Note that if you are doing ical.js changes, you will need to write an ical.js test and push the patch upstream. See here for how to run tests: https://github.com/mozilla-comm/ical.js/wiki/Running-Tests

Comment 8

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Comment on attachment 8416746 [details] [diff] [review]
patch - v1

Review of attachment 8416746 [details] [diff] [review]:
-----------------------------------------------------------------

r+ for the libical part, given its C code I think the possible performance hit for the qsort will be less severe.

::: calendar/libical/src/libical/icalrecur.c
@@ +1916,5 @@
>      return days_list;
>  }
>  
> +/* A compare function to be used for qsort() */
> +int compare (const void * a, const void * b) 

I'd suggest a more verbose name here. Also remove trailing whitespace.

Comment 9

[Decathlon]

I've tried to do some performance test. I've used
 new Date().getTime()
so the results are a bit(?) approximate because the execution time is between 0ms and 3ms, hence an average time has been calculated for all the calls to that function when Thunderbird has started.
In order to increase the time I've used a rule with more BYMONTHs:
RRULE:FREQ=YEARLY;BYMONTH=1,2,3,4,5,6,7,8,9,10,11;BYDAY=SU,MO,TU,WE,TH,FR,SA
and I've taken the time after line 5382 and before line 5447
http://mxr.mozilla.org/comm-central/source/calendar/base/modules/ical.js#5382

These are the results:

Attempt    n. calls           execution average time(ms)  
                         .sort()        binsearchInsert + splice
-----------------------------------------------------------------
   1          113        0.07964               0.22123
   2          113        0.11504               0.19469
   3          113        0.07964               0.20353
   4          113        0.07964               0.16814
   5          113        0.08849               0.15929
   6          113        0.12389               0.23893
   7          113        0.04424               0.15044
   8          113        0.06194               0.16814
   9          113        0.10619               0.17699
   10         113        0.09734               0.18584


Date().getTime() is too approximate, but it seems that the code with the function .sort() (patch-v1) is faster at least with that event. When you see the single calls, the execution time equal to 0ms and sometimes 1ms is the rule with .sort(), instead with binsearchInsert there are many 1ms, and 2ms (rarely 3 ms).

For less demanding events such as only one BYMONTH
RRULE:FREQ=YEARLY;BYMONTH=1;BYDAY=SU,MO,TU,WE,TH,FR,SA
it would need something more precise than Date().getTime() but here I need suggestions.

Philipp, what's you opinion?

Comment 10

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Thanks for doing the benchmarks. I'm surprised the sort() call is faster, I guess its also because sort() is optimized and binsearchinsert is pure js. We might want to rewrite our binary search to use asm.js at some point.

If you want to test more simple rules, I'd suggest to modify the benchmark to just do a lot more calls in succession, i.e 1000+. This way it takes more time in total, its easier to compare and the 3ms inaccuracy is not much of a problem.

In the end, go with whatever is fastest and least pain to implement :)

Comment 11

[Decathlon]

Attachment: patch qsort() - only libical with test

(In reply to Philipp Kewisch [:Fallen] from comment #10)
> If you want to test more simple rules, I'd suggest to modify the benchmark
> to just do a lot more calls in succession

Ok, I've inserted a loop that executes the code inside the function 1000 times every time it is called and tested two different events: 

RRULE:FREQ=YEARLY;BYMONTH=1,2,3,4,5,6,7,8,9,10,11;BYDAY=SU,MO,TU,WE,TH,FR,SA

      average time with 60 calls:    patch-v1 (sort)          404 ms
                                     patch binSearchInsert    1010 ms


RRULE:FREQ=YEARLY;BYMONTH=1;BYDAY=WE,FR
                                   
      average time with 60 calls:    patch-v1 (sort)          42 ms 
                                     patch binSearchInsert    53 ms

                                     
these are typical values with several attempts and not a particular case, hence, even with the less demanding rule, the patch-v1 with sort() is faster (around 15-25%) than the patch with binSearchInsert().


> I'm surprised the sort() call is faster, I guess its also because sort()
> is optimized and binsearchinsert is pure js.

Actually it's not a direct comparison between the functions because the patches have different structures. binSearchInsert() must be called every time we insert an item in the array, instead sort() can be called only once after the array has been filled. It seems the best performance of the patch with sort() is caused by the minor number of calls.

Indeed I've also done a direct comparison using sort() instead of binsearchInsert() in the second patch in order to test with the same number of calls. The result is that binSearchinsert() is much faster with the first rule, something like 2.5-3 times faster (execution time increases to 2500-3000ms), instead with the other rule the results are similar.


This patch addresses the note in comment 8 and includes only code for libical and adds tests.
I will do a pull request on GitHub for the ical.js part.

Comment 12

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

(In reply to Decathlon from comment #11)
> Created attachment 8543510 [details] [diff] [review]
> patch qsort() - only libical with test
> 
> (In reply to Philipp Kewisch [:Fallen] from comment #10)
> > If you want to test more simple rules, I'd suggest to modify the benchmark
> > to just do a lot more calls in succession
> 
> Ok, I've inserted a loop that executes the code inside the function 1000
> times every time it is called and tested two different events: 
Great numbers, I like the perf improvement.

> 
> > I'm surprised the sort() call is faster, I guess its also because sort()
> > is optimized and binsearchinsert is pure js.
> 
> Actually it's not a direct comparison between the functions because the
> patches have different structures. binSearchInsert() must be called every
> time we insert an item in the array, instead sort() can be called only once
> after the array has been filled. It seems the best performance of the patch
> with sort() is caused by the minor number of calls.
I was just so surprised since in theory, binary insert is faster than quicksort when arrays are sorted. The time to insert and sort should be compared: while a binary insert is slower on inserting, it doesn't need to be sorted at the end and we have O(n). On the other hand the inserts using quicksort are O(1) but the sort is O(n log n) which is slightly larger.

> 
> Indeed I've also done a direct comparison using sort() instead of
> binsearchInsert() in the second patch in order to test with the same number
> of calls. The result is that binSearchinsert() is much faster with the first
> rule, something like 2.5-3 times faster (execution time increases to
> 2500-3000ms), instead with the other rule the results are similar.
With direct comparison you mean including insert and sort? Maybe we can differ the algorithm used by rule type.

Comment 13

[Decathlon]

Attachment: patch qsort() - only libical with test (for checkin)

(In reply to Philipp Kewisch [:Fallen] from comment #12)

> With direct comparison you mean including insert and sort? Maybe we can
> differ the algorithm used by rule type.

I meant I substituted the function binSearchInsert() with sort() in the patch built for binSearchInsert() (the patch named "binsearchInsert - v1") just for curiosity to see the difference in the same conditions: with that patch the function sort() is very slow with rules with many elements, but with simple rules it gives the same execution time of binSearchInsert().
Anyway the first patch (named "patch-v1" with sort()) is faster for every simple or complex rule compared to the patch "binsearchInsert - v1" so there is no need to differentiate the algorithm by rule type.

Comment 14

[Decathlon]

(In reply to Philipp Kewisch [:Fallen] from comment #12)

> With direct comparison you mean including insert and sort? Maybe we can
> differ the algorithm used by rule type.

I meant I substituted the function binSearchInsert() with sort() in the patch built for binSearchInsert() (the patch named "binsearchInsert - v1"). Just curiosity to see the difference in the same conditions: sort() is very slow with rules with many elements, but with simple rules there is no difference (with that patch). Anyway the first patch (named "patch-v1") is faster for every rule compared to "binsearchInsert - v1" so there is no need to differentiate the algorithm by rule type.

Comment 15

[Philipp Kewisch [:Fallen] [:📆][:🧩]]

Ok, thanks for the explanation!

Comment 16

[Geoff Lankow (:darktrojan)]

https://hg.mozilla.org/comm-central/rev/43cc5528d919

I wonder if this bug still exists in libical and if the fix should be upstreamed. I think our version of libical is somewhat out-of-date though, isn't it?

I'll leave this bug open as it still depends on bug 1115667, although I think it's about to turn comm-central orange without those changes.

Comment 17

[Geoff Lankow (:darktrojan)]

Yeah, it's going to go orange. Pushed https://hg.mozilla.org/comm-central/rev/f303df80b775 to fix.

Comment 18

[Geoff Lankow (:darktrojan)]

… and https://hg.mozilla.org/comm-central/rev/73adfa7f6c27 to really fix it.