memory consumption

[Thomblin]

Hi there,

I am currently prototyping a service which stores up to 30 million entries in one scc hashmap and a little above 1 million entries in another scc hashmap, consuming up to around 80 GB of memory. During night there is less traffic and the entries are removed step by step to around 10 million and 500.000 entries. According to https://docs.rs/scc/latest/scc/hash_map/struct.HashMap.html#resize I would expect that the memory consumption of my service shrinks accordingly, however so far I can only observe that it stays at the highest level. Is that expected, or do I need to call a certain function?

My data structure looks like this:

type Session = Arc<sccHashmap<String, SessionData>>;
type StoredCars = Arc<sccHashmap<String, Arc<Car>>>;

pub struct Store {
    session: Session,
    cars: StoredCars, 
}

pub struct SessionData {
    pub offers: Vec<Offer>,
    pub created_at: DateTime<Utc>,
}

[wvwwvwwv]

Hi @Thomblin,

The load factor of hash map containers (including std::collection::hash_map) is anecdotally kept at around 50%.

In your case, the number of entries decreased from 30 million to 10 million, so I assume the hashmap's capacity was 64 million. scc::HashMap starts to shrink when the load factor reaches ~6%, while 10 million entries amount to ~15% of the capacity. This means that in order for scc::HashMap to shrink, more entries should be removed.

In other words, scc::HashMap's shrinking policy is very conservative, so your application's memory consumption stays almost the same.

I may have to introduce a way to set a custom shrinking policy later.

[Thomblin]

Hello @wvwwvwwv

Thanks a lot for your fast reply and explanation. Allow me some follow up questions:

I assume that the load factor of 50% was chosen to balance size and key collisions?
Would it make sense to have the load factor as well as the shrink limit to be configurable? I could give it a try. (I guess the 16 at https://github.com/wvwwvwwv/scalable-concurrent-containers/blob/2ce0d97f88b95980a79c1281e92e2b96d1f577c5/src/hash_table.rs#L1024C50-L1024C61 needs to be moved into a variable then and accordingly change fn try_resize()?)

With the load factor of 50% and the "slow" shrinking: Does that mean that a lot of memory is reserved but never used? Given my datastructure using Arc<> and Vec<>, am I lucky as Arc stores a reference only and Vec is inititialized with 0 capacity, so that less memory is reserved (I don't have a deep understanding of these concepts yet)

[wvwwvwwv]

Hi @Thomblin again,

50% is an exaggeration, and it's usually ~2/3.

Hash table containers usually expand their internal storage when the capacity is 75-95% full; in the case of scc::HashMap, it's 87.5%. The capacity usually doubles, so the load factor becomes 37.5-47.5% right after a resize. Therefore, hash tables are mostly 37.5% - 95% full, and the average is ~66%.

Would it make sense to have the load factor as well as the shrink limit to be configurable?

Yes, that makes sense, but I'd prefer it to be a constant generics (type parameter) rather than a variable.

Does that mean that a lot of memory is reserved but never used?

That's correct, and that's what most hash tables are doing. Some - including Java's ConcurrentHashMap, or papaya - allocate heap memory for each entry (analogous to V = Box<T>), but that has a drawback; frequent heap allocations cause heap fragmentation that's bad for a long-lasting, frequently updated key-value store.

[Thomblin]

That make sense.

Regarding constant generics. I guess you mean to change

pub(super) trait HashTable<K, V, H, L: LruList, const TYPE: char>

to something like

pub(super) trait HashTable<K, V, H, L: LruList, const TYPE: char, const SHRINK: usize, const LOAD: uszize>

I would think that the HashTable contains too many generics then. Is it worth the mess?

Else maybe something like the following. Either way, it would be a breaking change I guess.

pub trait Config {
    const TYPE: char;
    const SHRINK: usize;
    const LOAD: usize;
}

pub(super) trait HashTable<K, V, H, L: LruList, C: Config>

I cannot tell how many people would actually use it (me included, now that I learned more about it). So maybe it breaks too much for some more flexibility. What do you think?

[wvwwvwwv]

I like this idea,

pub trait Config {
    const TYPE: char;
    const SHRINK: usize;
    const LOAD: usize;
}

pub(super) trait HashTable<K, V, H, L: LruList, C: Config>

and it would not be a breaking change as long as a default config is provided.

On the other hand, I can just relax the shrinking policy (e.g., shrink if len/capacity < 0.1-0.25) as that does not affect overall performance much.
-> It's a matter of the choice of the constant value; I'd like it to be ~12.5% but that won't cover your case. Opinions?

[Thomblin]

So. I am still experimenting with this. I guess I lack some deeper Rust knowledge. Adding the Config creates a lot of troubles with the compiler, as it needs to know the exact implementation during compile time, which might not be what we want. Using dyn Config seems not to be allowed.

In case you want to take a look at it, maybe you have an idea: https://github.com/Thomblin/scalable-concurrent-containers/pull/1/files

[wvwwvwwv]

The change looks solid to me, especially the part where you combined the container type with the shrink parameter into Config.

If you have trouble resolving compile-time errors, one simpler solution would be to introduce a new type parameter to fn remove<const SHRINK_FACTOR: usize = xx>(&self...) and fn try_shrink<const SHRINK_FACTOR: usize = xx>(&self...) instead of the whole container type.