After you run the test, check the account (userInfoAddress in your test) with this command solana account %account_pubkey% (local validator must be running) and you will see that the account bytes returned have a lot of unused space (the padding 0s at the end).

What's likely happening is that Anchor is deserializing your account and thus putting the account in memory, the heap space is limited to 32k, and so when your account is more than or close to this it will create the error Error: memory allocation failed, out of memory.

To confirm this, get the account in JSON format, compress it, and calculate the size. You can do this with this command (local validator must be running):

anchor account solana_memory_issue.UserInfo %account_pubkey% | jq -c | wc -c

Convert the result to KB (divide by 1024) and you will get 32.99 KB.

Solutions to this depend on what you're trying to achieve. Maybe this answer to a similar question can help you.

PS: I greatly appreciate you adding the git link to reproduce this error.

After you run the test, check the account (userInfoAddress in your test) with this command solana account %account_pubkey% (local validator must be running) and you will see that the account bytes returned have a lot of unused space (the padding 0s at the end). So there is still space left in the account.

I have run your test and consistently get 496 friends added, I cannot reproduce the situation where "it throws this error randomly", so my answer is based on my results where the behavior is consistent. Although it still runs out of memory faster than you would expect.

Why it's running out of memory is because when you use Vec<T>.push(), it will reallocate memory in a way that is best suited and performant for most use-cases, and since memory reallocation is expensive it often just doubles the memory needed by the Vec<T> just so that it will not have to do a new reallocation too soon. So often your Vec<T> that by your calculations is, say, 100 bytes, will actually take up up to 200 bytes of memory.

So given that Vec<Friend> is 33 bytes * number of friends, the program in my case consistently fails after it added 496 friends. At 496 friends it represents 16368 bytes. At the next .push() it will try to double the Vec size which would now be 32kb+ bytes.

Given that Solana programs are limited to heap size of max 32kb, our Vec<Friends> + other variables in memory easily go over this limit and an error is thrown. 

You can see these changes in memory allocation if you add this code to pub fn add_friend() after the .push()

let capacity = ctx.accounts.user_info.friends.capacity();
let size_of_friend = std::mem::size_of::<Friend>();
msg!("Capacity: {}, Size Of Friend: {}, Size: {}", capacity, size_of_friend, capacity * size_of_friend);

Notice how capacity of the Vec changes, with doubling often when it reallocates memory. These are the logs from my local machine.

There are different ways of manually allocating memory for a Vec in Rust, such as Vec::reserve().

PS: I appreciate you adding the git link to reproduce this error.