Closed Bug 1662345 Opened 5 years ago Closed 4 years ago

PLDHashTable store can waste memory due to slop

Categories

(Core :: XPCOM, enhancement)

Product:
Core
Component:
XPCOM
Type:
enhancement

Tracking

()

Status:
RESOLVED INVALID

People

(Reporter: pbone, Assigned: pbone)

References

(Blocks 1 open bug)

Details

(Whiteboard: [MemShrink][clownshoes])

Attachments

(1 file, 5 obsolete files)

Alternative patch for non power-of-2 tables
19.30 KB, patch
Details | Diff | Splinter Review

PLDHashTable has a power-of-two capacity, however in that memory it allocates storage for it's data plus 32bit hashes. This can result in slop for example if an entry is a 64bit value and 32bit hash, It requires N*48bits memory, which jemalloc will often round up to the nearest power-of-two (when it's more than 512bytes).

Maybe jemalloc could be more tolerant, or this could allocate storage for the entries separate from the hashes: this costs an extra allocation and only helps when the entries have a power-of-two size.

Here's the DMD record for a process that loads example.com

Live {
126 blocks in heap block record 4 of 13,854
129,024 bytes (96,768 requested / 32,256 slop)
Individual block sizes: 1,024 x 126
1.31% of the heap (7.20% cumulative)
Allocated at {
#01: replace_calloc(unsigned long, unsigned long) (/mnt/dev/moz/memshrink/memory/replace/dmd/DMD.cpp:1105)
#02: PLDHashTable::Add(void const*, std::nothrow_t const&) (/mnt/dev/moz/memshrink/objdir-dmd/dist/include/PLDHashTable.h:363)
#03: nsAtomTable::RegisterStaticAtoms(nsStaticAtom const*, unsigned long) (/mnt/dev/moz/memshrink/xpcom/ds/PLDHashTable.cpp:567)
#04: NS_InitAtomTable() (/mnt/dev/moz/memshrink/xpcom/ds/nsAtomTable.cpp:470)
#05: NS_InitXPCOM (/mnt/dev/moz/memshrink/xpcom/build/XPCOMInit.cpp:272)
#06: XRE_InitEmbedding2(nsIFile*, nsIFile*, nsIDirectoryServiceProvider*) (/mnt/dev/moz/memshrink/toolkit/xre/nsEmbedFunctions.cpp:198)
#07: mozilla::ipc::ScopedXREEmbed::Start() (/mnt/dev/moz/memshrink/ipc/glue/ScopedXREEmbed.cpp:83)
#08: mozilla::dom::ContentProcess::Init(int, char**) (/mnt/dev/moz/memshrink/dom/ipc/ContentProcess.cpp:201)
}
}

Nice catch.

Note that mozilla::HashTable has the same issue. When we switched HashTable over to a PLDHashTable-like storage scheme, we got significant JS content memory wins (~1% or so) -- but I don't know if those numbers really accounted for the internal slop or not. I guess before, a 64-bit value and 32-bit hash would have been 128 bits due to internal padding in the entries. So depending on the different values of N, N16 bytes (128bits) vs. N12 bytes (96 bits) could be a significant savings in actual requested memory from jemalloc.

I think we have generally assumed that contiguous key-value storage means that we incur the minimum number of cache misses...but with the move to logically separated key storage and value storage in the same allocation, we have set things up so that we (presumably) take two cache misses, as the key and value are now widely separated from each other. So maybe if we moved to actually different allocations for the key storage and value storage, the cache misses would stay the same but we'd do a better job of sizing the storage better?

Also, I presume that those blocks are coming from nsAtomSubTable, of which we have 128 instances...but DMD is telling us that 126 of them have the same size (which is the initial size)? That sounds like our hash function is doing a terrible job of distributing entries to the sub tables, at the very least, and we should consider trying to fix that....

