Skip to content

Dynamic allocation during default construction #159

@simark

Description

@simark

I initially assumed that default constructing an unordered_dense map or set would be basically free (i.e. no dynamic allocation), like the std:: version. But it doesn't seem to be the case. The default constructor forwards to:

    explicit table(std::size_t bucket_count,
                   Hash const& hash = Hash(),
                   KeyEqual const& equal = KeyEqual(),
                   allocator_type const& alloc_or_container = allocator_type())
        : m_values(alloc_or_container)
        , m_buckets(alloc_or_container)
        , m_hash(hash)
        , m_equal(equal) {
        if (0 != bucket_count) {
            reserve(bucket_count);
        } else {
            allocate_buckets_from_shift();
            clear_buckets();
        }
    }

... with bucket_count == 0. allocate_buckets_from_shift() (regardless of the code branch taken) resizes m_buckets, which dynamically allocates.

Would there be a way to make the default constructor not dynamically allocate, without significantly affecting the performance on the other code paths? I'm thinking that we would need to add some of these in some other code paths:

if (m_buckets.empty()) [[unlikely]] {
    // initialize m_buckets
}

The reason I think it would be nice to have no dynamic allocation in the default constructor is that you could put a map or set in a scope and pay nothing if you end up not using it (and without wrapping it in an optional or something like that).

Of course, if doing this significantly degrades the performance on the other more important code paths, I understand it's probably not desirable.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions