This CL contains two optimizations that were measured together.
1) InsertMiss (i. e. successful insert) optimization:
The idea that in case there is no kDeleted, we already know 99% of the information. So we are finding the position to insert with 2 asm instructions (or 3 in case of ARM or portable) and passing that as a hint into `prepare_insert`.
`prepare_insert` is out of the line in order to minimize effect on InsertHit (the most important case). `prepare_insert` may use the hint in case we still have growth and no kDeleted is guaranteed.
In case of kDeleted, we still call `find_first_non_full` in order to potentially find kDeleted slot earlier. We may consider different ways to do it faster for kDeleted later.
2) `find_first_non_full` optimization:
After optimization #1 `find_first_non_full` is used:
1. during resize and copy
2. right after resize
3. during DropDeletedWithoutResize
3. in InsertMiss for tables with kDeleted
In cases 1-3 the table is quite sparse.
1. After resize it is 7/16 sparse
2. During resize it is 7/16 maximum, but during first inserts it is much sparser.
3. During copy it may be up to 7/8, but at the beginning it is way sparser.
4. During DropDeletedWithoutResize it is 25/32 sparse, but at the beginning it is way sparser.
The only case, where the table is not known to be sparse, with `find_first_non_full` usage is a table with deleted elements. But according to hashz, we have <3% such tables. Adding an extra branch wouldn't hurt much there.
PiperOrigin-RevId: 619681885
Change-Id: Id3e2852cc6d85f6c8f90982d7aeb14799696bf39