(In reply to Nathan Froyd [:froydnj] from comment #1)

Nice catch.

Thanks.

Also, I presume that those blocks are coming from nsAtomSubTable, of which we have 128 instances...but DMD is telling us that 126 of them have the same size (which is the initial size)? That sounds like our hash function is doing a terrible job of distributing entries to the sub tables, at the very least, and we should consider trying to fix that....

I checked this. There's nothing obviously wrong with the hash distribution. The sub tables have between 9 and 29 entries, most of them static. 122 of them contain 64 entries and the others contain 32 entries. 32 is the default (4096 / 128). I assume we're seeing the ~122 subtables that have a capacity of 64 in this DMD record, and some other DMD record is showing the remaining subtables - since the allocation path is different (at least different enough, given that PLDHashTables don't allocate storage until the first entry is added (that's how I read it)

Maybe they could be distributed more evenly, 9-29 is a big-ish range, I'm not sure what's within "normal". Some tables, at one point crossed over whatever load factor they need to grow to 64 bytes long and others didn't. It seems okay to me but this is really the first time I've looked at this code.

I'm looking more deeply. I'm trying two different things and will compare them:

  1. Allocate separate storage for values and hashes. This will help with this case, and with any case when each value's size is a power-of-two. But it could still lead to swap if a value is not a power-of-two.

  2. Let the hash table have a non-power-of-two size and choose its size so that it fits nicely within a power-of-two amount of bytes. This means using division/mod to calculate an array index from a hash. Depending on the processor this could be 5-40 cycles longer than a shift, that could be prohibitivey expensive or completely unmeasurable, depending on what else is going on. But it has the benefit of utilising memory efficiently.

Assignee: nobody → pbone
Status: NEW → ASSIGNED

Adding this method makes it clearer what code is doing when it checks that
the storage has been allocated.

Depends on D89565

Allocate entries and hashes separately to avoid a clownshoes allocation.
When the entries are 64 bit (eg pointers) but the hashes are 32bit
the size of the storage is not a power of two which can cause wasted memory
within jemalloc. This will only use a power-of-two amount of storage when
the entries in the table are a power-of-two size themselves.

Depends on D89566

(In reply to Paul Bone [:pbone] from comment #3)

I'm looking more deeply. I'm trying two different things and will compare them:

  1. Allocate separate storage for values and hashes. This will help with this case, and with any case when each value's size is a power-of-two. But it could still lead to swap if a value is not a power-of-two.

  2. Let the hash table have a non-power-of-two size and choose its size so that it fits nicely within a power-of-two amount of bytes. This means using division/mod to calculate an array index from a hash. Depending on the processor this could be 5-40 cycles longer than a shift, that could be prohibitively expensive or completely unmeasurable, depending on what else is going on. But it has the benefit of utilising memory efficiently.

Hi froydnj, Do you know if idea #2 here could be worth the effort?

I checked, a modern fancy desktop CPU can do a divide in less than 12 cycles, but an older CPU could be 40cycles. IMHO this is in the "we won't know unless we test" ballpark. Also we could avoid divide/mod if we did something else to extract some bits from the hash but not distributed it evenly across the table, like:

index = hash >> shift;
if (index >= capacity) {
    // index will be no more than capacity*2
    index -= capacity/2;
}

My guess is most data would be power-of-two sized anyway so this might be skipped most of the time.

Thanks.

Flags: needinfo?(nfroyd)

(In reply to Paul Bone [:pbone] from comment #9)

(In reply to Paul Bone [:pbone] from comment #3)

I'm looking more deeply. I'm trying two different things and will compare them:

  1. Allocate separate storage for values and hashes. This will help with this case, and with any case when each value's size is a power-of-two. But it could still lead to swap if a value is not a power-of-two.

  2. Let the hash table have a non-power-of-two size and choose its size so that it fits nicely within a power-of-two amount of bytes. This means using division/mod to calculate an array index from a hash. Depending on the processor this could be 5-40 cycles longer than a shift, that could be prohibitively expensive or completely unmeasurable, depending on what else is going on. But it has the benefit of utilising memory efficiently.

Hi froydnj, Do you know if idea #2 here could be worth the effort?

I don't have any sense of how much option 2 would save compared to option 1 or how expensive it would be compared to what we have now. My suspicion is that the hash table performance is essentially dominated by cache misses and so the division would be somewhat lost in the noise, but I don't have a strong justification for that. Is that "fancy desktop CPU" you refer to to x86-64 only, or does it also take aarch64 into account?

Flags: needinfo?(nfroyd)

x86-64 only, I didn't check ARM/aarch64.

(In reply to Paul Bone [:pbone] from comment #11)

x86-64 only, I didn't check ARM/aarch64.

A quick check told me that:
ARM: division isn't always provided by the hardware, gcc & clang call some external function. mod certainly isn't provided by the hardware.
aarch64: division is provided, mod isn't but is usually compiled as a division and subtract. It's unclear how many cycles division would take (I didn't search for long enough).

Using the other method both ARM and aarch64 compile the conditional part as what I think is a conditional subtraction (I'm reading godbolt output but I haven't learnt ARM/aarch64).

I'll probably test the shift and conditional-subtract method, and may test the division/mod method. Who knows, it could all be masked by memory accesses. Has anybody tested this before, do we have microbenchmarks? I will mainly use browser benchmarks but microbenchmarks will help us find signal in noise.

AFAIK every high-speed hash table implementation out there uses power-of-two sizing. That alone makes me reluctant to move away from it.

Paul, you mentioned 48 bit entries a few times. I think you mean 96 bits? (A 32-bit hash plus a 64-bit value.)

Like Nathan, I am wary about splitting the storage in two. It's something I've considered in the past but shied away from. Doubling the number of allocations could hurt performance, and lots of hash table instances wouldn't benefit. Support both representations might be acceptable, though if there is a runtime selection path that could also hurt performance. If the selection is entirely done at compile-time, that might be ok, but I'm not sure how feasible it is.

I understand the motivation, I'm just not sure that the trade-offs are favourable.

(In reply to Nicholas Nethercote [:njn] from comment #13)

AFAIK every high-speed hash table implementation out there uses power-of-two sizing. That alone makes me reluctant to move away from it.

So there's two very good reasons why they're a power-of-2. The one that's obvious is that masks and shifts are MUCH faster than divs and mods. And not all CPUs implement mod, on ARM it's done in software. So what I'm considering is something like:

let shift be CeilLog2(capacity).

index = hash >> shift;
if (index >= capacity) {
index -= capacity;
}

it won't distribute things in the table perfectly, but it avoids mod or div and compiles to 5 instructions, the condition is implemented with a conditional move rather than a branch. It's still more expensive than a shift alone, but it might be worth while. I almost have it working and will know soon. (maybe I'm still wrong, but I'd like to find out).

The other reason these tables use a power-of-two capacity is if the 2nd hash value is odd, then the hash value and capacity have no common multiples and therefore the open-addressing is guanteed to visit every cell in the table. If the capacity is not a power-of-two then we need extra termination checks or another way to visit every cell (add 1 to the index each time it wraps around). Again, I don't know the affect yet.

The non-power-of-two table also means that we need to store the capacity rather than the shift amount. That could make things worse. We may need to store both to compute hash1 quickly.

Paul, you mentioned 48 bit entries a few times. I think you mean 96 bits? (A 32-bit hash plus a 64-bit value.)

Yes, i should have said 96bit. a 64bit value plus a 32bit hash.

Like Nathan, I am wary about splitting the storage in two. It's something I've considered in the past but shied away from. Doubling the number of allocations could hurt performance, and lots of hash table instances wouldn't benefit. Support both representations might be acceptable, though if there is a runtime selection path that could also hurt performance. If the selection is entirely done at compile-time, that might be ok, but I'm not sure how feasible it is.

I'll investigate this as an option.

I understand the motivation, I'm just not sure that the trade-offs are favourable.

Right, I don't know yet either, I'm trying to find out & find which option is best. The other thing that I'll measure is just how much total slop could be saved across all instances of these tables.

Depends on: 1666746

Comment on attachment 9174620 [details]
Bug 1662345 - pt 1. Add an IsAllocated method r=froydnj

Revision D89564 was moved to bug 1666746. Setting attachment 9174620 [details] to obsolete.

Attachment #9174620 - Attachment is obsolete: true

Comment on attachment 9174622 [details]
Bug 1662345 - pt 3. Reuse SlotForIndex to avoid duplicate code r=froydnj

Revision D89566 was moved to bug 1666746. Setting attachment 9174622 [details] to obsolete.

Attachment #9174622 - Attachment is obsolete: true

Hi njn, mccr8 & others, Here's the tests that I ran and what we may gain/loose by merging these patches.

Baseline

Using DMD and looking at a content process that has loaded example.com, there is 84KB of slop for allocations from PLDHashTable::Add and PLDHashTable::ChangeTable. That's the total amount of memory savings we could possibly make here.

 Total: 423968
 Slop: 84992  (20.0%)

Baseline performance is:

  succ_lookups  fail_lookups insert_remove       iterate         total
       39.0 ms       37.9 ms       14.0 ms       20.3 ms      111.1 ms
       39.6 ms       40.3 ms       14.2 ms       20.2 ms      114.4 ms
       40.0 ms       38.0 ms       13.1 ms       19.4 ms      110.5 ms
       39.1 ms       38.1 ms       13.0 ms       19.0 ms      109.3 ms
       38.9 ms       38.0 ms       13.0 ms       20.4 ms      110.3 ms

Avg:   39.3 ms       38.5 ms       13.5 ms       19.9 ms      111.1 ms

I tried two different ideas:

Split keys from values

Split the storage (as in these patches) to separate keys and values:

Total: 278720

Slop: 11776 (4.2%)

This saves 59KB of memory compared with baseline.

succ_lookups  fail_lookups insert_remove       iterate         total
     37.4 ms       33.1 ms       14.0 ms       20.5 ms      104.9 ms
     38.8 ms       35.4 ms       13.7 ms       19.9 ms      107.8 ms
     37.5 ms       34.3 ms       13.2 ms       20.7 ms      105.7 ms
     37.2 ms       34.1 ms       13.0 ms       20.8 ms      105.0 ms
     37.1 ms       33.9 ms       13.1 ms       20.5 ms      104.7 ms
Avg: 37.6 ms       34.2 ms       13.4 ms       20.5 ms      105.6 ms
     -4.33%       -11.17%        -0.74%        +3.2%         -5.49%

That's 5.5% faster! I think that's because some address calculations are simplified. This is a microbenchmark and it's too noisy to see within Firefox. Likewise the about:memory report shows that things have moved around, it's not an obvious win there. I also didn't measure the cost of having a second pointer within the PLDHashTable class.

Use a non power-of-two capacity so that the size in bytes can be closer to a power-of-two:

TL;DR: as we expected this is a dead-end. But I want to include it anyway. I hoped it may have a chance, that the extra computation would be something like only 2% slower, in the range where we might consider paying 2% of a performance hit for memory savings.

Depending on the size of the table, we round in different ways. Below 512 bytes we round to a power-of-two capacity, between 512B and 4KB we use a power-of-two size in bytes (or close to it). Above 4KB we round to the nearest 4KB. Index computations are done with a bitmask and conditional subtraction (they're not perfect but it's faster than anything with a division). I had to modify the tests so that the load factor remained the same making the test fair, but it was the difference between 1024 and 1025 elements.

Total: 361600 Slop: 1048 (0.3%) - Although slop is much reduced this actually increases the total memory usage (measured with DMD) since there are now different thresholds to resizing the table. On average things may be better since it can now use this memory.

  succ_lookups  fail_lookups insert_remove       iterate         total
       41.4 ms       43.7 ms       13.8 ms       20.8 ms      119.7 ms
       42.2 ms       43.8 ms       13.8 ms       21.5 ms      121.3 ms
       40.7 ms       43.7 ms       13.6 ms       20.1 ms      118.2 ms
       41.1 ms       42.9 ms       13.4 ms       20.1 ms      117.6 ms
       41.4 ms       41.7 ms       13.1 ms       20.3 ms      116.5 ms

Avg:   41.4 ms       43.2 ms       13.5 ms       20.6 ms      118.7 ms
       +5.3%        +12.2%          0%           +3.5%         +6.8%

It was also 6.6% slower.

Flags: needinfo?(n.nethercote)
Flags: needinfo?(continuation)

This is the alternative idea I tested for a hash table with a non-power-of-two size.

We have this:

Baseline

Total: 423968
Slop: 84992  (20.0%)

Split keys from values:

Total: 278720
Slop: 11776 (4.2%)

Total dropped by 145,248 bytes while slop dropped by 73,216. Why are those changes so different?

It would be interesting to see DMD output in cumulative mode to see if the total number of allocations is significantly affected by doing two allocations instead of one.

Flags: needinfo?(n.nethercote)
Flags: needinfo?(continuation)

(In reply to Nicholas Nethercote [:njn] from comment #19)

We have this:

Baseline

Total: 423968
Slop: 84992  (20.0%)

Split keys from values:

Total: 278720
Slop: 11776 (4.2%)

Total dropped by 145,248 bytes while slop dropped by 73,216. Why are those changes so different?

I assumed it was some varability in what firefox might be doing between runs - but that is a big difference. I'd like to check again / find out.

It would be interesting to see DMD output in cumulative mode to see if the total number of allocations is significantly affected by doing two allocations instead of one.

Good idea.

Small notes re non-powers of two:

  • you can optimize modulo by doing some precomputation: https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h This replaces a mod instruction by a multiply, a multiply-high, two subtractions and a conditional move.
  • for hash tables specifically there's a cute trick you can use: assuming the hash is uniformly distributed in [0, 2^64) or [0, 2^32), you can do a multiply-high by X to turn that into a uniformly distributed number in [0, X).

I think the latter trick might give slightly better performance tha shift + subtract + conditional move, and also maybe win some by making the bucket distribution more even, but it may very well still be a dead end.

Attachment #9174621 - Attachment is obsolete: true

This was an interesting exercise, but:

  • As Simon says, there may be one more trick but it's a long-shot.
  • We no-longer need this solution because I modified jemalloc to handle more size classes.
Status: ASSIGNED → RESOLVED
Closed: 4 years ago
Resolution: --- → INVALID
Attachment #9174623 - Attachment is obsolete: true
Attachment #9174624 - Attachment is obsolete: true
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: