blob: 8a21a201752d1c57bedec97060be9b24dd25c1eb [file]
/-
Copyright (c) 2024 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Sebastian Ullrich
-/
prelude
import Lean.Util.Trace
/-! `trace.profiler.output` Firefox Profiler integration -/
namespace Lean.Firefox
/-! Definitions from https://github.com/firefox-devtools/profiler/blob/main/src/types/profile.js -/
abbrev Milliseconds := Float
structure Category where
name : String
color : String
subcategories : Array String := #[]
deriving FromJson, ToJson
structure ProfileMeta where
interval : Milliseconds := 0 -- should be irrelevant with `tracing-ms`
startTime : Milliseconds
categories : Array Category := #[]
processType : Nat := 0
product : String := "lean"
preprocessedProfileVersion : Nat := 48
markerSchema : Array Json := #[]
deriving FromJson, ToJson
structure StackTable where
frame : Array Nat
«prefix» : Array (Option Nat)
category : Array Nat
subcategory : Array Nat
length : Nat
deriving FromJson, ToJson
structure SamplesTable where
stack : Array Nat
time : Array Milliseconds
weight : Array Milliseconds
weightType : String := "tracing-ms"
length : Nat
deriving FromJson, ToJson
structure FuncTable where
name : Array Nat
isJS : Array Json := #[]
relevantForJS : Array Json := #[]
resource : Array Int
fileName : Array (Option Nat)
lineNumber : Array (Option Nat)
columnNumber : Array (Option Nat)
length : Nat
deriving FromJson, ToJson
structure FrameTable where
func : Array Nat
inlineDepth : Array Json := #[]
innerWindowID : Array Json := #[]
length : Nat
deriving FromJson, ToJson
structure RawMarkerTable where
data : Array Json := #[]
name : Array Json := #[]
length : Nat := 0
deriving FromJson, ToJson
structure ResourceTable where
type : Array Json := #[]
length : Nat := 0
deriving FromJson, ToJson
structure Thread where
name : String
processType : String := "default"
isMainThread : Bool := true
samples : SamplesTable
markers: RawMarkerTable := {}
stackTable : StackTable
frameTable : FrameTable
resourceTable : ResourceTable := {}
stringArray : Array String
funcTable : FuncTable
deriving FromJson, ToJson
structure Profile where
meta : ProfileMeta
libs : Array Json := #[]
threads : Array Thread
deriving FromJson, ToJson
/-- Thread with maps necessary for computing max sharing indices -/
structure ThreadWithMaps extends Thread where
stringMap : Std.HashMap String Nat := {}
funcMap : Std.HashMap Nat Nat := {}
stackMap : Std.HashMap (Nat × Option Nat) Nat := {}
/-- Last timestamp encountered: stop time of preceding sibling, or else start time of parent. -/
lastTime : Float := 0
-- TODO: add others, dynamically?
def categories : Array Category := #[
{ name := "Other", color := "gray" },
{ name := "Elab", color := "red" },
{ name := "Meta", color := "yellow" }
]
private partial def addTrace (pp : Bool) (thread : ThreadWithMaps) (trace : MessageData) :
IO ThreadWithMaps :=
(·.2) <$> StateT.run (go none trace) thread
where
go parentStackIdx? : _ → StateT ThreadWithMaps IO Unit
| .trace data msg children => do
if data.startTime == 0 then
return -- no time data, skip
let mut funcName := data.cls.toString
if !data.tag.isEmpty then
funcName := s!"{funcName}: {data.tag}"
if pp then
funcName := s!"{funcName}: {← msg.format}"
let strIdx ← modifyGet fun thread =>
if let some idx := thread.stringMap[funcName]? then
(idx, thread)
else
(thread.stringMap.size, { thread with
stringArray := thread.stringArray.push funcName
stringMap := thread.stringMap.insert funcName thread.stringMap.size })
let category := categories.findIdx? (·.name == data.cls.getRoot.toString) |>.getD 0
let funcIdx ← modifyGet fun thread =>
if let some idx := thread.funcMap[strIdx]? then
(idx, thread)
else
(thread.funcMap.size, { thread with
funcTable := {
name := thread.funcTable.name.push strIdx
resource := thread.funcTable.resource.push (-1)
-- the following fields could be inferred from `Syntax` in the message
fileName := thread.funcTable.fileName.push none
lineNumber := thread.funcTable.lineNumber.push none
columnNumber := thread.funcTable.columnNumber.push none
length := thread.funcTable.length + 1
}
frameTable := {
func := thread.frameTable.func.push thread.funcMap.size
length := thread.frameTable.length + 1
}
funcMap := thread.funcMap.insert strIdx thread.funcMap.size })
let frameIdx := funcIdx
let stackIdx ← modifyGet fun thread =>
if let some idx := thread.stackMap[(frameIdx, parentStackIdx?)]? then
(idx, thread)
else
(thread.stackMap.size, { thread with
stackTable := {
frame := thread.stackTable.frame.push frameIdx
«prefix» := thread.stackTable.prefix.push parentStackIdx?
category := thread.stackTable.category.push category
subcategory := thread.stackTable.subcategory.push 0
length := thread.stackTable.length + 1
}
stackMap := thread.stackMap.insert (frameIdx, parentStackIdx?) thread.stackMap.size })
modify fun thread => { thread with lastTime := data.startTime }
for c in children do
if let some nextStart := getNextStart? c then
-- add run time slice between children/before first child
modify fun thread => { thread with samples := {
stack := thread.samples.stack.push stackIdx
time := thread.samples.time.push (thread.lastTime * 1000)
weight := thread.samples.weight.push ((nextStart - thread.lastTime) * 1000)
length := thread.samples.length + 1
} }
go (some stackIdx) c
-- add remaining slice after last child
modify fun thread => { thread with
lastTime := data.stopTime
samples := {
stack := thread.samples.stack.push stackIdx
time := thread.samples.time.push (thread.lastTime * 1000)
weight := thread.samples.weight.push ((data.stopTime - thread.lastTime) * 1000)
length := thread.samples.length + 1
} }
| .withContext _ msg => go parentStackIdx? msg
| _ => return
/-- Returns first `startTime` in the trace tree, if any. -/
getNextStart?
| .trace data _ children => do
if data.startTime != 0 then
return data.startTime
if let some startTime := children.findSome? getNextStart? then
return startTime
none
| .withContext _ msg => getNextStart? msg
| _ => none
def Thread.new (name : String) : Thread := {
name
samples := { stack := #[], time := #[], weight := #[], length := 0 }
stackTable := { frame := #[], «prefix» := #[], category := #[], subcategory := #[], length := 0 }
frameTable := { func := #[], length := 0 }
stringArray := #[]
funcTable := {
name := #[], resource := #[], fileName := #[], lineNumber := #[], columnNumber := #[],
length := 0 }
}
def Profile.export (name : String) (startTime : Milliseconds) (traceState : TraceState)
(opts : Options) : IO Profile := do
let thread := Thread.new name
-- wrap entire trace up to current time in `runFrontend` node
let trace := .trace {
cls := `runFrontend, startTime, stopTime := (← IO.monoNanosNow).toFloat / 1000000000,
collapsed := true } "" (traceState.traces.toArray.map (·.msg))
let thread ← addTrace (Lean.trace.profiler.output.pp.get opts) { thread with } trace
return {
meta := { startTime, categories }
threads := #[thread.toThread]
}
structure ThreadWithCollideMaps extends ThreadWithMaps where
/-- Max sharing map for samples -/
sampleMap : Std.HashMap Nat Nat := {}
/--
Adds samples from `add` to `thread`, increasing the weight of existing samples with identical stacks
instead of pushing new samples.
-/
private partial def collideThreads (thread : ThreadWithCollideMaps) (add : Thread) :
ThreadWithCollideMaps :=
StateT.run collideSamples thread |>.2
where
collideSamples : StateM ThreadWithCollideMaps Unit := do
for oldSampleIdx in [0:add.samples.length] do
let oldStackIdx := add.samples.stack[oldSampleIdx]!
let stackIdx ← collideStacks oldStackIdx
modify fun thread =>
if let some idx := thread.sampleMap[stackIdx]? then
-- imperative to preserve linear use of arrays here!
let ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, o6⟩ := thread
let ⟨s1, s2, weight, s3, s4⟩ := samples
let weight := weight.set! idx <| weight[idx]! + add.samples.weight[oldSampleIdx]!
let samples := ⟨s1, s2, weight, s3, s4⟩
⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, o6⟩
else
-- imperative to preserve linear use of arrays here!
let ⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, sampleMap⟩ :=
thread
let ⟨stack, time, weight, _, length⟩ := samples
let samples := {
stack := stack.push stackIdx
time := time.push time.size.toFloat
weight := weight.push add.samples.weight[oldSampleIdx]!
length := length + 1
}
let sampleMap := sampleMap.insert stackIdx sampleMap.size
⟨⟨⟨t1, t2, t3, samples, t5, t6, t7, t8, t9, t10⟩, o2, o3, o4, o5⟩, sampleMap⟩
collideStacks oldStackIdx : StateM ThreadWithCollideMaps Nat := do
let oldParentStackIdx? := add.stackTable.prefix[oldStackIdx]!
let parentStackIdx? ← oldParentStackIdx?.mapM (collideStacks ·)
let oldFrameIdx := add.stackTable.frame[oldStackIdx]!
let oldFuncIdx := add.frameTable.func[oldFrameIdx]!
let oldStrIdx := add.funcTable.name[oldFuncIdx]!
let strIdx ← getStrIdx add.stringArray[oldStrIdx]!
let funcIdx ← modifyGet fun thread =>
if let some idx := thread.funcMap[strIdx]? then
(idx, thread)
else
(thread.funcMap.size, { thread with
funcTable := {
name := thread.funcTable.name.push strIdx
resource := thread.funcTable.resource.push (-1)
fileName := thread.funcTable.fileName.push none
lineNumber := thread.funcTable.lineNumber.push none
columnNumber := thread.funcTable.columnNumber.push none
length := thread.funcTable.length + 1
}
frameTable := {
func := thread.frameTable.func.push thread.funcMap.size
length := thread.frameTable.length + 1
}
funcMap := thread.funcMap.insert strIdx thread.funcMap.size })
let frameIdx := funcIdx
modifyGet fun thread =>
if let some idx := thread.stackMap[(frameIdx, parentStackIdx?)]? then
(idx, thread)
else
(thread.stackMap.size,
let ⟨⟨⟨t1,t2, t3, t4, t5, stackTable, t7, t8, t9, t10⟩, o2, o3, stackMap, o5⟩, o6⟩ :=
thread
let { frame, «prefix», category, subcategory, length } := stackTable
let stackTable := {
frame := frame.push frameIdx
«prefix» := prefix.push parentStackIdx?
category := category.push add.stackTable.category[oldStackIdx]!
subcategory := subcategory.push add.stackTable.subcategory[oldStackIdx]!
length := length + 1
}
let stackMap := stackMap.insert (frameIdx, parentStackIdx?) stackMap.size
⟨⟨⟨t1,t2, t3, t4, t5, stackTable, t7, t8, t9, t10⟩, o2, o3, stackMap, o5⟩, o6⟩)
getStrIdx (s : String) :=
modifyGet fun thread =>
if let some idx := thread.stringMap[s]? then
(idx, thread)
else
(thread.stringMap.size, { thread with
stringArray := thread.stringArray.push s
stringMap := thread.stringMap.insert s thread.stringMap.size })
/--
Merges given profiles such that samples with identical stacks are deduplicated by adding up their
weights. Minimizes profile size while preserving per-stack timing information.
-/
def Profile.collide (ps : Array Profile) : Option Profile := do
let base ← ps[0]?
let thread := Thread.new "collided"
let thread := ps.map (·.threads) |>.flatten.foldl collideThreads { thread with }
return { base with threads := #[thread.toThread] }
end Lean.Firefox