Open
Description
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.
get_stringview_wtf8
- O(n) or O(1)?
- If
stringref
is implemented with a WTF16 encoding, this sounds like it’s O(n) to copy. - If
stringref
is implemented with a WTF8 encoding, this can be a O(1) no-op. - Is there a fancy way to guarantee O(1) here?
get_stringview_wtf16
- O(n) or O(1)?
- If
stringref
is implemented with a WTF16 encoding, this can be a O(1) no-op. - If
stringref
is implemented with a WTF8 encoding, this sounds like it’s O(n) to copy, or compute breadcrumbs. - Is there a fancy way to guarantee O(1) here?
string.concat
- O(n) or O(1)?
- Are implementations expected to use ropes to defer concatenation of strings?
string.eq
- O(n) or O(1)?
- Are implementations expected to use hash-consing to guarantee O(1) comparisons?
string.measure_[utf8/wtf8/wtf16]
- O(n) or O(1)?
string.is_usv_sequence
- 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
Labels
No labels