Upgrade to Pro — share decks privately, control downloads, hide ads and more …

A+Bから始める異常高速化

 A+Bから始める異常高速化

Library Checker: Many A + B (128bit) の問題を題材に、競技プログラミング向け入出力処理の高速化に取り組んだ話

2023-07-18 第4回ComputerScience集会@VRChat にて発表

Mizar

July 19, 2023
Tweet

Other Decks in Programming

Transcript

  1. 競技プログラミング・外典
    A+Bから始める異常高速化
    ~競プロ向け標準入出力周りの高速化研究~
    ComputerScience集会#4 @VRChat 2023-07-18
    Mizar/みざー

    View Slide

  2. 自己紹介
    Mizar/みざー
    VRChatは 2020年5月より
    2022年から競技プログラミング始めました
    AtCoderレーティング Algorithm:水色(最高
    値:1342), Heuristic:水色(1298)
    Rust を主な使用言語として参加
    毎週土曜日(稀に日曜日)21:00~22:40開催の
    AtCoder Beginner Contest (ABC) に参加
    ABC 終了後 23時頃~ VRC競プロ部 で集まって
    ABC感想会をしています
    過去のTalk: 2022-09-23, 2022-09-25 「64bit数の素
    数判定」@理系集会Prime など
    A+Bから始める異常高速化
    Mizar/みざー
    2

    View Slide

  3. Caution: Unsafe Rust
    この発表にはアンセーフなコードを含みます。使用する場合は自己責任でどうぞ。
    画像: The Rustonomicon: Meet Safe and Unsafe より
    Rust 裏本 (Rustonomicon 日本語訳) https://doc.rust-jp.rs/rust-nomicon-ja/
    A+Bから始める異常高速化
    Mizar/みざー
    3

    View Slide

  4. 偉大なる先人は言いました (1)
    -- Michael A. Jackson. Principles of Program Design, Academic Press, 1975
    -- 鳥居宏次訳, “構造的プログラム設計の原理,” 日本コンピュータ協会, 1980.
    A+Bから始める異常高速化
    Rules of Optimization:
    ソフトウェア最適化の原則:
    Rule 1: Don't do it.
    第一法則:最適化するな。
    Rule 2 (for experts only): Don't do it yet.
    第二法則(上級者限定):まだするな。


    Mizar/みざー
    4

    View Slide

  5. 偉大なる先人は言いました (2)
    -- Donald E. Knuth. 1974. Structured Programming with go to Statements. ACM Comput.
    Surv. 6, 4 (Dec. 1974), 261–301.
    A+Bから始める異常高速化
    Programmers waste enormous amounts of time thinking about, or worrying about,
    the speed of non critical parts of their programs, and these attempts at efficiency
    actually have a strong negative impact when debugging and maintenance are
    considered. We should forget about small efficiencies, say about 97% of the time:
    premature optimization is the root of all evil.
    プログラマーは、プログラムの重要でない部分のスピードについて考えたり、悩んだ
    りすることに膨大な時間を浪費している。そして、こうした効率化の試みは、デバッ
    グやメンテナンスのことを考えると、実際には強い悪影響を及ぼす。小さな効率性、
    例えば97%程度の効率性については忘れるべきだ:時期尚早の最適化は諸悪の根源で
    ある。


    Mizar/みざー
    5

    View Slide

  6. Caution: 邪道な高速化の世界へようこそ
    競技プログラミングの楽しみ方としては、本質から外れた、実行時間を可能な限り削るた
    めの小手先の工夫になります。今回の物も自分の趣味色が強い実装なので、AtCoder上で
    の利用を想定した proconio クレートなどへ取り込まれる事も恐らく無いかと思います。
    競技プログラミングの問題の実行時間は、典型的には 2000ms 程度が許されていますが、
    通常の問題では 10ms 程度の影響も出ることのない範囲です。
    逆に、入出力で 0.1ms でもプログラムの実行時間を削りたい人、低レイヤー寄りの高速化
    に興味のある人は、是非挑戦してみてください。
    今回扱う問題は、入出力の量が特に多く、実行時間の入出力部分への影響が比較的大きい
    ものになります。(作問側の想定としても、入出力テストのための問題の一つと位置づけ
    られているようです)
    A+Bから始める異常高速化
    Mizar/みざー
    6

    View Slide

  7. Library Checker: Many A + B (128bit) https://judge.yosupo.jp/problem/many_aplusb_128bit
    問題文: この問題は ケースあります。 整数 が与えられます。 を出力してください。
    制約:
    ( 参考: )
    入力
    出力
    サンプル (上段: 入力サンプル、下段: 出力サンプル)
    5
    1 2
    11 22
    -111 -222
    10000000000000000000000000000000000000 10000000000000000000000000000000000000
    1234567890123456789012345678901234567 -10000000000000000000000000000000000000
    3
    33
    -333
    20000000000000000000000000000000000000
    -8765432109876543210987654321098765433
    A+Bから始める異常高速化




    Mizar/みざー
    7

    View Slide

  8. CASE 1: 出力回数が多い時に毎回 println! すると遅いです : 実行時間 537ms :
    https://judge.yosupo.jp/submission/149768
    println! は毎回OSに出力を行うため、OSくんを50万回呼びつける人状態になります。
    use std::io::prelude::*;
    fn main() {
    let stdin = std::io::stdin();
    let mut lines = stdin.lock().lines();
    let n = lines.next().unwrap().unwrap().parse::().unwrap();
    for _ in 0..n {
    let s = lines.next().unwrap().unwrap();
    let mut token = s.split_ascii_whitespace();
    let a = token.next().unwrap().parse::().unwrap();
    let b = token.next().unwrap().parse::().unwrap();
    println!("{}", a + b); // 500000回出力するのに毎回println!は…
    }
    }
    A+Bから始める異常高速化
    Mizar/みざー
    8

    View Slide

  9. CASE 2: 出力回数が多い時は Write システムコール呼び出し回数の低減に BufWriter を使
    いましょう ( proconio クレートの #[fastout] はこれに相当 ) : 実行時間 222ms :
    https://judge.yosupo.jp/submission/149239
    use std::io::prelude::*;
    fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let mut lines = stdin.lock().lines();
    let mut writer = std::io::BufWriter::new(stdout.lock()); // 出力バッファ
    let n = lines.next().unwrap().unwrap().parse::().unwrap();
    for _ in 0..n {
    let s = lines.next().unwrap().unwrap();
    let mut token = s.split_ascii_whitespace();
    let a = token.next().unwrap().parse::().unwrap();
    let b = token.next().unwrap().parse::().unwrap();
    writeln!(&mut writer, "{}", a + b).unwrap(); // バッファに出力
    }
    }
    A+Bから始める異常高速化
    Mizar/みざー
    9

    View Slide

  10. どこが高速化できそう?
    標準入力をバッファ付きで1行ずつ入力している所
    一度に入力全体を読み込んでから処理できないか?
    行単位・トークン (空白文字区切り) 単位への分割をしている所
    入力バイト列が UTF-8 として有効かどうか検査をしている
    改行文字区切り・空白文字区切りで分割する処理が二重になっている
    競技プログラミングの入力形式は、通常は改行文字と空白文字をまとめて分割して
    しまっても問題なく入力できる(トークン数が可変であっても、問題文と最初の入
    力から入力すべきトークンの数が分かるようになっている)
    トークン文字列から数値にパース(文字データの解析・変換処理)している所
    文字列→128bit整数 の変換は最大で 回行う・入力は最大で約40MB
    足し算した結果を文字列にフォーマットしている所
    128bit整数→文字列 の変換は最大で 回行う・出力は最大で約20MB
    A+Bから始める異常高速化
    Mizar/みざー
    10

    View Slide

  11. CASE 3: 一度に全部読み込み、改行と空白文字をまとめて分割 実行時間: 213ms
    https://judge.yosupo.jp/submission/149269
    use std::io::prelude::*;
    fn main() {
    let (mut stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let mut input = String::with_capacity(67_108_864); // 読み込みの格納先
    stdin.read_to_string(&mut input).unwrap(); // 一度に読み込み
    let mut token = s.split_ascii_whitespace(); // まとめて分割
    let mut writer = std::io::BufWriter::new(stdout.lock());
    let n = token.next().unwrap().parse::().unwrap();
    for _ in 0..n {
    let a = token.next().unwrap().parse::().unwrap();
    let b = token.next().unwrap().parse::().unwrap();
    writeln!(&mut writer, "{}", a + b).unwrap();
    }
    }
    A+Bから始める異常高速化
    Mizar/みざー
    11

    View Slide

  12. 標準入力・標準出力の流れ
    (リダイレクト)
    パイプ(FIFO)
    キャラクターデバイスなど
    (リダイレクト)
    パイプ(FIFO)
    キャラクターデバイスなど
    標準⼊⼒ 提出プログラム 標準出⼒
    ファイル
    ジャッジプログラム
    ターミナル(端末)
    ファイル
    ジャッジプログラム
    ターミナル
    通常ジャッジの場合: 入出力:ファイル
    入力が(書き込み中でない)ファイルだとプログラムの実行開始時点で最後まで読み込
    める
    問題がインタラクティブ(対話的)の場合: 入出力:パイプ(FIFO)
    ターミナル(端末)上で実行する場合: 入出力:キャラクターデバイスなど
    パイプ(FIFO)やキャラクタデバイスなどでの入力だと、プログラムの実行開始時点で
    最後まで読み込める保証が無い
    A+Bから始める異常高速化
    Mizar/みざー
    12

    View Slide

  13. 標準入力がファイルかどうかの判定(Linux)
    Linux の fstat システムコール で stat 構造体を
    取得する
    ファイル種別を示すビットマスク(ソケット/
    シンボリックリンク/通常のファイル/ブロ
    ックデバイス/ディレクトリ/キャラクター
    デバイス/FIFO(名前付きパイプ))、ファイル
    種別が通常のファイルであればファイルサ
    イズ、所有権、最終修正時刻など
    Rust の場合、 std::fs::File::from_raw_fd で 標
    準入力 (File Decscriptor : 0) の Fileオブジェク
    トを作り、 std::fs::File::metadata を使うとこ
    れらの情報を取得できる
    2023-06-01 リリースの Rust 1.70.0 では 入
    出力がターミナル(端末)かどうかを判定する
    std::io::IsTerminal トレイトが安定化
    struct stat {
    dev_t st_dev; /* ファイルがあるデバイスの ID */
    ino_t st_ino; /* inode 番号 */
    mode_t st_mode; /* アクセス保護 (ファイル種別の検査) */
    nlink_t st_nlink; /* ハードリンクの数 */
    uid_t st_uid; /* 所有者のユーザー ID */
    gid_t st_gid; /* 所有者のグループ ID */
    dev_t st_rdev; /* デバイス ID (特殊ファイルの場合) */
    off_t st_size; /* 全体のサイズ (バイト単位) */
    blksize_t st_blksize; /* ファイルシステム I/O でのブロックサイズ */
    blkcnt_t st_blocks; /* 割り当てられた 512B のブロック数 */
    /* Linux 2.6 以降では、カーネルは以下のタイムスタンプ
    フィールドでナノ秒の精度をサポートしている。
    Linux 2.6 より前のバージョンでの詳細は NOTES を参照。 */
    struct timespec st_atim; /* 最終アクセス時刻 */
    struct timespec st_mtim; /* 最終修正時刻 */
    struct timespec st_ctim; /* 最終状態変更時刻 */
    #define st_atime st_atim.tv_sec /* 後方互換性 */
    #define st_mtime st_mtim.tv_sec
    #define st_ctime st_ctim.tv_sec
    };
    A+Bから始める異常高速化
    Mizar/みざー
    13

    View Slide

  14. read vs mmap
    read システムコール : ファイルディスクリプターからバッファーに読み込む
    Rust の場合、標準ライブラリではこちらが使われる(Stdin の バッファーサイズは
    8192bytes 固定、 40Mbytesの入力に readシステムコール が 約5000回必要)
    mmap, munmap システムコール : ファイルやデバイスをメモリーにマップ/アンマップする
    入力がファイルであることを前提に、今回はこちらを使って一括で読み込んでみます
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn stdin() -> Stdin {
    static INSTANCE: OnceLock>> = OnceLock::new();
    Stdin {
    inner: INSTANCE.get_or_init(|| { // stdio::STDIN_BUF_SIZE は 8192bytes で固定
    Mutex::new(BufReader::with_capacity(stdio::STDIN_BUF_SIZE, stdin_raw()))
    }),
    }
    }
    A+Bから始める異常高速化
    Mizar/みざー
    14

    View Slide

  15. CASE 4: mmapを使用 : 実行時間 191ms : https://judge.yosupo.jp/submission/149279
    #![cfg(target_os = "linux")]
    use std::io::prelude::*;
    fn solve(s: &str) {
    let stdout = std::io::stdout();
    let mut token = s.split_ascii_whitespace();
    let mut writer = std::io::BufWriter::new(stdout.lock());
    let n = token.next().unwrap().parse::().unwrap();
    for _ in 0..n {
    let a = token.next().unwrap().parse::().unwrap();
    let b = token.next().unwrap().parse::().unwrap();
    writeln!(&mut writer, "{}", a + b).unwrap();
    }
    }
    fn main() {
    unsafe {
    use std::os::unix::io::FromRawFd;
    // unsafe: 標準入力 (file discriptor 0) の metadata を取得 (内部で fstat システムコール)
    match std::fs::File::from_raw_fd(0).metadata() {
    Ok(metadata) if metadata.is_file() => { // 入力がファイルだった時の処理
    let filelen = metadata.len(); // ファイルサイズ
    // unsafe: mmap システムコール にてファイルをメモリマップドアクセス
    let input = mmap(std::ptr::null_mut(), filelen as usize, 1, 2, 0, 0);
    // unsafe: UTF-8 の有効性チェックを省略、 &[u8] を &str に強制キャスト
    solve(std::str::from_utf8_unchecked(std::slice::from_raw_parts(
    input,
    filelen as usize,
    )));
    }
    _ => panic!(), // panic: このサンプルでは、入力がファイルでなかった時の実装は省略
    }
    }
    }
    // unsafe: FFI
    // (foreign function interface)
    // Linux C Library (libc)
    #[link(name = "c")]
    extern "C" {
    pub fn mmap(
    addr: *mut u8,
    length: usize,
    prot: i32,
    flags: i32,
    fd: i32,
    off: isize,
    ) -> *mut u8;
    }
    A+Bから始める異常高速化
    Mizar/みざー
    15

    View Slide

  16. 入力がファイル以外だった時のアプローチ
    Rust では std::io::BufRead トレイト
    に fill_buf (バッファが空なら充填し
    て取得できた領域を返す、空でなけれ
    ば使っていない領域を返す), consume (
    fill_buf で受け取った領域からどれ
    だけ消費したかを BufRead に伝えて後
    の fill_buf で消費済みの領域が再び
    戻ってこないようにする) という比較
    的低レベルな機能があるので、これを
    使って実装する方法があります。
    今回は時間の関係で、こちらのアプロ
    ーチの詳細は省略します。
    use std::io;
    use std::io::prelude::*;
    let stdin = io::stdin();
    let mut stdin = stdin.lock();
    let buffer = stdin.fill_buf().unwrap();
    // work with buffer
    // バッファを消費する
    println!("{buffer:?}");
    // ensure the bytes we worked with aren't returned again later
    // 消費したバイト列の領域が、また後で fill_buf によって戻ってこないようにする
    let length = buffer.len();
    stdin.consume(length);
    A+Bから始める異常高速化
    Mizar/みざー
    16

    View Slide

  17. 文字列 → 128bit整数への変換ですが…
    これは10000個の非負整数が書かれた文字列を128bit整数へ変換するベンチマークですが…
    何と、Rustでは 初期値0 から 文字列を左から順番に見ていって 10倍してから その桁の数
    字を足す という処理を繰り返した方が約2倍速かったりします。 (測定環境: AMD Zen+)
    str::parse::()
    722,148 ns/iter (+/- 6,374)
    bench.iter(|| -> Vec {
    values
    .iter()
    .map(|s| s.parse::().unwrap())
    .collect::>()
    });
    文字列先頭から1文字ずつ処理:
    370,237 ns/iter (+/- 6,918)
    bench.iter(|| -> Vec {
    values
    .iter()
    .map(|s| {
    s.as_bytes()
    .iter()
    .fold(0u128, |p, &c| p * 10 + ((c - b'0') as u128))
    })
    .collect::>()
    });
    A+Bから始める異常高速化
    Mizar/みざー
    17

    View Slide

  18. 何故 Rust の parse は遅い? (推測)
    その文字列が本当にその数値型に正常に収まる数値が書かれているか検査しながら変換
    しているので遅い。
    今回は、入力された文字列が制約通りであると仮定し、検査処理を省略して 文字列
    →整数 のパースを実装してみます
    10進数の文字列を変換するのに特化せず、任意の基数の文字列を変換できるよう汎化し
    ているため。
    10進数が書かれた文字列の処理に特化させて最適化を図ってみます
    A+Bから始める異常高速化
    Mizar/みざー
    18

    View Slide

  19. ←LSB(最下位byte) (最上位byte)MSB→
    e n d i a n n e s s ⏎
    65
    6E
    64
    69
    61
    6E
    6E
    65
    73
    73
    0A
    656E6E6169646E65
    656E6469616E6E65
    Byte列
    リトルエンディアン
    ビッグエンディアン
    エンディアン (endianness) / バイト順 (byte order)
    右図: ASCII文字列 "endianness⏎" の先頭8byteの領域を、それぞれのエンデ
    ィアンで8byte整数として読み込んだ値の16進数表記
    2bytes 幅以上の数値をコンピュータ上のメモリに格納する時や、データとし
    て転送する時に、最下位のbyte (LSB: Least Significant Bit/Byte) から順番に
    格納や転送を行うことを リトルエンディアン (little-endian) と言います。逆
    に、最上位のbyte (MSB: Most Significant Bit/Byte) から順番に行うものは ビ
    ッグエンディアン (big-endian) と言います。
    Intel/AMD x86_64 アーキテクチャでは、主にこのリトルエンディアンが使わ
    れています。
    ビッグエンディアン は、例えば インターネット上での通信プロトコル、
    TCP/IP のヘッダ部分で数値をエンコーディングするのに使われます(ネット
    ワークバイトオーダー)。 TCP/IP のペイロード部分のエンディアンはアプリ
    ケーションの実装次第で異なります。
    A+Bから始める異常高速化
    Mizar/みざー
    19

    View Slide

  20. 8byte長の文字列を64bit整数に分割統治法で変換(1)
    まずは、例として "12345678" の文字列を リトルエンディアン の 64bit整数型 に読み込ん
    でみます。
    ← LSB (最下位byte)    (最上位byte) MSB →
    "12345678" 8byte文字列
    0x38
    (56)
    "8"
    0x37
    (55)
    "7"
    0x36
    (54)
    "6"
    0x35
    (53)
    "5"
    0x34
    (52)
    "4"
    0x33
    (51)
    "3"
    0x32
    (50)
    "2"
    0x31
    (49)
    "1"
    u64::from_le_bytes
    64bit整数(8bit区切り)
    (10進数表記)
    ← MSB (最上位バイト)    (最下位バイト) LSB →
    A+Bから始める異常高速化
    Mizar/みざー
    20

    View Slide

  21. 8byte長の文字列を64bit整数に分割統治法で変換(2)
    次に、64bit整数 0x0F0F0F0F0F0F0F0F と AND演算 をして不要な所をマスクし、各桁毎の数
    を取り出します。
    "12345678" 8byte文字列
    0x38
    (56)
    "8"
    0x37
    (55)
    "7"
    0x36
    (54)
    "6"
    0x35
    (53)
    "5"
    0x34
    (52)
    "4"
    0x33
    (51)
    "3"
    0x32
    (50)
    "2"
    0x31
    (49)
    "1"
    u64::from_le_bytes
    0x08
    (8)
    0x07
    (7)
    0x06
    (6)
    0x05
    (5)
    0x04
    (4)
    0x03
    (3)
    0x02
    (2)
    0x01
    (1)
    AND 0x0F0F0F0F0F0F0F0F
    64bit整数(8bit区切り)
    (10進数表記)
    A+Bから始める異常高速化
    Mizar/みざー
    21

    View Slide

  22. 8byte長の文字列を64bit整数に分割統治法で変換(3)
    次に、整数 0xA01 (10進数で 2561 ) を掛け算します。
    2桁ごとに区切った数が現れています。
    "12345678" 8byte文字列
    0x38
    (56)
    "8"
    0x37
    (55)
    "7"
    0x36
    (54)
    "6"
    0x35
    (53)
    "5"
    0x34
    (52)
    "4"
    0x33
    (51)
    "3"
    0x32
    (50)
    "2"
    0x31
    (49)
    "1"
    u64::from_le_bytes
    0x08
    (8)
    0x07
    (7)
    0x06
    (6)
    0x05
    (5)
    0x04
    (4)
    0x03
    (3)
    0x02
    (2)
    0x01
    (1)
    AND 0x0F0F0F0F0F0F0F0F
    0x4E
    (78)
    0x43
    (67)
    0x38
    (56)
    0x2D
    (45)
    0x22
    (34)
    0x17
    (23)
    0x0C
    (12)
    0x01
    (1)
    × 0x0000000000000A01
    64bit整数(8bit区切り)
    (10進数表記)
    A+Bから始める異常高速化
    Mizar/みざー
    22

    View Slide

  23. 8byte長の文字列を64bit整数に分割統治法で変換(4)
    次に、8bit の 右シフト演算 をして、2桁ごとにまとめた値の位置を調整します。
    "12345678" 8byte文字列
    0x38
    (56)
    0x37
    (55)
    0x36
    (54)
    0x35
    (53)
    0x34
    (52)
    0x33
    (51)
    0x32
    (50)
    0x31
    (49)
    u64::from_le_bytes
    0x08
    (8)
    0x07
    (7)
    0x06
    (6)
    0x05
    (5)
    0x04
    (4)
    0x03
    (3)
    0x02
    (2)
    0x01
    (1)
    AND 0x0F0F0F0F0F0F0F0F
    0x4E
    (78)
    0x43
    (67)
    0x38
    (56)
    0x2D
    (45)
    0x22
    (34)
    0x17
    (23)
    0x0C
    (12)
    0x01
    (1)
    × 0x0000000000000A01
    0x00
    (0)
    0x4E
    (78)
    0x43
    (67)
    0x38
    (56)
    0x2D
    (45)
    0x22
    (34)
    0x17
    (23)
    0x0C
    (12)
    >> 8
    64bit整数(8bit区切り)
    (10進数表記)
    A+Bから始める異常高速化
    Mizar/みざー
    23

    View Slide

  24. 8byte長の文字列を64bit整数に分割統治法で変換(5)
    次に、 0x00FF00FF00FF00FF との AND演算 をして、 不要な桁にマスクを掛けます。
    "12345678" 8byte文字列
    0x38 0x37 0x36 0x35 0x34 0x33 0x32 0x31 u64::from_le_bytes
    0x08 0x07 0x06 0x05 0x04 0x03 0x02 0x01 AND 0x0F0F0F0F0F0F0F0F
    0x4E
    (78)
    0x43
    (67)
    0x38
    (56)
    0x2D
    (45)
    0x22
    (34)
    0x17
    (23)
    0x0C
    (12)
    0x01
    (1)
    × 0x0000000000000A01
    0x00
    (0)
    0x4E
    (78)
    0x43
    (67)
    0x38
    (56)
    0x2D
    (45)
    0x22
    (34)
    0x17
    (23)
    0x0C
    (12)
    >> 8
    0x00
    (0)
    0x4E
    (78)
    0x00
    (0)
    0x38
    (56)
    0x00
    (0)
    0x22
    (34)
    0x00
    (0)
    0x0C
    (12)
    AND 0x00FF00FF00FF00FF
    64bit整数(8bit区切り)
    (10進数表記)
    A+Bから始める異常高速化
    Mizar/みざー
    24

    View Slide

  25. 8byte長の文字列を64bit整数に分割統治法で変換(6)
    次は、16bit区切りの値に注目して処理していきます。
    "12345678" 8byte文字列
    0x004E
    (78)
    0x0038
    (56)
    0x0022
    (34)
    0x000C
    (12)
    u64::from_le_bytes
    AND 0x0F0F0F0F0F0F0F0F
    × 0x0000000000000A01 >> 8
    AND 0x00FF00FF00FF00FF
    16bit区切り
    (10進数表記)
    A+Bから始める異常高速化
    Mizar/みざー
    25

    View Slide

  26. 8byte長の文字列を64bit整数に分割統治法で変換(7)
    整数 0x640001 (10進数で 6553601 ) を掛け算、16ビット右シフト、 0x0000FFFF0000FFFF と
    の AND演算をします。
    "12345678" 8byte文字列
    0x004E
    (78)
    0x0038
    (56)
    0x0022
    (34)
    0x000C
    (12)
    u64::from_le_bytes
    AND 0x0F0F0F0F0F0F0F0F
    × 0x0000000000000A01 >> 8
    AND 0x00FF00FF00FF00FF
    0x162E
    (5678)
    0x0D80
    (3456)
    0x04D2
    (1234)
    0x220C
    (12)
    × 0x0000000000640001
    0x0000
    (0)
    0x162E
    (5678)
    0x0D80
    (3456)
    0x04D2
    (1234)
    >> 16
    0x0000
    (0)
    0x162E
    (5678)
    0x0000
    (0)
    0x04D2
    (1234)
    AND 0x0000FFFF0000FFFF
    A+Bから始める異常高速化
    Mizar/みざー
    26

    View Slide

  27. 8byte長の文字列を64bit整数に分割統治法で変換(8)
    最後に 32bit 区切りで見ていきます。整数 0x271000000001 (10進数で 42949672960001 ) を掛
    け算、32ビット右シフト をします。これで完成です。
    "12345678" 8byte文字列
    0x0000162E
    (5678)
    0x000004D2
    (1234)
    u64::from_le_bytes
    AND 0x0F0F0F0F0F0F0F0F
    × 0x0000000000000A01 >> 8
    AND 0x00FF00FF00FF00FF
    × 0x0000000000640001 >> 16
    AND 0x0000FFFF0000FFFF
    0x00BC614E
    (12345678)
    0x000004D2
    (1234)
    × 0x0000271000000001
    0x00000000
    (0)
    0x00BC614E
    (12345678)
    >> 32
    A+Bから始める異常高速化
    Mizar/みざー
    27

    View Slide

  28. 8byte長の文字列を64bit整数に分割統治法で変換(9)
    Rust でのコードにすると、このような感じになります。
    fn parseuint_raw8b(s: [u8; 8]) -> u64 {
    (((((u64::from_le_bytes(s) & 0x0f0f0f0f0f0f0f0f)
    .wrapping_mul((10 << 8) + 1) >> 8) & 0x00ff00ff00ff00ff)
    .wrapping_mul((100 << 16) + 1) >> 16) & 0x0000ffff0000ffff)
    .wrapping_mul((10000 << 32) + 1) >> 32
    }
    符号なし整数10000個のparse 32bit整数(~10桁) 64bit整数(~20桁) 128bit整数(~39桁)
    str::parse::().unwrap()
    str::parse::().unwrap()
    str::parse::().unwrap()
    117,630 ns/iter
    (+/- 1,631)
    238,559 ns/iter
    (+/- 2,310)
    720,681 ns/iter
    (+/- 16,091)
    文字列先頭から1文字ずつ
    65,094 ns/iter
    (+/- 717)
    131,462 ns/iter
    (+/- 1,320)
    364,676 ns/iter
    (+/- 4,186)
    分割統治法で8文字ずつ
    32,570 ns/iter
    (+/- 420)
    56,551 ns/iter
    (+/- 637)
    94,753 ns/iter
    (+/- 568)
    A+Bから始める異常高速化
    Mizar/みざー
    28

    View Slide

  29. 8byte長の文字列を64bit整数
    に分割統治法で変換(10)
    x86_64 アセンブラに変換した後の結
    果はこのような感じになります。
    レジスタ代入が4回、掛け算が3回、
    AND演算が3回、右シフト演算が3回で
    処理できている事が見て取れます。
    これと同様の手法は、SIMDレジスタ
    を用いてもっと長い区切りで並列的に
    処理することもできます。
    fn parseuint_raw8b(s: [u8; 8]) -> u64 {
    (((((u64::from_le_bytes(s) & 0x0f0f0f0f0f0f0f0f)
    .wrapping_mul((10 << 8) + 1) >> 8) & 0x00ff00ff00ff00ff)
    .wrapping_mul((100 << 16) + 1) >> 16) & 0x0000ffff0000ffff)
    .wrapping_mul((10000 << 32) + 1) >> 32
    }
    parseuint_raw8b:
    movabs rax, 1085102592571150095 # 0x0F0F0F0F0F0F0F0F
    and rax, rdi # AND演算
    imul rax, rax, 2561 # × 0xA01
    shr rax, 8 # 右8ビットシフト
    movabs rcx, 71777214294589695 # 0x00FF00FF00FF00FF
    and rcx, rax # AND演算
    imul rax, rcx, 6553601 # × 0x640001
    shr rax, 16 # 右16ビットシフト
    movabs rcx, 281470681808895 # 0x0000FFFF0000FFFF
    and rcx, rax # AND演算
    movabs rax, 42949672960001 # 0x0000271000000001
    imul rax, rcx # 掛け算
    shr rax, 32 # 右32ビットシフト
    ret # return
    A+Bから始める異常高速化
    Mizar/みざー
    29

    View Slide

  30. 128bit整数から文字列への変換(1)
    より、128bit整数は最大 桁の整数になります。 0000 ~ 9999 ま
    での 桁の 個の文字列を事前生成し、入力された数を 進数に変換、 桁ごと
    に出力します。 (divrem: 除算によってその商と剰余の両方を求める演算)
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    divrem 10³²
    divrem 10³²
    divrem 10¹⁶
    divrem 10¹⁶
    divrem 10⁸
    divrem 10⁸
    divrem 10⁴
    divrem 10⁴
    divrem 10³²
    divrem 10¹⁶
    divrem 10⁸
    divrem 10⁴
    と での除算・剰余算は、現状のRustでは最適化が甘い(ソフトウェア実装の
    128bit除算ライブラリ __udivti3 が使われる: 比較的遅い)ので、手動で最適化します。
    A+Bから始める異常高速化
    Mizar/みざー
    30

    View Slide

  31. 3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    3
    34
    40
    02
    28
    82
    23
    36
    66
    69
    92
    20
    09
    93
    38
    84
    46
    63
    34
    46
    63
    33
    37
    74
    46
    60
    07
    74
    43
    31
    17
    76
    68
    82
    21
    11
    14
    45
    55
    5
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    340282366920938463463374607431768211455
    divrem 10³²
    divrem 10³²
    divrem 10¹⁶
    divrem 10¹⁶
    divrem 10⁸
    divrem 10⁸
    divrem 10⁴
    divrem 10⁴
    divrem 10³²
    divrem 10¹⁶
    divrem 10⁸
    divrem 10⁴
    A+Bから始める異常高速化
    Mizar/みざー
    31

    View Slide

  32. 128bit整数から文字列への変換(2)
    128bit(最大 桁)の整数を で除算し、 上位 桁 と 下位 桁に分割する。
    fn divrem_1e32(x: u128) -> (u32, u128) {
    // (y0, y1) = (floor(x / 10^32), x mod 10^32)
    // floor((2^128)/(10^32)) = 3402823
    let mut y0 = ((((x >> 64) as u64 as u128) * 3402823) >> 64) as u32;
    let mut y1 = x - (y0 as u128) * 1_0000_0000_0000_0000_0000_0000_0000_0000;
    if let Some(yt) = y1.checked_sub(1_0000_0000_0000_0000_0000_0000_0000_0000) {
    y1 = yt;
    y0 += 1;
    }
    (y0, y1)
    }
    A+Bから始める異常高速化
    Mizar/みざー
    32

    View Slide

  33. 128bit整数から文字列への変換(3)
    桁の整数 を で除算し、 上位 桁 と 下位 桁に分割する。
    fn divrem_1e16(x: u128) -> (u64, u64) {
    debug_assert!(x < 1_0000_0000_0000_0000_0000_0000_0000_0000);
    // (z0, z1) = (floor(x / 10^16), x mod 10^16)
    // floor((2^107)/(10^16)) = 16225927682921336
    let mut z0 = ((((x >> 43) as u64 as u128) * 16225927682921336) >> 64) as u64;
    let mut z1 = (x - (z0 as u128) * 1_0000_0000_0000_0000) as u64;
    if let Some(zt) = z1.checked_sub(1_0000_0000_0000_0000) {
    z1 = zt;
    z0 += 1;
    }
    (z0, z1)
    }
    A+Bから始める異常高速化
    Mizar/みざー
    33

    View Slide

  34. 128bit整数から文字列への変換(4)
    通常の除算を使用した場合のアセンブラ出力例:
    汎用的な128bit除算のソフトウェア実装 __udivti3 を呼
    び出していたり、レジスタの使用量が多く、 push /
    pop が発生していたりするのが見て取れます。
    const D32U: u128 = 100000000000000000000000000000000;
    pub fn divrem_1e32_std(x: u128) -> (u32, u128) {
    let y0 = (x / D32U) as u32;
    let y1 = x % D32U;
    (y0, y1)
    }
    divrem_1e32_std:
    push r15
    push r14
    push r12
    push rbx
    push rax
    mov rbx, rsi
    mov r14, rdi
    movabs r15, -8814407033341083648
    movabs r12, 5421010862427
    mov rdx, r15
    mov rcx, r12
    call qword ptr [rip + [email protected]]
    mov rcx, rax
    mov rsi, rdx
    imul r12, rax
    mov rax, rcx
    mul r15
    add rdx, r12
    imul rsi, r15
    add rsi, rdx
    sub r14, rax
    sbb rbx, rsi
    mov eax, ecx
    mov rdx, r14
    mov rcx, rbx
    add rsp, 8
    pop rbx
    pop r12
    pop r14
    pop r15
    ret
    A+Bから始める異常高速化
    Mizar/みざー
    34

    View Slide

  35. 128bit整数から文字列への変換(5)
    での除算専用化した場合のアセンブラ出力例:
    __udivti3 の呼び出しが排除され、レジスタの使用量が
    減っているのが見て取れます。
    const D32U: u128 = 100000000000000000000000000000000;
    pub fn divrem_1e32(x: u128) -> (u32, u128) {
    // (y0, y1) = (floor(x / 10^32), x mod 10^32)
    // floor((2^128)/(10^32)) = 3402823
    let mut y0 = ((((x >> 64) as u64 as u128) * 3402823) >> 64) as u32;
    let mut y1 = x - (y0 as u128) * D32U;
    if let Some(yt) = y1.checked_sub(D32U) {
    y1 = yt;
    y0 += 1;
    }
    (y0, y1)
    }
    divrem_1e32:
    mov r8, rsi
    mov ecx, 3402823
    mov rax, rsi
    mul rcx
    mov rsi, rdx
    movabs rcx, -5421010862428
    mov r10, rdx
    imul r10, rcx
    movabs r9, 8814407033341083648
    mov rax, rdx
    mul r9
    add r10, rdx
    add rax, rdi
    adc r10, r8
    add r9, rax
    adc rcx, r10
    movabs rdx, -8814407033341083649
    cmp rdx, rax
    movabs rdx, 5421010862427
    sbb rdx, r10
    cmovae rcx, r10
    cmovae r9, rax
    adc esi, 0
    mov eax, esi
    mov rdx, r9
    ret
    A+Bから始める異常高速化
    Mizar/みざー
    35

    View Slide

  36. 128bit整数から文字列への
    変換(6)
    ベンチマーク結果:
    縦軸: 1出力あたりの所要時間(単位:ナノ秒)
    横軸: 出力する数の10進数での桁数
    青線: Rustの標準フォーマッタによる出力
    (128bit整数)
    黄線: Rustの標準フォーマッタによる出力
    (64bit整数)
    for &e in values.iter() {
    use std::fmt::Write;
    write!(&mut s, "{}", e).unwrap();
    s.push(' ');
    }
    赤線: 今回の実装(128bit整数)
    緑線: 今回の実装(64bit整数)
    A+Bから始める異常高速化
    Mizar/みざー
    36

    View Slide

  37. A+Bから始める異常高速化
    Mizar/みざー
    37

    View Slide

  38. let c_std = || -> String {
    let mut s = String::with_capacity(N * 40);
    for &e in values.iter() {
    use std::fmt::Write;
    write!(&mut s, "{}", e).unwrap(); // 標準のフォーマッタによる出力
    s.push(' '); // 空白文字区切り、write!内のフォーマット文字列に空白文字加えるより、こちらのが速い
    }
    s
    };
    let c_lib = || -> String {
    let mut s = String::with_capacity(N * 40);
    let v = unsafe { s.as_mut_vec() };
    let r = v.as_mut_ptr();
    let mut p = r;
    for &e in values.iter() {
    unsafe {
    dec4le.rawbytes_u128(&mut p, e); // 今回作成した出力ルーチンを呼び出し
    *p = b' '; // 空白文字区切り
    p = p.add(1);
    }
    }
    unsafe { v.set_len((p as usize) - (r as usize)) };
    s
    };
    std版参考: Qiita: Rustで数値を連結した文字列を作るときはItertools::joinが速い
    A+Bから始める異常高速化
    Mizar/みざー
    38

    View Slide

  39. 全部やった結果・まとめ
    CASE 1: 毎回println: 実行時間 537ms :
    https://judge.yosupo.jp/submission/149768
    CASE 2: BufWrite使用: 実行時間 222ms :
    https://judge.yosupo.jp/submission/149239
    CASE 3: 一度に読み込む: 実行時間 213ms :
    https://judge.yosupo.jp/submission/149269
    CASE 4: mmap使用: 実行時間 191ms :
    https://judge.yosupo.jp/submission/149279
    CASE 5: 整数入出力の改善など: 実行時間 54ms :
    https://judge.yosupo.jp/submission/150470
    右図は、CASE5の提出結果とそのソースコードを表示し
    たページのスクリーンショットです。
    A+Bから始める異常高速化
    Mizar/みざー
    39

    View Slide

  40. もっと速い実装
    Many A + B (128bit) では半分の私の実
    装よりも半分の実行時間な投稿もあり
    ます。
    こちらは入出力に10進数 2進数の基数
    変換を用いず、10進数のままで加減算
    を行うという物なので、方向性は私の
    実装とはかなり異なるものです。
    https://judge.yosupo.jp/submissions/?
    problem=many_aplusb_128bit&order=
    %2Btime&status=AC
    A+Bから始める異常高速化
    Mizar/みざー
    40

    View Slide

  41. Fastest Submissions
    Problem Fastest
    abc176_d - Wizard in Maze #39583732 17ms mizarjp
    abc177_e - Coprime #39139951 23ms mizarjp
    abc276_e - Round Trip #36922510 10ms mizarjp
    abc277_e - Crystal Switches #36835455 35ms mizarjp
    abc278_c - FF #39521560 27ms mizarjp
    abc282_d - Make Bipartite 2 #37363957 30ms mizarjp
    abc282_e - Choose Two and Eat One #39487837 11ms mizarjp
    abc283_b - First Query Problem #37591131 12ms mizarjp
    abc283_e - Don't Isolate Elements #37589533 11ms mizarjp
    abc284_d - Happy New Year 2023 #37871413 3ms mizarjp
    abc285_d - Change Usernames #38145408 24ms mizarjp
    abc287_d - Match or Not #38441125 11ms mizarjp
    abc287_e - Karuta #38546029 35ms mizarjp
    abc289_d - Step Up Robot #38825162 6ms mizarjp
    abc289_f - Teleporter Takahashi #38877573 15ms mizarjp
    abc290_c - Max MEX #39049092 12ms mizarjp
    abc290_d - Marking #39049375 26ms mizarjp
    Problem Fastest
    abc293_d - Tying Rope #39908999 25ms mizarjp
    abc293_f - Zero or One #39667931 6ms mizarjp
    abc293_g - Triple Index #39893894 161ms mizarjp
    abc294_c - Merge Sequences #39893227 17ms mizarjp
    abc294_d - Bank #39920030 17ms mizarjp
    abc296_c - Gap Existence #40275393 19ms mizarjp
    abc298_f - Rook Score #40687882 57ms mizarjp
    abc300_d - AABCC #41063134 5ms mizarjp
    abc302_d - Impartial Gift #41565791 36ms mizarjp
    abc304_e - Good Graph #41968115 54ms mizarjp
    abc305_d - Sleep Log #42177274 68ms mizarjp
    abc307_e - Distinct Adjacent #42932150 2ms mizarjp
    arc152_b - Pass on Path #37894497 11ms mizarjp
    arc158_b - Sum-Product Ratio #39710167 14ms mizarjp
    arc158_c - All Pair Digit Sums #39731553 58ms mizarjp
    tessoku_book_h - Two Dimensional Sum #37536471 31ms mizarjp
    tupc2022_a - Sum Sort #39400989 7ms mizarjp
    tupc2022_c - Flip Grid #39452326 52ms mizarjp
    A+Bから始める異常高速化
    Mizar/みざー
    41

    View Slide

  42. まとめ
    Rust は標準で何でもかんでも速いわけじゃない
    エラーチェックや汎用化の都合などで、専用に最適化したものより遅い事も
    Rust は安全に書くこともできる言語ですが、敢えてそれを踏み外す事もできる
    FFI (foreign function interface)、インラインアセンブラ、生ポインタ、etc.
    注意深く使えば、 unsafe な部分の悪影響を極小化しつつ、いろいろできる…かも?
    異常高速化の世界へようこそ!
    でも、不要不急の高速化を無理に試みなくても大丈夫です。たぶん。
    A+Bから始める異常高速化
    Mizar/みざー
    42

    View Slide

  43. 参考資料
    今回は使用していませんが、このような実装も存在するという紹介です。
    文字列→float (C++) : https://github.com/fastfloat/fast_float
    float→文字列 (C++) : https://github.com/jk-jeon/dragonbox
    文字列→int (Rust) : https://github.com/pacman82/atoi-rs
    int→文字列 (Rust) : https://github.com/dtolnay/itoa
    文字列→float (Rust) : https://github.com/aldanor/fast-float-rust
    float→文字列 (Rust) : https://github.com/dtolnay/dragonbox
    除算/剰余算の特殊化アルゴリズム (Rust) : https://github.com/AaronKutch/specialized-div-rem
    A+Bから始める異常高速化
    Mizar/みざー
    43

    View Slide

  44. VRC競プロ部 案内
    主に土曜23時頃~ (AtCoder Beginner Contest (ABC)
    開催日) ABC感想会
    AtCoder Beginner Contest にリアルタイムで参加
    した人たちで集まって、 Group+ インスタンスに
    てわいわいと感想会をやっています。初めての方
    は Discord / VRChat Group に参加しておいた方が
    スムーズだと思います。
    https://discord.gg/VDQMrAb
    https://vrchat.com/home/group/grp_f11873db-
    0ce5-4f7d-940b-532f97a60ead
    主に日曜夜 (コンテストがない週): テーマ別勉強会
    2023-06開催 SECCON Beginners CTF 2023 に
    VRC-procon チームで参加 (20位)
    A+Bから始める異常高速化
    Mizar/みざー
    44

    View Slide

  45. VRC競プロ部 コンテスト
    2023-07-21(金)21:20 ~ 23:20 yukicoder にて
    https://yukicoder.me/contests/447
    私は A 問題のWriterとして作問に参加しました。今回
    の A 問題 は AtCoder Beginner Contest での B問題 程
    度の難易度を想定しています。
    リアルタイムでの参加はもちろん、都合が合わない、
    難しすぎた、という方でも、問題や解説を後で見るだ
    けでも、皆さんに楽しんで頂けたらと思います。
    右上: 今回 2023-07-21開催
    右下: 前回 2023-05-26開催
    A+Bから始める異常高速化
    Mizar/みざー
    45

    View Slide

  46. https://yukicoder.me/contests/447
    https://twitter.com/cleantted_s/status/1226803108086312964
    A+Bから始める異常高速化

    View Slide

  47. A+Bから始める異常高速化
    Mizar/みざー

    View Slide