Mô phỏng 20 triệu hạt bằng JavaScript

 (dgerrells.com)
4 điểm bởi GN⁺ 2024-07-09 | 1 bình luận | Chia sẻ qua WhatsApp
  • Bắt đầu từ mô phỏng hạt JavaScript chỉ dùng CPU, tác giả đạt mục tiêu 1 triệu hạt ở 60fps trên điện thoại và mở rộng ví dụ cuối cùng lên tới 20 triệu hạt
  • Cốt lõi về hiệu năng là tránh mảng đối tượng, đặt dữ liệu hạt trong bộ nhớ liên tục bằng TypedArray và SharedArrayBuffer, đồng thời chia việc theo từng lõi CPU bằng Web Worker
  • Nút thắt thực tế bộc lộ rõ hơn ở khâu vẽ màn hình và truy cập bộ nhớ thay vì tính vị trí hạt, và việc ghi ngẫu nhiên vào pixel buffer gây ra CPU cache miss
  • Tác giả từng bước giảm bottleneck qua pixel buffer riêng cho từng Worker, đồng bộ bằng postMessage, double buffering, lưới đếm số hạt theo pixel, và render texture trên GPU
  • Kiến trúc cuối cùng để CPU mô phỏng và GPU render texture lưới theo độ phân giải màn hình, xử lý khoảng 20 triệu hạt ở ~20fps trên M1 Mac

Mục tiêu và cách tiếp cận cơ bản

  • Thử thách là mô phỏng 1 triệu hạt ở 60fps trên điện thoại chỉ bằng JavaScript thuần và CPU, không dùng WebAssembly
  • Tác giả cho rằng mảng đối tượng JavaScript đơn giản có giới hạn về hiệu năng đơn lõi trên di động và cách bố trí bộ nhớ, nên chọn cách xử lý dữ liệu bằng mảng liên tục
  • Với khối lượng tính toán lớn, mảng bộ nhớ liên tục và dày đặc để có thể đưa nhiều dữ liệu nhất có thể vào CPU cache là rất quan trọng
  • Mảng và đối tượng JavaScript thông thường khó đảm bảo được bố trí dày đặc như mảng hay struct trong ngôn ngữ cấp thấp
  • TypedArray cho phép tạo mảng byte liên tục có kích thước cố định, giúp quản lý bộ nhớ ở mức tương đối thấp trong JavaScript

Bản triển khai đầu tiên: SharedArrayBuffer và Web Worker

  • Dữ liệu hạt được lưu bằng cách đặt view Float32Array lên trên SharedArrayBuffer
    • Mỗi hạt được biểu diễn bằng bốn giá trị số thực 32-bit: x, y, dx, dy
    • Dùng stride = 4, byte_stride = stride * 4 để index buffer phẳng
  • Mô phỏng bắt đầu từ cập nhật vị trí đơn giản ở mỗi frame với x += dx, y += dy
  • Multithreading được cấu thành từ Web Worker và SharedArrayBuffer
    • Main thread chia các chunk hạt cho từng Worker
    • Worker chỉ đọc và ghi chunk được giao để tránh nhiều thread cùng ghi vào một vùng nhớ
  • Để dùng SharedArrayBuffer trong trình duyệt cần các header sau
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • Cơ chế đồng bộ ban đầu dùng một SharedArrayBuffer chuyên để báo hiệu
    • Main thread ghi tín hiệu chạy cho Worker
    • Worker kiểm tra tín hiệu bằng setInterval(..., 1), rồi ghi trạng thái sẵn sàng khi xong việc
  • Render dùng ImageData theo kiểu một rasterizer chạy trên CPU
    • Mỗi hạt được vẽ thành một pixel trên màn hình
    • Hạt nằm ngoài màn hình sẽ bị bỏ qua để tránh truy cập ngoài phạm vi mảng
    • Dùng putImageData để vẽ kết quả lên Canvas
  • Profiling ban đầu cho thấy phần việc của Worker chỉ tốn vài ms, còn phần lớn thời gian dành cho render trên main thread
  • Bộ nhớ được cấp phát một lần khi khởi động và không tạo object mới trong vòng lặp mô phỏng, nên gần như không phát sinh garbage

