Clean up and slim down atoms

NEW
Assigned to

Status

()

3 years ago
5 months ago

People

(Reporter: njn, Assigned: njn)

Tracking

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox48 affected)

Details

(Assignee)

Description

3 years ago
Our atoms implementation is something of a mess. There are lots of complications w.r.t. static vs non-static atoms. There are also space inefficiencies -- on 64-bit platforms the space taken per static atom is 2N + ~120 bytes, where N is the number of chars (including the terminating null).

I have plans to improve the situation.
(Assignee)

Updated

3 years ago
Blocks: 1257128
(Assignee)

Updated

3 years ago
Blocks: 1257207
(Assignee)

Updated

3 years ago
Depends on: 529808
(Assignee)

Updated

3 years ago
Depends on: 1257402
(Assignee)

Updated

3 years ago
No longer blocks: 1257128, 1257207
Depends on: 1257128, 1257207
(Assignee)

Updated

3 years ago
Depends on: 1260871
(Assignee)

Comment 1

3 years ago
The following diagram shows all the data structures required for a single
static atom "foobar". All sizes are for 64-bit platforms.

> static nsFakeStringBuffer<N=7> foobar_buffer (.data, 8+2N bytes)
> /-----------------------------------------\ <------+
> | int32_t mRefCnt = 1 // never reaches 0  |        |
> | uint32_t mSize = 14 // 7 x 16-bit chars |        |
> | u"foobar"           // the actual chars | <----+ |
> \-----------------------------------------/      | |
>                                                  | |
> PermanentAtomImpl (heap, 32 bytes)               | |
> /----------------------------------------------\ | | <-+
> | void* vtablePtr    // implicit               | | |   |
> | uint32_t mLength = 6                         | | |   |
> | uint32_t mHash = ...                         | | |   |
> | char16_t* mString = @------------------------|-+ |   |
> | uintptr_t mRefCnt  // from NS_DECL_ISUPPORTS |   |   |
> \----------------------------------------------/   |   |
>                                                    |   |
> static nsIAtom* foobar (.bss, 8 bytes)             |   |
> /---\ <-----------------------------------+        |   |
> | @-|-------------------------------------|------------+
> \---/                                     |        |   |
>                                           |        |   |
> static nsStaticAtom (.d.r.ro.l, 16 bytes) |        |   |
> (this element is part of a larger array)  |        |   |
> /------------------------------------\    |        |   |
> | nsStringBuffer* mStringBuffer = O--|----|--------+   |
> | nsIAtom** mAtom = @----------------|----+            |
> \------------------------------------/                 |
>                                                        |
> AtomTableEntry (heap, ~2 x 16 bytes[*])                |
> (this entry is part of gAtomTable)                     |
> /-------------------------\                            |
> | uint32_t mKeyHash = ... |                            |
> | AtomImpl* mAtom = @-----|----------------------------+
> \-------------------------/                            |
>                                                        |
> StaticAtomEntry (heap, ~2 x 16 bytes[*])               |
> (this entry is part of gStaticAtomTable)               |
> /-------------------------\                            |
> | uint32_t mKeyHash = ... |                            |
> | nsIAtom* mAtom = @------|----------------------------+
> \-------------------------/
> 
> [*] Each hash table is half full on average, so each entry takes up
> approximately twice its actual size.

Yes, there is really all that: 2N + 64 + ~64 bytes per static atom. There are
about 2700 static atoms (once duplicates from separate lists are eliminated),
which gives a total of 5400N + 172,800 + ~172,800 bytes.

Here's what the pieces are for.

- foobar_buffer contains the actual chars.
  - mRefCnt isn't useful. We set it to 2 early on to ensure the buffer never
    gets released (because releasing a static buffer would be bad).
  - mSize is statically known, so also isn't useful.
  - The chars are 16-bit even though static atoms are always ASCII. 
  All this space is wasted so that static atoms look the same as dynamic atoms
  and can be treated the same.

- PermanentAtomImpl is the actual nsIAtom implementation.
  - mLength is redundant w.r.t. foobar_buffer:mSize. (For dynamic atoms that's
    not true, because the storage might have excess space, in which case mSize
    will be more than 2*(mLength+1)).
  - mRefCnt isn't used. PermanentAtomImpl::{AddRef,Release} always return 2 and
    1, and deletion of PermanentAtomImpls is done manually.

- foobar is a global handle to the atom so we can refer to it directly. (In
  reality this would be part of a class, e.g. nsGkAtoms::foobar.)

- The nsStaticAtom array is used at start-up, by RegisterStaticAtoms(). It just
  provides a way to associate foobar and foobar_buffer (which are both static)
  with the heap-allocated PermanentAtomImpl. It's not used after start-up.

- The entry in gAtomTable is so we can look it up by name. mKeyHash is based on
  the mHash in the PermanentAtomImpl.

- The entry in gStaticAtomTable is so the HTML5 parser can look it up by name.
  Again, mKeyHash is based on the mHash in the PermanentAtomImpl. The HTML5
  parser runs off the main thread, so it needs static atoms to be stored
  separately from gAtomTable in a read-only table. (gStaticAtomTable has a
  notion of "sealing" which ensures the read-only-ness.) Bug 529808 tried and
  failed to remove gStaticAtomTable.

I have some ideas to slim these structures down which I am currently exploring.
(Assignee)

Updated

3 years ago
Depends on: 1261735
(Assignee)

Updated

2 years ago
Depends on: 1407117
(Assignee)

Comment 2

a year ago
> > static nsFakeStringBuffer<N=7> foobar_buffer (.data, 8+2N bytes)
> > /-----------------------------------------\ <------+
> > | int32_t mRefCnt = 1 // never reaches 0  |        |
> > | uint32_t mSize = 14 // 7 x 16-bit chars |        |
> > | u"foobar"           // the actual chars | <----+ |
> > \-----------------------------------------/      | |
>
> - foobar_buffer contains the actual chars.
>   - mRefCnt isn't useful. We set it to 2 early on to ensure the buffer never
>     gets released (because releasing a static buffer would be bad).
>   - mSize is statically known, so also isn't useful.
>   - The chars are 16-bit even though static atoms are always ASCII. 
>   All this space is wasted so that static atoms look the same as dynamic
> atoms
>   and can be treated the same.

Bug 1407117 removed nsFakeStringBuffer, so the mRefCnt and mSize fields are gone now. The u"foobar" is still around.

> > PermanentAtomImpl (heap, 32 bytes)               | |
> > /----------------------------------------------\ | | <-+
> > | void* vtablePtr    // implicit               | | |   |
> > | uint32_t mLength = 6                         | | |   |
> > | uint32_t mHash = ...                         | | |   |
> > | char16_t* mString = @------------------------|-+ |   |
> > | uintptr_t mRefCnt  // from NS_DECL_ISUPPORTS |   |   |
> > \----------------------------------------------/   |   |

This is now called nsAtom. Bug 1400459 got rid of the vtablePtr. sizeof(nsAtom) is now 24 bytes on 64-bit, but that gets rounded up to 32 bytes by mozjemalloc.
Depends on: 1400459
(Assignee)

Updated

a year ago
Depends on: 1411469
(Assignee)

Updated

a year ago
Depends on: 1392185
(Assignee)

Updated

a year ago
Depends on: 1445113
(Assignee)

Updated

a year ago
Depends on: 1449395
(Assignee)

Updated

a year ago
Depends on: 1449787
(Assignee)

Updated

a year ago
Assignee: nobody → n.nethercote
(Assignee)

Updated

a year ago
Depends on: 1392883
(Assignee)

Comment 3

6 months ago
After all the clean-ups, we now have this:

> const char16_t[7] (.rodata, 2(N+1) bytes)
> (this is detail::gGkAtoms.foobar_string)
> /-----------------------------------------\ <--+
> | u"foobar"           // the actual chars |    |
> \-----------------------------------------/    |
>                                                |
> const nsStaticAtom (.rodata, 12 bytes)         |
> (this is within detail::gGkAtoms.mAtoms[])     |
> /-------------------------------------\ <---+  |
> | uint32_t mLength:30 = 6             |     |  |
> | uint32_t mKind:2 = AtomKind::Static |     |  |
> | uint32_t mHash = ...                |     |  |
> | uint32_t mStringOffset = @----------|-----|--+
> \-------------------------------------/     |
>                                             |
> constexpr nsStaticAtom* (0 bytes) @---------+
> (this is nsGkAtoms::foobar)                 |
>                                             |
> AtomTableEntry (heap, ~2 x 16 bytes[*])     |
> (this entry is part of gAtomTable)          |
> /-------------------------\                 |
> | uint32_t mKeyHash = ... |                 |
> | nsAtom* mAtom = @-------|-----------------+
> \-------------------------/
>
> [*] Each hash table is half full on average, so each entry takes up
> approximately twice its actual size.
>
> static shared bytes: 12 + 2(N+1)
> static unshared bytes: 0
> dynamic bytes: ~32
> total bytes: 12 + 2(N+1) + ~32 * num_processes

On the "slim down" front, the only way I can see to shrink this further would be to reduce sizeof(AtomTableEntry) from 16 bytes to 12 bytes by better packing hash table entries, but that's outside the scope of this bug.

On the "clean up" front, there is still bug 1392185, which would remove the need for html5 atoms.
(Assignee)

Updated

6 months ago
Depends on: 1497734
(Assignee)

Comment 4

5 months ago
Patches just landed for bug 1392185, which is the last blocker. Yay!
You need to log in before you can comment on or make changes to this bug.