optimiazte emhash8 about pocketpy HOT 18 CLOSED

Thanks for your advice.

As for now, there is a new class StrName which does pooling for all identifiers. So we don't need to hash std::string anymore.

emhash8::HashMap<StrName, PyVar>

StrName is a 32 bit integer. So I'd like to find a special hash for this case.

from pocketpy.

Currently there is a huge overhead in function call.

When doing a call like f(x, y, z), we need to new a hashmap to store locals. And the locals will soon be freed when function returns.

For this case, I think the hashmap can be optimized for storing 0-8 elements(regular argument numbers of a function call) and it has good new/delete performance.

from pocketpy.

now only emhash5 support small hashmap,
you can try it by define EMH_SMALL_SIZE = 8

from pocketpy.

#define EMH_FIND_HIT can improve finding hit performance(10%) in emash5/6, but find miss is some slow.

from pocketpy.

now only emhash5 support small hashmap, you can try it by define EMH_SMALL_SIZE = 8

That's awesome. What happens if adding more than 8 elements with EMH_SMALL_SIZE=8.

from pocketpy.

if size > EMH_SMALL_SIZE, it will alloc heap memory and copy stack memory to heap.
just like llvm::SmallVector do. user do not care about any memory issiue.

from pocketpy.

from pocketpy.

Great. I also have an idea to implement a very customized version, focusing on <int32, PyVar>.

For example, I want to pre-make some hashmap that sizes 8, 16, 32. When needed, we can just retrieve one from the pool.

cpython's hashmap always use the power of 2 as capacity, and they use a hash function only works for 2^x.

from pocketpy.

Great. I also have an idea to implement a very customized version, focusing on <int32, PyVar>.

For example, I want to pre-make some hashmap that sizes 8, 16, 32. When needed, we can just retrieve one from the pool.

emhash5 only used a fixed marco EMH_SMALL_SIZE, as for support different small stack hash map,
EMH_SMALL_SIZE need to be a template arg like llvm::SmallVector do

from pocketpy.

https://github.com/python/cpython/blob/main/Objects/dictobject.c#L172

from pocketpy.

but emhash5 is used a fixed marco value, so need change it to be a template arg

Perhaps it is not the case.
I mean pre-making the underlying array, not hashmap instance. When the hashmap enlarges, it retrieves a low level array from the pool.

If I can access to the low level array, there is a faster way to move a bunch of PyVar.(tagged pointers)

However, it is only applicable for my case. It is not universal.

from pocketpy.

but emhash5 is used a fixed marco value, so need change it to be a template arg

Perhaps it is not the case. I mean pre-making the underlying array, not hashmap instance. When the hashmap enlarges, it retrieves a low level array from the pool.

If I can access to the low level array, there is a faster way to move a bunch of PyVar.(a tagged pointer)

**inline const value_type* values() const { return _pairs; }** 

in emhash8, _pairs is is a continuous array and easy used(do not change keys outside)

but for emhash5-7. the values is also continuous but some node is empty.

from pocketpy.

emhash8<int, int> e8 = {{1,2},{2,0}};
const auto& node = *values();
for (int i = 0; i < e8.size(); i++)
  doit(node[i].first, node[i].second);

maybe I can add index opertion to emhash8.

from pocketpy.

Thank you~I will try!

from pocketpy.

if no any deletion on emhash8, the order of nodes array just as insertion order.

from pocketpy.

I am trying a fancy idea.

I noticed a fact that, the keys of some hashmap is already known. For example, int has __add__, __sub__, etc. Its keys won't change. A function locals, the keys are predefined in the symbol table. (unless one call setattr or exec to dynamically add key)

So I made a simple hashmap with some special things.

1. calulate the initial capacity with predefined keys, so the hashmap won't do expensive rehash.
2. use find_perfect_hash_seed to get a hash seed (get into hash function) that with no/few collision.
3. Dynamic load_factor, for type/module object, small load factor is used since they are not frequently new/delete. For normal objects, use standard load factor to save memory.

In my test, with these change, most of the time we are doing perfect hash.

    uint32_t find_perfect_hash_seed(uint32_t capacity, const std::vector<StrName>& keys){
        if(keys.empty()) return -1;
        std::set<uint32_t> indices;
        std::vector<std::pair<uint32_t, float>> scores;
        for(int i=0; i<kHashSeeds.size(); i++){
            indices.clear();
            for(auto key: keys){
                uint32_t index = _hash(key, capacity, kHashSeeds[i]);
                indices.insert(index);
            }
            float score = indices.size() / (float)keys.size();
            scores.push_back({kHashSeeds[i], score});
        }
        std::sort(scores.begin(), scores.end(), [](auto a, auto b){ return a.second > b.second; });
        return scores[0].first;
    }

However, this method only ensures all keys are mapped into different index. Find hit is fast. Find miss is unknown.

from pocketpy.

https://github.com/renzibei/fph-table, just tiny faster than flat hash.

https://martin.ankerl.com/2022/08/27/hashmap-bench-01/#benchmark-results-table

**A very interesting new contender: This hashmap implementation uses a perfect hash, thus it doesn’t have any collisions. This should make it extremely fast for lookups, but with a potentially high overhead for insert/removal.

The Good
Find is extremely fast, regardless of the hash. In fact, std::hash or boost::hash is best here even with their bad hash quality.
The Bad
Insert and erase and copying the map is very very slow, the slowest in the benchmark. Memory usage is very high. I’d say this map is good for stable data that is never modified, and when you can afford the high memory usage.
About
Website: https://github.com/renzibei/fph-table/tree/noseed, Tested version: 1a613aba (noseed), License: none specified**

from pocketpy.

That makes sense. It still require some time to find perfect mapping algo.

I also changed the layout of <KeyT, valueT>. Normally we use std::pair or struct to store them.

While I use this.

[key0, key1, key2, ...] [val0, val1, val2, ...]

https://github.com/blueloveTH/pocketpy/blob/main/src/namedict.h#L19

So I can use memset to reset keys/values/both, instead of calling destructor. (it only works for specific type and cannot be a template dict impl)

from pocketpy.