author Nicholas Nethercote <>
Fri, 10 Aug 2018 18:00:29 +1000
changeset 431180 ad30dc53e38ec41adc99f81fd8a5102ecf7775fd
parent 1 9b2a99adc05e53cd4010de512f50118594756650
permissions -rw-r--r--
Bug 1481998 - Make mozilla::Hash{Map,Set}'s entry storage allocation lazy. r=luke,sfink Entry storage allocation now occurs on the first lookupForAdd()/put()/putNew(). This removes the need for init() and initialized(), and matches how PLDHashTable/nsTHashtable work. It also removes the need for init() functions in a lot of types that are built on top of mozilla::Hash{Map,Set}. Pros: - No need for init() calls and subsequent checks. - No memory allocated for empty tables, which are not that uncommon. Cons: - An extra branch in lookup() and lookupForAdd(), but not in put()/putNew(), because the existing checkOverloaded() can handle it. Specifics: - Construction now can take a length parameter. - init() is removed. Explicit length-setting, when necessary, now occurs in the constructors. - initialized() is removed. - capacity() now returns zero when the entry storage is absent. - lookupForAdd() is no longer `const`, because it can instantiate the storage, which requires modifications. - lookupForAdd() can now return an invalid AddPtr in two cases: - old: hashing failure (due to OOM in the hasher) - new: OOM while instantiating entry storage The existing failure handling paths for the old case work for the new case. - clear(), finish(), and clearAndShrink() are replaced by clear(), compact(), and reserve(). The old compactIfUnderloaded() is also removed. - Capacity computation code is now in its own functions, bestCapacity() and hashShift(). setTableSizeLog2() is removed. - uint32_t is used throughout for capacities, instead of size_t, for consistency with other similar values. - changeTableSize() now takes a capacity instead of a deltaLog2, and it can now handle !mTable. Measurements: - Total source code size is reduced by over 900 lines. Also, lots of existing lines got shorter (i.e. two checks were reduced to one). - Executable size barely changed, down by 2 KiB on Linux64. The extra branches are compensated for by the lack of init() calls. - Speed changed negligibly. The instruction count for Bench_Cpp_MozHash increased from 2.84 billion to 2.89 billion but any execution time change was well below noise.

Please be apprised of the following Legal Notices:

A) The U.S. District Court for the Eastern District of Virginia has
ruled that the Netscape Navigator code does not infringe Wang's U.S.
Patent No. 4,751,669 ("the '669 Patent") because: 1) HTML is not
Videotex as defined by the '669 patent; 2) web servers are not central
suppliers; and 3) Navigator does not "connect," as defined by the '669
Patent, to web servers on the Internet. Wang may appeal this decision to
the Federal Circuit. Wang contended that its Patent disclosing a
"Videotex" system, is infringed by the following functionality in the
Netscape Navigator code: 1) the animated logo and status line indicators
--See Claims 1,8 and 9; 2) the "File Save As" function --See Claims
23-27; 3) Bookmarks and Rename Bookmarks in the Properties window --See
Claims 20-22; 4) storing HTML, GIF, and JPEG files and adding filename
extensions --See Claim 38

B) Intermind owns pending U.S. patent applications on communications
systems which employ metadata ("channel objects") to define a control
structure for information transfer. The Netscape code does not infringe
as released; however, modifications which utilize channel objects as
described by Intermind should be considered carefully. The following is
a statement from Intermind: "Intermind's claims fundamentally involve
the use of a control structure to automate communications. ...The
essence of Intermind's top claim is that two devices sender and receiver
have persistent storage, communicate over a network, and exchange a
control structure including metadata which describes: 1) what
information is to be updated, 2) when to update this information, and 3)
how to transfer the updated information. In addition, at least the
receiving device must be able to process the metadata in order to
perform the update determination and transfer. Any digital
communications system which incorporates all of these elements will be
covered by Intermind's patents." See

C) Stac, Inc., and its licensing agent Hi/fn, own several patents which
disclose data compression methods implementing an LZS compression
algorithm, including U.S. Patent Nos. 4,701,745 and 5,016, 009 ("the
Stac Patents"). The Netscape Communicator code does not perform
compression. If you modify the Netscape source code to perform
compression, please take notice of the Stac Patents.

D) Netscape Communications Corporation ("Netscape") does not guarantee
that any source code or executable code available from the
domain is Year 2000 compliant.