Skip to content

Algorithmic complexity of instructions #56

Open
@eqrion

Description

@eqrion

What is the desired algorithmic complexity of the following instructions?

Disclaimer: I understand that the spec says nothing about algorithmic complexity of instructions. However the rough algorithmic complexity of instructions does matter in-practice for whether a module can feasibly run on an implementation.

  1. get_stringview_wtf8
    1. O(n) or O(1)?
    2. If stringref is implemented with a WTF16 encoding, this sounds like it’s O(n) to copy.
    3. If stringref is implemented with a WTF8 encoding, this can be a O(1) no-op.
    4. Is there a fancy way to guarantee O(1) here?
  2. get_stringview_wtf16
    1. O(n) or O(1)?
    2. If stringref is implemented with a WTF16 encoding, this can be a O(1) no-op.
    3. If stringref is implemented with a WTF8 encoding, this sounds like it’s O(n) to copy, or compute breadcrumbs.
    4. Is there a fancy way to guarantee O(1) here?
  3. string.concat
    1. O(n) or O(1)?
    2. Are implementations expected to use ropes to defer concatenation of strings?
  4. string.eq
    1. O(n) or O(1)?
    2. Are implementations expected to use hash-consing to guarantee O(1) comparisons?
  5. string.measure_[utf8/wtf8/wtf16]
    1. O(n) or O(1)?
  6. string.is_usv_sequence
    1. O(n) or O(1)?

It seems like many operations here are either linear or constant time depending on how the host implements stringref (WTF8/WTF16 backed) (with ropes/without) (hash-consed constants or not).

If this is the case, I’m concerned that this could lead to future incompatibilities where modules are written assuming something is constant time, but it’s in fact linear on a host with a different implementation.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions