--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -4019,16 +4019,25 @@
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "58",
     "kind": "exponential",
     "high": 1000,
     "n_buckets": 10,
     "bug_numbers": [1283007],
     "description": "Time spent fallocating Variable-Length PrefixSet (ms)"
   },
+  "URLCLASSIFIER_VLPS_CONSTRUCT_TIME": {
+    "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
+    "expires_in_version": "60",
+    "kind": "exponential",
+    "high": 5000,
+    "n_buckets": 15,
+    "bug_numbers": [1336865],
+    "description": "Time spent constructing Variable-Length PrefixSet from file (ms)"
+  },
   "URLCLASSIFIER_VLPS_LOAD_CORRUPT": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "58",
     "kind": "boolean",
     "bug_numbers": [1305581],
     "description": "Whether or not a variable-length prefix set loaded from disk is corrupted (true = file corrupted)."
   },
   "URLCLASSIFIER_LC_PREFIXES": {

--- a/toolkit/components/url-classifier/LookupCacheV4.cpp
+++ b/toolkit/components/url-classifier/LookupCacheV4.cpp
@@ -115,16 +115,18 @@ LookupCacheV4::IsHashEntryConfirmed(cons
 {
   // TODO : Bug 1311935 - Implement v4 caching
   *aConfirmed = true;
 }
 
 nsresult
 LookupCacheV4::Build(PrefixStringMap& aPrefixMap)
 {
+  Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_VLPS_CONSTRUCT_TIME> timer;
+
   return mVLPrefixSet->SetPrefixes(aPrefixMap);
 }
 
 nsresult
 LookupCacheV4::GetPrefixes(PrefixStringMap& aPrefixMap)
 {
   return mVLPrefixSet->GetPrefixes(aPrefixMap);
 }