perf functions getEntriesByName and getEntriesByType seem to have unnecessarily bad performance

[tomjw64]

Version

v16.14.0

Platform

Linux 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

Subsystem

internal/lib/perf

What steps will reproduce the bug?

// slow.js
let iter = 0

const getEntries = process.argv[2] === 'name'
  ? () => performance.getEntriesByName('x')
  : () => performance.getEntriesByType('measure')

while (++iter <= process.argv[3]) {
  performance.mark('x')
  performance.mark('y')
  performance.measure('x', 'x', 'y')
  getEntries()
}
console.log(getEntries().length)

// fast.js
let iter = 0
let entries = {
  mark: {},
  measure: {}
}

const getEntriesByType = (type) => [].concat(...Object.values(entries[type]))
const getEntriesByName = (name) => entries.mark[name].concat(entries.measure[name])
const mark = (name) => {
  if (!entries.mark[name]) { entries.mark[name] = [] }
  entries.mark[name].push(performance.mark(name))
}
const measure = (name, start, end) => {
  if (!entries.measure[name]) { entries.measure[name] = [] }
  entries.measure[name].push(performance.measure(name, start, end))
}

const getEntries = process.argv[2] === 'name'
  ? () => getEntriesByName('x')
  : () => getEntriesByType('measure')

while (++iter <= process.argv[3]) {
  mark('x')
  mark('y')
  measure('x', 'x', 'y')
  getEntries()
}
console.log(getEntries().length)

$ time node slow.js name 10000
20000

real	0m15.021s
user	0m14.930s
sys	0m0.196s
$ time node slow.js type 10000
10000

real	0m7.476s
user	0m7.482s
sys	0m0.020s
$ time node fast.js name 10000
20000

real	0m0.188s
user	0m0.117s
sys	0m0.117s
$ time node fast.js type 10000
10000

real	0m0.083s
user	0m0.107s
sys	0m0.009s

How often does it reproduce? Is there a required condition?

Lots of marks or measures must be present to see a noticeable difference in performance. Additionally, the name parameter for the getEntriesByName function must be for a entry name that exists in the buffers, as far as I can tell.

What is the expected behavior?

No response

What do you see instead?

getEntriesByName and getEntriesByType take significantly longer than a naive entry tracking solution using object key lookups and concatenation.

Additional information

kMaxPerformanceEntryBuffers makes clear that no more than 1000000 entries should be present. Maybe that implies that the performance expectations for these functions should not be high and that users should be expected to regularly clear entries instead.

[benjamingr]

cc @legendecas @jasnell

I'm wondering why this uses linked lists and not arrays (which are faster in pretty much every way?)

[legendecas]

@benjamingr it's used to prevent allocation and expansion of the array on the entry creation time, at which it is much more performance-sensitive than observing the entries.

[benjamingr]

@legendecas but array allocation/size increase is amortized O(1) isn't it? If allocation is a problem we can use a FixedQueue like other places in the code probably?

[legendecas]

From what I understand, expansion of array is not constant time. The content of the array has to be copied to the new larger location. I think FixedQueue could be a good alternative to the linked list.

[benjamingr]

@legendecas

expansion of array is not constant time

You're right - it's not constant. It's amortized constant time which is not quite the same thing - it basically means "acts like O(1) for a large enough N since the expensive operations are split across many invocations" (happy to elaborate with a more formal definition if you prefer).

(Anyway a FixedQueue is the best of both worlds since it's also allocation friendly for resets)

[jasnell]

FixedQueue would likely be fine here.

[gioragutt]

As a wise Benji once said - I'm taking a stab at this 🗡

[benjamingr]

Verified arrays have amortized O(1) allocation https://source.chromium.org/chromium/chromium/src/+/main:v8/src/codegen/code-stub-assembler.cc;drc=c26af9bfc075bbed0c70d2371b9021d3a3479d92;l=5275?q=BuildAppendJSArray&ss=chromium%2Fchromium%2Fsrc