Cách dùng đúng Array.splice() trong JavaScript... nếu bạn có hơn 10000 element
TLDR:
- Array method mà xoá elements trong JavaScript scale như O(n)
- JavaScript dùng inline-caching để có dynamic objects nhanh
- HiddenClass ghi nhớ thứ tự properties, giúp các Objects sử dụng inline-caching
- Array có thứ tự nên không thể dùng HiddenClass
- Khi Array phải dùng property (khi có empty index) thì sẽ không còn inline-cache nữa
- Vì thế khi sử dụng Array.method cho array lớn ta có thể pass replacement items (eg: Array.splice(i, 2, false, false) hoặc dùng cấu trúc khác như Set và Objects để đạt hiệu năng tối đa của JavaScript
Một hôm mình gặp lời khuyên từ một anh senior rằng sử dụng Set sẽ nhanh hơn Array khi viết state trong React.
Mình đã tham khảo vài dí dụ trên mạng và dùng Code này:
const timer = function() {
const start = new Date()
return {
stop: function() {
const end = new Date()
const time = end.getTime() - start.getTime()
console.log('Operation', 'finished in', time, 'ms\n')
}
}
}
const genRandom = function(min, max) {
return Math.random() * (max - min) + min
}
const values = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
const genValue = function () {
const index = Math.round(genRandom(0, values.length - 1))
return values[index]
}
const randomProperties = ['prop1', 'prop2', 'prop3', 'prop4', 'prop5']
const genRandomProperty = function() {
const index = Math.round(genRandom(0, randomProperties.length - 1))
return randomProperties[index]
}
const RandomObject = function() {
this.value = genValue()
this.property = genRandomProperty()
this.numeric = Math.round(genRandom(0,100))
}
const genRandomObjects = (iterable, iteration) => {
for (let i = 0; i < iteration; i++) {
if (iterable instanceof Array) {
iterable.push(new RandomObject())
} else if (iterable instanceof Set) {
iterable.add(new RandomObject())
} else {
console.error('Not array or set')
}
}
}
// Arrow function for accessing name
const changeProperty = (iterable) => {
if (iterable instanceof Array) {
for (let i = 0; i < iterable.length; i++) {
iterable[i].property = genRandomProperty()
}
} else if (iterable instanceof Set) {
for (let key of iterable) {
key.property = genRandomProperty()
}
} else {
console.error('Not array or set')
}
}
const deleteProp1 = (iterable) => {
for (let key of iterable) {
if (key.property === 'prop1') {
iterable.delete(key)
}
}
}
const deleteProp1Array = (iterable) => {
for (let i = 0; i < iterable.length; i++) {
if(iterable[i].property === 'prop1') {
iterable.splice(i, 1)
i--
}
}
}
const randomInsertArray = (iterable) => {
for (let i = 0; i < iterable.length; i++) {
if(iterable[i].property === 'prop1') {
iterable.splice(i, 0, 'random')
}
}
}
const deleteProp1Packed = (iterable) => {
for (let i = 0; i < iterable.length; i++) {
if(iterable[i].property === 'prop1') {
iterable.splice(i, 1, 'nothing')
i--
}
}
}
const deleteProp2Packed = (iterable) => {
for (let i = 0; i < iterable.length; i++) {
if(iterable[i].property === 'prop1') {
iterable.splice(i, 2, 'nothin','nothin')
}
}
}
const test = function(callBack, name) {
let newTimer = timer("Set")
callBack()
console.log(`Operation ${name} succeeded`)
newTimer.stop()
}
let iterations = process.argv[2]
let objectArray = []
console.log(`Testing array operations with ${iterations} iterations`)
test(() => genRandomObjects(objectArray, iterations), "array generation")
let objectArrayCopy = [...objectArray]
let objectArrayCopy2 = [...objectArray]
let objectInsertArrayCopy = [...objectArray]
test(() => changeProperty(objectArray), "array modification")
test(() => deleteProp1Array(objectArray), "array deletion")
test(() => deleteProp1Packed(objectArrayCopy), "packed deletion")
test(() => deleteProp2Packed(objectArrayCopy2), "packed 2 deletion")
console.log(`There was ${iterations} objects generated. ${iterations - objectArray.length} objects deleted`)
let objectSet = new Set()
console.log(`Testing set operations with ${iterations} iterations`)
test(() => genRandomObjects(objectSet, iterations), "set generation")
test(() => changeProperty(objectSet), "set modification")
test(() => deleteProp1(objectSet), "set deletion")
console.log(`There was ${iterations} objects generated. ${iterations - objectArray.length} objects deleted`)
Mình cũng thấy tò mò nên lên mạng coi thử thì thấy hoá ra khá đúng. Sau đây là kết quả:
Kết quả 10.000 elements
Kết quả 50.000 elements
Kết quả với 500.000 elements...
Lần này máy mình mém đóng băng...
Và với 1.000.000 elements thì Node trên máy mình đứng luôn (CPU i5 12400 / 32gb RAM)
Qua đoạn test sau thì có thể thấy là Array.splice() chậm hơn set.delete thì chậm hơn x22000 lần... mà các operations khác thì bthg.
Nên mình nghĩa là cái này có đụng gì đó tới splice nó xoá và phải re-shift thứ tự array.
Mà nếu do Array.splice() nó delete thì maybe chỉ cần replace với một value nào đó mình placeholder là empty như false thì hiệu năng y chang modify.
Và thế là hết, miễn sao trong array lớn không đụng tới thứ tự là hiệu năng ok....
He he nhưng mà vẫn chưa hiểu rõ nên mình procrastinate bằng cách đi tìm thử nguồn gốc tại sao. Mấy anh trên stack overflow trả lời dựa trên big O và implementation trong V8, gì đó liên quan đến inline caching, hidden class... mà không nói rõ tại sao.
Trong phần sau, mình sẽ bàn về các chủ đề này để làm rõ lý do tại sao điều này lại xảy ra và đi qua các khái niệm liên quan như Named vs Index properties, HiddenClass, Inline-caching để giải thích hành vi này của JavaScript.
Properties trong JavaScript engine
HiddenClass
HiddenClass là một chức năng để JavaScript có chức năng thay đổi object property. Mọi Object trong các JavaScript engine hiện đại đều có HiddenClass.
HiddenClass chứa thông tin của bất kỳ thay đổi nào lên Object. Nếu thêm hay đổi thứ tự hoặc xoá property thì HiddenClass thì phân nhánh, tạo ra một chuỗi hiddenClass cho từng thay đổi, theo cấu trúc Directed Acylic Graph
Nếu các Object có cùng HiddenClass thì khi ta retrieve property nào đó thì engine không phải lookup mà chỉ cần nhớ vị trí của các properties của nhiều Object chung HiddenClass.
Inline caching
Tại sao JavaScript cần phải làm điều này?
JavaScript là dynamic language, điều này có nghĩa là JavaScript cho phép người dùng thay đổi property của Object sau khi đã initialized.
Object là cấu trúc dữ liệu phức tạp. Để có thể chứa được cấu trúc này trong memory thì các ngôn ngữ khác phải map chính xác vị trí từng thành phần của Object trong memory, nên vì thế không cho thay đổi property.
Trong engine, khi thay đổi properties thì engine vẫn sẽ phải thực hiện chức năng lookup dynamically mỗi khi đụng tới objects. Chức năng này cực kỳ tốn kém.
Nếu các bạn để ý, HiddenClass ghi nhớ lại "vị trí từng property theo thứ tự chính xác", giống hệt cách non-dynamic language map property. Vị trí này sẽ được HiddenClass lưu trữ trong một Array (gọi là properties store) với mỗi offset của từng property trong Array được lưu lại.
Nhờ HiddenClass, mỗi khi truy cập các properties của các Object có HiddenClass giống nhau thì Object chỉ cần tìm đến offset đã được lưu trong HiddenClass về vị trí của property trong properties store. Biểu đồ dưới miêu tả quá trình này (Shape là HiddenClass)
Kỹ thuật này gọi là "inline caching".
Vì phải giữ mỗi vị trí và trật tự của từng property nên HiddenClass thì phải được thay đổi ngay từ khi từng Object được tạo và thay đổi.
V8 đánh đổi sự phức tạp của HiddenClass để có thể thay đổi Object property nhanh như non-dynamic language.
Về chi tiết, Properties có thể được chứa trong bản thân Object nhưng số lượng có hạn. Nếu nhiều hơn thì sẽ được đưa properties store (array). Các properties được inline cache thì được V8 gọi là "fast" properties.
Nhờ HiddenClass mà bất kỳ code nào đụng tới property có chung HiddenClass thì không phải lookup mà chứa sẵn trong properties array store và mỗi property trong properties array store có số "offset" có thể tìm trong O(1) trong HiddenClass.
Tuy nhiên, không có gì là free cả, các property không đc cache thì lại là slow properties.
Trở về với HiddenClass và properties store array trên, khi nhiều properties bị thay đổi (xoá) thì sẽ có rất nhiều HiddenClass và Properties store array được tạo ra và gây tốn tài nguyên memory và thời gian.
Vì thế, để có thể giảm thiểu performance cost của cơ chế này thì JavaScript dùng "slow properties".
Đơn giản là vì JavaScript không dùng HiddenClass (và vì thế inline caching) cho các properties này mà vẫn đổi property được nên phải dùng dictionary lookup.
Mà như đã bàn ở phần dynamic vs non-dynamic language, thì performance cost của việc này là cực kỳ nhiều so với O(1).
HiddenClass và Inline caching trong Array
Những gì ta bàn ở trên trở nên phức tạp hơn một chút với Array. Trong memory, Array cơ bản được store trong một nơi khác name properties như object. Tại sao?
Array có một sự phức tạp là access pattern của chúng khác với objects. Objects thì thường được sử dụng như là cấu trúc còn Array thì thông tin thay đổi nhiều hơn. Vì thế việc sử dụng HiddenClass cho Array tốn kém hơn nhiều do có sự thay đổi nhiều.
Vì thế, inline caching trong Array chỉ đơn giản là chứa mỗi elements trong một elements store là array.
Trong biểu đồ trên "Shape" giống HiddenClass nhưng chỉ có một mà không đổi.
Ngoài ra, Objects có named properties trong khi Array thì properties được indexed (luôn theo số thứ tự). Những trường hợp như những index bị trống có (bị xoá) có thể gây vấn đế với chức năng.
Ví dụ, vì JavaScript là một prototype-based language nên khi array bị trống thì việc xử lý các index trống có thể dẫn đến việc lookup cho index đó trên prototype tree.
Tuy nhiên, array-indexed properties (element trong array) thì lại không có HiddenClass.
Vì Array không dùng HiddenClass nên để chứa các index trống thì JavaScript chọn cách đặc một giá trị là "the_hole" để Array vẫn có thứ tự và không phải lookup lên prototype của nó.
Fast (inline) và Dictionary elements
Tuy nhiên, điều này cũng có giới hạn. Vì JavaScript không muốn phải phí không gian chứa Array có nhiều lỗ hổng, đặc biệt cho các Array nhiều elements, nên JavaScript sẽ dùng Dictionary để chứa Elements thay vì array elements store.
Nếu ta thay đổi property của Array như Objects thì nó sẽ bị chứa như Dictionary.
Và từ đó hiệu năng của Inline caching sẽ không còn nữa. Để có thể support nhiều data type trong array, engine của JavaScript phân biệt nhiều loại array packed (không lỗ) hay holey (có lỗ) với nhiều data types khác nhau và dispatch chức năng cho C++
Trong thuật toán của method Array.splice() trong JavaScript. Bản thân nó chia ra thành 2 path là fast và slow. Nếu số element bị xoá khác số element thêm vào thì nó sẽ phải dùng một vài method mà sẽ khiến Array hoạt động theo dạng dictionary.
Và vì thế đó là lý do tại sao nếu ta gọi bất kỳ function modify thứ tự Array cho các Array có nhiều elements thì có thể có performance impact cao.
Tuy nhiên, chỉ cần ta nhớ rằng mọi Object và Array đều có 2 path là Slow và Fast là có thể dễ dàng optimize code của mình.
Cảm ơn các bạn đã đọc bài viết dài và phức tạp!
Mình xin lỗi nếu có sai sót gì. Mình chỉ viết để học tập nên nếu có sai sót gì xin các bạn bỏ qua và sửa sai giúp mình nhé.
Nguồn tham khảo:
All rights reserved
