Novaで違いを理解しながらreverse/toReversedを実装した

目次

• Intro
• 仕様書においての違い
• Novaの実装
• 実行速度
• まとめ

Intro

ArrayとTypedArrayのいくつかのメソッドには、ミュータブルとイミュータブルな違いがあるメソッドが存在しています。例えばsortやreverseなど。

筆者は直近で、%TypedArray%.prototype.reverseと%TypedArray%.prototype.toReversedをNovaに実装したので、今回はそれぞれの違いについて書いていこうと思います。

• feat(ecmascript): %TypedArray%.prototype.reverse #593
• feat(ecmascript): %TypedArray%.prototype.toReversed #611

使い方などはたくさんすでに記事はあると思うので、その辺りは割愛します。

仕様書においての違い

reverseはミュータブルなメソッドになるので、本体データを直接変更すれば問題ないです。仕様書を見ても、特段気になるような点はなくいつも通りといった感じです。

しかしtoReveresedはイミュータブルなメソッドになるので、本体データを書き換えないようにしないといけないです。これが実装前は筆者としてはあまりイメージが湧いていませんでした。

というわけで仕様書を見てみると、以下のようになっていました。

TypedArray.prototype.toReversed

TypedArray.prototype.reverse

Let O be the this value. Let taRecord be ? ValidateTypedArray(O, seq-cst). Let length be TypedArrayLength(taRecord). Let A be ? TypedArrayCreateSameType(O, « 𝔽(length) »). Let k be 0. Repeat, while k < length: Let from be ! ToString(𝔽(length - k - 1)). Let Pk be ! ToString(𝔽(k)). Let fromValue be ! Get(O, from). Perform ! Set(A, Pk, fromValue, true). Set k to k + 1. Return A.

Let O be the this value. Let taRecord be ? ValidateTypedArray(O, seq-cst). Let len be TypedArrayLength(taRecord). Let middle be floor(len / 2). Let lower be 0. Repeat, while lower ≠ middle: Let upper be len - lower - 1. Let upperP be ! ToString(𝔽(upper)). Let lowerP be ! ToString(𝔽(lower)). Let lowerValue be ! Get(O, lowerP). Let upperValue be ! Get(O, upperP). Perform ! Set(O, lowerP, upperValue, true). Perform ! Set(O, upperP, lowerValue, true). Set lower to lower + 1. Return O.

toReversedには、TypedArrayCreateSameTypeというabstruct operationがあります。 これをみると、以下のようになっています。

このabstract operationでは、同じ型のTypedArrayのコピーを作るよう書いてあります。ただコピーと言っても完全なコピーではなく、元の配列と同じ長さの空っぽの配列が作られます。

そして元の配列の値を逆順にセットしていき、終わればコピー後の値を返せば、toReversedの完成です。

Novaの実装

reverseはmutableなsliceをarray_bufferから取り出し、そのsliceを直接reverseするようにしています。

fn reverse_typed_array<'a, T: Viewable + Copy + std::fmt::Debug>(
    agent: &mut Agent,
    ta: TypedArray,
    len: usize,
    gc: NoGcScope<'a, '_>,
) -> JsResult<'a, ()> {
    let array_buffer = ta.get_viewed_array_buffer(agent, gc);
    let byte_offset = ta.byte_offset(agent);
    let byte_length = ta.byte_length(agent);
    let byte_slice = array_buffer.as_mut_slice(agent);
    if byte_slice.is_empty() {
        return Ok(());
    }
    let byte_slice = if let Some(byte_length) = byte_length {
        let end_index = byte_offset + byte_length;
        if end_index > byte_slice.len() {
            return Ok(());
        }
        &mut byte_slice[byte_offset..end_index]
    } else {
        &mut byte_slice[byte_offset..]
    };
    let (head, slice, _) = unsafe { byte_slice.align_to_mut::<T>() };
    if !head.is_empty() {
        return Err(agent.throw_exception_with_static_message(
            ExceptionType::TypeError,
            "TypedArray is not properly aligned",
            gc,
        ));
    }
    let slice = &mut slice[..len];
    slice.reverse();
    Ok(())
}

ここら辺の高速化については別でブログ書いてるので、そちらを見ていただきたいです（ネイティブコードを使ったNovaのTypedArray.prototype.indexOfの最適化）

ではtoReversedではどうしているかというと、まだ高速化のアプローチはできていないです。 なので現状の実装は以下のようになっています。

// 6. Repeat, while k < length,
while k < len {
    // a. Let from be ! ToString(𝔽(length - k - 1)).
    let from = PropertyKey::Integer((len - k - 1).try_into().unwrap());
    // b. Let Pk be ! ToString(𝔽(k)).
    let pk = PropertyKey::try_from(k).unwrap();
    // c. Let fromValue be ! Get(O, from).
    let from_value = get(agent, scoped_o.get(agent), from, gc.reborrow())
        .unbind()?
        .bind(gc.nogc());
    // d. Perform ! Set(A, Pk, fromValue, true).
    unwrap_try(try_set(
        agent,
        scope_a.get(agent).into_object(),
        pk,
        from_value.unbind(),
        true,
        gc.nogc(),
    ))
    .unwrap();
    // . Set k to k + 1.
    k += 1;
}

その時もらったレビューを見返してみると、TypedArrayCreateSameTypeで作られたaと、元のTypedArrayであるoを比較して、それらが一緒のContentTypeで、ただ別のオブジェクトってことがわかれば、 あとはaにoをコピーさせてaを返すようにすればいいだけだったので、今なら全然できる気がしてきました。

実行速度

今回のブログテーマと若干ずれているかもですが、一応測っておきました。

reverseはすでにそれなりの速度で実行されるんですが、toReversedは現状のNovaのTypedArrayの構造上少し面倒だったので特に何もしてないです。

const SIZE = 10_000_000;
const arr = new Uint32Array(SIZE);
arr.toReversed();

// toReversed
❯ time andromeda run index.js
andromeda run index.js  0.39s user 0.02s system 97% cpu 0.423 total

const SIZE = 10_000_000;
const arr = new Uint32Array(SIZE);
arr.reverse();

// reverse
❯ time andromeda run index.js
andromeda run index.js  0.00s user 0.01s system 53% cpu 0.019 total

試しに測ってみましたが、思ったよりtoReversedも早かった。（andromedaとはNovaを使ったruntimeです）

ちなみにreverseのv8との比較ついでにnodeとandromedaで動かしてみたら以下のようになった。

const SIZE = 10_000_000;
const arr = new Uint32Array(SIZE);
arr.reverse();

❯ time andromeda run index.js
andromeda run index.js  0.00s user 0.01s system 53% cpu 0.019 total

❯ time node index.js
node index.js  0.04s user 0.01s system 80% cpu 0.056 total

Nova早い。（ランタイムを経由しての比較だからなんとも言えないだろうけど）

まとめ

以上がNovaの%TypedArray%.prototype.reverseと%TypedArray%.prototype.toReversedの違いについてでした。 mdnで動きを見ている時は同じような感じかなと思っていましたが、仕様書とRustで実装してみると、違いを感じれて面白かったです。