321159 - Hashtable: specialized equality tests

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, enhancement)

Description

[Igor Bukanov]

Currently hashtable API always use generic equality test provided with JS_NewHashTable. It is not possible for a hashtable client to supply a specialized key equality test during table lookups to take advantage of particular properties of the key such as type etc.

For example, consider the implementation of js_AtomizeDouble where currently JS_HashTableRawLookup calls generic comparator js_compare_atom_keys. The comparator starts with checking if both its arguments are strings which is always false in this case. In addition the generic comparator forces js_AtomizeDouble to construct pseudo double jsval just to satisfy JSHashComparator signature.

It would be nice if hashtable would provide an alternative to JS_HashTableRawLookup that takes comparator as parameter.

Comment 1

[Igor Bukanov]

Attachment: Implementation: JS_HashTableRawSearc

The patch adds 

/*
 * Search hash table for first entry with the given keyHash and for which
 * hashTester returns true.
 */
extern JS_PUBLIC_API(JSHashEntry **)
JS_HashTableRawSearch(JSHashTable *ht, JSHashNumber keyHash,
                      JSHashTester hashTester, void *hashTesterArg);


and changes to js_AtomizeDouble and js_AtomizeString to use the new method with custom equality tests. It allowed to eliminate code to construct aligned pointers for pseudo jsval.

The patch changed JS_HashTableRawAdd and JS_HashTableRawRemove not to call JS_HashTableRawLookup but rather add old hashtable entries to the head of bucket chain as it is already known that the entries are unique and would never occur on the newly constructed chain.

Another optimization is that the string hashing code use the newly added js_EqualStrings which a faster then js_CompareStrings since hashing just needs to know if strings are equal or not, not whether str1 < == > str2.

Comment 2

[Igor Bukanov]

I am not working on the bug right now.

Comment 3

[Luke Wagner [:luke]]

JS_HashTable is gone, at least from js/src.