Replies: 11 comments 14 replies
-
|
@methane ^^ |
Beta Was this translation helpful? Give feedback.
-
|
At one point in Matt's talk, he discusses a rejected cache-line-friendly design that requires 8-byte keys, and explicitly says that if he were designing a hash map for Python, he would use that design. (Note, however, that Python's insertion ordering guarantees make a lot of this stuff a bit trickier.) Basically, keys are collected in groups of seven, with the struct for each group looking something like: typedef struct {
uint8_t ever_full : 1;
uint8_t tombstones : 7;
uint8_t hashes[7]; // Low byte of each hash.
PyObject *keys[7];
} seven_keys;...then use intrinsics on the first 8 bytes to probe for hits. |
Beta Was this translation helpful? Give feedback.
-
Wouldn't it mostly be a matter of switching to I guess variants with uint8_t, uint16_t, uint32_t and uint64_t like in the current CPython dict could help with that memory usage, but then it would probably be preferred to use the standard Swiss Table structure (not the "Cache Line Aware Groups" version). Something like struct _dictkeysobject {
Py_ssize_t dk_refcnt;
uint8_t dk_log2_size;
...
/* Everything below could be computed dynamically, not actual struct members */
uint8_t CONTROL_BYTES[CURRENT_NUM_BINS][16];
union {
uint8_t SMALL_INDICES[CURRENT_NUM_BINS][16];
uint16_t MEDIUM_INDICES[CURRENT_NUM_BINS][16];
uint32_t LARGE_INDICES[CURRENT_NUM_BINS][16];
uint32_t HUGE_INDICES[CURRENT_NUM_BINS][16];
};
DictKeysEntry items_in_insertion_order[16 * CURRENT_NUM_BINS /* capacity */];
};Memory overhead would be a bit larger for small dicts (2 bytes per entry instead of 1 in the main hash table, and the minimum size would be bigger), but probably not that bad. |
Beta Was this translation helpful? Give feedback.
-
|
One could even attempt to write a C++ extension module that uses pre-existing |
Beta Was this translation helpful? Give feedback.
-
|
I impressed how they lookup value in a group: https://youtu.be/ncHmEUmJZf4?t=1739. Currently, our Current:
Idea:
(When SSE2 can be used, we can use same idea for len<=16 hash.) |
Beta Was this translation helpful? Give feedback.
-
|
This is proof of concept code.
Microbenchmark for the best scenario: Note that all of (1,9,17,25) has 1 mod 8. So searching 25 needs four comparison. On the other hand, more realistic microbenchmark shows very small difference. And I can not see any difference for pyperformance. |
Beta Was this translation helpful? Give feedback.
-
I had used wrong version for benchmarking. I reran the pyperformance and get "1% faster". And I implemented vector16 that works only with SSE2: |
Beta Was this translation helpful? Give feedback.
-
|
vector16 is implemented in methane/cpython#40 too. It seems performance improvement is significant. But I want to try implementing #219 (reply in thread) before finishing this dict-vector branch. |
Beta Was this translation helpful? Give feedback.
-
|
I noticed that optimizing for small dicts is not so important for now. Looking up from small dicts was important because small dict is very popular for instance namespace. But now:
That explains vector8 and vector16 have only 1% benefit. To optimize 2^5 ~ 2^10 cases, especially 2^6, implementing swisstable for all sizes seems much better to me. |
Beta Was this translation helpful? Give feedback.
-
|
Yes. |
Beta Was this translation helpful? Give feedback.
-
|
Is this discussion overlapping with #133 - could we relate or join these explicitly? revisiting #133 … also, there maybe performance trade-offs to consider depending on when and how we select the best fitting CPU instruction sets. I see four open issues in the aHash project that may be of interest here: |
Beta Was this translation helpful? Give feedback.
-
|
I don't think two issues are tightly coupled. Unlike Rust, string in Python caches hash value, and dict in Python stores hash values of keys too. |
Beta Was this translation helpful? Give feedback.
-
|
How would this hypothetical new design handle split dictionaries? |
Beta Was this translation helpful? Give feedback.
-
|
In my idea, no change for split dictionary. I will try supporting 16-vector and split dictionary use it instead of hash table. |
Beta Was this translation helpful? Give feedback.
-
|
Yeah, it doesn't sound like this is going to be a killer change |
Beta Was this translation helpful? Give feedback.
-
|
For small dict-keys, it may well be faster to perform a linear scan over the keys. It is also a lot simpler than fancy SSE stuff. |
Beta Was this translation helpful? Give feedback.
-
|
One other possibility is to use bi-directional layout, as we do for the quickened code (and values array in python/cpython#31191). Now: With bi-directional layout: This removes the overhead of computing the offset of |
Beta Was this translation helpful? Give feedback.
-
Beta Was this translation helpful? Give feedback.
-
|
Since Before After |
Beta Was this translation helpful? Give feedback.
-
|
I don't think it makes any difference because dictkeys object is 16byte aligned and cache line is 64byte. |
Beta Was this translation helpful? Give feedback.
-
|
But wouldn’t that leave two 4-byte holes? |
Beta Was this translation helpful? Give feedback.
-
|
Would you use "Write a reply" textarea instead of "Write a comment"? |
Beta Was this translation helpful? Give feedback.
-
|
Next time. :-) Anyway looks like he edited the comment. |
Beta Was this translation helpful? Give feedback.
-
|
I implemented Swisstable: methane/cpython#41
Swisstable hash reduces conflict. But it makes one more lookup layer. Swisstable hash is cache friendly, but our compact dict is cache friendly too. I suspend trying Swisstable. If someone interested in Swisstable, please try to change set, instead of dict.
|
Beta Was this translation helpful? Give feedback.
-
|
Thanks for trying that out. |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
I was reading about Rust's new hash table the other day, and found some articles about the hash table it derives from. Might be a good idea to look into this and incorporate some of the ideas, given how hot hash tables are in Python:
Beta Was this translation helpful? Give feedback.
All reactions