lukewagner
commented
5 years ago One idea I've been pondering is to have a single, fairly-general memory-to-sequence lifting instruction that takes a function immediate with signature: [i32]→[T,i32,bool] where: the incoming i32 is the pointer to the element which is to be turned into a T element (for a seq<T>), the bool result indicates whether there is a next element and, if so, the i32 result is a pointer to it.
For a std::vector<uint8_t> this would look like (using Nick's wasm idea, and pulling in let from function-references) [Edit: take out explicit wasm...end]:
(@interface func (export ...) (param $vec i32) (result (seq u8))
(i32.load offset=4 (local.get $vec)) ;; vec.end()
let (local $end i32)
(i32.load offset=0 (local.get $vec)) ;; vec.begin()
memory-to-sequence (func (param $p i32) (result u8 i32 bool)
(lift-int i32 u8 (i32.load8_u (local.get $p))) ;; *p
(i32.add (local.get $p) (i32.const 1)) ;; p = p + sizeof(uint8_t)
(lift-bool (i32.eq (dup) (local.get $end))) ;; (p == end)
)
end
)Inlining the lambda function into the memory-to-sequence instruction's implied for loop, this adapter could be compiled fairly easily into a pretty-efficient loop in machine code. Optimizing this further into a memcpy would involve some fairly simple analysis, but it's possible that this would feel arbitrary enough to motivate a more-specialized instruction that was guaranteed to map to a memcpy.
The neat thing though is that the same memory-to-sequence+lambda design would allow mapping a std::list<uint8_t> to a sequence just as easily [Edit: take out explicit wasm...end]:
(@interface func (export ...) (param $list i32) (result (seq u8))
(i32.load offset=0 (local.get $list)) ;; list.begin()
memory-to-sequence (func (param $p i32) (result u8 i32 bool)
(lift-int i32 u8 (i32.load8_u (local.get $p))) ;; *p
(i32.load offset=4 (local.get $p)) ;; p->next
(lift-bool (i32.eq (dup) (i32.const 0))) ;; (p == nullptr)
)
)Lowering is a separate topic, but WDYT about this lifting?
fgmccabe
jgravelle-google
Here's a dump of what I've been thinking about sequences so far. This is informed generally by the experimenting I've been doing in my polyfill/interpreter. This isn't so much an "I have answers" so much as it is a "here's why I'm thinking this is tricky"
Core use cases (in order of importance)
Sample sequences
C++ alone has three immediate options:
T*buffer (plus length separately)std::vector<T>std::list<T>Assume vector is implemented as a struct with a pointer to a buffer, a length, and a current capacity. Assume list is implemented as a doubly-linked list, with pointers to the front and back.
I'm using C++ here because it can represent this in a variety of ways. For any given language I expect we only need to idiomatically support a single style. So for C++ we can have compiler support to autogenerate buffer adapters, but not linked lists, whereas in Scheme we could natively support linked lists but not necessarily anything else.
Complications
Assume we model a buffer of arbitray bytes as to list and vice-versa.
The vector case is surprisingly tricky to handle. On the one hand we can reuse the buffer-copying logic to marshal the actual data over. On the other hand, we need to maintain the vector invariants as we go (length, capacity). We either need to use a fold primitive and call in to the C++ code to push_back every element (and let C++ maintain the invariants), use the mem-to-seq instructions and fix up the invariants at the end, or move the invariant-maintaining logic in to the body of the folds. The only one of those that is amenable to optimization is to defer fixing up the internal state. I can't quite imagine how to express that without hand-writing the adapter, however (although for std::vector, as part of the standard library, we are technically able to do so).
seq<u8>. To support a maximally-efficient copy, we need to have primitives that can be optimized into a single memcpy. For the C-style simple buffer, we can do something similar tomemory-to-string/string-to-memory, which takes ptr + length and produces a seq, and vice-versa (open question: does this handle only u8, or is it parameterized, and what type is it parameterized on, interface types or wasm types?). For the linked list case, this is fundamentally impossible (and that's ok). We do need to be able to build a sequence from a linked list, so we will at minimum need another pair of primitives to do so. In my polyfill I triedfold-seqandrepeat-until(using helper functions), to go from seqFor simplicity of specification it may be nice to just have a single kind of general primitive, some form of fold or loop, and have clear rules for where it is optimized away into a memcpy. It is also probably better to start with the more general primitive, and add alternative more-optimal ones later on.