Bản triển khai thứ hai: đầu vào và tương tác kiểu trọng lực

  • Dữ liệu đầu vào được thêm vào SharedArrayBuffer đang dùng cho trạng thái mô phỏng
    • Lưu delta time, tọa độ chuột x/y, trạng thái chạm, chiều rộng/chiều cao màn hình
    • Trạng thái chạm gần như là boolean nhưng vẫn dùng 4 byte
  • Tác giả thêm hiệu ứng để hạt bị hút về điểm chạm khi người dùng nhấn lên màn hình
    • Có tham khảo dạng 1 / r² của công thức trọng lực thật, nhưng được chỉnh lại để ưu tiên tương tác thú vị hơn là mô phỏng vật lý chính xác
    • Thêm suy hao tương đương ma sát để hạt không tăng tốc vô hạn rồi bay khỏi màn hình
  • Màu render cũng được sửa để thay đổi theo vị trí hạt
    • Điều chỉnh giá trị kênh RGB bằng x / width, y / height
    • Nếu lưu màu riêng cho từng hạt thì kích thước hạt sẽ tăng lên, nên tác giả dùng màu theo vị trí để giảm lượng dữ liệu
  • Có thể thử nghiệm tới 2 triệu hạt và thay đổi số lượng hạt bằng query parameter count trong URL
  • Ở 10 triệu hạt, framerate giảm mạnh, và profiling cho thấy ghi pixel vào ImageData chậm hơn cả Worker
  • Khi chỉ ghi kênh xanh dương và alpha thay vì toàn bộ RGB, thời gian render trên một số môi trường giảm từ khoảng 80~90ms xuống 16~18ms
    • Mức chênh lệch này khác nhau tùy CPU, và trên desktop Ryzen còn rõ hơn so với M1 MacBook Air

Bản triển khai thứ ba: Worker ghi pixel buffer

  • Để tận dụng nhiều lõi CPU hơn, Worker được giao thêm việc vẽ pixel chứ không chỉ mô phỏng
  • Để tránh nhiều Worker cùng ghi vào một pixel buffer, tác giả dùng pixel buffer riêng cho từng Worker
    • Dùng SharedArrayBuffer kích thước CPU_CORES * window.innerWidth * window.innerHeight * 3
    • Mỗi Worker có một RGB buffer toàn màn hình riêng
  • Main thread cộng dồn toàn bộ pixel buffer của các Worker rồi ghi vào ImageData
  • Bản này xuất hiện hiện tượng màn hình nhấp nháy
    • Main thread đọc cùng buffer đúng lúc Worker đang xóa buffer của nó bằng fill(0)
    • Ở các bản trước, việc đọc dữ liệu cũ từ frame trước không dễ nhận ra, còn lần này thao tác xóa của Worker lộ rõ thành hiện tượng nhấp nháy từng phần
  • Các hướng xử lý được cân nhắc gồm đồng bộ bằng Atomics, chờ Worker hoàn tất qua postMessage, và double buffering

Bản triển khai thứ tư: đồng bộ bằng postMessage

  • Để loại bỏ nhấp nháy, tác giả bỏ mảng tín hiệu và đổi sang báo Worker hoàn tất bằng postMessage
  • Main thread quản lý giá trị activeWorkers
    • Mỗi khi một Worker xong việc sẽ gửi message và làm giảm activeWorkers
    • Khi tất cả Worker xong, main thread mới render rồi yêu cầu requestAnimationFrame tiếp theo
  • Cách này giải quyết được hiện tượng nhấp nháy
  • Tuy nhiên thời gian frame không cải thiện nhiều, thậm chí còn có thể tệ hơn
    • Vì main thread không làm gì trong lúc chờ Worker hoàn tất
    • Với 2 triệu hạt, có trường hợp tiết kiệm được khoảng 7ms nếu Worker không phải chờ main thread render
  • Để giảm bottleneck này, tác giả áp dụng double buffering vốn phổ biến trong driver đồ họa

