Can serde serialize cause stack overflows on wasm32?

1

Does serde::serialize use O(1) stack depth or O(d) stack depth, where d is the 'depth' of the struct (when viewed as a tree) ?

Main concern here is whether "deep / linear" structs can cause serde::serialize to stackoverflow on wasm32. In particular something like:

struct Cons<T> {
  car: T,
  cdr: Option<Rc<Cons<T>>,
}
2

Interesting question. I believe that if you derive the implementation, then it does need stack proportional to the depth of your data structure. What a manual implementation could do - well - if it serializes a singly linked list like your example into a sequence, then that can of course be done in constant stack space.

I'm not sure about whether you can reduce stack usage if you still want to serialize deeply nested structs into deeply nested JSON (or whatever output format you choose). I'm not sure if that's possible in constant/limited stack space with serde's trait infrastructure at all - another question is what the stack usage of concrete serializers / deserializers are, e. g. for serde_json.

I'm unable to investigate further right now because I'm on mobile and it's also pretty late already in Europe.

Actually, some quick googling revealed something like

serde_stacker - Rust

the existence of which does suggest that

  • stack overflows are usually a potential problem, and
  • it's not trivial to work around them (the crate uses some dynamic stack growing infrastructure, the crate stacker. stacker - Rust)

Another skim of the API of the Serialize and Serializer traits from serde seems to confirm that it's hard or impossible to avoid growing the stack without something magical like stacker that can execute callbacks on some new grown stack.

1 Like
3

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.