Help me uncurse this bit of cursed rust code

[wild cove]

can you write this more elegantly?

this repeats push too much, but is readable

    fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
        let len = self.len();
        if len < self.capacity() {
            self.push(v);
        } else if let Ok(_) = self.try_reserve(len + 1) {
            self.push(v);
        } else {
            self.try_reserve_exact(len + 1)?;
            self.push(v);
        }
        Ok(())
    }

this is unreadable imo but doesn't repeat code

    fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
        let len = self.len();
        if len >= self.capacity() && self.try_reserve(len + 1).is_err() {
            self.try_reserve_exact(len + 1)?;
        }
        self.push(v);
        Ok(())
    }

[steady moss]

Why not just always call try_reserve?

[wild cove]

try_reserve_exact might work where try_reserve might not? At least that's my understanding

[steady moss]

Well you can also call it when there is more than enough capacity and it will be fine

[wild cove]

how so? If I call try_reserve_exact every time I'm going to allocate one position at a time, which is slow

[potent tulip]

Probably something like this?

fn push_checked(&mut self, v: V) -> Result<(), (TryReserveError, V)> {
  let len = self.len();
  if len == self.capacity() {
    match self.try_reserve(len + 1) {
      Ok(_) => ()
      Err(e) => return Err((e, v)),
    }
  }
self.push(v);
Ok(())
}

[wild cove]

it's missing the retry with exact

[potent tulip]

Yeah, because that's pointless

[wild cove]

and it doesn't push when it has space

[potent tulip]

try_reserve_exact has the same failure conditions, and an API that once an year is slightly nicer

[steady moss]

If the Vec is small

[potent tulip]

You don't need it

[steady moss]

If Vec is big then they become the same

[wild cove]

I'm confused

[potent tulip]

try_reserve may increase the capacity you request sometimes, if the vec is small and the type is also small.

try_reserve_exact won't do that. That is the only difference.

(also, you probably want to do double the vec's capacity, not add one, else push becomes O(n) eventually)

[wild cove]

I though try_reserve would do the doubling for me, like I thought it would "allocate enough for what you asked but I might do more"

[junior flint]

While not guaranteed, if try_reservefails, try_reserve_exact should also fail.

[wild cove]

hmmm

I'm still confused :/

when would I want to use use one over the other?

maybe that way I'll understand

try reserve says

The collection may reserve more space to speculatively avoid frequent reallocations.
I thought this basically meant that the vec would keep on using it's usual cap doubling algorithm

and I then assumed that try_reserve_exact wouldn't do that

[potent tulip]

Nope, it doesn't.

try_reserve only overallocates slightly for small vectors with small element types.

[junior flint]

Actually....

I might be wrong

@potent tulip ```rust
let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

    // This guarantees exponential growth. The doubling cannot overflow
    // because `cap <= isize::MAX` and the type of `cap` is `usize`.
    let cap = cmp::max(self.cap * 2, required_cap);
    let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);

https://doc.rust-lang.org/src/alloc/raw_vec.rs.html#390-395

[wild cove]

it calls grow_amortized, which I thought was the doubling thing

[junior flint]

Yeah

[wild cove]

yeah, it's there self.cap * 2

[potent tulip]

Huh, it does double? Nevermind then

Maybe we should, uh, say that in the docs

It sounds like it could matter

[wild cove]

yeah, I want to implement this like: try to double, if you can't try just one (it could be smarter but it's like this for now)

[junior flint]

@wild cove Either way. ```rust
fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
self.try_reserve(len+1).or_else(|_| self.try_reserve_exact(len + 1))?;

self.push(v)

}

[steady moss]

push does this oh no

[wild cove]

😮 because try reserve already checks cap, right?

nice

[junior flint]

TBH, I expected try_reserve to be more conservative and will fallback to try_reserve_exact if the capacity's too big

[steady moss]

"Vec does not guarantee any particular growth strategy when reallocating when full, nor when reserve is called. The current strategy is basic and it may prove desirable to use a non-constant growth factor. Whatever strategy is used will of course guarantee O(1) amortized push."

well at least it's sort of there

[junior flint]

Also, you don't even necessarily need the or_else there.

fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
    self.try_reserve(len+1);
    self.try_reserve_exact(len + 1)?;

    self.push(v)
}

would also work.

[wild cove]

you just need let _ = on the first one

but that's actually good

[potent tulip]

Though I'd try to return v on error

So the caller can get it back if the allocation fails, and use it for something else

[junior flint]

This one might have very slightly worse performance, because needs_to_grow might run twice. But in LLVM I trust.

[wild cove]

yeah, that's a good idea. I liked that but forgot

thanks!

[steady moss]

?eval ```rust
let mut min = 0;
let mut max = usize::MAX;

let mut x: Vec<u8> = Vec::new();

while min + 1 < max {
let mid = min / 2 + max / 2 + (min & max & 1);

x.clear();
match x.try_reserve_exact(mid) {
    Ok(_) => min = mid,
    Err(_) => max = mid,
}

}

println!("available memory: {}", min);

[regal finch]

     Running `target/debug/playground`

available memory: 4294967294
()

[steady moss]

complete side tangent

[wild cove]

binary searching avaiable memory

so, I ended up having to write it like this

    fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
        let len = self.len();
        if let Err(_) = self.try_reserve(len + 1) {
            let mut additional = len >> 1;
            loop {
                match self.try_reserve_exact(len + additional) {
                    Ok(_) => break,
                    Err(e) => {
                        additional >>= 1;
                        if additional == 0 {
                            return Err(e);
                        }
                    }
                }
            }
        }
        Ok(self.push(v))
    }

try_reserve doubles every time, so when it reached half of the available ram it just never succeded again
try_reserve_exact reserves 1 or 2 positions, so it was really slow

[steady moss]

self.try_reserve_exact(len + additional) should be self.try_reserve_exact(additional)

[wild cove]

huh

I've been doing this wrong the whole time

🤦

[steady moss]

try_reserve takes the extra you want

[junior flint]

Uhh

Oh wtf, it does

🤔

[steady moss]

this code clears it before hand

[junior flint]

If you're doing it that way, might as well just use try_reserve_exact all the way through.

Oh wait I'm dumb

I forgot that the try_reserve family bases it on length and not capacity.

[wild cove]

okay, final final final code

    fn push_checked(&mut self, v: V) -> Result<(), TryReserveError> {
        let before = self.capacity();
        if let Err(_) = self.try_reserve(1) {
            let mut additional = self.len() >> 1;
            loop {
                match self.try_reserve_exact(additional) {
                    Ok(_) => break,
                    Err(e) => {
                        additional >>= 1;
                        if additional == 0 {
                            return Err(e);
                        }
                    }
                }
            }
            let after = self.capacity();
            println!("used fallback {before} => {after} (+{additional})");
        } else {
            let after = self.capacity();
            if before != after {
                println!("used normal {before} => {after}");
            }
        }
        Ok(self.push(v))
    }

printlns for nice visualization

[dreamy iron]

The reserve methods need how many elements beyond the current length you need capacity for.

fn push_checked(&mut self, v: V) -> Result<(), (V, TryReserveError)> {
    if self.len() == self.capacity() {
        // Try to reserve space for half the current length more elements
        if let Err(_) = self.try_reserve((self.len() >> 1) + 1) {
            // If that fails, try to reserve space for 1 more element
            if let Err(e) = self.try_reserve_exact(1) {
                // If even that fails, return the element, so that it doesn't need to be cloned/recreated, and the error
                return Err((v, e));
            }
        }
    }
    self.push(v);
    Ok(())
}