Bản triển khai thứ năm: double buffering và bottleneck cache

  • Double buffering tạo hai pixel buffer và đổi buffer hoạt động sau mỗi frame
    • Trong khi main thread vẽ một buffer, Worker chuẩn bị frame kế tiếp trên buffer còn lại
  • Sau khi áp dụng, Worker không còn phải chờ main thread render, và một số frame trước đó vượt 50ms nay gần hơn với 16ms
  • Phần code vẫn chậm là ba dòng cộng giá trị vào các kênh RGB của pixel buffer
  • Nguyên nhân là dù dữ liệu được lưu liên tục, thứ tự truy cập lại không liên tục
    • pixelIndex tính từ x, y của hạt không được sắp theo thứ tự mảng hạt
    • Mỗi vòng lặp đều nhảy đến vị trí ngẫu nhiên trong pixel buffer, gần như một mẫu truy cập ngẫu nhiên
  • Kiểu truy cập này gây cache miss khi dữ liệu hạt và dữ liệu pixel không cùng nằm gọn trong cache
  • Ví dụ tính toán trên iPhone như sau
    • Công thức: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • Kết quả vượt 15MB, quá lớn để đưa vào L1 cache
  • Ở bản này, trên chip M1, mô phỏng 2 triệu hạt mất khoảng 4ms, truy cập dữ liệu pixel mất khoảng 3.5ms, và ghi vào pixel buffer mất khoảng 7ms
  • Trên điện thoại có thể giữ 60fps với 1 triệu hạt, nhưng trên desktop có hơn 20 thread, main thread phải cộng dồn hơn 20 pixel buffer mỗi frame nên tốn tới 30ms

Bản triển khai thứ sáu: lực kéo về vị trí ban đầu

  • Hiệu ứng mới là hạt càng rời xa vị trí ban đầu thì càng bị hút mạnh trở lại
  • Để làm vậy, mỗi hạt được thêm hai giá trị vị trí ban đầu sx, sy
    • Một hạt có sáu float: x, y, dx, dy, sx, sy
    • particleStride tăng lên 6
  • Code Worker được thêm hàm tính lực và dùng object cache để tránh tạo garbage
  • Kết quả tạo ra hiệu ứng hình ảnh giống thạch hoặc chất lỏng, với các xoáy hạt như giấy hay vải bị vò lại
  • Từ đây xuất hiện ý tưởng không lưu pixel buffer theo từng Worker nữa mà chuyển sang một lưới chỉ đếm số hạt trên mỗi pixel

Bản triển khai thứ bảy: lưới đếm số hạt theo pixel

  • Thay vì lưu giá trị RGB, chỉ lưu số lượng hạt ở từng vị trí pixel sẽ giảm bộ nhớ xuống còn 1/3
  • Vì màu được tính từ vị trí x, y chứ không phải dữ liệu riêng của từng hạt, nên chỉ cần số đếm theo pixel là đủ để render
  • Tác giả đổi sang để tất cả Worker cùng chia sẻ một lưới đếm số hạt
    • Main thread không còn phải cộng dồn buffer riêng của từng Worker
    • Vấn đề chi phí cộng render tăng theo số lượng Worker được giải quyết
  • Công thức tính cache mới là
    • screen width * screen height + bytes per particle * total particles / number of workers
    • Trên iPhone: 2532 * 1170 + 16 * 2,000,000 / 5
    • Khoảng 9.3MB, giảm khoảng 30% so với trước nhưng vẫn quá lớn cho L1 cache
  • Render duyệt toàn bộ pixel, đọc số hạt tại pixel đó, tính RGB rồi đặt lại lưới bằng fill(0)
  • Sau khi mô phỏng, Worker tính pCountIndex cho hạt còn trong màn hình rồi thực hiện activeGrid[pCountIndex]++
  • Thay đổi này đặc biệt hữu ích khi có nhiều Worker, và trên desktop có thể dùng đủ cả 24 thread
  • Dù vậy, có trường hợp M1 MacBook Air vẫn nhanh hơn desktop Ryzen 9 3900X
    • Ryzen 9 3900X có L3 cache 64MB nhưng L1 chỉ 64KB
    • M1 thế hệ đầu có L1 cache 320KB, trong đó 128KB cho dữ liệu và 192KB cho lệnh
    • Có vẻ L1 data cache lớn hơn giúp giảm độ trễ chờ bộ nhớ

