would PLDHashTable/nsTHashtable be faster with an Add API whose caller promises there's no existing entry?

NEW
Unassigned

Status

()

enhancement
P3
normal
2 years ago
Last year

People

(Reporter: dbaron, Unassigned)

Tracking

({perf})

Trunk
Points:
---

Firefox Tracking Flags

(firefox55 affected)

Details

Right now PLDHashTable::Add and nsTHashTable::PutEntry assume that hashtable addition operations need to search for an existing entry and return it if there is an existing entry.

Some callers don't need this guarantee; they can guarantee that there's no existing matching entry in the table (e.g., if objects add themselves to the hash in their constructor).

If there were a separate API for this type of Add (probably with debug-only assertions), SearchTable could be faster for this type of add since it wouldn't need to skip over removed entries (see the "firstRemoved" variable) to search for existing entries before eventually returning firstRemoved if no existing entry was found.

It may be worth investigating whether this would be a worthwhile performance improvement, and, if so, doing it.
(In reply to David Baron :dbaron: ⌚️UTC-7 from comment #0)
> If there were a separate API for this type of Add (probably with debug-only
> assertions), SearchTable could be faster for this type of add since it
> wouldn't need to skip over removed entries (see the "firstRemoved" variable)
> to search for existing entries before eventually returning firstRemoved if
> no existing entry was found.

khuey pointed out to me (when I mentioned this to him) that there's an even bigger win:  that we could skip the (MatchEntryKeyhash(entry, aKeyHash) && matchEntry(entry, aKey)) test too (by just assuming it fails)!
Oh, and also worth noting since I apparently didn't mention it in comment 0 despite intending to:  if we did this, this API should have DEBUG-only assertions to verify that the caller's promise is correct.
Priority: -- → P3
The described optimization is exactly what PLDHashTable::FindFreeEntry() does. It's used when rehashing the table.

mozilla::Hash{Set,Map} expose this functionality via putNewInfallible().
Actually... PLDHashTable::FindFreeEntry() checks for free entries. mozilla::HashTable::putNewInfallible() checks for non-live entries, which means it will work when a table has removed entries, which would be necessary for this function to be reasonable. (The 3rd point in the comment above FindFreeEntry -- "assume that no entries have been removed from the current table structure" -- could then be removed.)
You need to log in before you can comment on or make changes to this bug.