Array initialization using default Foo struct

Hello! Any help here would be greatly appreciated.

The rust code below populates an array with default Foo values, up to N elements. I wish to do the same thing without having to explicitly code the Foo elements. That would obviously be unreasonable for large values of N (1K to 1M, or even more).

Also, my primary goal is speed so I wish to avoid using vectors.

I also would like to avoid unsafe code blocks. If I must use unsafe, then the simpler the better for obvious reasons. ( I tend to think that if unsafe is required, then it should be a very high priority to call for an improvement to rust-lang to change this. Therefore I would like the code easily modified to take advantage of such a hypothetical future version of rust. )

Again, I really appreciate any input here. If this is indeed a problem area in the language I think the answer(s) provided here would be very important to pin down. If there are references or links then please share!

struct Foo {
    abc: String,
    def: u32,
}

const N : usize = 2;

fn main() {
    let foo: [Foo; N] = [
        Foo{
            abc: "default".to_string(),
            def: 0,
        },
        Foo{
            abc: "default".to_string(),
            def: 0,
        },
    ];
    
    for bar in foo.iter() {
        println!("bar.abc={}, bar.def={}", bar.abc, bar.def);
    }
}

String already allocates for its contents (I believe it actually uses Vec internally for this). The overhead of the top-level Vec is going to be negligible if you have arrays of thousands or millions. Also, arrays that large are likely to overflow your stack and prematurely terminate your program. If N is known, then vec![] or Vec::with_capacity(N) can be used to do the allocation in one go:

#[derive(Clone)]
struct Foo {
    abc: String,
    def: u32,
}

impl Default for Foo {
    fn default() -> Self {
        Self {
            abc: "default".to_string(),
            def: 0,
        }
    }
}

const N : usize = 2;

fn main() {
    let foo = vec![Foo::default(); N].into_boxed_slice();
    
    for bar in foo.iter() {
        println!("bar.abc={}, bar.def={}", bar.abc, bar.def);
    }
}

Playground

Note the implementations of Clone and Default. I’ve also used Vec::into_boxed_slice() so that there are no concerns about inadvertently resizing the Vec later (possibly incurring allocation overhead).

The vast majority of the allocation overhead for large N will be in String::clone(), which allocates new memory for each String instance.

If you can avoid fields owning heap allocated memory and use only field types that implement Copy, then you can #[derive(Clone, Copy)] your structure, and use a plain array literal (= [Foo::default(); N];), but again beware of stack-space!

3 Likes

I appreciate your comments about Vec however, my use of String was to be taken as a random choice (as implied by the name Foo) and should have been less complex to avoid Vectors. In my real application "abc" might be a tree of struct that also have structs over which I would have the same performance concerns. And if using a Vector is okay, I would like to be able to run benchmarks.

Same goes for concerns about stack usage. Imagine many of these running in parallel. Again, I think this should be easier.

I use Prolog which is makes very heavy use of stack--- point being that massive stacks are not always something to avoid-- it's just another LIFO structure after all. They are sometimes an effective approach in AI where recursion is very frequent.

I wish to expand on my desire not to use Vector. I am migrating C code to Rust and it would not be a good result after all the work to find that Rust performs less efficiently due to something about vectors.

Maybe my concern is misplaced, but just "hoping" that vectors are going to be as fast feels too much like relying on a garbage collector to be efficient. In order to compete with my C version I think I really need these to be blocks of memory that I control.

You might want to look at [arrayvec - Rust] which is effectively

