Comments (18)
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.
- calulate the initial capacity with predefined keys, so the hashmap won't do expensive rehash.
- use
find_perfect_hash_seed
to get a hash seed (get into hash function) that with no/few collision. - 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.
Related Issues (20)
- [BUG] Negative exponent causes invalid literal number error HOT 2
- Is it possible to use wasm like pyscript? HOT 2
- [BUG] `sys.stderr.write()` does not use `vm->stderr_write()`
- [BUG] `exit()` calls `std::exit()` instead of raising a `SystemExit` HOT 2
- [BUG] Memory leak during class member function binding HOT 9
- [BUG] `help()` references `__signature__`, which does not exist on native_func's. HOT 16
- [BUG] Evalating many small expression uses too much memory HOT 8
- [BUG] Dangling pointer of string_view from __cached_codes in VM object HOT 2
- [v2.0-c11] move core implementation to C11 HOT 4
- Make `Dict` c11 HOT 1
- [Feature] Enable GCC-7 Support HOT 2
- HelloGitHub Badge HOT 2
- [Feature] Support wasm32 target (without WASI) HOT 1
- [Question] Compile to WASI with clang HOT 12
- [BUG] "out of bounds memory access" when compiled to wasm HOT 13
- [Feature] Please allow non-static stdout/stderr options HOT 2
- [Documentation] Directions for CMAKE as static library HOT 1
- [BUG] TypeError when creating an object from a class which inherits from a dataclass
- [BUG] pocketpy.h: No such file or directory when embedding pkpy HOT 1
- [Feature] status of bind11? HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from pocketpy.