You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The fix for #1449 was unfortunately not quite complete, and introduced a regression. See #1486.
While the regression is now fixed, we are leaving a lot of performance on the table, and have regressed back to O(n^2) on the expiration list.
The conversion to an array should be changed to retain the index so that during removal we can recover the slot without having to look for it. As this is the hot code path, this will save a lot of cycles.
Additionally we need to keep the "next expiration time" in a per expiration queue variable, so that we can avoid waking up the expiration loop unless that loop needs to be woken for rescheduling because the newly inserted item expires sooner than any other item on the array (or is the only item on the array).
The text was updated successfully, but these errors were encountered:
There were several problems with the array implementation, both
from performance and from correctness. This corrects those errors
(hopefully) and restores the expiration lists as linked lists.
The fix for #1449 was unfortunately not quite complete, and introduced a regression. See #1486.
While the regression is now fixed, we are leaving a lot of performance on the table, and have regressed back to O(n^2) on the expiration list.
The conversion to an array should be changed to retain the index so that during removal we can recover the slot without having to look for it. As this is the hot code path, this will save a lot of cycles.
Additionally we need to keep the "next expiration time" in a per expiration queue variable, so that we can avoid waking up the expiration loop unless that loop needs to be woken for rescheduling because the newly inserted item expires sooner than any other item on the array (or is the only item on the array).
The text was updated successfully, but these errors were encountered: