bmcdonald3 / chapel Goto Github PK
View Code? Open in Web Editor NEWThis project forked from chapel-lang/chapel
a Productive Parallel Programming Language
Home Page: https://chapel-lang.org
License: Other
This project forked from chapel-lang/chapel
a Productive Parallel Programming Language
Home Page: https://chapel-lang.org
License: Other
Reading:
Writing:
General:
C_HDF5
moduleOur hash table probing method was switched from using regular quadratic probing to triangular numbers probing. A property of quadratic probing is the table must not exceed 50% capacity to guarantee finding a slot, but triangular numbers probing guarantees finding a slot if there is an open one, regardless of capacity (it checks each slot exactly once). This means that we can give more flexibility to users of map
by exposing a maxLoadFactor
(to be consistent with other languages) to allow them to decide when is best for their map
to grow.
var m = new map(int, int);
m.setMaxLoadCapacity(0.75);
maxLoadCapacity
is set through a setter method and takes a fraction that corresponds to the % full that the table can reach before resizing
var m = new map(int, int);
m.setMaxLoadCapacity(2);
Identical to proposal 1, but the maxLoadCapacity
is set by an integer whose reciprocal (1/val) is the max capacity (i.e., passing 2 means your max capacity is 1/2 or 50%)
var m = new map(int, int, maxLoadCapacity=.75);
maxLoadCapacity
is a keyword argument for the map
constructor
max_load_factor()
which allows setting how full the map will be before resizingmax_load_factor = 2
= 1/2, so map can be 50% full before resize; max_load_factor = 3
= 1/3 so map can be 33% full before resize)Usage:
std::unordered_map<std::int, std::int> m;
m.max_load_factor(2); // map can now be up to 50% full (numslots/loadfactor)
(thanks for pointing this one out Andrew)
Hashtable
constructor can take an initial capacity and a loadFactor
loadFactor
in Java is a fraction, rather than an integer (e.g., loadFactor = .75
means table can be 75% full)Usage:
Hashtable<int, int> m = new Hashtable<int, int>(10, 0.50); // initial capacity 10, table can be up to 50% full
loadFactor
, but instead allows setting of an initial capacity, which may have the same effect in many casesmap
nowMotivated by: chapel-lang#18427 and https://github.com/Cray/chapel-private/issues/2536
PR with proposal 1: chapel-lang#18523
C++ load factor: https://en.cppreference.com/w/cpp/container/unordered_map/max_load_factor
Java hashtable: https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html
Rust hashmap: https://doc.rust-lang.org/std/collections/struct.HashMap.html
Currently, the Chapel Map uses the default hash function in all scenarios, so even if the user wanted to use their own hash function, they are not able to. Many languages have hash table implementations that allow users to provide their own hash functions, and I also have observed performance improvements in certain instances with this change. I am proposing that we add this functionality to the map
API.
hash
method provided on the key type proc int.hash() {
return calculateHash();
}
var myMap:map(int,string);
// will use the above hash since it is defined on int, even though not explicitly stated by user
myMap[1] = "hello";
map
to accept a hash record or first class functionproc doHash(arg, seed:uint): uint {
return calculateHash();
}
var myMap2: map(int, string, doHash);
myMap2[1] = "hello 2";
hash
method provided on the key type:hash
method now has special meaning, it might no longer be used in applications for other purposes, not very intuitive; no one would know how to use it unless they had seen the documentationmap
to accept a hash record or first class function:I ran into this while running performance tests on the k-nucleotide benchmark, where the C++ implementation that our implementation is based on allows a user to pass a hash function. The k-nucleotide implementation does the hashing with a required hash function before using the map, so we are double hashing in that case. If you want more info on the result of using the built in/user defined hash, see: https://github.com/Cray/chapel-private/issues/2365
C++ implementation usage:
struct T {
... other stuff ...
struct hash{
uint64_t operator()(const T& t)const{ return t.data; }
};
};
cc_hash_table<T,unsigned,T::hash> myMap;
PREPARE FOR ARKOUDA MEETING ON WEDNESDAY:
Second batch:
make
for ArrowMap()
Short term
Sort of short term
Exposing a maxLoadFactor
(name chosen to be consistent with other languages, open for discussion) to allow users to decide when is best for their map
to grow can help improve both performance and memory in specific cases. Choosing a higher load factor can help save memory on unnecessary map allocations if memory is a concern. Choosing a lower load factor can help improve performance because it can reduce the number of slots probed when there are collisions.
var m = new map(int, int);
m.setMaxLoadCapacity(0.75);
var m = new map(int, int);
m.setMaxLoadCapacity(2);
var m = new map(int, int, maxLoadCapacity=.75);
map
std::unordered_map<std::int, std::int> m;
m.max_load_factor(2); // map can now be up to 50% full (numslots/loadfactor)
Hashtable<int, int> m = new Hashtable<int, int>(10, 0.50); // initial capacity 10, table can be up to 50% full
loadFactor
, but instead allows setting of an initial capacity, which may have the same effect in many casesmap
nowMotivated by: chapel-lang#18427 and https://github.com/Cray/chapel-private/issues/2536
PR with proposal 1: chapel-lang#18523
C++ load factor: https://en.cppreference.com/w/cpp/container/unordered_map/max_load_factor
Java hashtable: https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html
Rust hashmap: https://doc.rust-lang.org/std/collections/struct.HashMap.html
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.