Best way to initialize array of 'drop' objects *inplace*

Q: I need to initialize a large (multi-GB) array of 'Drop' (aka !Copy) objects, and due to the large size, I'd like to initialize these objects inplace. The usual recommendations -- e.g., 'transmute' & friends -- don't work for !Copy objects, as they ... wait for it ... copy the array! I'd prefer to perform this initialization using safe Rust -- if possible. I've seen references to the possibility of extended Rust with C++-like 'RVO' optimizations, which might eventually provide an elegant solution.

Just to be clear, the problem with initializing arrays of 'Drop' objects is that any assignment attempts to 'Drop' the previous object prior to initializing the current object. Clearly this circularity has to be broken somehow.

What are the 'best practices' for this 'Drop array initialization' problem?

I assume the array is on the heap, i.e. the end result should be a Vec or a Box<[T]>, is that correct? Because in that case, you could just move into the Vec one-by-one by pushing onto its end.

2 Likes

Thx, H2CO3, I've seen recommendations like this before, but this method has numerous problems -- e.g., pushing stuff onto a too-short Vec can cause the Vec to get -- shudder -- copied, which would invalidate the existing objects (assuming that Vec's work at all for this problem).

I'd like to explore the possibility of not putting this array on the heap, since I'd eventually like this program to run on 'bare metal'/VM.

Unless you are doing something specifically weird (or at the very least unsafe), this shouldn't matter. Rust's moves are bitwise copies, types are expected to be copied around like that, and invalidation is either tracked statically (by the compiler) or dynamically (by the collection). If this weren't the case, you couldn't put any Drop type in a Vec.

You aren't going to be able to put multiple GB worth of data on the stack, that one is certain.

8 Likes

If you're considering arrays, you must know the number of elements statically, so you can use with_capacity to avoid reallocation.

And to reiterate one of @H2CO3's points, "not Copy" does not mean "can't move". If you're actually dealing with something that you think can't move, this is probably an XY-problem situation.

15 Likes

Drop objects can be memcpyd too, just like Copy types. non-Copy doesn't really mean it doesn't get copied in memory, but that the old copy is not allowed to be used after the object is copied. Rust doesn't have types can't be copied by memcpy, which is why it needs wrappers like Pin which make it harder to do by accident.

3 Likes

I would recommend something like this:

struct BigObject { ... }

let expected_number_of_items = 1_000_000;
let mut items = Vec::with_capacity(expected_number_of_items);

for i in 0..expected_number_of_items {
  let object: BigObject = ...;
  items.push(object);
}

It's simple, intuitive, and will almost always optimise to what you want. Using the Vec::with_capacity() constructor with an appropriate size also means you won't resize the vector, which may trigger extra memcpy() calls.

If you need to initialize the values in-place then you can use the Vec::spare_capacity_mut() method to access the uninitialized parts of the buffer so they can be initialized using unsafe.

#[derive(Debug)]
struct BigObject {
    first: u32,
    second: u32,
}

let expected_number_of_items = 1_000_000;
let mut items: Vec<BigObject> = Vec::with_capacity(expected_number_of_items);

unsafe {
    for uninitialized_item in items.spare_capacity_mut() {
        let uninitialized_item = uninitialized_item.as_mut_ptr();
        // initialize each field individually
        (*uninitialized_item).first = 1;
        (*uninitialized_item).second = 2;
    }

    // Safety: We've just initialized everything 
    items.set_len(items.capacity());
}

(playground)

This variant works well if the objects themselves are quite large (e.g. each BigObject contains big arrays or whatever) and if, as part of your benchmarking and analysis of the generated assembly, you find LLVM isn't optimising away the memcpy() from items.push().

7 Likes

Re: 'You aren't going to be able to put multiple GB worth of data on the stack, that one is certain'

bigstack.rs:

// Allocate a huge array on the stack.

