Visitar URL original
perf: improve sort algorithm (#2756) · nodejs/undici@cffdfb3 · GitHub
Skip to content

Commit cffdfb3

Browse files
tsctxronag
tsctx
authored and
ronag
committed
perf: improve sort algorithm (#2756)
* perf: improve sort algorithm * benchmark: add headers-length32.mjs * fix: benchmark * fix: fix performance regression for sorted arrays * test: add sorted test * refactor: simplify * refactor: remove comment
1 parent bdfb863 commit cffdfb3

84 files changed

Lines changed: 675 additions & 127 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎benchmarks/cacheGetFieldValues.mjs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
import { bench, group, run } from 'mitata'
2-
import { getFieldValues } from '../lib/cache/util.js'
2+
import { getFieldValues } from '../lib/web/cache/util.js'
33

44
const values = [
55
'',

‎benchmarks/headers-length32.mjs‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import { bench, run } from 'mitata'
2+
import { Headers } from '../lib/fetch/headers.js'
3+
4+
const headers = new Headers(
5+
[
6+
'Origin-Agent-Cluster',
7+
'RTT',
8+
'Accept-CH-Lifetime',
9+
'X-Frame-Options',
10+
'Sec-CH-UA-Platform-Version',
11+
'Digest',
12+
'Cache-Control',
13+
'Sec-CH-UA-Platform',
14+
'If-Range',
15+
'SourceMap',
16+
'Strict-Transport-Security',
17+
'Want-Digest',
18+
'Cross-Origin-Resource-Policy',
19+
'Width',
20+
'Accept-CH',
21+
'Via',
22+
'Refresh',
23+
'Server',
24+
'Sec-Fetch-Dest',
25+
'Sec-CH-UA-Model',
26+
'Access-Control-Request-Method',
27+
'Access-Control-Request-Headers',
28+
'Date',
29+
'Expires',
30+
'DNT',
31+
'Proxy-Authorization',
32+
'Alt-Svc',
33+
'Alt-Used',
34+
'ETag',
35+
'Sec-Fetch-User',
36+
'Sec-CH-UA-Full-Version-List',
37+
'Referrer-Policy'
38+
].map((v) => [v, ''])
39+
)
40+
41+
const kHeadersList = Reflect.ownKeys(headers).find(
42+
(c) => String(c) === 'Symbol(headers list)'
43+
)
44+
45+
const headersList = headers[kHeadersList]
46+
47+
const kHeadersSortedMap = Reflect.ownKeys(headersList).find(
48+
(c) => String(c) === 'Symbol(headers map sorted)'
49+
)
50+
51+
bench('Headers@@iterator', () => {
52+
headersList[kHeadersSortedMap] = null
53+
return [...headers]
54+
})
55+
56+
await run()

‎benchmarks/headers.mjs‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
import { bench, group, run } from 'mitata'
2+
import { Headers } from '../lib/fetch/headers.js'
3+
4+
const characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
5+
const charactersLength = characters.length
6+
7+
function generateAsciiString (length) {
8+
let result = ''
9+
for (let i = 0; i < length; ++i) {
10+
result += characters[Math.floor(Math.random() * charactersLength)]
11+
}
12+
return result
13+
}
14+
15+
const settings = {
16+
'fast-path (tiny array)': 4,
17+
'fast-path (small array)': 8,
18+
'fast-path (middle array)': 16,
19+
'fast-path': 32,
20+
'slow-path': 64
21+
}
22+
23+
for (const [name, length] of Object.entries(settings)) {
24+
const headers = new Headers(
25+
Array.from(Array(length), () => [generateAsciiString(12), ''])
26+
)
27+
28+
const headersSorted = new Headers(headers)
29+
30+
const kHeadersList = Reflect.ownKeys(headers).find(
31+
(c) => String(c) === 'Symbol(headers list)'
32+
)
33+
34+
const headersList = headers[kHeadersList]
35+
36+
const headersListSorted = headersSorted[kHeadersList]
37+
38+
const kHeadersSortedMap = Reflect.ownKeys(headersList).find(
39+
(c) => String(c) === 'Symbol(headers map sorted)'
40+
)
41+
42+
group(`length ${length} #${name}`, () => {
43+
bench('Headers@@iterator', () => {
44+
// prevention of memoization of results
45+
headersList[kHeadersSortedMap] = null
46+
return [...headers]
47+
})
48+
49+
bench('Headers@@iterator (sorted)', () => {
50+
// prevention of memoization of results
51+
headersListSorted[kHeadersSortedMap] = null
52+
return [...headersSorted]
53+
})
54+
})
55+
}
56+
57+
await run()

‎benchmarks/sort.mjs‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
import { bench, group, run } from 'mitata'
2+
import { sort, heapSort, introSort } from '../lib/fetch/sort.js'
3+
4+
function compare (a, b) {
5+
return a < b ? -1 : 1
6+
}
7+
8+
const characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'
9+
const charactersLength = characters.length
10+
11+
function generateAsciiString (length) {
12+
let result = ''
13+
for (let i = 0; i < length; ++i) {
14+
result += characters[Math.floor(Math.random() * charactersLength)]
15+
}
16+
return result
17+
}
18+
19+
const settings = {
20+
tiny: 32,
21+
small: 64,
22+
middle: 128,
23+
large: 512
24+
}
25+
26+
for (const [name, length] of Object.entries(settings)) {
27+
group(`sort (${name})`, () => {
28+
const array = Array.from(new Array(length), () => generateAsciiString(12))
29+
// sort(array, compare)
30+
bench('Array#sort', () => array.slice().sort(compare))
31+
bench('sort (intro sort)', () => sort(array.slice(), compare))
32+
33+
// sort(array, start, end, compare)
34+
bench('intro sort', () => introSort(array.slice(), 0, array.length, compare))
35+
bench('heap sort', () => heapSort(array.slice(), 0, array.length, compare))
36+
})
37+
38+
group(`sort sortedArray (${name})`, () => {
39+
const array = Array.from(new Array(length), () => generateAsciiString(12)).sort(compare)
40+
// sort(array, compare)
41+
bench('Array#sort', () => array.sort(compare))
42+
bench('sort (intro sort)', () => sort(array, compare))
43+
44+
// sort(array, start, end, compare)
45+
bench('intro sort', () => introSort(array, 0, array.length, compare))
46+
bench('heap sort', () => heapSort(array, 0, array.length, compare))
47+
})
48+
}
49+
50+
await run()

‎index-fetch.js‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
'use strict'
22

3-
const fetchImpl = require('./lib/fetch').fetch
3+
const fetchImpl = require('./lib/web/fetch').fetch
44

55
module.exports.fetch = function fetch (resource, init = undefined) {
66
return fetchImpl(resource, init).catch((err) => {
@@ -10,12 +10,12 @@ module.exports.fetch = function fetch (resource, init = undefined) {
1010
throw err
1111
})
1212
}
13-
module.exports.FormData = require('./lib/fetch/formdata').FormData
14-
module.exports.Headers = require('./lib/fetch/headers').Headers
15-
module.exports.Response = require('./lib/fetch/response').Response
16-
module.exports.Request = require('./lib/fetch/request').Request
13+
module.exports.FormData = require('./lib/web/fetch/formdata').FormData
14+
module.exports.Headers = require('./lib/web/fetch/headers').Headers
15+
module.exports.Response = require('./lib/web/fetch/response').Response
16+
module.exports.Request = require('./lib/web/fetch/request').Request
1717

18-
module.exports.WebSocket = require('./lib/websocket/websocket').WebSocket
19-
module.exports.MessageEvent = require('./lib/websocket/events').MessageEvent
18+
module.exports.WebSocket = require('./lib/web/websocket/websocket').WebSocket
19+
module.exports.MessageEvent = require('./lib/web/websocket/events').MessageEvent
2020

21-
module.exports.EventSource = require('./lib/eventsource/eventsource').EventSource
21+
module.exports.EventSource = require('./lib/web/eventsource/eventsource').EventSource

‎index.js‎

Lines changed: 15 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -96,7 +96,7 @@ function makeDispatcher (fn) {
9696
module.exports.setGlobalDispatcher = setGlobalDispatcher
9797
module.exports.getGlobalDispatcher = getGlobalDispatcher
9898

99-
const fetchImpl = require('./lib/fetch').fetch
99+
const fetchImpl = require('./lib/web/fetch').fetch
100100
module.exports.fetch = async function fetch (init, options = undefined) {
101101
try {
102102
return await fetchImpl(init, options)
@@ -108,39 +108,39 @@ module.exports.fetch = async function fetch (init, options = undefined) {
108108
throw err
109109
}
110110
}
111-
module.exports.Headers = require('./lib/fetch/headers').Headers
112-
module.exports.Response = require('./lib/fetch/response').Response
113-
module.exports.Request = require('./lib/fetch/request').Request
114-
module.exports.FormData = require('./lib/fetch/formdata').FormData
115-
module.exports.File = require('./lib/fetch/file').File
116-
module.exports.FileReader = require('./lib/fileapi/filereader').FileReader
111+
module.exports.Headers = require('./lib/web/fetch/headers').Headers
112+
module.exports.Response = require('./lib/web/fetch/response').Response
113+
module.exports.Request = require('./lib/web/fetch/request').Request
114+
module.exports.FormData = require('./lib/web/fetch/formdata').FormData
115+
module.exports.File = require('./lib/web/fetch/file').File
116+
module.exports.FileReader = require('./lib/web/fileapi/filereader').FileReader
117117

118-
const { setGlobalOrigin, getGlobalOrigin } = require('./lib/fetch/global')
118+
const { setGlobalOrigin, getGlobalOrigin } = require('./lib/web/fetch/global')
119119

120120
module.exports.setGlobalOrigin = setGlobalOrigin
121121
module.exports.getGlobalOrigin = getGlobalOrigin
122122

123-
const { CacheStorage } = require('./lib/cache/cachestorage')
124-
const { kConstruct } = require('./lib/cache/symbols')
123+
const { CacheStorage } = require('./lib/web/cache/cachestorage')
124+
const { kConstruct } = require('./lib/web/cache/symbols')
125125

126126
// Cache & CacheStorage are tightly coupled with fetch. Even if it may run
127127
// in an older version of Node, it doesn't have any use without fetch.
128128
module.exports.caches = new CacheStorage(kConstruct)
129129

130-
const { deleteCookie, getCookies, getSetCookies, setCookie } = require('./lib/cookies')
130+
const { deleteCookie, getCookies, getSetCookies, setCookie } = require('./lib/web/cookies')
131131

132132
module.exports.deleteCookie = deleteCookie
133133
module.exports.getCookies = getCookies
134134
module.exports.getSetCookies = getSetCookies
135135
module.exports.setCookie = setCookie
136136

137-
const { parseMIMEType, serializeAMimeType } = require('./lib/fetch/dataURL')
137+
const { parseMIMEType, serializeAMimeType } = require('./lib/web/fetch/dataURL')
138138

139139
module.exports.parseMIMEType = parseMIMEType
140140
module.exports.serializeAMimeType = serializeAMimeType
141141

142-
const { CloseEvent, ErrorEvent, MessageEvent } = require('./lib/websocket/events')
143-
module.exports.WebSocket = require('./lib/websocket/websocket').WebSocket
142+
const { CloseEvent, ErrorEvent, MessageEvent } = require('./lib/web/websocket/events')
143+
module.exports.WebSocket = require('./lib/web/websocket/websocket').WebSocket
144144
module.exports.CloseEvent = CloseEvent
145145
module.exports.ErrorEvent = ErrorEvent
146146
module.exports.MessageEvent = MessageEvent
@@ -156,6 +156,6 @@ module.exports.MockPool = MockPool
156156
module.exports.MockAgent = MockAgent
157157
module.exports.mockErrors = mockErrors
158158

159-
const { EventSource } = require('./lib/eventsource/eventsource')
159+
const { EventSource } = require('./lib/web/eventsource/eventsource')
160160

161161
module.exports.EventSource = EventSource

‎lib/cache/symbols.js‎

Lines changed: 0 additions & 5 deletions
This file was deleted.

‎lib/client.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1500,7 +1500,7 @@ function write (client, request) {
15001500

15011501
if (util.isFormDataLike(body)) {
15021502
if (!extractBody) {
1503-
extractBody = require('./fetch/body.js').extractBody
1503+
extractBody = require('./web/fetch/body.js').extractBody
15041504
}
15051505

15061506
const [bodyStream, contentType] = extractBody(body)

‎lib/mock/mock-interceptor.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,7 @@ class MockInterceptor {
7474
if (opts.query) {
7575
opts.path = buildURL(opts.path, opts.query)
7676
} else {
77-
// Matches https://github.com/nodejs/undici/blob/main/lib/fetch/index.js#L1811
77+
// Matches https://github.com/nodejs/undici/blob/main/lib/web/fetch/index.js#L1811
7878
const parsedURL = new URL(opts.path, 'data://')
7979
opts.path = parsedURL.pathname + parsedURL.search
8080
}

lib/cache/cache.js renamed to lib/web/cache/cache.js

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,15 +2,15 @@
22

33
const { kConstruct } = require('./symbols')
44
const { urlEquals, getFieldValues } = require('./util')
5-
const { kEnumerableProperty, isDisturbed } = require('../core/util')
5+
const { kEnumerableProperty, isDisturbed } = require('../../core/util')
66
const { webidl } = require('../fetch/webidl')
77
const { Response, cloneResponse, fromInnerResponse } = require('../fetch/response')
88
const { Request, fromInnerRequest } = require('../fetch/request')
99
const { kState } = require('../fetch/symbols')
1010
const { fetching } = require('../fetch/index')
1111
const { urlIsHttpHttpsScheme, createDeferredPromise, readAllBytes } = require('../fetch/util')
1212
const assert = require('node:assert')
13-
const { getGlobalDispatcher } = require('../global')
13+
const { getGlobalDispatcher } = require('../../global')
1414

1515
/**
1616
* @see https://w3c.github.io/ServiceWorker/#dfn-cache-batch-operation

0 commit comments

Comments
 (0)