Generating and returning large structs

1

(language compiler)

I am generating a large AST (a tree of structs, collections of structs, enums etc). That cant go on the stack because its big and I need to pass it around. I have a module with an entry point that takes as input the source code and returns the AST. What is the canonical way to do this (lets say the type is AST)

  • pub fn gen(..) -> AST
  • pub fn gen(..) -> Box
  • pub fn gen (&mut AST)
  • pub fn gen(..) -> Rc

where I have

struct ASTGenerator{
    ast:xxx
    ...
}

impl ASTGenerator{
   pub fn gen xxxx
}

in the first one I try to get the magic rust RVO to work. I cant. Maybe its because the thing I am generating is a member of the generator struct

returning Box doesnt work because I would have to build the ast on the stack and then return a boxed copy (I think)

any tips?

2

Are you sure that you actually have a large value? It’s not the size of the whole tree that matters, but the size of one node. Check the actual size:

println!("{}", size_of::<AST>());

If it is not more than a couple hundred bytes, don’t worry about it. If it is — why is it large? What is the definition of your AST type?

1 Like
3

If at all possible, this. The caller can decide how to manage memory.

I'd be more than a little surprised if a parse tree was "too large to pass on the stack," as parse trees tend to be composed of multiple, separately-created nodes, rather than one big, fixed-sized structure. Can you share the declaration of AST and of any structs contained directly inside of it (without an intervening &, &mut, Box, Rc, Arc, Vec, etc)?

1 Like
4

well duh , what an idiot, its actually very small, logically huge but made up of Maps, and Vecs of things !

But, for the sake of completeness what would have been the answer if this was one huge structure.

6

I'd probably evaluate both pub fn gen() -> Box<AST> and pub fn populate(ast: &mut AST) in context, to see which reads more clearly for the use cases I care about. As the version that takes &mut AST can be applied to many different kinds of previously-allocated value, I might prefer it if clarity is otherwise neck-and-neck.

There is no canonically-correct answer, it's all about what works for your program or for your library's users, ultimately, but I frequently prefer deferring concrete decisions about memory allocation as far up the call tree as I can while keeping the code reasonably clear in the process.

7

actually after some thought I still dont know what to do. When I return the root object (which is just

pub struct MoiraProgram<TInst> {
 
    pub functions: Vec<Function<TInst>>,
    current_function: usize,
}

it gets cloned and that will recursively descend everything and clone them too. Thats a lot of copying - I agree I am not going to blow the stack

8

If you are in a position of needing to pass around a program AST in a way that requires cloning, use Arc instead of Box. This allows the structure to be shared between different users.

9

Recursive implementations of Clone, including the implementation generated by #[derive(Clone)], will consume stack space proportionate to the depth of the cloned values, at least. However, if that's a concern, you can always implement Clone by hand, doing something more suitable to the shape of the structure.

Test that it is an issue, first, though. Parse trees tend to have depths on the order of tens to hundreds of nodes, depending on the level of granularity of the parser and on the structure of the language, and "hundreds" of values the size of a Vec (a pointer and a length, basically), a usize, and some padding is going to come out to single-digit numbers of kilobytes at worst. You likely have more than enough stack space, unless you're targeting extremely limited systems.

As @kpreid says, if you don't need to clone these values, don't. The only time I'd expect to need to copy the parse tree after it's constructed, or to need to copy part of it, is to modify it. If your algorithm doesn't need to modify the tree, walk it in place. Replacing Box with Arc is one path to accomplishing that.

10

isnt it getting copied when I return it? I cant make the RVO work if I am returning a struct member ( the return statement complains that there is no clone on the root bject - thats how I reckon the RVO isnt working)

Recursive implementations of Clone , including the implementation generated by #[derive(Clone)] , will consume stack space proportionate to the depth of the cloned values, at least.

99% of the tree is on the heap (vecs and hashmaps), not the stack

11

There's no one easy answer is the problem. So any answer tends to be very specific to the situation you actually have.

After all, as here, it's somewhat rare to have huge single values.

12

Early on when I started using Rust, I was certain that this would be a problem I would into from time to time, but so far it hasn't happened.

I don't know why I imagined that my structs in C where so huge that porting them to Rust would be an issue.

1 Like
13

Could you maybe share a bit more context on what kind of things you’re trying (in code examples, I guess) when reasoning about return-value-optimization in the context of Rust?

I know RVO mostly from (limited) C++ knowledge, but the situation in that language is a lot different because of implicit (expensive) copy constructors. RVO is important – for example – in particular to avoid expense of copy constructors (which could end up recursively copying a bunch of heap data); the stack size of objects also isn’t too large all that often, so that’s often only a minor concern.

C++ is also “fun” in how their (version of doing) moves is rather complex, sometimes requires explicit annotations (std::move), and for example for RVO of a local variable, usage of the std::move function can actually be detrimental.

So while e.g.

// Rust
let y = x.clone();

is Rust’s analogous syntax for C++’s

// C++
auto y = x;

whereas

// Rust
let y = x;

(for non-Copy types) is more like

// C++
auto y = std::move(x);

With RVO in mind however, returning a local variable x from a function in C++ should not use

// C++
return std::move(x);

but instead

// C++
return x;

but this absolutely does not mean that e.g.

// Rust
return x.clone();

would be an analogous choice in Rust. In Rust, there is no rule for any clone-elision. Clone::clone isn’t anything special at all anyway, it’s mostly a library-concept.

In case that’s what you were trying, i.e.

// Rust
return x.field.clone();

to check out whether some sort of “RVO” can kick in to eliminate that .clone(), … not that does not work. But you shouldn’t need it anyway; just don’t do .clone() when you don’t need it.

I’m reading your sentence of

if I am returning a struct member ( the return statement complains that there is no clone on the root object […] )

as that this above might possibly be what you tried, but of course this is only me guessing, and can be completely wrong. You simply don’t sufficiently explain at all what you were actually doing here, so I can’t possibly know :wink:

3 Likes