Giới hạn của tối ưu hóa chỉ dùng CPU

  • Sau nhiều tối ưu hóa, tác giả đạt khoảng 2x cải thiện tốc độ so với bản multithread đầu tiên
  • Mục tiêu xử lý 1 triệu hạt 60fps trên điện thoại bằng JavaScript thuần chạy CPU đã hoàn thành
  • Tuy nhiên kết quả tổng thể không hẳn quá ấn tượng, và tác giả kỳ vọng ngôn ngữ biên dịch có thể nhanh hơn 10 lần
  • Nếu dùng được lệnh SIMD trong tight loop thì vẫn còn dư địa tăng tốc
  • Ở bước tiếp theo, tác giả giữ mô phỏng trên CPU nhưng chuyển riêng phần render sang pipeline GPU truyền thống để so sánh

20 triệu hạt và render bằng GPU

  • So sánh render GPU đầu tiên dùng GPU instancing của threejs để vẽ một plane/quad cho mỗi hạt
  • Cách này có hiệu năng thấp hơn kỳ vọng
    • Instancing trong threejs cần cập nhật matrix cho từng vị trí hạt, và việc này chạy trên CPU đơn luồng
    • Dữ liệu biến đổi của hạt phải được upload lên GPU mỗi frame, và chính việc truyền này bị chậm
  • Khi mô phỏng 4 triệu hạt trên chip M1, 80% thời gian frame dùng để gửi dữ liệu sang GPU
  • Trên desktop, tỷ lệ thời gian truyền dữ liệu là 30%, nhưng đây vẫn là bottleneck lớn nhất
  • Phương án thay thế là dùng lưới đếm số hạt đã tạo ở trên như một texture và render một quad toàn màn hình
    • Lượng dữ liệu gửi sang GPU được cố định theo độ phân giải màn hình thay vì số lượng hạt
    • Đây là một đánh đổi: mô phỏng lớn sẽ giảm lượng truyền, nhưng mô phỏng nhỏ có thể lại gửi nhiều dữ liệu hơn
  • Với threejs và custom pixel shader, bản thử nghiệm được dựng rất nhanh và render trên main thread chỉ mất vài ms, gần như không phụ thuộc quy mô mô phỏng
  • Trong kiến trúc này, Worker chạy nhanh nhất có thể, còn mô phỏng bị ràng buộc trực tiếp vào số lõi CPU ở cả bài toán lớn lẫn nhỏ
  • Mỗi Worker dành khoảng 50% thời gian cho tính toán số học và khoảng 50% cho cập nhật số đếm trong lưới hạt
  • Hiệu năng của bản cuối như sau
    • Trên M1 Mac chạy bằng pin, 20 triệu hạt đạt khoảng 20fps
    • Trên desktop, khoảng 30 triệu hạt cho fps tương tự
    • Theo bài test của một người bạn dùng CPU 32 lõi, con số này lên tới khoảng 40 triệu hạt
  • Demo liên quan:

Tổng kết

  • CPU và GPU có thể xử lý phép tính số rất nhanh
  • Phần chậm nằm ở việc di chuyển dữ liệu, đặc biệt là truy cập bộ nhớ ngẫu nhiên
  • Muốn viết code nhanh, cần hiểu phần cứng cache và di chuyển dữ liệu như thế nào
  • SharedArrayBuffer và Web Worker rất hữu ích cho các thử nghiệm tận dụng nhiều lõi trong JavaScript
  • Tác giả dự định thử compute shader khi WebGPU được chấp nhận rộng rãi hơn

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-07-09
Ý kiến trên Hacker News

  • Sẽ tốt hơn nếu nhúng trực tiếp mô phỏng vào trong bài blog
    Tôi đã phải cuộn lên cuộn xuống khá lâu mới tìm ra link tới mô phỏng thực tế
    Cũng có thể chọn một mức chạy ổn trên cả điện thoại cũ, hoặc cho nó tự điều chỉnh theo tốc độ khung hình, hay đơn giản là đặt vài liên kết ngay đầu bài
    https://ciechanow.ski/ là một ví dụ đẳng cấp thế giới cho thấy việc đưa mô phỏng vào trong bài viết có thể tuyệt vời đến mức nào
    Ngày xưa website nào cũng từng nhúng những yếu tố tương tác ngầu như vậy
    Và tôi nghĩ vẫn có thể chạy mô phỏng hạt trên GPU mà không cần WebGPU
    Ví dụ: https://news.ycombinator.com/item?id=19963640

    • Đây là một trong những ví dụ xuất sắc nhất về blog giải thích mà tôi từng thấy
      Ước gì đây trở thành chuẩn mực cho việc chia sẻ thông tin. Nếu đã đáng để chia sẻ thì cũng đáng để làm cho dễ hiểu
    • Mô phỏng chất lỏng đó thực sự đáng kinh ngạc
    • Tôi đồng ý là nhúng trực tiếp sẽ tốt hơn
      Tôi đã cân nhắc nhúng từng phiên bản, nhưng lo là sẽ có quá nhiều worker chạy cùng lúc
      Tôi dự định sẽ cập nhật để nhúng phiên bản cuối ở cuối bài
      Blog đó có mức độ hoàn thiện cực cao ở từng ví dụ, thực sự rất hay
      Chỉnh sửa: tôi đã thử thêm bản nhúng, nhưng các header cần thiết không hợp với những bản nhúng khác, và các phiên bản cũ vẫn còn bị khóa trong codesandbox
    • Chỉ cần ghi “nếu muốn nghịch bản app hoàn chỉnh thì hãy nhảy xuống cuối” là được

  • Tôi vừa thử trực tiếp bản demo trên di động [0], khá ấn tượng
    [0] https://dgerrells.com/sabby

    • Nó còn hoạt động với nhiều ngón tay
      Thật ấn tượng khi đây là JavaScript thuần, và việc độ trễ tăng lên theo số ngón tay khiến tôi nghĩ là có nhiều dữ liệu hơn đang qua lại giữa các thread
    • Trông kỳ lạ mà hữu cơ, giống như cấu trúc lipid trong món súp nguyên thủy
    • Tôi khá hài lòng vì trên điện thoại của mình, Firefox chạy tốt hơn Chrome

  • Chỉ tò mò thôi, nhưng tôi tự hỏi liệu có thể mã hóa dữ liệu này vào một số JS duy nhất thay vì biểu diễn mỗi hạt bằng bốn số thực dấu phẩy động 32 bit là x, y, dx, dy hay không
    Phạm vi số nguyên an toàn của JS là 2^53 - 1 = 9,007,199,254,740,991, còn phạm vi Float32Array dùng trong bài là từ -3.4e38 đến 3.4e38
    Ví dụ nếu vị trí màn hình là canvas 1000x1000 thì có thể biểu diễn bằng các số từ 0~1,000,000, và ngay cả khi thêm 10 mức dưới pixel thì cũng mới là 100,000,000, vẫn dư sức nằm trong phạm vi của JS
    Tốc độ dx, dy cũng được tính bằng số thực ngẫu nhiên trong khoảng -10 đến +10 qua (Math.random()*2-1)*10, nhưng nếu chỉ cần một chữ số thập phân là đủ thì có thể đổi sang phạm vi số nguyên từ -100~+100, và như vậy chỉ cần 10,000 giá trị khả dĩ
    Kết hợp cả hai thì 10,000 * 100,000,000 = 1,000,000,000,000, tức một nghìn tỷ giá trị để biểu diễn hạt, vẫn nằm trong MAX_SAFE_INTEGER của JS
    Vậy nên có vẻ có thể nhét dữ liệu của một hạt vào một MAX_SAFE_INTEGER duy nhất hoặc một phần tử Float32Array, như vậy sẽ không cần stride và tính nhất quán của dữ liệu cũng có thể chắc chắn hơn
    Tuy nhiên cũng có thể chi phí mã hóa/giải mã lớn hơn phần bộ nhớ tiết kiệm được, nên xét về hiệu năng thì hoàn toàn không đáng

  • Rất ấn tượng, nhưng tôi thắc mắc đoạn này
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    Ngoại trừ waitAsync[1], Atomics API có vẻ không dùng promise
    Trước đây tôi đã dùng Atomics nhưng không cần xử lý mã bất đồng bộ/promise
    Tôi tò mò không biết bên trong nó có dùng promise hay là tôi đã bỏ sót điều gì
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • Cũng có mô phỏng xử lý gần 20 triệu hạt
    Có thể chạy và lập trình tại đây: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • Video rất hay, nhưng các liên kết codesandbox trong try it out here không hoạt động trên Chrome desktop trên macOS
    Xuất hiện lỗi CORS như Uncaught ReferenceError: SharedArrayBuffer is not defined và ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep

    • Trình chỉnh sửa inline của codesandbox chặn việc thiết lập header, nên phải mở phần xem trước trong tab riêng
      Nếu dùng trình duyệt chú trọng quyền riêng tư thì cũng có thể bị chặn
      Sau này tôi sẽ thử thêm ví dụ nhúng
      Có thể thử bản cuối tại đây: https://dgerrells.com/sabby

  • Tuyệt vời
    Tôi đã dành một giờ để hiểu và vọc mã, rồi làm một bản triển khai thời gian thực ở đây: https://particules.kapochamo.com/index.html

    • Lúc mới mở ra tôi đã rất bất ngờ
      Nó thật sự đẹp, và khó mà tin được JS lại có thể mô phỏng nhiều hạt đến vậy
    • Quá đỉnh
      Ấn tượng vì bạn đã đào sâu vào mã đến mức đó

  • Có lẽ nên thử xem chrome://tracing có mang lại thêm insight không
    Tôi biết đến nó từ đây: https://youtu.be/easvMCCBFkQ?t=114

  • Tôi rất muốn gửi ngay cái này cho đội UI đang làm mấy ứng dụng React chậm chạp
    JS thật sự rất nhanh, và đặc biệt là cực nhanh nếu được viết tốt

    • Vấn đề là JS mang tính thành ngữ và JS nhanh trên thực tế gần như đối lập nhau
      JS nhanh trông giống một phương ngữ C tệ hại, và bạn không nên cấp phát đối tượng cho garbage collection, nhưng ngôn ngữ này lại thiếu các lựa chọn tốt không cần cấp phát
      Hầu như không ai trong một ứng dụng JS phức tạp lại xử lý mọi cấp phát bộ nhớ bằng các con trỏ trong một ArrayBuffer khổng lồ, và nếu đã vậy thì chuyển sang WebAssembly còn dễ hơn
    • JavaScript có lẽ là ngôn ngữ được đầu tư nhiều thời gian công sức của con người nhất cho các tối ưu hóa engine khác nhau
      Điều đáng tiếc là không thể chỉ dựa vào JS mà còn phải trộn nhiều thao tác DOM, và trong UI chúng ta làm thì phần chậm thường chính là các thao tác DOM đó