// Parse a usize constant from a numeric environment variable.
const fn parse_usize(s: &str) -> usize
{
  let mut out:usize = 0;
  let mut i:usize = 0;
  while i<s.len()
  {
    out *= 10;
    out += (s.as_bytes()[i] - b'0') as usize;
    i += 1;
  }
  out
}

use std::mem::{size_of_val};

const ELIMIT: &'static str = env!("SLIMIT");
const SLIMIT: usize = 1024*parse_usize(ELIMIT);
const MB: usize = 1024*1024;

#[allow(unused_mut)]
fn main()
{
  println!("Hello, world!");
  println!("SLIMIT = {}",SLIMIT);
  let mut bigbuffer = [0u8;SLIMIT - MB];
  println!("size_of_val(&bigbuffer) = {} MB",(size_of_val(&bigbuffer) as f64)/(MB as f64));
}

Output:

Hello, world!
SLIMIT = 2048000000
size_of_val(&bigbuffer) = 1952.125 MB

So we've allocated & initialized a ~2GB array on the stack in Rust.

I did some further experiments, and found that the current Rust system --
even on a 64-bit x86_64 system -- crashes if I attempt to utilize a stack
segment of greater than 2GB (2^31).

I thought that this was a curious limitation -- reminiscent of 32-bit x386
systems -- so I did a similar experiment in Clang (LLVM's C language
implementation). On the same 64-bit x86_64 system, I was able to
allocate and initialize a 12 gbyte (a tad under the 12GByte real memory
size) array on the stack. (Curiously, a 13 gbyte array crashed the
Clang system, even though there was still plenty of swap space, but I
don't know if this crash was a Clang bug, or a Linux bug.)

So this limitation isn't due to the LLVM system which is targeted by
Rust's 'rustc' compiler, but some Rust-specific limitation.

Where could I file a bug report on this rather arbitrary Rust-specific
limitation for 64-bit Rust implementations?

What is your stack size (ulimit -s) set to?

FWIW, this is how high I was able to go, so I'm obviously not seeing the same behavior:

Hello, world!
SLIMIT = 10240000000
size_of_val(&bigbuffer) = 9764.625 MB

I can't go much higher than that with whatever the system default limits are (I get an error from ulimit).

I'm curious what might be causing clang's behavior to differ in your case. The only thing I can think offhand is stack clash protection (which Rust enables by default), so I wonder if using -fstack-clash-protection with clang might change the behavior, but I'm less certain since I'm not seeing the same thing to start with.

(I have to say I wouldn't recommend relying on having such a big stack though....)

I suspect you are running afoul of optimisations. The size_of_val(&bigbuffer) expression is known completely at compile time, therefore the bigbuffer variable never actually gets used and LLVM optimizes it out.

To test this hypothesis, I copied your code to the Playground.

const SLIMIT: usize = 50 * 1024 * 1024;
const MB: usize = 1024 * 1024;

fn main() {
    println!("Hello, world!");
    println!("SLIMIT = {}", SLIMIT);
    let mut bigbuffer = [0u8; SLIMIT - MB];
    println!(
        "size_of_val(&bigbuffer) = {} MB",
        (size_of_val(&bigbuffer) as f64) / (MB as f64)
    );

    // for (i, elem) in bigbuffer.iter_mut().enumerate() {
    //     *elem = (i % 256).try_into().unwrap();
    // }
    // println!("{:?}", bigbuffer[2034]);
}

(playground)

If you run that code in release mode then it executes just fine, however if you run in debug mode or with those lines uncommented then the bigbuffer doesn't get optimised out and you blow the stack.

4 Likes

Neither. It's not a bug. You are holding it wrong.

The stack was never meant to be used for storing multi-GB arrays. I don't understand your rationale for that. You claim to be using an embedded system, and that there is no dynamic allocation. But even embedded systems with resources like that usually feature a CPU powerful enough to host at least a minimalistic runtime library with a naïve malloc implementation. It is not common
practice even on embedded systems to do what you are attempting to do.

3 Likes
$ ulimit -s
12000000

I have 12GB of real memory on this x86_64; 4GB of swap space.

OK, I just increased my swap space to 16GB, and my Clang program
was able to alloca and initialize a 15GB array. It took a while due to the
swapping (setting swappiness=80 helped), but it didn't crash, so Clang
can properly handle multi-GB stack-allocated arrays.

Here's my new stack size limit, which is bigger than my real memory (12GB):

$ ulimit -s
16000000

Bottom line: Clang is working properly.

OK, here's my latest Rust version & output:

// Allocate a huge array on the stack.

// Parse a usize constant from a numeric environment variable.
const fn parse_usize(s: &str) -> usize
{
  let mut out:usize = 0;
  let mut i:usize = 0;
  while i<s.len()
  {
    out *= 10;
    out += (s.as_bytes()[i] - b'0') as usize;
    i += 1;
  }
  out
}

use std::mem::{size_of_val};

const ELIMIT: &'static str = env!("SLIMIT");
const SLIMIT: usize = 1024*parse_usize(ELIMIT);
const MB: usize = 1024*1024;
const STEP: usize = 512;

#[allow(unused_mut)]
fn main()
{
  println!("Hello, world!");
  println!("SLIMIT = {}",SLIMIT);
  {
    let mut bigbuffer = [0u8;SLIMIT];
    println!("size_of_val(&bigbuffer) = {} MB",(size_of_val(&bigbuffer) as f64)/(MB as f64));
    for i in (0..bigbuffer.len()).step_by(STEP) { bigbuffer[i] = 42u8; }
    println!("buffer initialized");
  }
}
$ ulimit -s
16000000
$ rustc --version
rustc 1.61.0-nightly (4b043faba 2022-02-24)
$ SLIMIT=10000000 cargo run
   Compiling myslimit v0.1.0 (~/rs_projects/myslimit)
    Finished dev [unoptimized + debuginfo] target(s) in 3.42s
     Running `target/debug/myslimit`
Hello, world!
SLIMIT = 10240000000
size_of_val(&bigbuffer) = 9765.625 MB
buffer initialized

So, Rust (at least Rust nightly) is able to alloca & initialize a 10GB
array on x86_64 architecture.

This almost main-memory-sized array allocation takes about 10
seconds on my old machine.

On the Linux 'System Monitor' window, you can watch the virtual
memory march up to 10 GB and then immediately fall back when
the Rust program finishes.

1 Like

Here's my best safe attempt in Rust so far:

// alloca and initialize a potentially huge array of 'Drop' objects.

// Parse a usize constant from a numeric environment variable.
const fn parse_usize(s: &str) -> usize
{ let mut out:usize = 0; let mut i:usize = 0;
  while i<s.len() { out *= 10; out += (s.as_bytes()[i] - b'0') as usize; i += 1; }
  out }

const EBYTES: &'static str = env!("SBYTES");
const SBYTES: usize = parse_usize(EBYTES);
const STEP: usize = 2;

// An example of a Drop (=!Copy) object which should not be moved.
mod no_copy
{

use std::ptr::{null};
use std::fmt::{Debug,Error,Formatter};

pub struct MyDrop { p: *const MyDrop, n: &'static str }

fn checkconsistency(this: &MyDrop) { assert!(this.p==null::<MyDrop>() || this.p==this); }

impl Debug for MyDrop
{ fn fmt(&self, f:&mut Formatter) -> Result<(),Error>
  { checkconsistency(self); write!(f, "MyDrop l: {:p} p: {:p} n: {}",self,self.p,self.n) } }

impl Drop for MyDrop { fn drop(&mut self) { checkconsistency(self); println!("MyDrop::drop self = {:?}",self) } }

pub fn myinit(this: &mut MyDrop, name:&'static str)
{ assert!(this.p==null::<MyDrop>());	       // Fail if already initialized.
  this.p = this; this.n = name; checkconsistency(this);
  println!("myinit this after  = {:?}",this); }

// Need an innocuous 'constant' for 2-step initialization.
pub const MYDROPNULL: MyDrop = MyDrop { p: null::<MyDrop>(), n: "from MYDROPNULL" };

}

use crate::no_copy::{MyDrop,MYDROPNULL,myinit};
#[allow(unused_imports)] use std::ptr::null;
use std::mem::{size_of};

fn main()
{ { println!("&MYDROPNULL = {:p}",&MYDROPNULL);	// appears to allocate temporary & immediately throw it away
    let pmydropconst = &MYDROPNULL;
    println!("pmydropconst = {:p} {:?}",pmydropconst,*pmydropconst);
    println!("before allocating mydrop...");
//    let mut mydrop: MyDrop = MyDrop { p: null::<MyDrop>(), n: "from mydrop" };	// fail: fields p,n are private.
    let mut mydrop: MyDrop = MYDROPNULL;
    println!("after allocating mydrop...");
    myinit(&mut mydrop,"from mydrop init"); }
  println!("");
  { let mut bigbuffer = [MYDROPNULL;SBYTES/size_of::<MyDrop>()];
    println!("SBYTES = {} size_of::<MyDrop>() = {} bigbuffer.len() = {}",SBYTES,size_of::<MyDrop>(),bigbuffer.len());
    let bigbufferslice = &mut bigbuffer[..];   		   // bigbuffer can't move with slice outstanding!
    for i in (0..bigbufferslice.len()).step_by(STEP) { myinit(&mut bigbufferslice[i],"from init loop"); }
    println!("bigbufferslice initialized");
    bigbufferslice[0]=MYDROPNULL;                          // Unfortunately, we can't disallow this.
    println!("bigbufferslice[0] = {:?}",bigbufferslice[0]);
    for i in 0..bigbufferslice.len() { println!("bigbufferslice[{}] = {:?}",i,bigbufferslice[i]) } }
  println!("Done.");
}
$ SBYTES=128 cargo run
   Compiling mydroparray v0.1.0 (~/rs_projects/mydroparray)
    Finished dev [unoptimized + debuginfo] target(s) in 0.31s
     Running `target/debug/mydroparray`
&MYDROPNULL = 0x7ffc7d0ce1e0
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce1e0 p: 0x0 n: from MYDROPNULL
pmydropconst = 0x7ffc7d0ce200 MyDrop l: 0x7ffc7d0ce200 p: 0x0 n: from MYDROPNULL
before allocating mydrop...
after allocating mydrop...
myinit this after  = MyDrop l: 0x7ffc7d0ce2a0 p: 0x7ffc7d0ce2a0 n: from mydrop init
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce2a0 p: 0x7ffc7d0ce2a0 n: from mydrop init
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce200 p: 0x0 n: from MYDROPNULL

SBYTES = 128 size_of::<MyDrop>() = 24 bigbuffer.len() = 5
myinit this after  = MyDrop l: 0x7ffc7d0ce318 p: 0x7ffc7d0ce318 n: from init loop
myinit this after  = MyDrop l: 0x7ffc7d0ce348 p: 0x7ffc7d0ce348 n: from init loop
myinit this after  = MyDrop l: 0x7ffc7d0ce378 p: 0x7ffc7d0ce378 n: from init loop
bigbufferslice initialized
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce318 p: 0x7ffc7d0ce318 n: from init loop
bigbufferslice[0] = MyDrop l: 0x7ffc7d0ce318 p: 0x0 n: from MYDROPNULL
bigbufferslice[0] = MyDrop l: 0x7ffc7d0ce318 p: 0x0 n: from MYDROPNULL
bigbufferslice[1] = MyDrop l: 0x7ffc7d0ce330 p: 0x0 n: from MYDROPNULL
bigbufferslice[2] = MyDrop l: 0x7ffc7d0ce348 p: 0x7ffc7d0ce348 n: from init loop
bigbufferslice[3] = MyDrop l: 0x7ffc7d0ce360 p: 0x0 n: from MYDROPNULL
bigbufferslice[4] = MyDrop l: 0x7ffc7d0ce378 p: 0x7ffc7d0ce378 n: from init loop
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce318 p: 0x0 n: from MYDROPNULL
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce330 p: 0x0 n: from MYDROPNULL
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce348 p: 0x7ffc7d0ce348 n: from init loop
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce360 p: 0x0 n: from MYDROPNULL
MyDrop::drop self = MyDrop l: 0x7ffc7d0ce378 p: 0x7ffc7d0ce378 n: from init loop
Done.

Comments:

There appears to be no way to properly initialize arrays of Drop objects with only one pass.
We must first initialize the array with an innocuous copyable value, and then initialize each
element again with the proper value.
Unfortunately, this method also allows us to effectively uninitialize the array element by
assigning the innocuous value again.

BTW, Rust allows us to take the address of this supposed 'constant' (!?!), but for some reason
it allocates a new copy and immediately throws it away (!?!).

I don't understand the point of Rust's allowing assignment for !Copy objects; if Rust had
a more rational way to initialize !Copy objects, then assignment wouldn't be necessary.

This is called static rvalue reference promotion. 1414-rvalue_static_promotion - The Rust RFC Book

The tool to avoid this is MaybeUninit<T>. However, you in particular should be very very careful with how you use it.

This performs the move operation: the source is logically deinitialized and will no longer be dropped.

4 Likes

This is simply false. It is entirely possible to initialize an array containing !Copy elements directly, in one pass. Here are 3 different ways that demonstrate this claim.

I can assure you the Rust way is entirely rational. It is not the fault of the language if you don't understand memory management and/or trying to do highly unconventional (at best) or dubious things with the language.

2 Likes

Thx, riking, for the clarifications & pointers.

Re: "= performs the move operation: the source is logically deinitialized and will no longer be dropped"

That protocol would be marvelous if it were universally true; however, as we have seen,
Rust allows re-assignment with this so-called 'constant' MYDROPNULL. So I'm wondering
why Rust allows Drop objects to be assigned from these copyable constants, which would be
unnecessary with a better initialization protocol.

Re: "The tool to avoid this is MaybeUninit<T> ... you ... should be very very careful with how you use it"

I'll be happy to post my attempts at using MaybeUninit; they're an even bigger (and unsafer) pain.

First of all, a !Copy type is !Copy no matter where it comes from. In your code above, the constant isn't (logically) "copied", it is not changing type, and it is not becoming magically Copy temporarily. It is the case instead that a constant is re-created using its initializing value any time it is used (its name is mentioned). This is one of the reasons why the value of a const must be known at compile time.

There is no reason to disallow arbitrary things in a language. Allowing non-Copy types in constants is useful, allowing assignment to non-Copy places is also useful, and both are consistent with how any other types work. This practice doesn't cause memory unsafety, so it is fine.

Re: "It is not the fault of the language if you are trying to do highly unconventional things with the language"

Phew! & thx for the compliment. I would be wasting my time coding & posting if I only wanted to do
conventional things!

I'm purposely trying to push the boundaries of Rust, and I'm putting my effort into Rust because it is
mostly a terrific language which I hope will get better with my comments and the comments of thousands of others.

1 Like

Rust won't get better by comments declaring that it's "irrational". It won't getter by artificially restricting working constructs after the fact, either, and doing so would cause high amounts of unwarranted frustration, since Rust promises to break as few things as realistically possible in order to maintain backwards compatibility, and what you are asking for would break lots of existing code, really for no good reason.

Anyway, feature requests for the design of the language are off-topic here. If you have a serious, well-thought-out RFC that is backwards-compatible, you can post it on IRLO instead.

1 Like