Source code
Revision control
Copy as Markdown
Other Tools
/* -*- indent-tabs-mode: nil; js-indent-level: 2 -*-
* vim: sw=2 ts=2 sts=2 expandtab
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
/**
* This component handles frecency recalculations and decay on idle.
*/
const lazy = {};
ChromeUtils.defineESModuleGetters(lazy, {
});
ChromeUtils.defineLazyGetter(lazy, "logger", function () {
return lazy.PlacesUtils.getLogger({ prefix: "FrecencyRecalculator" });
});
// Decay rate applied daily to frecency scores.
// A scaling factor of .975 results in an half-life of 28 days.
const FRECENCY_DECAYRATE = "0.975";
XPCOMUtils.defineLazyPreferenceGetter(
lazy,
"frecencyDecayRate",
"places.frecency.decayRate",
FRECENCY_DECAYRATE,
null,
val => {
if (typeof val == "string") {
val = parseFloat(val);
}
if (val > 1.0) {
lazy.logger.error("Invalid frecency decay rate value: " + val);
val = parseFloat(FRECENCY_DECAYRATE);
}
return val;
}
);
// An adaptive history entry is removed if unused for these many days.
XPCOMUtils.defineLazyPreferenceGetter(
lazy,
"adaptiveHistoryExpireDays",
"places.adaptiveHistory.expireDays",
90
);
// For origins frecency calculation only sample pages visited recently.
XPCOMUtils.defineLazyPreferenceGetter(
lazy,
"originsFrecencyCutOffDays",
"places.frecency.originsCutOffDays",
90
);
// This pref stores whether recalculation should be faster.
// It is set when we detect that a lot of changes happened recently, and it
// will survive restarts. Once there's nothing left to recalculate, we unset
// the pref and return to the normal recalculation rate.
// Note this getter transforms the boolean pref value into an integer
// acceleration rate.
const PREF_ACCELERATE_RECALCULATION = "places.frecency.accelerateRecalculation";
XPCOMUtils.defineLazyPreferenceGetter(
lazy,
"accelerationRate",
PREF_ACCELERATE_RECALCULATION,
false,
null,
accelerate => (accelerate ? 2 : 1)
);
// Time between deferred task executions.
const DEFERRED_TASK_INTERVAL_MS = 2 * 60000;
// Maximum time to wait for an idle before the task is executed anyway.
const DEFERRED_TASK_MAX_IDLE_WAIT_MS = 5 * 60000;
// Number of entries to update at once.
const DEFAULT_CHUNK_SIZE = 50;
// Threshold used to evaluate whether the number of Places events from the last
// recalculation is high enough to deserve a recalculation rate increase.
const ACCELERATION_EVENTS_THRESHOLD = 250;
export class PlacesFrecencyRecalculator {
classID = Components.ID("1141fd31-4c1a-48eb-8f1a-2f05fad94085");
/**
* A DeferredTask that runs our tasks.
*/
#task = null;
/**
* Handler for alternative frecency.
* This allows to manager alternative ranking algorithms to experiment with.
*/
#alternativeFrecencyHelper = null;
/**
* This is useful for testing.
*/
get alternativeFrecencyInfo() {
return this.#alternativeFrecencyHelper?.sets;
}
constructor() {
lazy.logger.trace("Initializing Frecency Recalculator");
this.QueryInterface = ChromeUtils.generateQI([
"nsIObserver",
"nsISupportsWeakReference",
]);
// Do not initialize during shutdown.
if (
Services.startup.isInOrBeyondShutdownPhase(
Ci.nsIAppStartup.SHUTDOWN_PHASE_APPSHUTDOWNTEARDOWN
)
) {
return;
}
this.#createOrUpdateTask();
lazy.AsyncShutdown.profileChangeTeardown.addBlocker(
"PlacesFrecencyRecalculator: shutdown",
() => this.#finalize()
);
// The public methods and properties are intended to be used by tests, and
// are exposed through the raw js object. Since this is expected to work
// based on signals or notification, it should not be necessary to expose
// any API for the product, though if that would become necessary in the
// future, we could add an interface for the service.
this.wrappedJSObject = this;
// This can be used by tests to await for the decay process.
this.pendingFrecencyDecayPromise = Promise.resolve();
Services.obs.addObserver(this, "idle-daily", true);
Services.obs.addObserver(this, "frecency-recalculation-needed", true);
this.#alternativeFrecencyHelper = new AlternativeFrecencyHelper(this);
// Run once on startup, so we pick up any leftover work.
lazy.PlacesUtils.history.shouldStartFrecencyRecalculation = true;
this.maybeStartFrecencyRecalculation();
}
#createOrUpdateTask() {
let wasArmed = this.#task?.isArmed;
if (this.#task) {
this.#task.disarm();
this.#task.finalize().catch(console.error);
}
this.#task = new lazy.DeferredTask(
this.#taskFn.bind(this),
DEFERRED_TASK_INTERVAL_MS / lazy.accelerationRate,
DEFERRED_TASK_MAX_IDLE_WAIT_MS / lazy.accelerationRate
);
if (wasArmed) {
this.#task.arm();
}
}
async #taskFn() {
if (this.#task.isFinalized) {
return;
}
const refObj = {};
const histogram = "PLACES_FRECENCY_RECALC_CHUNK_TIME_MS";
TelemetryStopwatch.start(histogram, refObj);
try {
if (await this.recalculateSomeFrecencies()) {
TelemetryStopwatch.finish(histogram, refObj);
} else {
TelemetryStopwatch.cancel(histogram, refObj);
}
} catch (ex) {
TelemetryStopwatch.cancel(histogram, refObj);
console.error(ex);
lazy.logger.error(ex);
}
}
#finalize() {
lazy.logger.trace("Finalizing frecency recalculator");
// We don't mind about tasks completiion, since we can execute them in the
// next session.
this.#task.disarm();
this.#task.finalize().catch(console.error);
}
#lastEventsCount = 0;
/**
* Evaluates whether recalculation speed should be increased, and eventually
* accelerates.
* @returns {boolean} whether the recalculation rate is increased.
*/
maybeUpdateRecalculationSpeed() {
if (lazy.accelerationRate > 1) {
return true;
}
// We mostly care about additions to cover the common case of importing
// bookmarks or history. We may care about removals, but in most cases they
// reduce the number of entries to recalculate.
let eventsCount =
PlacesObservers.counts.get("page-visited") +
PlacesObservers.counts.get("bookmark-added");
let accelerate =
eventsCount - this.#lastEventsCount > ACCELERATION_EVENTS_THRESHOLD;
if (accelerate) {
Services.prefs.setBoolPref(PREF_ACCELERATE_RECALCULATION, true);
this.#createOrUpdateTask();
}
this.#lastEventsCount = eventsCount;
return accelerate;
}
#resetRecalculationSpeed() {
if (lazy.accelerationRate > 1) {
Services.prefs.clearUserPref(PREF_ACCELERATE_RECALCULATION);
this.#createOrUpdateTask();
}
}
/**
* Updates a chunk of outdated frecency values. If there's more frecency
* values to update at the end of the process, it may rearm the task.
* @param {Number} chunkSize maximum number of entries to update at a time,
* set to -1 to update any entry.
* @resolves {boolean} Whether any entry was recalculated.
*/
async recalculateSomeFrecencies({ chunkSize = DEFAULT_CHUNK_SIZE } = {}) {
// In case of acceleration we don't bump up the chunkSize to avoid issues
// with slow disk systems.
lazy.logger.trace(
`Recalculate ${chunkSize >= 0 ? chunkSize : "infinite"} frecency values`
);
let affectedCount = 0;
let hasRecalculatedAnything = false;
let db = await lazy.PlacesUtils.promiseUnsafeWritableDBConnection();
await db.executeTransaction(async function () {
let affected = await db.executeCached(
`UPDATE moz_places
SET frecency = CALCULATE_FRECENCY(id)
WHERE id IN (
SELECT id FROM moz_places
WHERE recalc_frecency = 1
ORDER BY frecency DESC, visit_count DESC
LIMIT ${chunkSize}
)
RETURNING id`
);
affectedCount += affected.length;
});
let shouldRestartRecalculation = affectedCount >= chunkSize;
hasRecalculatedAnything = affectedCount > 0;
if (hasRecalculatedAnything) {
PlacesObservers.notifyListeners([new PlacesRanking()]);
}
// Also recalculate some origins frecency.
affectedCount = await this.#recalculateSomeOriginsFrecencies({
chunkSize,
});
shouldRestartRecalculation ||= affectedCount >= chunkSize;
hasRecalculatedAnything ||= affectedCount > 0;
// If alternative frecency is enabled, also recalculate a chunk of it.
affectedCount =
await this.#alternativeFrecencyHelper.recalculateSomeAlternativeFrecencies(
{ chunkSize }
);
shouldRestartRecalculation ||= affectedCount >= chunkSize;
hasRecalculatedAnything ||= affectedCount > 0;
if (chunkSize > 0 && shouldRestartRecalculation) {
// There's more entries to recalculate, rearm the task.
this.maybeUpdateRecalculationSpeed();
this.#task.arm();
} else {
this.#resetRecalculationSpeed();
// There's nothing left to recalculate, wait for the next change.
lazy.PlacesUtils.history.shouldStartFrecencyRecalculation = false;
this.#task.disarm();
}
return hasRecalculatedAnything;
}
async #recalculateSomeOriginsFrecencies({ chunkSize }) {
lazy.logger.trace(`Recalculate ${chunkSize} origins frecency values`);
let affectedCount = 0;
let db = await lazy.PlacesUtils.promiseUnsafeWritableDBConnection();
await db.executeTransaction(async () => {
// NULL frecencies are normalized to 1.0 (to avoid confusion with pages
// 0 frecency special meaning), as the table doesn't support NULL values.
let affected = await db.executeCached(
`
UPDATE moz_origins
SET frecency = IFNULL((
SELECT sum(frecency)
FROM moz_places h
WHERE origin_id = moz_origins.id
AND last_visit_date >
strftime('%s','now','localtime','start of day',
'-${lazy.originsFrecencyCutOffDays} day','utc') * 1000000
), 1.0), recalc_frecency = 0
WHERE id IN (
SELECT id FROM moz_origins
WHERE recalc_frecency = 1
ORDER BY frecency DESC
LIMIT ${chunkSize}
)
RETURNING id`
);
affectedCount += affected.length;
// Calculate and store the frecency threshold. Origins whose frecency is
// above this value will be considered meaningful and autofilled.
// While it may be tempting to do this only when some frecency was
// updated, that won't catch the edge case of the moz_origins table being
// emptied.
// In case of NULL, the default threshold is 2, that is higher than the
// default frecency set above.
let threshold = (
await db.executeCached(`SELECT avg(frecency) FROM moz_origins`)
)[0].getResultByIndex(0);
await lazy.PlacesUtils.metadata.set(
"origin_frecency_threshold",
threshold ?? 2
);
});
return affectedCount;
}
/**
* Forces full recalculation of any outdated frecency values.
* This exists for testing purposes; in tests we don't want to wait for
* the deferred task to run, this can enforce a recalculation.
*/
async recalculateAnyOutdatedFrecencies() {
this.#task.disarm();
return this.recalculateSomeFrecencies({ chunkSize: -1 });
}
/**
* Whether a recalculation task is pending.
*/
get isRecalculationPending() {
return this.#task.isArmed;
}
/**
* Invoked periodically to eventually start a recalculation task.
*/
maybeStartFrecencyRecalculation() {
if (
lazy.PlacesUtils.history.shouldStartFrecencyRecalculation &&
!this.#task.isFinalized
) {
lazy.logger.trace("Arm frecency recalculation");
this.#task.arm();
}
}
/**
* Decays frecency and adaptive history.
* @resolves once the process is complete. Never rejects.
*/
async decay() {
lazy.logger.trace("Decay frecency");
let refObj = {};
TelemetryStopwatch.start("PLACES_IDLE_FRECENCY_DECAY_TIME_MS", refObj);
// Ensure moz_places_afterupdate_frecency_trigger ignores decaying
// frecency changes.
lazy.PlacesUtils.history.isFrecencyDecaying = true;
try {
let db = await lazy.PlacesUtils.promiseUnsafeWritableDBConnection();
await db.executeTransaction(async function () {
// Decay all frecency rankings to reduce value of pages that haven't
// been visited in a while.
await db.executeCached(
`UPDATE moz_places SET frecency = ROUND(frecency * :decay_rate)
WHERE frecency > 0 AND recalc_frecency = 0`,
{ decay_rate: lazy.frecencyDecayRate }
);
// Decay potentially unused adaptive entries (e.g. those that are at 1)
// to allow better chances for new entries that will start at 1.
await db.executeCached(
`UPDATE moz_inputhistory SET use_count = use_count * :decay_rate`,
{ decay_rate: lazy.frecencyDecayRate }
);
// Delete any adaptive entries that won't help in ordering anymore.
await db.executeCached(
`DELETE FROM moz_inputhistory WHERE use_count < :use_count`,
{
use_count: Math.pow(
lazy.frecencyDecayRate,
lazy.adaptiveHistoryExpireDays
),
}
);
TelemetryStopwatch.finish("PLACES_IDLE_FRECENCY_DECAY_TIME_MS", refObj);
PlacesObservers.notifyListeners([new PlacesRanking()]);
});
} catch (ex) {
TelemetryStopwatch.cancel("PLACES_IDLE_FRECENCY_DECAY_TIME_MS", refObj);
console.error(ex);
lazy.logger.error(ex);
} finally {
lazy.PlacesUtils.history.isFrecencyDecaying = false;
}
}
observe(subject, topic) {
lazy.logger.trace(`Got ${topic} topic`);
switch (topic) {
case "idle-daily":
this.pendingFrecencyDecayPromise = this.decay();
// Also recalculate frecencies.
lazy.logger.trace("Frecency recalculation on idle");
lazy.PlacesUtils.history.shouldStartFrecencyRecalculation = true;
this.maybeStartFrecencyRecalculation();
return;
case "frecency-recalculation-needed":
lazy.logger.trace("Frecency recalculation requested");
this.maybeUpdateRecalculationSpeed();
this.maybeStartFrecencyRecalculation();
return;
case "test-execute-taskFn":
subject.promise = this.#taskFn();
return;
case "test-alternative-frecency-init":
this.#alternativeFrecencyHelper = new AlternativeFrecencyHelper(this);
subject.promise =
this.#alternativeFrecencyHelper.initializedDeferred.promise;
}
}
}
class AlternativeFrecencyHelper {
initializedDeferred = Promise.withResolvers();
#recalculator = null;
sets = {
pages: {
// This pref is only read once and used to kick-off recalculations.
enabled: Services.prefs.getBoolPref(
"places.frecency.pages.alternative.featureGate",
false
),
// Key used to store variables in the moz_meta table.
metadataKey: "page_alternative_frecency",
// The table containing frecency.
table: "moz_places",
// Object containing variables influencing the calculation.
// Any change to this object will cause a full recalculation on restart.
variables: {
// Current version of origins alternative frecency.
// ! IMPORTANT: Always bump up when making changes to the algorithm.
version: 2,
highWeight: Services.prefs.getIntPref(
"places.frecency.pages.alternative.highWeight",
100
),
mediumWeight: Services.prefs.getIntPref(
"places.frecency.pages.alternative.mediumWeight",
50
),
lowWeight: Services.prefs.getIntPref(
"places.frecency.pages.alternative.lowWeight",
20
),
halfLifeDays: Services.prefs.getIntPref(
"places.frecency.pages.alternative.halfLifeDays",
30
),
numSampledVisits: Services.prefs.getIntPref(
"places.frecency.pages.alternative.numSampledVisits",
10
),
},
method: this.#recalculateSomePagesAlternativeFrecencies,
},
origins: {
// This pref is only read once and used to kick-off recalculations.
enabled: Services.prefs.getBoolPref(
"places.frecency.origins.alternative.featureGate",
false
),
// Key used to store variables in the moz_meta table.
metadataKey: "origin_alternative_frecency",
// The table containing frecency.
table: "moz_origins",
// Object containing variables influencing the calculation.
// Any change to this object will cause a full recalculation on restart.
variables: {
// Current version of origins alternative frecency.
// ! IMPORTANT: Always bump up when making changes to the algorithm.
version: 2,
// Frecencies of pages are ignored after these many days.
daysCutOff: Services.prefs.getIntPref(
"places.frecency.origins.alternative.daysCutOff",
90
),
},
method: this.#recalculateSomeOriginsAlternativeFrecencies,
},
};
constructor(recalculator) {
this.#recalculator = recalculator;
this.#kickOffAlternativeFrecencies()
.catch(console.error)
.finally(() => this.initializedDeferred.resolve());
}
async #kickOffAlternativeFrecencies() {
let recalculateFirstChunk = false;
for (let [type, set] of Object.entries(this.sets)) {
// Now check the variables cached in the moz_meta table. If not found we
// assume alternative frecency was disabled in the previous session.
let storedVariables = await lazy.PlacesUtils.metadata.get(
set.metadataKey,
null
);
// Check whether this is the first-run, that happens when the alternative
// ranking is enabled and it was not at the previous session, or variables
// were changed. We should recalculate all the alternative frecency values.
if (
set.enabled &&
!lazy.ObjectUtils.deepEqual(set.variables, storedVariables)
) {
lazy.logger.trace(
`Alternative frecency of ${type} must be recalculated`
);
await lazy.PlacesUtils.withConnectionWrapper(
`PlacesFrecencyRecalculator :: ${type} alternative frecency set recalc`,
async db => {
await db.execute(`UPDATE ${set.table} SET recalc_alt_frecency = 1`);
}
);
await lazy.PlacesUtils.metadata.set(set.metadataKey, set.variables);
recalculateFirstChunk = true;
continue;
}
if (!set.enabled && storedVariables) {
lazy.logger.trace(`Clean up alternative frecency of ${type}`);
// Clear alternative frecency to save on space.
await lazy.PlacesUtils.withConnectionWrapper(
`PlacesFrecencyRecalculator :: ${type} alternative frecency set NULL`,
async db => {
await db.execute(`UPDATE ${set.table} SET alt_frecency = NULL`);
}
);
await lazy.PlacesUtils.metadata.delete(set.metadataKey);
}
}
if (recalculateFirstChunk) {
// Do a first recalculation immediately, so we don't leave the user
// with unranked entries for too long.
await this.recalculateSomeAlternativeFrecencies();
// Ensure the recalculation task is armed for a second run.
lazy.PlacesUtils.history.shouldStartFrecencyRecalculation = true;
this.#recalculator.maybeStartFrecencyRecalculation();
}
}
/**
* Updates a chunk of outdated frecency values.
* @param {Number} chunkSize maximum number of entries to update at a time,
* set to -1 to update any entry.
* @resolves {Number} Number of affected pages.
*/
async recalculateSomeAlternativeFrecencies({
chunkSize = DEFAULT_CHUNK_SIZE,
} = {}) {
let affected = 0;
for (let set of Object.values(this.sets)) {
if (!set.enabled) {
continue;
}
try {
affected += await set.method({ chunkSize, variables: set.variables });
} catch (ex) {
console.error(ex);
}
}
return affected;
}
async #recalculateSomePagesAlternativeFrecencies({ chunkSize }) {
lazy.logger.trace(
`Recalculate ${chunkSize} alternative pages frecency values`
);
// Since it takes a long period of time to recalculate frecency of all the
// pages, due to the high number of them, we artificially increase the
// chunk size here.
let db = await lazy.PlacesUtils.promiseUnsafeWritableDBConnection();
let affected = await db.executeCached(
`UPDATE moz_places
SET alt_frecency = CALCULATE_ALT_FRECENCY(moz_places.id),
recalc_alt_frecency = 0
WHERE id IN (
SELECT id FROM moz_places
WHERE recalc_alt_frecency = 1
ORDER BY frecency DESC
LIMIT ${chunkSize * 2}
)
RETURNING id`
);
return affected;
}
async #recalculateSomeOriginsAlternativeFrecencies({ chunkSize, variables }) {
lazy.logger.trace(
`Recalculate ${chunkSize} alternative origins frecency values`
);
let affectedCount = 0;
let db = await lazy.PlacesUtils.promiseUnsafeWritableDBConnection();
await db.executeTransaction(async () => {
let affected = await db.executeCached(
`
UPDATE moz_origins
SET alt_frecency = (
SELECT sum(frecency)
FROM moz_places h
WHERE origin_id = moz_origins.id
AND last_visit_date >
strftime('%s','now','localtime','start of day',
'-${variables.daysCutOff} day','utc') * 1000000
), recalc_alt_frecency = 0
WHERE id IN (
SELECT id FROM moz_origins
WHERE recalc_alt_frecency = 1
ORDER BY frecency DESC
LIMIT ${chunkSize}
)
RETURNING id`
);
affectedCount += affected.length;
// Calculate and store the alternative frecency threshold. Origins above
// this threshold will be considered meaningful and autofilled.
if (affected.length) {
let threshold = (
await db.executeCached(`SELECT avg(alt_frecency) FROM moz_origins`)
)[0].getResultByIndex(0);
await lazy.PlacesUtils.metadata.set(
"origin_alt_frecency_threshold",
threshold
);
}
});
return affectedCount;
}
}