Hashtable: specialized equality tests

RESOLVED WONTFIX

Status

()

Core
JavaScript Engine
--
enhancement
RESOLVED WONTFIX
13 years ago
6 years ago

People

(Reporter: Igor Bukanov, Unassigned)

Tracking

Trunk
Points:
---
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

13 years ago
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.
(Reporter)

Comment 1

13 years ago
Created attachment 206562 [details] [diff] [review]
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.
Assignee: general → igor.bukanov
Status: NEW → ASSIGNED

Updated

13 years ago
Flags: testcase-
(Reporter)

Comment 2

11 years ago
I am not working on the bug right now.
Assignee: igor → general
Status: ASSIGNED → NEW
JS_HashTable is gone, at least from js/src.
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.