struct ArrayVec<T, const N: usize> {
    buf: [MaybeUninit<T, N>,
    len: usize,
}
1 Like

Interesting. I will. Thanks for the suggestion!

If they’re fixed-size “plain old data”, then it should be possible to implement the Copy trait and just use the plain array literal syntax [Foo::default(); N]. If they’re not fixed size, things get complicated.

On this machine, ulimit tells me that my stack size limit is 8 MiB, but this only applies to the main thread’s stack, which Linux grows up to that on page-fault. Additional threads get 2 MiB, although you can configure that. I only mention it because you said “1M, or even more [elements]”, which would easily hit those limits. I don’t know about Prologue, but if C works for you then so should Rust.

In C terms, Vec is essentially a thin wrapper for malloc() on creation, free() on destruction (along with calling destructors if applicable), and realloc()/memcpy() if you resize it. Destruction is deterministic, so no garbage collection. Converting it to Box<[Foo]> removes the possibility of accidental realloc(). The elements are stored consecutively in a single block of memory thus allocated (ignoring any nested Vec/String/Box etc. structure fields). Other than that, there is the same indirection overhead that you’d potentially have in C with a pointer-accessed malloc()ed array, which in turn is dependent on hardware architecture.

Indexing into Vec is checked (something like assert(i < N) in C), but that is true for built-in Rust arrays and slices too, and can often optimized away in loops.

1 Like

There's a very important distinction between Copy and Clone-but-not-Copy here.

If you're using a type with any sort of drop logic (deallocating like String or HashMap, closing files, etc) then you might as well just use Vec. The one deallocation for the heap memory for 1M elements is completely negligible compared to needing to actually run that logic for all 1M elements.

(Honestly, even for a small copy thing like u16, by the time there's 1M elements you might as well put them on the heap anyway. Stack arrays are great for dozens of values, but by the time there are hundreds of thousands, just allocate it. A million allocations is potentially a problem. One is not. You're presumably going to look at all of the items at some point, which dwarfs the cost of allocating space.)

As a meta-point, why do you need so many default-initialized values? Can you just not initialize them until you have a useful value?

There’s ongoing work to add helper methods for something like this, like #75644. There’s also the unstable <[T; N]>::map. Unfortunately, the Default implementation of arrays is still limited to fixed sizes up to 32 due to the [T; 0] implementation having been (accidentally) stabilized without any T: Default bound. But this can be enough for a small, known constant.

There’s also this article Methods for Array Initialization in Rust | Josh Mcguigan - The things I write

Someone else already mentioned arrayvec for a possible tool to use.

To demonstrate why <[T; N]>::map is useful, look at this:

#![feature(array_map)]

struct Foo {
    abc: String,
    def: u32,
}

const N : usize = 2;

fn main() {
    let foo = [(); N].map(|()| {
        Foo{
            abc: "default".to_string(),
            def: 0,
        }
    });
    
    for bar in foo.iter() {
        println!("bar.abc={}, bar.def={}", bar.abc, bar.def);
    }
}
2 Likes

Thank you (all) very much, this is all very helpful and insightful.

In fact, I have no desire to initialize the elements to a default value and it would be nice to know how to do that easily and without unsafe code blocks. I will be populating the array in sequential order and only then will the values ever be accessed. My thinking on this topic essentially starts with the sample code I provided. Is there a way to modify my sample code to declare the array without any initialization at all and have the compiler smart enough to detect invalid accesses until the elements are assigned one by one? ( I assume there is not any sort of runtime validation that would panic and prevent reading from an uninitialized array element, am I wrong about that? )

One other comment related to stack worth expanding upon and then a question. I had mentioned Prolog previously when discussing the potential for very large stack requirements. ( If you would prefer me to open a separate topic on this, please just ask. )

When you write Prolog code, recursion is a fundamental pattern used in all but the most simple programs. For example there are no loops. Instead you declare a recursive decent through your sequence until a base case is reached which in effect terminates the loop. The result is that any Prolog coder is intimately aware of the notion of tail call recursion and will typically try his or her best to make use of it. (not always possible).

Now the question-- Does rust-lang compiler perform tail-call recursion optimization?

In my particular use case, there are no Prolog like patterns, but there is a Lisp orientation. I'm creating a Genetic Programing (GP) solution and so deep recursion is a potential problem to solve-- not for simple loops of course, however in the classic solution to GP, which I'm following, the application
will "evolve" Lisp Like S-Expressions. The depth of which will be fairly limited <1000, still the interpretation of which will require recursion, so tail call optimization could provide substantial performance (and memory) gains.

Yes, sometimes, but it also sometimes doesn't. There is no way to get the compiler to guarantee that it happens.

C'est la vie! Thanks. I thought it was worth asking. True for complex cases in Prolog too. So that's often why you need to provide huge stacks.

Such "runtime validation" would be manifested explicitly on type level - that is, you have to create an array of Nones and then replace them one by one with Somes.

There is no way to check whether memory is uninitialized or not. You have to store the information elsewhere, such as in the length field in the case of a Vec<T>. As @Cerberuser mentions, you can sometimes store the information in the type system, but this involves using different types for the different cases.

Besides these, if you run the code under the miri interpreter, it can detect it in some cases.

That makes sense. I was imagining a system whereby a runtime construct would insure that for any given array index that was not initialized (all of them to start) a read would cause a panic if performed before a write on that index. Such a system could use a bitmap (for example) and then once all the elements were initialized the bitmap could be destroyed and validation turned off because it was no longer required.

btw/ A bitmap would handle the case where the array addresses were initialized randomly. Since it is so common for an array to be initialized sequentially--- a trait could assert that case and no bitmap would be required. Instead a scalar "max initialized index" value would be all you would need. Any attempts to initialize the array out of sequence, would cause a panic. And again, once that value reached the array capacity, the validation could be turned off.

Better yet, you could have a system that assumed sequential initialization sequences, and store a table of min max ranges that have been initialized, once that table exceeded a certain size it could automatically be converted into a bitmap.

This is exactly what the arrayvec crate that @Mokuz mentioned earlier does.