On 11.08.2010 00:32, chromatic wrote:
On Tuesday 10 August 2010 at 14:26, luben karavelov wrote:
It helps with hash expansion because when you double the size of bucket
store you have to move arround only a half of the keys, and their new
locations is guarantted to be free
I'm not sure I believe that's the case with our implementation. Besides that,
I was under the impression (see The Practice of Programming) that picking a
prime number for the array size produces a better distribution of keys in
buckets. The argument is that the lack of a common factor between the array
size, the hash seed, and likely hash values produces a better distribution.
Maybe we need some sort of intrusive benchmark with likely hash values that
shows the statistical goodness or badness of our implementation.
-- c
Yes, prime number as a hash table size will be better for hash
distribution but it will make hash resizing cost more. On other hand, it
will permit to get non-constant grow factor that will make resizing less
often and the hash table will be more space efficient. I nave taken a
look on some hash table implementations and it is common to use a vector
of prime numbers as first hash table sizes.
As a part of the hash-cleanup effort, I have attached a patch that moves
the checks for constant keys/values out of the src/hash.c in
corresponding PMCs. All test pass. The only functional difference is
that if hash table is constant and is indexed by PMC I also check that
key PMC is constant.
luben
Index: src/hash.c
===================================================================
--- src/hash.c (revision 48417)
+++ src/hash.c (working copy)
@@ -1027,8 +1027,6 @@
Hash_key_type hkey_type, hash_comp_fn compare, hash_hash_key_fn keyhash)>
Creates and initializes a hash. Function pointers determine its behaviors.
-The container passed in is the address of the hash PMC that is using it. The
-hash and the PMC point to each other.
Memory from this function must be freed.
@@ -1059,7 +1057,6 @@
hash->seed = interp->hash_seed;
hash->mask = INITIAL_BUCKETS - 1;
hash->entries = 0;
- hash->container = PMCNULL;
bp = (HashBucket *)((char *)alloc + sizeof (Hash));
hash->free_list = NULL;
@@ -1367,21 +1364,6 @@
HashBucket *bucket = hash->bucket_indices[hashval & hash->mask];
const hash_comp_fn compare = hash->compare;
- /* When the hash is constant, check that the key and value are also
- * constant. */
- if (!PMC_IS_NULL(hash->container)
- && PObj_constant_TEST(hash->container)) {
- if (hash->key_type == Hash_key_type_STRING
- && !PObj_constant_TEST((PObj *)key))
- Parrot_ex_throw_from_c_args(interp, NULL,
EXCEPTION_INVALID_OPERATION,
- "Used non-constant key in constant hash.");
- if (((hash->entry_type == enum_type_PMC)
- || (hash->entry_type == enum_type_STRING))
- && !PObj_constant_TEST((PObj *)value))
- Parrot_ex_throw_from_c_args(interp, NULL,
EXCEPTION_INVALID_OPERATION,
- "Used non-constant value in constant hash.");
- }
-
/* See if we have an existing value for this key */
while (bucket) {
/* store hash_val or not */
Index: src/pmc/hash.pmc
===================================================================
--- src/pmc/hash.pmc (revision 48417)
+++ src/pmc/hash.pmc (working copy)
@@ -78,7 +78,6 @@
(Parrot_Hash_attributes *) PMC_data(SELF);
attr->hash = parrot_new_hash(INTERP);
- attr->hash->container = SELF;
PObj_custom_mark_destroy_SETALL(SELF);
}
@@ -91,7 +90,6 @@
Hash_key_type_STRING,
STRING_compare,
(hash_hash_key_fn)key_hash_STRING);
- attr->hash->container = SELF;
PObj_custom_mark_destroy_SETALL(SELF);
}
@@ -150,7 +148,6 @@
Hash * const new_hash = (Hash *)ptr;
PARROT_HASH(SELF)->hash = new_hash;
- new_hash->container = SELF;
if (old_hash)
parrot_hash_destroy(INTERP, old_hash);
@@ -206,7 +203,6 @@
PARROT_HASH(SELF)->hash = new_hash;
- new_hash->container = SELF;
if (old_hash)
parrot_hash_destroy(INTERP, old_hash);
@@ -269,7 +265,6 @@
}
PARROT_HASH(SELF)->hash = new_hash;
- new_hash->container = SELF;
if (old_hash)
parrot_hash_destroy(INTERP, old_hash);
@@ -456,6 +451,12 @@
PMC *box;
HashBucket *b;
+ if (PObj_constant_TEST(SELF)
+ && !PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC key in constant hash.");
+
if (!nextkey) {
parrot_hash_put(INTERP, hash, keystr,
hash_value_from_int(INTERP, hash, value));
@@ -491,6 +492,13 @@
VTABLE void set_integer_keyed_str(STRING *key, INTVAL value) {
Hash * const hash = (Hash *)SELF.get_pointer();
+
+ if (PObj_constant_TEST(SELF)
+ && !PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant key in constant hash.");
+
parrot_hash_put(INTERP, hash, hash_key_from_string(INTERP, hash, key),
hash_value_from_int(INTERP, hash, value));
}
@@ -636,6 +644,17 @@
PMC *box;
HashBucket *b;
+ if (PObj_constant_TEST(SELF)){
+ if (!PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC key in constant hash.");
+ if (!PObj_constant_TEST((PObj *)value))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING value in constant hash.");
+ }
+
if (!nextkey) {
parrot_hash_put(INTERP, hash, keystr,
hash_value_from_string(INTERP, hash, value));
@@ -665,6 +684,18 @@
VTABLE void set_string_keyed_str(STRING *key, STRING *value) {
Hash * const hash = (Hash *)SELF.get_pointer();
+
+ if (PObj_constant_TEST(SELF)){
+ if (!PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING key in constant hash.");
+ if (!PObj_constant_TEST((PObj *)value))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING value in constant hash.");
+ }
+
parrot_hash_put(INTERP, hash,
hash_key_from_string(INTERP, hash, key),
hash_value_from_string(INTERP, hash, value));
@@ -672,6 +703,13 @@
VTABLE void set_string_keyed_int(INTVAL key, STRING *value) {
Hash * const hash = (Hash *)SELF.get_pointer();
+
+ if ((PObj_constant_TEST(SELF))
+ && (!PObj_constant_TEST((PObj *)value)))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING value in constant hash.");
+
parrot_hash_put(INTERP, hash,
hash_key_from_int(INTERP, hash, key),
hash_value_from_string(INTERP, hash, value));
@@ -762,6 +800,11 @@
PMC *box = PMCNULL;
HashBucket *b;
+ if (PObj_constant_TEST(SELF)
+ && !PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC key in constant hash.");
if (!nextkey) {
PMC * const val = get_number_pmc(INTERP, value);
@@ -793,6 +836,12 @@
VTABLE void set_number_keyed_str(STRING *key, FLOATVAL value) {
PMC * const val = get_number_pmc(INTERP, value);
+ if (PObj_constant_TEST(SELF)
+ && !PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING key in constant hash.");
+
parrot_hash_put(INTERP, (Hash *)SELF.get_pointer(), key, val);
}
@@ -811,6 +860,18 @@
PMC *box;
HashBucket *b;
+ if (PObj_constant_TEST(SELF)) {
+ if (!PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC key in constant hash.");
+
+ if (!PObj_constant_TEST((PObj *)value))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC value in constant hash.");
+ }
+
if (!nextkey) {
parrot_hash_put(INTERP, hash, keystr, value);
return;
@@ -842,6 +903,19 @@
VTABLE void set_pmc_keyed_str(STRING *key, PMC *value) {
Hash * const hash = (Hash *)SELF.get_pointer();
+
+ if (PObj_constant_TEST(SELF)) {
+ if (!PObj_constant_TEST((PObj *)key))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING key in constant hash.");
+
+ if (!PObj_constant_TEST((PObj *)value))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING value in constant hash.");
+ }
+
parrot_hash_put(INTERP, hash, hash_key_from_string(INTERP, hash, key),
hash_value_from_pmc(INTERP, hash, value));
}
@@ -1163,7 +1237,6 @@
PARROT_ASSERT((INTVAL)hash->key_type == k_type);
PARROT_ASSERT(hash->entry_type == v_type);
- hash->container = SELF;
hash->entries = elems;
}
}
Index: src/dynpmc/dynlexpad.pmc
===================================================================
--- src/dynpmc/dynlexpad.pmc (revision 48417)
+++ src/dynpmc/dynlexpad.pmc (working copy)
@@ -52,7 +52,6 @@
hash = parrot_new_hash(INTERP);
attrs->hash = hash;
- hash->container = SELF;
PObj_custom_mark_destroy_SETALL(SELF);
}
@@ -166,6 +165,17 @@
VTABLE void set_pmc_keyed_str(STRING* name, PMC* value) {
PMC *std_pad = PARROT_DYNLEXPAD(SELF)->init;
+ if (PObj_constant_TEST(SELF)) {
+ if (!PObj_constant_TEST((PObj *)name))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant STRING key in constant hash.");
+ if (!PObj_constant_TEST((PObj *)value))
+ Parrot_ex_throw_from_c_args(INTERP, NULL,
+ EXCEPTION_INVALID_OPERATION,
+ "Used non-constant PMC value in constant hash.");
+ }
+
if (std_pad && VTABLE_exists_keyed_str(INTERP, std_pad, name))
VTABLE_set_pmc_keyed_str(INTERP, std_pad, name, value);
Index: include/parrot/hash.h
===================================================================
--- include/parrot/hash.h (revision 48417)
+++ include/parrot/hash.h (working copy)
@@ -62,9 +62,6 @@
/* alloced - 1 */
UINTVAL mask;
- /* The owner PMC */
- PMC *container;
-
/* The type of key object this hash uses */
Hash_key_type key_type;
_______________________________________________
http://lists.parrot.org/mailman/listinfo/parrot-dev
