Closed Bug 1400193 Opened 2 years ago Closed 2 years ago

Shrink PLDHashTable

Categories

(Core :: XPCOM, enhancement)

56 Branch
enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla58
Tracking Status
firefox58 --- fixed

People

(Reporter: njn, Assigned: njn)

Details

Attachments

(2 files, 1 obsolete file)

No description provided.
The current code replaces one PLDHashTable's mGeneration with another. If the
two generation values happen to be equal, it will look as though the storage
hasn't changed when really it has.

The fix is to use EntryStore::Set() to update mEntryStore, which increments
mGeneration appropriately.
Attachment #8908542 - Flags: review?(nfroyd)
Assignee: nobody → n.nethercote
Status: NEW → ASSIGNED
Attached patch (part 2) - Shrink PLDHashTable (obsolete) — Splinter Review
This patch reduces sizeof(PLDHashTable) as follows.

- 64-bit: from 40 bytes to 32
- 32-bit: from 28 bytes to 24

It does this by doing the following.

- It moves mGeneration from EntryStore to PLDHashTable, to avoid 4 bytes of
  padding on 64-bit. This requires tweaking EntryStore::Set() as explained in a
  comment.

- It shrinks mEntrySize from uint32_t to uint16_t, to cut 2 bytes of data and
  another 2 bytes of padding on both 32-bit and 64-bit.

It also changes mHashShift from int16_t to uint16_t, which is more sensible.
And it reorders the fields so the word-sized ones are at the start, which makes
it easier to imagine the memory layout.
Attachment #8908544 - Flags: review?(nfroyd)
Comment on attachment 8908542 [details] [diff] [review]
(part 1) - Fix subtle bug in PLDHashTable's move constructor

Review of attachment 8908542 [details] [diff] [review]:
-----------------------------------------------------------------

Good idea.

::: xpcom/ds/PLDHashTable.cpp
@@ +230,5 @@
>  
>    // Move non-const pieces over.
> +  mHashShift = aOther.mHashShift;
> +  mEntryCount = aOther.mEntryCount;
> +  mRemovedCount = aOther.mRemovedCount;

I kind of like using Move() on these, even though move construction is trivial, because it prevents things from going wrong if the types of these happen to change in non-trivial ways.  WDYT?
Attachment #8908542 - Flags: review?(nfroyd) → review+
Comment on attachment 8908544 [details] [diff] [review]
(part 2) - Shrink PLDHashTable

Review of attachment 8908544 [details] [diff] [review]:
-----------------------------------------------------------------

This is a good thing, thank you.
Attachment #8908544 - Flags: review?(nfroyd) → review+
FWIW, here's some thoughts on the possibility of shrinking this further. (All this is inspired by bug 1400100, where ImageValue size is notable for gmail, and ImageValue contains a hashtable.)

- mOps: difficult to change.

- mHashShift: could shrink to uint8_t, saving 1 byte.

- mEntrySize: could shrink to uint8_t, saving 1 byte. Entries larger than 255 are ridiculously large and should be replaced with pointers, anyway. (More aggressive would be to move it into PLDHashTableOps, saving another byte.)

- mEntryCount: difficult to change, because kMaxCapacity is (1 << 26).

- mRemovedCount: difficult to change, because it's maximum value is 1/4 of mEntryCount's, i.e. (1 << 24).

- mEntryStore: difficult to change.

- mGeneration: could be reduced to uint16_t, saving 2 bytes. (More aggressive would be to reduce it to uint8_t and then xor it with mEntryStore in Generation(), saving another byte.)

Combining the non-aggressive options, we could save another 4 bytes. On 64-bit sizeof(PLDHashTable) would stay as 32 bytes, but on 32-bit it would drop from 24 to 20. I'll give that a try on Monday.
Updated version that shrinks it to 20 bytes on 32-bit.
Attachment #8909188 - Flags: review?(nfroyd)
Attachment #8908544 - Attachment is obsolete: true
Comment on attachment 8909188 [details] [diff] [review]
(part 2) - Shrink PLDHashTable

Review of attachment 8909188 [details] [diff] [review]:
-----------------------------------------------------------------

This makes me a little more nervous, but I guess we have ways of dealing with this, see below.

::: xpcom/ds/PLDHashTable.cpp
@@ +209,5 @@
>    , mChecker()
>  #endif
>  {
> +  // An entry size greater than 0xff is unlikely, but let's check anyway.
> +  MOZ_ASSERT(aEntrySize == uint32_t(mEntrySize));

WDYT about making this MOZ_DIAGNOSTIC_ASSERT, or even MOZ_RELEASE_ASSERT?  I think it would be really unlikely for something to make it into the tree and never exercise a hash table creation codepath, but if it did, somehow, things would go very badly at runtime, and it'd be nice to have a little more checking.

Alternatively, could we have a setup like:

public:
  // Assuming the compiler would appropriately type_check the type of the
  // EntrySize parameter and complain about things not fitting...otherwise
  // we might have to resort to a static_assert.
  template<uint8_t EntrySize>
  PLDHashTable(const PLDHashTableOps* aOps, uint32_t aLength)
    : PLDHashTable(aOps, EntrySize, aLength)
  {}

private:
  PLDHashTable(const PLDHashTableOps*, uint8_t aEntrySize, uint32_t aLength);

to force people at compile time to honor the size requirement?  I guess it's possible we wouldn't know the size of things at compile time, but that seems kind of unlikely.
Attachment #8909188 - Flags: review?(nfroyd) → review+
MOZ_RELEASE_ASSERT is good, I've done that. I also had to modify the gtest. Try looks good:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=99e3c1645f31d6e0a2b941205349a3d62ccade0d
https://hg.mozilla.org/mozilla-central/rev/bd2852c72cae
https://hg.mozilla.org/mozilla-central/rev/4dce29de45e3
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla58
You need to log in before you can comment on or make changes to this bug.