Conversation

Notices

1. Embed this notice
   KOMIYA Atsushi (komiya_atsushi@mastodon.cloud)'s status on Tuesday, 25-Jul-2023 10:41:27 JST KOMIYA Atsushi

   BigInt を使うという手も考えたが、BigInt は任意精度の整数みたいなので（もしかしたら処理系によっては 2^64 以下の数値の場合に最適化された実装がなされているかもしれないけどそのあたりがいまいち読めないので）パフォーマンスが気になってしまう。

   • Embed this notice
     Hiroshi Kurokawa (hydrakecat@mastodon.cloud)'s status on Tuesday, 25-Jul-2023 10:41:24 JST Hiroshi Kurokawa

     in reply to

     @komiya_atsushi JSに一切詳しくないのですが、なんのために40ビットのビットシフトが必要なんでしょうか。浮動小数点数演算で2のべき乗の除算をするのは指数部を変更するだけになるので、あまり意味のない操作になりそうな気がしたのでした。

   • Embed this notice
     KOMIYA Atsushi (komiya_atsushi@mastodon.cloud)'s status on Tuesday, 25-Jul-2023 11:44:26 JST KOMIYA Atsushi

     in reply to

     • Hiroshi Kurokawa

     @hydrakecat 具体的な話をしてしまうと ULID を JS で実装（車輪の再発明）しようとしていて、ミリ秒の時刻 (これは 48 ビット) や 80 ビットの乱数列（40 ビットに分割して 2 つの数値で表現する想定）を Base 32 エンコードするときに右ビットシフト＆ビット AND で処理しようとしたのがきっかけの話題でした。

   • Embed this notice
     Hiroshi Kurokawa (hydrakecat@mastodon.cloud)'s status on Tuesday, 25-Jul-2023 12:09:14 JST Hiroshi Kurokawa

     in reply to

     @komiya_atsushi あー、なるほどです。うーん、ビットANDは剰余演算でやる感じですよね。浮動小数点数の演算がどれくらい最適化されるかよく分かりませんが、40ビットくらいなら自分はUint8Arrayも候補に入れるかもです。Base32エンコード前提で5ビット分ずつ保持しておくとか？あ、でもそれだとBase32エンコードのまま計算するこれと一緒になるのか。再発明したいのは、これが遅いからですかね……。
     https://github.com/ulid/javascript/blob/a5831206a11636c94d4657b9e1a1354c529ee4e9/lib/index.ts

   • Embed this notice
     KOMIYA Atsushi (komiya_atsushi@mastodon.cloud)'s status on Wednesday, 26-Jul-2023 09:17:09 JST KOMIYA Atsushi

     in reply to

     • Hiroshi Kurokawa

     @hydrakecat ですです。厳密に速度を計測したわけではないのと、あと普通に使う分にはたぶんこの実装で十分な気はしていますが、ちょっと速くできそうな余地があったので再発明してみようかな、と思ったのでした。

     なお Base 32 エンコードを (10 ビット消費して) 一度に 2 文字ずつテーブルルックアップで変換する方法を雑に実装して jsperf で速度を比較してみましたが、これは L2 キャッシュに載らなくなるせいか、2 倍ぐらい遅い結果になりました 😇

   • Embed this notice
     KOMIYA Atsushi (komiya_atsushi@mastodon.cloud)'s status on Wednesday, 26-Jul-2023 09:38:40 JST KOMIYA Atsushi

     in reply to

     • Takuo Kihira 🍧

     @tkihira 僕も jsperf で雑に比較をしていましたが、比較の仕方がよくなかったのか、除算と BigInt + 右シフトの結果に差が出ていませんでした。ベンチマーク難しい…

   • Embed this notice
     Takuo Kihira 🍧 (tkihira@mstdn.jp)'s status on Wednesday, 26-Jul-2023 09:38:41 JST Takuo Kihira 🍧

     in reply to

     @komiya_atsushi 直感ですが BigInt の方がパフォーマンスが出そうな気がします。BigInt 周りはかなり最適化されているので

   • Embed this notice
     Takuo Kihira 🍧 (tkihira@mstdn.jp)'s status on Wednesday, 26-Jul-2023 09:38:41 JST Takuo Kihira 🍧

     in reply to

     @komiya_atsushi すみません、全然嘘でした。比較にならないレベルで Number の方が速かったです
     https://jsperf.app/fokiho/1/preview

   • Embed this notice
     Takuo Kihira 🍧 (tkihira@mstdn.jp)'s status on Wednesday, 26-Jul-2023 09:38:41 JST Takuo Kihira 🍧

     in reply to

     @komiya_atsushi 察するに、V8 の BigInt は多分多倍長整数演算は GMP なり何なりのライブラリを利用しており、それらのライブラリは 64 bit 以下の数値を最適化するインセンティブがないので（uint を使えばいい）、その結果としてこれだけ遅くなってしまったのだと推測しております