Efficiently Insert a Value in a Map

How to efficiently insert a value in a Map, supposing thousands of values in a Vec for a single Principal. How to append a Vec using this Map
The crate I am using is ic-stable-structures

pub static USERS_TRADED_IDS:RefCell<StableBTreeMap<Principal , Vec<u64> , Memory>>=RefCell::new(
    StableBTreeMap::init(
        MEMORY_MANAGER.with(|m| m.borrow().get(MemoryId::new(5))),
    )
);
    pub fn add_id(_user_id: Principal, id: u64) {
        let res = USERS_TRADED_IDS.with(|id| {
            let user_ids_opt = id.borrow_mut().get(&_user_id);

            let mut user_id: TradedIds = match user_ids_opt {
                None => TradedIds(Vec::new()),
                Some(ids) => ids,
            };

            user_id.0.push(id);
            id.borrow_mut().insert(_user_id, user_id);
        });


    }

The above is my implementation, but I want to know from the experts, if Is there any other efficient way to insert a value in this map and append the Vec which contains thousands of u64 values

StableBtreeMap looks like a very specialized data structure. I'm guessing your question is best answered by an expert in this area (ic_stable_structures and internetcomputer.org). Do you think that's true?

Yes, StableBtreeMap is a specialized data structure, but as a newbie, I thought the underlying language was Rust so most operations are the same. My concern is that appending the Vec by transferring the ownership to a new variable and then inserting the whole Vec later is not feasible. So I want to know how to append the Vec within the same ownership.

In a std BTreeMap, there is no drawback to moving a Vec out of a map, appending something to it, and then moving it back in again. The move is just a copy of a very small structure.

The question is whether the insert that you're doing on the StableBTreeMap is expensive enough to try to avoid. I would say that even if it is as cheap as using a std BTreeMap, if you're doing it a very large number of times, then it is worth trying to avoid the insert when there is an existing Vec in the map.

The problem I have in making a suggestion is that I don't know the semantics of StableBTreeMap get and insert. It appears that get returns an owned value, but it doesn't remove it from the map so that means it clones it in some way. When I look at the code it looks like it is materializing it from bytes. If that's true, it is recreating the Vec every time you get it and probably serializing it into bytes again when you insert it, and it will be extremely expensive to append large numbers of values to the Vec one at a time like this.

Note that StableBTreeMap has no get_mut so you can't get a mutable reference to the Vec and change it. Which makes sense if the map's elements are stored as byte arrays!

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.